Linear Algebra

Front 1

Interpretations of y=Ax

Back 1

y is measurement or observation; x is unknown to be determined

x is ‘input’ or ‘action’; y is ‘output’ or ‘result’

y = Ax defines a function or transformation that maps x ∈ R^n into
y ∈ R^m

Front 2

Interpretation of aij

Back 2

aij is gain factor from jth input (xj) to ith output (yi)

ith row of A concerns ith output

jth column of A concerns jth input

Front 3

A is lower triangular

Back 3

aij = 0 for i < j, means yi only depends on x1, . . . , xi

Front 4

A is diagonal

Back 4

aij = 0 for i != j, means ith output depends only on ith input

Front 5

sparsity pattern of A

Back 5

list of zero/nonzero entries of
A, shows which xj affect which yi

Front 6

Jacobian of A

Back 6

the derivative matrix of A

Front 7

Vector space

Back 7

a vector space or linear space (over the reals) consists of
• a set V
• a vector sum + : V × V → V
• a scalar multiplication : R × V → V
• a distinguished element 0 ∈ V

Front 8

Subspace

Back 8

• a subspace of a vector space is a subset of a vector space which is itself
a vector space
• roughly speaking, a subspace is closed under vector addition and scalar
multiplication
• examples V1, V2, V3 above are subspaces of Rn

Front 9

Independent set of vectors

Back 9

a set of vectors {v1, v2, . . . , vk} is independent if
a1v1 + a2v2 + · · · + akvk = 0 ⇒ a1 = a2 = · · · = 0
• coefficients of a1v1 + a2v2 + · · · + akvk are uniquely determined, i.e.,
a1v1 + a2v2 + · · · + akvk = b1v1 + b2v2 + · · · + bkvk
implies a1 = b1, a2 = b2, . . . , ak = bk
• no vector vi can be expressed as a linear combination of the other vectors v1, . . . , vi−1, vi+1, . . . , vk

Front 10

Basis

Back 10

set of vectors {v1, v2, . . . , vk} is a basis for a vector space V if

• v1, v2, . . . , vk span V, i.e., V = span(v1, v2, . . . , vk)

• {v1, v2, . . . , vk} is independent

• for a given vector space V, the number of vectors in any basis is the
same

Front 11

Dimension of V

Back 11

number of vectors in any basis

Front 12

Nullspace of a matrix

Back 12

the nullspace of A ∈ R^m×n is defined as
N(A) = { x ∈ R^n | Ax = 0 }

Front 13

Zero nullspace

Back 13

A is called one-to-one if 0 is the only element of its nullspace:
N(A) = {0}

Front 14

Onto matrices

Back 14

A is called onto if R(A) = Rm ⇐⇒
• Ax = y can be solved in x for any y
• columns of A span R^m
• A has a right inverse, i.e., there is a matrix B ∈ R^n×m s.t. AB = I
• rows of A are independent
• N(A^T ) = {0}
• det(AA^T ) != 0

Front 15

Inverse

Back 15

A ∈ R^n×n is invertible or nonsingular if detA != 0

• columns of A are a basis for R^n
• rows of A are a basis for R^n
• y = Ax has a unique solution x for every y ∈ R^n
• A has a (left and right) inverse denoted A−1 ∈ R^n×n, with
AA−1 = A−1A = I
• N(A) = {0}
• R(A) = R^n
• detA^TA = detAA^T != 0

Front 16

Rank

Back 16

rank(A) = dimR(A)
(nontrivial) facts:
• rank(A) = rank(A^T )
• rank(A) is maximum number of independent columns (or rows) of A
hence rank(A) ≤ min(m, n)
• rank(A) + dimN(A) = n

Front 17

Full rank

Back 17

for A ∈ R^m×n we always have rank(A) ≤ min(m, n)

we say A is full rank if rank(A) = min(m, n)

Front 18

norm

Back 18

for x ∈ R^n
||x|| = √(x^Tx)

Front 19

Inner product

Back 19

<x, y> := x1y1 + x2y2 + · · · + xnyn = x^T y

Front 20

Orthonormal set of vectors

Back 20

set of vectors u1, . . . , uk ∈ R^n is
• normalized if ||u|| = 1, i = 1, . . . , k
(ui are called unit vectors or direction vectors)
• orthogonal if ui ⊥ uj for i != j
• orthonormal if both

Front 21

Orthonormal basis for R^n

Back 21

• suppose u1, . . . , un is an orthonormal basis for R^n
• then U = [u1 · · · un] is called orthogonal: it is square and satisfies
U^TU = I

Front 22

Gram-Schmidt procedure

Back 22

given independent vectors a1, . . . , ak ∈ Rn, G-S procedure finds
orthonormal vectors q1, . . . , qk s.t.
span(a1, . . . , ar) = span(q1, . . . , qr) for r ≤ k

Front 23

QR decomposition

Back 23

also called QR factorization: A = QR
Q^TQ = Ik, and R is upper triangular & invertible

Front 24

Overdetermined linear equations

Back 24

y = Ax where A ∈ R^m×n is (strictly) skinny, i.e., m > n

Front 25

BLUE property

Back 25

linear measurement with noise:
y = Ax + v