Detailed slide-by-slide text content extracted from this presentation.
Slide 01
Linear Algebra
- The Mathematics of Spaces, Transformations, and Structure
- Linear algebra is the branch of mathematics concerned with vector spaces, linear transformations, and systems of linear equations. It is arguably the most useful mathematics ever developed--undergirding machine learning, quantum mechanics, computer graphics, signal processing, statistics, and virtually every branch of modern science and engineering.
Slide 02
Vectors: The Building Blocks
- A vector is an object that has both magnitude and direction. In linear algebra, vectors are generalized far beyond arrows in space to become elements of abstract vector spaces--but the geometric intuition remains valuable.
- Geometric View
- In 2D or 3D space, a vector is an arrow from the origin to a point. The vector (3, 2) points to the location 3 units right and 2 units up. Vectors encode both "where" and "how far" simultaneously.
- Algebraic View
- A vector is an ordered list of numbers (a tuple). In R^n, a vector has n components: v = (v1, v2, ..., vn). These components can represent anything: pixel colors, stock prices, audio frequencies, quantum states.
- Vector Operations
- Addition: (a1, a2) + (b1, b2) = (a1+b1, a2+b2). Scalar multiplication: c(a1, a2) = (ca1, ca2). These two operations--adding vectors and scaling them--are the foundation upon which all of linear algebra is built.
- Key Insight: Vectors are not just lists of numbers. They represent elements of a space that can be combined (added) and scaled (multiplied by constants) while staying within that space. This closure property under addition and scalar multiplication defines what it means to be a vector space.
Slide 03
Vector Spaces
- A vector space V over a field F (typically the real numbers R) is a set of objects called vectors, equipped with two operations (addition and scalar multiplication) satisfying eight axioms.
- The Eight Axioms
- Closure under addition
- Commutativity of addition
- Associativity of addition
- Existence of zero vector
- Existence of additive inverses
- Closure under scalar multiplication
- Distributivity over vector addition
- Distributivity over field addition
- Examples of Vector Spaces
- R^n -- n-tuples of real numbers
- Polynomials of degree at most n
- Continuous functions on [a,b]
- Solutions to a homogeneous differential equation
- m x n matrices over R
- Sequences of real numbers
- The trivial space {0}
- The power of the vector space abstraction is its generality. Polynomials, functions, matrices, and geometric vectors all obey the same rules, so theorems proved about abstract vector spaces apply to all of them simultaneously.
Slide 04
Subspaces, Span, and Linear Independence
- Three interconnected concepts form the structural backbone of linear algebra: subspaces, span, and linear independence. Together they answer: "What subset of a vector space is generated by a given collection of vectors?"
- Subspace
- A subset W of a vector space V is a subspace if it is itself a vector space under the same operations. Test: (1) contains the zero vector, (2) closed under addition, (3) closed under scalar multiplication. Lines and planes through the origin are subspaces of R^3.
- Span
- The span of vectors {v1, ..., vk} is the set of all linear combinations: c1v1 + c2v2 + ... + ckvk for all scalars ci. Span({v1,...,vk}) is always a subspace--the smallest subspace containing all the vectors.
- Linear Independence
- Vectors {v1, ..., vk} are linearly independent if the only solution to c1v1 + c2v2 + ... + ckvk = 0 is c1 = c2 = ... = ck = 0. No vector in the set can be written as a combination of the others. Independent vectors point in "genuinely different" directions.
- The Fundamental Question: Given a subspace, what is the minimum number of vectors needed to span it? That minimum number is the dimension, and a minimum spanning set of linearly independent vectors is a basis.
Slide 05
Bases and Dimension
- A basis for a vector space V is a set of vectors that is both linearly independent and spans V. Every vector in V can be uniquely expressed as a linear combination of basis vectors--this is the representation theorem.
- Standard Basis of R^n
- e1 = (1, 0, 0, ..., 0)
- e2 = (0, 1, 0, ..., 0)
- e3 = (0, 0, 1, ..., 0)
- ...
- en = (0, 0, 0, ..., 1)
- Any vector v = (a1, ..., an) = a1*e1 + ... + an*en. The components ARE the coordinates in this basis.
- Dimension
- The dimension of a vector space is the number of vectors in any basis. This is well-defined: all bases of a given space have the same number of vectors. R^n has dimension n. The space of polynomials of degree at most k has dimension k+1.
- Key theorem: In an n-dimensional space, any n+1 vectors must be linearly dependent, and any set of fewer than n vectors cannot span the space.
- Choosing different bases for the same space gives different coordinate representations of the same vector. Much of linear algebra concerns finding the "right" basis that reveals the structure of a problem.
Slide 06
Matrices
- A matrix is a rectangular array of numbers arranged in rows and columns. But matrices are far more than data tables--they represent linear transformations, encode systems of equations, and define geometric operations.
- Matrix as Transformation
- Every m x n matrix A defines a linear transformation T: R^n -> R^m by T(x) = Ax. The columns of A are the images of the standard basis vectors. A 2x2 matrix transforms the plane--rotating, reflecting, scaling, or shearing it.
- Matrix Multiplication
- AB represents composing transformation B first, then A. The (i,j) entry of AB is the dot product of row i of A with column j of B. Matrix multiplication is associative and distributive, but NOT commutative: AB does not equal BA in general.
- Special Matrices
- Identity matrix I (diagonal 1s, rest 0): leaves all vectors unchanged. Zero matrix: sends all vectors to zero. Diagonal matrices: scale each axis independently. Symmetric matrices (A = A^T): arise naturally in physics and optimization.
- Matrix multiplication example:
- [2 1] [1 3] [2*1+1*0 2*3+1*4] [2 10]
- [0 3] [0 4] = [0*1+3*0 0*3+3*4] = [0 12]
Slide 07
Systems of Linear Equations
- A system of m linear equations in n unknowns can be written as Ax = b, where A is the coefficient matrix, x is the unknown vector, and b is the right-hand side. Solving such systems is one of the oldest and most important problems in mathematics.
- Gaussian Elimination: The systematic algorithm for solving linear systems. Form the augmented matrix [A|b], then use row operations (swap rows, multiply a row by a nonzero scalar, add a multiple of one row to another) to reduce to row echelon form. Back-substitution gives the solution.
- Existence and Uniqueness
- A system Ax = b has: (1) a unique solution if rank(A) = rank([A|b]) = n (number of unknowns); (2) infinitely many solutions if rank(A) = rank([A|b])
- Geometric Interpretation
- In R^3, each equation defines a plane. Two equations define (typically) a line of intersection. Three equations define a point. If planes are parallel (inconsistent) or coincide (dependent), we get no solution or infinitely many.
- Modern applications solve millions of equations simultaneously. Google's PageRank solves a system with billions of unknowns. Climate models, structural engineering, and circuit analysis all reduce to linear systems.
Slide 08
Linear Transformations
- A function T: V -> W between vector spaces is a linear transformation if it preserves the vector space operations: T(u + v) = T(u) + T(v) and T(cv) = cT(v). Linearity means the transformation respects the structure of the space.
- Examples in R^2
- Rotation by theta: preserves lengths and angles
- Reflection across a line: flips the plane
- Scaling: stretches/compresses uniformly
- Shearing: tilts one axis relative to another
- Projection: collapses one dimension
- Key Properties
- Every linear transformation has a matrix representation (once bases are chosen)
- Composition of linear maps = matrix multiplication
- Kernel (null space): {v : T(v) = 0} -- what gets "destroyed"
- Image (range): {T(v) : v in V} -- what gets "hit"
- Rank-Nullity Theorem: dim(kernel) + dim(image) = dim(domain)
- The Rank-Nullity Theorem is one of the most important results in linear algebra. It says: what a linear transformation "kills" (null space) plus what it "produces" (image) always adds up to the dimension of the input space. Nothing is lost--it's either mapped somewhere or collapsed to zero.
Slide 09
Determinants
- The determinant is a scalar value associated with a square matrix that encodes geometric and algebraic information: whether the matrix is invertible, how it scales volumes, and the sign of orientation change.
- Geometric Meaning
- det(A) = the signed volume of the parallelepiped formed by the column vectors of A. If det(A) > 0, orientation is preserved. If det(A)
- Properties
- det(AB) = det(A) * det(B)
- det(A^T) = det(A)
- det(cA) = c^n * det(A) for n x n matrix
- A is invertible if and only if det(A) is not zero
- Swapping rows changes sign of determinant
- Row of zeros implies det = 0
- Computation
- For 2x2: det([a,b;c,d]) = ad - bc. For larger matrices: cofactor expansion along any row or column, or reduce to triangular form (product of diagonal entries). Computational cost: O(n^3) via elimination, O(n!) via cofactors.
- 2x2 determinant:
- det [a b] = ad - bc
- [c d]
- 3x3 determinant (Sarrus' rule or cofactor expansion):
- det [a b c]
- [d e f] = a(ei-fh) - b(di-fg) + c(dh-eg)
- [g h i]
Slide 10
Eigenvalues and Eigenvectors
- Eigenvalues and eigenvectors are perhaps the most important concept in applied linear algebra. An eigenvector of a matrix A is a nonzero vector v such that Av = lambda*v for some scalar lambda (the eigenvalue). The transformation merely scales v--it doesn't change its direction.
- Finding Eigenvalues: Solve the characteristic equation det(A - lambda*I) = 0. This is a polynomial of degree n (the characteristic polynomial), so an n x n matrix has at most n eigenvalues (counted with multiplicity, exactly n over the complex numbers).
- Geometric Interpretation
- Under a linear transformation, most vectors change both direction and magnitude. Eigenvectors are the special directions that are merely stretched (or flipped if lambda
- Diagonalization
- If A has n linearly independent eigenvectors, then A = PDP^(-1), where D is diagonal (eigenvalues on diagonal) and P's columns are the eigenvectors. Diagonalization makes computing A^k trivial: A^k = PD^kP^(-1), since D^k just raises each diagonal entry to the kth power.
- Applications
- Stability analysis of dynamical systems
- Principal Component Analysis (PCA) in data science
- Google's PageRank (dominant eigenvector)
- Quantum mechanics (observables as eigenvalues)
- Vibration analysis in engineering
- Markov chain steady states
Slide 11
Inner Product Spaces
- An inner product generalizes the dot product to abstract vector spaces, providing notions of length, angle, distance, and orthogonality. These geometric concepts become available in any inner product space--including function spaces.
- The Dot Product in R^n
- u . v = u1*v1 + u2*v2 + ... + un*vn. Properties: symmetric (u.v = v.u), linear in each argument, positive definite (v.v > 0 unless v = 0). Length: ||v|| = sqrt(v.v). Angle: cos(theta) = (u.v)/(||u||*||v||).
- Orthogonality
- Vectors u and v are orthogonal if u . v = 0. An orthogonal set of nonzero vectors is always linearly independent. An orthonormal basis (orthogonal and unit length) makes computation particularly clean: coordinates are just dot products with basis vectors.
- Function Spaces
- For continuous functions on [a,b]: the inner product <f,g> = integral of f(x)*g(x) dx. This makes sin(nx) and cos(mx) orthogonal on [0, 2*pi]--the foundation of Fourier analysis. Orthogonal polynomials (Legendre, Hermite) arise similarly.
- The Gram-Schmidt Process: Given any basis, produce an orthonormal basis. Start with v1, normalize it. Take v2, subtract its projection onto v1, normalize. Take v3, subtract projections onto v1 and v2, normalize. Continue until all vectors are mutually orthogonal and unit length.
Slide 12
Orthogonal Projections and Least Squares
- Projecting a vector onto a subspace finds the closest point in that subspace--the point minimizing the distance. This simple geometric idea underlies the entire theory of least-squares approximation.
- Projection onto a Line
- The projection of b onto the line spanned by a is: proj_a(b) = ((a.b)/(a.a)) * a. The residual b - proj_a(b) is orthogonal to a. This decomposes b into a component along a and a component perpendicular to a.
- Least Squares Solution
- When Ax = b has no solution (inconsistent system), the least squares solution x_hat minimizes ||Ax - b||^2. Solution: A^T*A*x_hat = A^T*b (the "normal equations"). Geometrically: project b onto the column space of A.
- Applications
- Linear regression fits a line to data points by least squares. Polynomial fitting, signal approximation, GPS positioning, and image reconstruction all use this framework. Any time you have more equations than unknowns, least squares finds the best approximate solution.
- "The method of least squares is the automobile of modern statistical analysis: despite its limitations, it transports everyone." -- Stephen Stigler
Slide 13
The Singular Value Decomposition (SVD)
- The SVD is arguably the most important matrix factorization in applied mathematics. Every matrix (not just square ones) can be decomposed as A = U*Sigma*V^T, revealing its fundamental geometric action.
- The SVD says: Every linear transformation can be decomposed into three steps: (1) rotate/reflect the input space (V^T), (2) scale along coordinate axes (Sigma), (3) rotate/reflect into the output space (U). The singular values on Sigma's diagonal measure how much each "direction" is stretched.
- Components
- U: m x m orthogonal matrix (left singular vectors)
- Sigma: m x n diagonal matrix (singular values sigma_1 >= sigma_2 >= ... >= 0)
- V^T: n x n orthogonal matrix (right singular vectors)
- Applications
- Image compression (keep only largest singular values)
- Noise reduction in signals
- Recommender systems (Netflix, Spotify)
- Latent semantic analysis in NLP
- Computing pseudoinverses
- Determining matrix rank numerically
- The SVD provides the best rank-k approximation to any matrix (Eckart-Young theorem): truncate to the k largest singular values and corresponding vectors. This powers dimensionality reduction across all of data science.
Slide 14
The Four Fundamental Subspaces
- Gilbert Strang emphasized that every m x n matrix A defines four fundamental subspaces that together reveal the complete geometric picture of the linear transformation.
- Column Space C(A)
- The set of all possible outputs Ax. A subspace of R^m with dimension r (the rank). The system Ax = b has a solution if and only if b is in the column space. It's "what A can produce."
- Null Space N(A)
- The set of all x where Ax = 0. A subspace of R^n with dimension n-r. It's "what A destroys"--the part of the input that maps to zero. Also called the kernel.
- Row Space C(A^T)
- The column space of A^T, equivalently the span of A's rows. A subspace of R^n with dimension r. Orthogonal complement of the null space: every input vector decomposes into a row-space component and a null-space component.
- Left Null Space N(A^T)
- The set of all y where A^T*y = 0. A subspace of R^m with dimension m-r. Orthogonal complement of the column space. These are the "impossible targets"--directions in the output that A can never reach.
- The Big Picture: R^n = Row Space + Null Space (orthogonal direct sum). R^m = Column Space + Left Null Space (orthogonal direct sum). A maps the row space isomorphically onto the column space and annihilates the null space. Dimensions: r + (n-r) = n and r + (m-r) = m.
Slide 15
Symmetric Matrices and Spectral Theorem
- Symmetric matrices (A = A^T) are the most important special class. They arise naturally throughout science--in physics (moment of inertia), optimization (Hessians), statistics (covariance matrices), and graph theory (adjacency matrices).
- The Spectral Theorem
- Every real symmetric matrix is orthogonally diagonalizable: A = Q*D*Q^T where Q is orthogonal and D is diagonal. This means: (1) all eigenvalues are real, (2) eigenvectors for distinct eigenvalues are orthogonal, (3) there exists an orthonormal basis of eigenvectors.
- Positive Definite Matrices
- A symmetric matrix is positive definite if x^T*A*x > 0 for all nonzero x. Equivalently: all eigenvalues are positive. These matrices define ellipsoids, arise as Hessians at minima, and guarantee convergence of optimization algorithms. They are the "good" matrices.
- Quadratic Forms
- The expression x^T*A*x (where A is symmetric) is a quadratic form. Its level sets are ellipses, hyperbolas, or paraboloids depending on the signs of eigenvalues. The eigenvectors give the principal axes; eigenvalues give the curvatures along each axis.
Slide 16
Applications in Machine Learning
- Modern machine learning is built on linear algebra. Neural networks, dimensionality reduction, and statistical learning all operate through matrix computations.
- Principal Component Analysis (PCA)
- Find the directions of maximum variance in high-dimensional data. Compute the covariance matrix, find its eigenvalues/eigenvectors. The top k eigenvectors define the best k-dimensional subspace for representing the data. Used in face recognition, gene expression analysis, and data visualization.
- Neural Networks
- Each layer of a neural network performs: output = activation(W*input + b), where W is a weight matrix. Training adjusts W via gradient descent. The entire forward pass is a sequence of matrix multiplications interleaved with nonlinearities. GPU acceleration of matrix operations enabled deep learning.
- Recommender Systems
- The Netflix Prize problem: approximate a sparse user-item rating matrix as a product of low-rank matrices (matrix factorization). Each user and item gets a vector; their dot product predicts the rating. SVD and its variants power most recommendation engines.
- Word Embeddings
- Word2Vec, GloVe, and similar models represent words as vectors in R^300 (approximately). Linear relationships encode meaning: king - man + woman ≈ queen. These vector operations on word embeddings revolutionized natural language processing.
Slide 17
Applications in Physics
- Linear algebra is the mathematical language of quantum mechanics, classical mechanics, electromagnetism, and general relativity. Physical theories are formulated in terms of vectors, operators, and eigenvalue problems.
- Quantum Mechanics
- Quantum states are vectors in a complex Hilbert space. Observables (position, momentum, energy) are represented by Hermitian operators. Measurement outcomes are eigenvalues; the state collapses to the corresponding eigenvector. The entire theory is linear algebra over complex numbers.
- Coupled Oscillators
- A system of springs and masses has equations of motion that reduce to an eigenvalue problem. Normal modes (eigenvectors) are the independent vibration patterns; natural frequencies are sqrt(eigenvalues). This applies to molecules, bridges, and buildings.
- Special Relativity
- Lorentz transformations are 4x4 matrices acting on spacetime vectors. The invariant interval ds^2 is preserved by these transformations. The group structure of these matrices (the Lorentz group) encodes the symmetries of spacetime.
- "God used beautiful mathematics in creating the world." -- Paul Dirac (whose bra-ket notation brought linear algebra to the heart of quantum physics)
Slide 18
Applications in Computer Graphics
- Every image you see on a computer screen is produced through linear algebra. Transformations, projections, and lighting calculations all reduce to matrix operations performed billions of times per second by GPUs.
- Transformation Matrices
- Rotation, scaling, translation, and perspective projection are all represented as 4x4 matrices (using homogeneous coordinates). Composing transformations = multiplying matrices. Every 3D object in a video game passes through a pipeline of matrix multiplications to reach your screen.
- The Graphics Pipeline
- Model space -> World space -> Camera space -> Clip space -> Screen space. Each transition is a matrix multiplication. The "Model-View-Projection" matrix (MVP) combines all transformations into a single matrix applied to each vertex.
- Image Processing
- Convolution kernels (3x3, 5x5 matrices) perform blur, sharpen, edge detection. SVD compresses images. Color transformations (brightness, contrast, color correction) are matrix operations in RGB or other color spaces.
Slide 19
Numerical Linear Algebra
- In practice, matrices are enormous and computations must be fast and stable. Numerical linear algebra develops algorithms that balance speed, memory, and accuracy in the face of floating-point arithmetic.
- LU Decomposition
- Factor A = LU (lower triangular times upper triangular). Solves Ax = b in O(n^2) after O(n^3) factorization. With pivoting (PA = LU), numerically stable. The workhorse for solving dense linear systems.
- QR Decomposition
- Factor A = QR (orthogonal Q times upper triangular R). More numerically stable than LU for least squares problems. Foundation of the QR algorithm for computing eigenvalues--the most important algorithm in numerical linear algebra.
- Iterative Methods
- For sparse systems (millions of unknowns, most entries zero): Conjugate Gradient, GMRES, and multigrid methods. They converge to the solution without ever forming the full matrix. Essential for PDEs, circuit simulation, and large-scale scientific computing.
- Condition Number
- The condition number kappa(A) = ||A|| * ||A^(-1)|| measures how sensitive the solution is to perturbations in the input. High condition number means small input errors cause large output errors. A matrix with kappa near 1 is "well-conditioned"; near infinity is "ill-conditioned."
Slide 20
Abstract Linear Algebra
- Beyond matrices and R^n, linear algebra extends to infinite-dimensional spaces, operators on function spaces, and algebraic structures that unify vast areas of mathematics.
- Hilbert Spaces
- Complete inner product spaces (possibly infinite-dimensional). The space L^2 of square-integrable functions is a Hilbert space. Fourier series express functions as infinite linear combinations of orthogonal basis functions (sines and cosines). Quantum mechanics lives in Hilbert space.
- Tensor Products
- Given vector spaces V and W, their tensor product V tensor W is a new space capturing "bilinear interactions." Tensors generalize vectors (rank 1) and matrices (rank 2) to higher dimensions. They're fundamental to general relativity, quantum entanglement, and deep learning architectures.
- Representation Theory
- Representing abstract group elements as matrices (linear transformations). This converts group theory problems into linear algebra problems. Applications: crystal symmetries in physics, coding theory, particle physics (the Standard Model's symmetry groups).
Slide 21
Historical Development
- Ancient China (2nd century BCE)
- The "Nine Chapters on the Mathematical Art" presents systematic methods for solving systems of linear equations, essentially performing Gaussian elimination 2,000 years before Gauss.
- Leibniz and the Determinant (1693)
- Leibniz introduced determinants as a tool for solving systems of equations. Cramer's rule (1750) formalized this approach, expressing solutions as ratios of determinants.
- Gauss and Elimination (1809)
- Carl Friedrich Gauss published the method of least squares and systematized the elimination process for solving systems, applied to astronomical calculations for determining orbits.
- Cayley and Matrices (1858)
- Arthur Cayley introduced the modern concept of a matrix as an algebraic object with its own arithmetic (addition, multiplication, inversion). He proved the Cayley-Hamilton theorem.
- Hilbert, Banach, von Neumann (1900-1940)
- The axiomatization of vector spaces, functional analysis, and operator algebras. Quantum mechanics demanded infinite-dimensional linear algebra. Von Neumann formalized quantum theory in the language of Hilbert spaces.
- The Computer Age (1950-present)
- LINPACK, LAPACK, BLAS libraries. The QR algorithm (1961). Sparse matrix methods. GPU computing. Today, linear algebra computations consume more computer cycles than any other mathematical operation.
Slide 22
Matrix Norms and Analysis
- Matrix norms measure the "size" of a matrix and are essential for understanding convergence, stability, and error in numerical computations.
- Operator Norms
- The operator norm ||A|| = max(||Ax||/||x||) measures the maximum stretching factor of A. It equals the largest singular value. Different vector norms (1-norm, 2-norm, infinity-norm) induce different matrix norms, each useful in different contexts.
- Frobenius Norm
- ||A||_F = sqrt(sum of all squared entries) = sqrt(trace(A^T*A)) = sqrt(sum of squared singular values). Easy to compute and useful for measuring "total energy" of a matrix. The matrix analog of the vector 2-norm.
- Spectral Radius
- rho(A) = max|lambda_i| (maximum absolute eigenvalue). Determines whether iterative methods converge: if rho(A) 0 as k -> infinity. Critical for analyzing dynamical systems: eigenvalues inside the unit circle mean stability.
Slide 23
Matrix Decompositions Beyond SVD
- Different matrix factorizations reveal different structures and serve different computational purposes. Choosing the right decomposition is an art in applied mathematics.
- Cholesky Decomposition
- For positive definite matrices: A = LL^T (lower triangular L). Twice as efficient as LU decomposition. Used in Monte Carlo simulation, optimization (solving normal equations), and Kalman filters. Failure of Cholesky proves a matrix is not positive definite.
- Schur Decomposition
- Every square matrix can be written A = QTQ* where Q is unitary and T is upper triangular. The diagonal of T contains the eigenvalues. More general than eigendecomposition (works even for defective matrices). Foundation of the QR algorithm for computing eigenvalues.
- Jordan Normal Form
- Every matrix is similar to a block-diagonal matrix of Jordan blocks. Each block has an eigenvalue on the diagonal and 1s on the superdiagonal. Reveals the algebraic structure of linear operators. Theoretically important but numerically unstable to compute.
- Polar Decomposition
- Every matrix A = UP where U is unitary and P is positive semidefinite. Generalizes polar form of complex numbers (z = re^(i*theta)): U gives the "rotation" part and P gives the "stretching" part. Used in continuum mechanics to separate rotation from deformation.
Slide 24
Linear Algebra in Statistics
- Modern statistics is built on linear algebra. From simple regression to multivariate analysis, the core operations involve projections, decompositions, and eigenstructures of data matrices.
- Covariance Matrices
- The covariance matrix Sigma captures all pairwise linear relationships among random variables. Its (i,j) entry is Cov(X_i, X_j). It is always symmetric and positive semidefinite. Its eigenstructure reveals the principal directions of variation in data.
- Multivariate Normal Distribution
- Defined entirely by mean vector mu and covariance matrix Sigma. The contours of constant probability density are ellipsoids whose axes align with Sigma's eigenvectors. Conditional distributions, marginalization, and sampling all reduce to linear algebra operations on these matrices.
- Linear Regression
- Fitting y = Xb + epsilon by least squares gives b_hat = (X^T*X)^(-1)*X^T*y. The hat matrix H = X(X^T*X)^(-1)*X^T projects observations onto the column space of X. Residuals lie in the orthogonal complement. All of ANOVA, hypothesis testing, and model comparison reduces to geometry in column space.
- Factor Analysis
- Modeling observed variables as linear combinations of a few latent factors: x = Lf + epsilon. The loading matrix L maps latent factors to observables. Estimating L from the covariance structure is an eigenvalue problem. Psychometrics, finance, and genomics all use this framework.
Slide 25
Linear Algebra in Signal Processing
- Digital signal processing--audio, images, communications--is fundamentally the manipulation of vectors and matrices. Every filter, transform, and encoding scheme has a linear algebraic interpretation.
- The Discrete Fourier Transform
- The DFT is a matrix multiplication: F*x, where F is the n x n Fourier matrix with entries F(j,k) = exp(-2*pi*i*jk/n). The FFT algorithm exploits F's structure to compute this in O(n*log(n)) instead of O(n^2). Perhaps the most important algorithm in engineering.
- Convolution and Filtering
- Convolution of two signals is matrix multiplication by a Toeplitz matrix. Circular convolution corresponds to multiplication by a circulant matrix--which is diagonalized by the DFT matrix. This is why filtering is done in the frequency domain: convolution becomes pointwise multiplication.
- Compressed Sensing
- If a signal is sparse (mostly zeros) in some basis, it can be reconstructed from far fewer measurements than traditional sampling theory requires. The mathematical conditions (RIP, coherence) are properties of the sensing matrix. This enables MRI acceleration and single-pixel cameras.
Slide 26
Linear Algebra in Optimization
- Optimization problems--finding minima of functions--invariably involve linear algebra at their core, whether through gradient computation, Hessian analysis, or constraint handling.
- Gradient Descent
- The update x_{k+1} = x_k - alpha * gradient(f(x_k)) is a linear algebra operation. The condition number of the Hessian determines convergence speed: well-conditioned = fast convergence; ill-conditioned = slow zigzag. Preconditioning (multiplying by approximate inverse) accelerates convergence.
- Newton's Method
- x_{k+1} = x_k - H^(-1)*g where H is the Hessian and g the gradient. Each step solves a linear system. Converges quadratically near a minimum but requires computing and inverting the Hessian. Quasi-Newton methods (BFGS, L-BFGS) approximate H using gradient information only.
- Linear Programming
- Minimize c^T*x subject to Ax = 0. The simplex method moves along edges of the feasible polytope; interior point methods traverse the interior. Both reduce to sequences of linear system solves. LP solves millions of real-world resource allocation problems daily.
- Semidefinite Programming
- Optimize over the cone of positive semidefinite matrices. Subsumes LP and many combinatorial optimization problems. Applications: control theory, combinatorial optimization relaxations, quantum information. The constraint "X is positive semidefinite" is a linear matrix inequality.
Slide 27
Linear Algebra in Cryptography
- Modern cryptographic systems rely heavily on linear algebra over finite fields and lattices. Both the security of encryption schemes and the methods to break them involve matrix operations.
- Error-Correcting Codes
- Reed-Solomon, LDPC, and turbo codes represent messages as vectors over finite fields. Encoding is matrix multiplication; decoding involves solving linear systems. Your phone, WiFi, and satellite TV all use linear algebra to correct transmission errors.
- Lattice-Based Cryptography
- Post-quantum cryptographic schemes (CRYSTALS-Kyber, adopted by NIST in 2024) are based on the hardness of lattice problems: finding the shortest vector in a high-dimensional lattice. A lattice is generated by integer linear combinations of basis vectors. These systems resist quantum computer attacks.
- Hill Cipher and Beyond
- The Hill cipher encrypts by multiplying plaintext vectors by a key matrix (mod 26). Modern block ciphers like AES use linear operations (matrix multiplication in GF(2^8)) combined with nonlinear substitution. The linear component provides diffusion; the nonlinear provides confusion.
Slide 28
Geometric Algebra and Extensions
- Several mathematical frameworks extend or reinterpret linear algebra, offering alternative perspectives that are sometimes more natural for specific applications.
- Geometric (Clifford) Algebra
- Extends vectors with a geometric product combining the dot product (inner) and wedge product (outer). Provides unified treatment of rotations, reflections, projections, and intersections in any dimension. Increasingly used in computer graphics, robotics, and physics as an alternative to matrices and quaternions.
- Quaternions
- 4D extension of complex numbers (1, i, j, k with i^2 = j^2 = k^2 = ijk = -1). Unit quaternions represent 3D rotations without gimbal lock. Used in aerospace navigation, game engines, and computer animation. Multiplication is a linear operation in the components.
- Multilinear Algebra
- Tensors, exterior algebras, and symmetric algebras generalize linear algebra to multilinear settings. A rank-3 tensor is a "3D matrix" with three indices. Tensor decomposition (CP, Tucker) extends SVD to higher dimensions. Critical in quantum chemistry, signal processing, and deep learning.
Slide 29
Key Theorems Summary
- Rank-Nullity Theorem
- For T: V -> W linear: dim(ker T) + dim(im T) = dim(V). The input dimension splits between "what's killed" and "what's produced."
- Spectral Theorem
- Every real symmetric matrix is orthogonally diagonalizable with real eigenvalues and orthogonal eigenvectors. Generalizes to: normal operators on Hilbert spaces have orthonormal eigenbases.
- Fundamental Theorem of Linear Algebra
- The four subspaces of A partition R^n and R^m into orthogonal pairs. Row space is perpendicular to null space; column space is perpendicular to left null space. The rank connects them all.
- Cayley-Hamilton Theorem
- Every square matrix satisfies its own characteristic polynomial: if p(lambda) = det(A - lambda*I), then p(A) = 0. A remarkable theorem: plug the matrix into its own characteristic equation and you always get the zero matrix.
Slide 30
The Essence of Linear Algebra
- Linear algebra succeeds because linearity is everywhere. Any smooth function is approximately linear near a point (the tangent approximation). Any periodic signal is a sum of sinusoids (Fourier analysis). Any complex system, when perturbed slightly from equilibrium, responds linearly.
- The deep insight of linear algebra is that by choosing the right basis--the right way to look at a problem--complex transformations become simple. Eigendecomposition finds axes along which a transformation merely scales. The SVD finds the directions of maximum action. Fourier analysis finds the frequencies hidden in a signal. In each case, the magic is the same: change basis to reveal structure.
- "Linear algebra is the most important subject in mathematics because it is the language of the applied sciences, the engine of computation, and the framework within which the abstract and the concrete meet." -- Gilbert Strang
- A presentation on Linear Algebra -- the mathematics of vector spaces, linear transformations, eigenvalues, and the hidden structure of data.
