AI summary by TwinMind
Five Factorizations of a Matrix
MIT OpenCourseWare
59m 51s
Introduction and Course Overview
- Lecture presents linear algebra as five key matrix factorizations
- Based on 6th edition (2023) of Strang's linear algebra textbook
- Factorizations: A=CR, A=LU, A=QR, A=XΛX⁻¹, A=UΣV^T
- Later factorizations involve eigenvalues and singular values
Key Concepts: Linear Independence and Matrix Multiplication
- Linear independence: vectors are dependent if some combination gives zero vector
- Matrix-vector multiplication A*X viewed as combination of matrix columns
- Matrix-matrix multiplication has multiple important interpretations
- Combinations form foundation of all linear algebra operations
Factorization 1: A = CR (Column-Row Factorization)
Example Matrix Analysis
- 3×3 matrix: columns [1,1,3], [2,3,7], [1,4,6]
- First two columns independent, third column = 2×first + 1×second
- Matrix C contains independent columns: [1,1,3], [2,3,7]
- Matrix R has form [I F] where I is identity, F captures dependencies
- R = [1,0,2; 0,1,1] showing third column as combination
Mathematical Framework
- Every matrix A factors as A = C*R
- C contains r independent columns (r = rank)
- R has r rows in reduced row echelon form
- R = [I F P] where P handles column permutations
- Independent columns go in C, dependent relationships captured in R
Fundamental Theorem
- Number of independent columns = number of independent rows
- This defines the rank of the matrix
- Column space and row space have same dimension
Vector Spaces and Four Fundamental Subspaces
Space Definitions
- Vector space: all combinations of given vectors
- Column space: all combinations of matrix columns
- Row space: all combinations of matrix rows
- Null space: solutions to Ax = 0
- Left null space: solutions to A^T x = 0
Dimensional Relationships
- Row space dimension = column space dimension = rank r
- Null space dimension = n - r (where n = number of columns)
- Left null space dimension = m - r (where m = number of rows)
- Spaces split the full dimensional space
Elimination Algorithm
Process Description
- Algorithm determines which columns are independent
- Progresses column by column across matrix
- Tests if column k+1 is combination of previous k columns
- Independent columns grow identity matrix in R
- Dependent columns contribute to F part of R
Example Calculation
- 3×4 matrix with equations: x₁+2x₂+x₃+x₄=17, etc.
- Elimination produces simplified form with zeros
- Results in R with independent rows [1,3,5] and [0,1,4,6]
- Null space vectors solve Rx = 0: [-3,-4,1,0] and [1,6,0,1]
Factorization 2: A = LU (Lower-Upper Decomposition)
- Most used factorization in numerical computing
- Billions of dollars annually spent on LU computations
- L = lower triangular matrix (zeros above diagonal)
- U = upper triangular matrix (zeros below diagonal)
- Sometimes requires permutation matrix P: PA = LU
- Solving Ax = b becomes two triangular systems: Lc = b, then Ux = c
Factorization 3: A = QR (Orthogonal-Triangular)
Orthogonal Vectors
- Orthogonal = perpendicular vectors
- Q contains orthonormal columns (length 1, perpendicular)
- Q^T Q = I (identity matrix)
- Orthogonal vectors are "super independent"
- Computing with orthogonal vectors is highly efficient
QR Properties
- Every matrix A can be factored as A = QR
- Q has orthonormal columns
- R is upper triangular
- Gram-Schmidt process converts independent columns to orthogonal
Factorizations 4 & 5: Eigenvalues and Singular Values
Eigenvalue Decomposition (Factorization 4)
- For symmetric matrices S: Sx = λx
- λ = eigenvalue, x = eigenvector
- Eigenvectors don't change direction under matrix multiplication
- S = XΛX⁻¹ where X contains eigenvectors, Λ contains eigenvalues
- Symmetric matrices have orthogonal eigenvectors
Singular Value Decomposition (Factorization 5)
- Most important factorization: A = UΣV^T
- Works for any matrix (rectangular, non-symmetric)
- U, V contain orthonormal vectors (singular vectors)
- Σ contains singular values (diagonal matrix)
- Geometric interpretation: rotation + scaling + rotation
- Finds orthogonal inputs that produce orthogonal outputs
2D Geometric Proof
- Standard basis vectors v=[1,0], w=[0,1] generally don't work
- Trying w, -v gives different angle after multiplication by A
- Continuous rotation argument: somewhere between exists perfect pair
- Mathematical proof that orthogonal inputs → orthogonal outputs exist
Deep Learning Connection
Problem Setup
- Training data: known input-output pairs (u₁,w₁), (u₂,w₂), etc.
- Goal: predict output for new input not in training set
- Need function that fits training data and generalizes well
Deep Learning Architecture
- Chain of simple functions: F₁ ∘ F₂ ∘ F₃ ∘ ... ∘ Fₖ
- Each function: Fᵢ(x) = ReLU(Aᵢx + bᵢ)
- ReLU function: max(0,x) - zero for negative, identity for positive
- Matrices Aᵢ and vectors bᵢ are learned parameters
- Combines linear algebra (matrices) with nonlinearity (ReLU)
ReLU Function Properties
- Piecewise linear: horizontal line below zero, 45° line above
- Example: ReLU(-7) = 0, ReLU(7) = 7
- Simple but effective nonlinear activation
- Enables complex function approximation through composition
