• Linear Algebra

Linear Algebra

linear system: $\{\begin{array}{r}{a}_1{x}_1+\dots a_n{x}_n=b\\ \dots \end{array}$

equivalent ∼—same solution set

consistent—have solution; inconsistent—no solutions

coefficient matrix: $\left[\begin{array}{ccc}{a}_1& \dots & a_n\\ \dots & \dots & \dots \end{array}\right]$

augmented matrix: $\left[\begin{array}{cccc}{a}_1& \dots & a_n& b\\ \dots & \dots & \dots & \dots \end{array}\right]$

row operation

replacement

interchange

scaling

row equivalent—same after proper row operation

⇒ equivalent matrix

entry—a_i**j o**r a_i, j o**r A[i, j]o**r A_i, j—the (i, j) entry of A

leading entry—leftmost entry of a nonzero row

(row) echelon form—step-like, leading entry going in to the right

echelon matrix

reduced echelon form—all leading entries are 1, entries below them are 0

an echelon form (REF) of…

the reduced echelon form (RREF) of…

only 1 for each matrix

pivot position—position corresponding to the leading entry of its reduced echelon form

pivot column—the column containing a pivot position

pivot—nonzero number in a pivot position

row reduction

forward phase—make pivots the leading entries

backward phase—eliminate non-pivots in pivot column

partial pivoting—use greatest entry in a column as the pivot for programming

solve linear system

basic variable—corresponding to pivot column

free variable—not so
solution set

element(s): 0—inconsisten**t o**r 1—consisten**t o**r ∞

parametric description—$\{\begin{array}{r}basic\\ variable1=f(free\\ variable1,\dots )\\ \dots \end{array}$

back-substitution—solve for the basic variables one by one dealing with echelon form

existence and uniqueness theorem—consistent$\{\begin{array}{r}1\\ unique\\ solution,if\\ no\\ free\\ variable\\ \infty \\ solutions,if\\ at\\ least\\ one\\ free\\ variable\end{array}$ ⇔ no rightmost column as pivot column

vector equation— x₁a₁ + … + x_na_n = b

column vector

solution for vector equation x₁a₁ + … + x_na_n = b equivalent to solution of $\left[\begin{array}{cccc}{\mathbf{a}}_1& \dots & {\mathbf{a}}_n& \mathbf{b}\end{array}\right]$

Spa**n{v_1,⋯, v_p}—subset of ℝⁿ spanned (/generated) by v_1,⋯, v_p—the set of all linear combinations of v_1,⋯, v_p

b ∈ spa**n{a₁, ⋯, a_n} ⇔ A has a pivot in every row

matrix equation Ax = b: $A\mathbf{x}=\left[\begin{array}{ccc}{\mathbf{a}}_1& \dots & {\mathbf{a}}_n\end{array}\right]\left[\begin{array}{c}{x}_1\\ \cdots \\ x_n\end{array}\right]=x_1{\mathbf{a}}_1+\dots +x_n{\mathbf{a}}_n$

$=\left[\begin{array}{c}{\mathbf{a}}^1\\ ⋮\\ {\mathbf{a}}^m\end{array}\right]\mathbf{x}=\left[\begin{array}{c}{\mathbf{a}}^1\cdot \mathbf{x}\\ ⋮\\ {\mathbf{a}}^m\cdot \mathbf{x}\end{array}\right]$

$b_i={\sum }_{k=1}^n\left(a_{i,k}\cdot x_k\right)$

Ax = b solution equivalent to x₁a₁ + … + x_na_n = b

existence of solutions—has solution iff b ∈ Spa**n{a₁, ⋯, a_n}

{v₁, ⋯, v_p} spans (/ generates) ℝ^m if Spa**n{v₁, ⋯, v_p} = ℝ^m

identity matrix I_n, $\{\begin{array}{r}{I}_{j,j}=1,j=1,\cdots ,n\\ I_{j,k}=0,j\ne k\end{array}$

I_nx = x ∀ x ∈ ℝⁿ

homogeneous linear system—can be writen as Ax = 0

opposite: heterogeneous

at least 1 solution x = 0, a.k.a. trivial solution

nontrivial solution iff ∃free variable

parametric vector form— x**=su** + tv (s, t ∈ ℝ) parametric vector equation of the plane

solution representation

vector

parameter vector form— x = p + tv (t ∈ ℝ) the equation of the line through p parallele to v

span

solution set of Ax = b— {w|w = p**+v_h} i**f ∃solutio**n p ∀solutio**n o**f Ax** = 0 v_h

linear dependency of matrix columns

a₁⋯a_n of A are linearly independent  ⇐ Ax = 0 has only the trivial solution

dependent  ⇐ ∃ c₁⋯c_n, c₁a₁ + ⋯ + c_na_n = 0

more vectors than entries in each vector ⇒ linearly dependent

linearly dependent ⇔ at least one vector = linear combination of the others

 ⇒ ∃v_j (j > i), v_j is a linear combination of v₁…v_j − 1 if {v₁…v_p} is linearly dependent AND v₁ ≠ 0

contains 0 ⇒ linearly dependent

linear transformation

transformation (/ function / mapping) T : ℝⁿ → ℝ^m

domain ℝⁿ

codomain ℝ^m

image T(x)

range: set of all images

matrix transformation x ↦ Ax

 ⇔ ∀ u**,** v, c, d,  T(cu + dv) = c**T(u) + d**T(v)

kernal Nul A

range Col A

matrix operations

diagonal entry—a_i**i

main diagonal

diagonal matrix—square matrix with all non-diagonal entries 0

zero metrix 0

vector multiplication $AB=A\left[\begin{array}{ccc}{\mathbf{b}}_1& \cdots & {\mathbf{b}}_p\end{array}\right]=\left[\begin{array}{ccc}A{\mathbf{b}}_1& \cdots & A{\mathbf{b}}_p\end{array}\right]$

A(Bx)=(A**B)x

row-column rule—$(AB{)}_{ij}=a_{i1}{b}_{1j}+\cdots a_{in}{b}_{nj}={\sum }_{k=1}^n{a}_{ik}{b}_{kj}$

*$AB=\left[\begin{array}{c}{\overleftarrow{a}}_1\\ ⋮\\ {\overleftarrow{a}}_m\end{array}\right]\left[\begin{array}{ccc}{\overrightarrow{b}}_1& \cdots & {\overrightarrow{b}}_p\end{array}\right]=\left[\begin{array}{ccc}{\overleftarrow{a}}_1{\overrightarrow{b}}_1& \cdots & {\overleftarrow{a}}_1{\overrightarrow{b}}_p\\ ⋮& \ddots & ⋮\\ {\overleftarrow{a}}_m{\overrightarrow{b}}_1& \cdots & {\overleftarrow{a}}_m{\overrightarrow{b}}_p\end{array}\right]$

A is right-multiplied by B, B is left-multiplied by A

A, B commute—A**B = B**A

power of matrix $A^k={\prod }_{i=1}^{k}A$

A⁰ is the identity matrix

transpose matrix A^T

(A**B)^T = B^TA^T

matrix inversion

invertible—for n × n matrix A, ∃ n × n matrix C, C**A = I_n = A**C

C: an inverse of A

(non)singular matrix—(not) invertible

2 × 2 matrix $A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\Rightarrow A^{-1}=\frac{1}{\det A}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]$ iff det A = a**d − b**c ≠ 0

∀ invertible n × n matrix A, b ∈ ℝⁿ, Ax = b ⇒ x**=**A⁻¹b

(A**B)⁻¹ = B⁻¹A⁻¹

(A^T)⁻¹ = (A⁻¹)^T

only product of invertible matrices is invertible

for n × n matrix: A is invertible

⇔ row equivalent to I_n

⇔ linear transformation x**↦Ax** is one-to-one

⇔ ∀ b**∈ℝⁿ, Ax** = b has solution

⇔ linear transformation x**↦Ax** maps ℝⁿ ***o***nto ℝⁿ

⇔ ∃ n × n matrix C, C**A = I

⇔ ∃ n × n matri**x D, A**D = I

 ⇔ A^T is invertible  ⇔ det A ≠ 0

⇔ columns of A forms a basis of ℝⁿ

 ⇔ Col A = ℝⁿ

 ⇔ 0 is not an eigenvalue of A

 ⇔ det A ≠ 0

invertible linear transformation T : ℝⁿ**↦ℝⁿ—∃ S : ℝⁿ↦**ℝⁿ, ∀ x ∈ ℝⁿ, S(T(x)) = x, T(S(x)) = x

S—the inverse T⁻¹

elementary matrix—obtained by performing a single elementary row operation on identity matrix

roo**p A = E**A, where E = roo**p I_m, roo**p is the single elementary row operation

elementary matrix E is invertible, E⁻¹ is another elementary matrix obtained by reversed row operation

n × n matrix A is invertible iff row equivalent to I_n

A⁻¹ = roo**p I_n if I_n = roo**p A

find A⁻¹—row reduce $\left[\begin{array}{cc}A& I\end{array}\right]$ and get $\left[{\begin{array}{cc}I& A\end{array}}^{-1}\right]$

LU fractorization—A = L**U

A : m × n matrix

L : m × m unit lower triangular matrix

lower triangular matrix—entries above the main diagonal are 0s

U : m × n echelon matrix

implementation—$A\mathbf{x}=\mathbf{b}\iff \begin{array}{c}L\mathbf{y}=\mathbf{b}\\ U\mathbf{x}=\mathbf{y}\end{array}$

calculation: p. 145

determinant $\det A={\sum }_{j=1}^n(-1{)}^{i+j}{a}_{ij}\det A_{ij}$

A is quare matrix

usually use i = 1 the first row

origin—the last pivot in echelon form of the matrix obtained without division

A_i**j—obtained by deleting the ith row and jth column in A

(i, j)-cofactor C_i**j = (−1)^i + jdet A_i**j

cofactor expansion across the ith row of A—$\det A={\sum }_{j=1}^n{a}_{ij}{C}_{ij}$

triangular matrix A—$\det A={\prod }_{i=1}^n{a}_{ii}$ the entries on the main diagonal

row/ column operation

replacement—same

interchange—opposite

scaling—scales the same way

echelon form U by row replacements and r interchanges

$\det A=\{\begin{array}{rlr}& (-1{)}^r{\prod }_{}^{}{u}_{ii}& when\\ A& & \\ is& & \\ invertible& & \\ & 0& when\\ A& & \\ is& & \\ not& & \\ invertible& & \end{array}$

det A = det A^T

det A**B = (det A)(det B) proved using elementary matrices

$\det A^{-1}=\frac{1}{\det A}$ if A is invertible

det k**A = kⁿdet A if A has n rows

linearity property—linear transformation $T\left(\mathbf{x}\right)=\det \left[\begin{array}{ccccccc}{\mathbf{a}}_1& \cdots & {\mathbf{a}}_{j-1}& \mathbf{x}& {\mathbf{a}}_{j+1}& \cdots & {\mathbf{a}}_n\end{array}\right]$ where only x is a variable

Cramer’s rule—the unique solution of Ax = b has entries $x_i=\frac{\det A_i\left(\mathbf{b}\right)}{\det A}$

A is invertible n × n matrix, b ∈ ℝ

$A_i\left(\mathbf{b}\right)=\left[\begin{array}{ccccc}{\mathbf{a}}_1& \cdots & \mathbf{b}& \cdots & {\mathbf{a}}_n\end{array}\right]$

Laplace transfrom—converts system of linear differential equations to system of linear algebraic equations

a way to find A⁻¹—A(A⁻¹)_j = (I_n)_j

${\left(A^{-1}\right)}_{ij}=\frac{\det A_i{({\mathbf{I}}_n)}_j)}{\det A}=\frac{C_{ji}}{\det A}$

adjugate/ classical adjoint of A—$$\begin{gathered} adj \\ A=\left[\begin{array}{ccc}{C}_{11}& \cdots & C_{n1}\\ ⋮& \ddots & ⋮\\ C_{1n}& \cdots & C_{nn}\end{array}\right] \end{gathered}$$

determinant as area or volume

area of parallelogram of 2 × 2 matrix A is |det A|

volume of parallelepiped of 3 × 3 matrix A is |det A|

linear transformation T : ℝ² → ℝ² (ℝ³ → ℝ³) determined by 2 × 2 (3 × 3) matrix A ⇒ {are**a (volum**e) o**f T(S)} = |det A| ⋅ {are**a (volum**e) o**f S}

vector space—10 axioms

subspace—3 axioms needed

0 ∈ H

H is closed under vector addition—u + v ∈ H

H is closed under multiplication by scalars—cu ∈ H

Spa**n{v_i} is a subset of vector space V if v_i ∈ V

null space of A, Nul A—solution set of Ax = 0

—is a subspace of ℝⁿ

explicit discription—with the vectors that span Nul A

basis—solve and represent with free variables

dim Nul A= number of free variables

column space of A, Col A—Spa**n{a₁, ⋯, a_n}

—is a subspace of ℝ^m

Col A = {b : b**=Ax**, x ∈ ℝⁿ}

Col A = ℝ^m iff ∀b ∈ ℝ^m, ∃x, Ax = b

basis—pivot columns

dim Col A= number of pivot columns

row space of A, $$\begin{gathered} Row \\ A—span\left\{\begin{array}{ccc}{\mathbf{a}}^1& \cdots & {\mathbf{a}}^n\end{array}\right\} \end{gathered}$$

—is a subspace of ℝⁿ

 = Col A^T

basis—pivot rows

kernal/ null space of linear transformation T—T(u) = 0

basis Β of subset H—linearly independent, span H

standard basis for ℝⁿ {e₁, ⋯, e_n}

spanning set A small AP

linearly dependent set A big AP

coordinate system

the unique representation theorem

Β-coordinates of x—scalars that map them

Β-coordinate vector of x—${\left[\mathbf{x}\right]}_B=\left[\begin{array}{c}{c}_1\\ ⋮\\ c_n\end{array}\right]$

coordinate mapping x ↦ [x]_Β

it is a one-to-one linear transformation—isomorphism

x = P_Β[x]_Β, where change of coordinate matrix P_Β = [b₁, ⋯, b_n]

dimension

finite-dimensional vector space—spanned by finite set

0 dimension—{0}

infinite-dimensional

dim ℙⁿ = n + 1

rank—dim Col A

rank thm—ran**k A + dim Nul A = n

an eigenvector corresponding to λ—x ≠ 0, Ax = λx, A i**s n × n

an eigenvalue of A—λ

main diagonal entries on triangular matrix

0 is an eigenvalue of A iff A is not invertible

find eigenvector x given eigenvalue λ: Ax = λx ⇒ (A − λ**I)x = 0

（A − λ**I）^T = A^T − λ**I

eigenspace of A—Nul (A − λ**I)

characteristic equation of A—det (A − λ**I) = 0

 ⇔ λ is an eigenvalue of A

characteristic polynomial of A (with degree n)

multiplicity of eigenvalue λ—the multiplicity as root

similarity—∃P invertible, P⁻¹A**P = B

PBP⁻¹ = A

A, B are similar

similarity transformation—A → P⁻¹A**P

same characteristic polynomial and same eigenvalues

diagonalize—A = PDP⁻¹ where D is diagonal

diagonalizable—∃P, D

 ⇔ A has n linearly independent eigenvectors

 ⇔ ∑dimensions of eigenspaces  = n

⇔ characteristic polynomial factors completely into linear factors

⇔ dimension of eigenspace for each λ= multiplicity

⇔ basis of all eigenspaces form a basis of ℝⁿ

 ⇐ A has n distinct eigenvalues

diagonizing—find eigenvalues  ⇒ D; find eigenspace basis  ⇒ P; check A**P = P**D

vector operation

inner product (dot product)—u ⋅ v**=**u^Tv

length—$\Vert \mathbf{v}\Vert =\sqrt{\mathbf{v}\cdot \mathbf{v}}$

normalizing—get unit vector in the same direction as nonzero vector

distance dis**t(u**,** v) = ∥u − v∥

orthogonal relationship

orthogonal—u ⋅ v**=**0

 ⇔ ∥u + v∥ = ∥u∥ + ∥v∥

orthogonal complement W^⊥—the set of all vectors orthogonal to subspace W

is a subset of ℝⁿ

interactive—A^⊥ = B ⇔ B^⊥ = A

(Row A)^⊥ = Nul A

(Col A)^⊥ = Nul A^T

orthogonal set—u_i**⋅**u_j = 0 ∀ i ≠ j

⇒ linearly independent

is a basis for the subspace

orthogonal basis—basis that is orthogonal set

weight—$c_j=\frac{\mathbf{y}\cdot {\mathbf{u}}_j}{{\mathbf{u}}_j\cdot {\mathbf{u}}_j}$ for y ∈ Spa**n{u_j}

$\mathbf{y}={\sum }_{}^{}{c}_j{\mathbf{u}}_j$

orthogonal projection— ${proj}_L\mathbf{y}=\hat{\mathbf{y}}=\frac{\mathbf{y}\cdot \mathbf{u}}{\mathbf{u}\cdot \mathbf{u}}\mathbf{u}$

$\mathbf{y}=\hat{\mathbf{y}}+\mathbf{z}$ where z**⊥**u

subspace L spanned by u

orthonormal set—unit vector orthogonal set

orthonormal basis—basis that is orthonormal set

Gram-Schmidt process—calculate orthonormal basis by subtracting projection

QR factorization—orthonormal basis of linearly independent matrix Q, R = Q^TA

orthogonal matrix—square matrix with orthonormal columns

 ⇔ U⁻¹ = U^T

⇔ orthonormal rows

∥Ux∥ = ∥x∥

(Ux) ⋅ (Uy) = x ⋅ y

Ux⊥Uy ⇔ x**⊥**y

product of orthogonal matrix is orthogonal matrix

orthogonal projection—${proj}_W\mathbf{y}=\hat{\mathbf{y}}={\sum }_{}^{}\frac{\mathbf{y}\cdot {\mathbf{u}}_i}{{\mathbf{u}}_i\cdot {\mathbf{u}}_i}{\mathbf{u}}_i$

${proj}_W\mathbf{y}={\sum }_{}^{}\left(\mathbf{y}\cdot {\mathbf{u}}_i\right){\mathbf{u}}_i=U{U}^T\mathbf{y}$ for U of orthonormal basis u_i

best approximation theorem—$\hat{\mathbf{y}}$ is the closest point in W to y

general least-square problem—find x for smallest least-square error ∥b − Ax∥

$$\begin{gathered} A\hat{\mathbf{x}}=\hat{\mathbf{b}}=pro{j}_{Col \\ A}\mathbf{b} \end{gathered}$$

⇔ normal equation—A^TAx = A^Tb

ran**k A^TA = ran**k A

Ax = b has a unique least-square solution ∀ b ∈ ℝ^m

 ⇔ A is linearly independent

 ⇔ A^TA is invertible

$\iff \hat{\mathbf{x}}={\left(A^{T}A\right)}^{-1}{A}^T\mathbf{b}$

$\iff R\hat{\mathbf{x}}=Q^T\mathbf{b}\iff \hat{\mathbf{x}}=R^{-1}{Q}^T\mathbf{b}$

Χβ**=**y
design matrix—Χ

parameter vector—β

observation vector—y

least-square line (line of regression)—y = β₀ + β₁x

observed value—y_i

predicted value—β₀ + β₁x_i

residual—β₀ + β₁x_i − y_i

Χβ = y where $X=\left[\begin{array}{r}\begin{array}{cc}1& x_1\end{array}\\ \begin{array}{cc}⋮& ⋮\end{array}\\ \begin{array}{cc}1& x_n\end{array}\end{array}\right],\beta =\left[\begin{array}{r}{\beta }_0\\ {\beta }_1\end{array}\right],\mathbf{y}=\left[\begin{array}{r}{y}_1\\ ⋮\\ y_n\end{array}\right]$

residual vector ϵ

diagonalization of symmetric matrix

symmetric matrix—A^T = A

eigenvectors from different eigenspaces are orthogonal

orthogonally diagonalizable—could have orthogonal matrix P

A = PDP⁻¹ = PDP^T

 ⇔ A is symmetric

spectral decomposition—$A={\sum }_{}^{}{\lambda }_i{\mathbf{u}}_i{\mathbf{u}}_i^T$

where u_i are the columns of P

u_iu_i^T is a projection matrix—pro**j_{ui}x**=**(u_iu_i^T)x

single value decomposition SVD—A = UΣV^T

left singular vectors form U is m × m orthogonal

$\Sigma =\left[\begin{array}{cc}D& 0_{(n-r)}^T\\ 0_{(m-r)}& 0_{(m-r)\times (n-r)}\end{array}\right]$ is m × n

$D=\left[\begin{array}{ccc}{\sigma }_1& & 0\\ & \ddots & \\ 0& & {\sigma }_r\end{array}\right]$, σ₁ ≥ ⋯ ≥ σ_r > 0

right singular vectors form V is n × n orthogonal

∀ m × n matrix A, A^TA is symmetic

its eigenvalues λ₁ ≥ ⋯ ≥ λ_i ≥ ⋯ ≥ 0

single values—${\sigma }_1,\cdots ,{\sigma }_n=\sqrt{{\lambda }_1},\cdots ,\sqrt{{\lambda }_n}$

for {v₁, ⋯****,v_n} with eigenvectors of A^TA correponding to λ₁ ≥ ⋯ ≥ λ_i, and A has r nonzero singular values, {Av₁, ⋯****,Av_r} is an orthogonal basis for Col A, ran**k A = r

find single value decomposition

find orthogonal diagonalization of A^TA—P, D^′

V = P to orthonomal  = {v_i}

D and Σ

U—${\mathbf{u}}_i=\frac{A{\mathbf{v}}_i}{{\sigma }_i}$