Linear Algebra

Eigenvalues, the SVD, norms and projections.

Linear Algebra

The core objects of linear algebra (matrices, eigenvalues, the SVD, norms and projections) and what they cost to compute.

Notation

Vector and matrix – A vector x∈Rnx \in \mathbb{R}^n is a column of nn real numbers. A matrix A∈Rm×nA \in \mathbb{R}^{m \times n} has mm rows and nn columns, and AijA_{ij} is the entry in row ii, column jj. The transpose A⊤A^\top swaps rows and columns, so (A⊤)ij=Aji(A^\top)_{ij} = A_{ji}.

Identity and inverse – The identity II has ones on the diagonal and zeros elsewhere, so AI=AAI = A. A square matrix AA is invertible if some A−1A^{-1} satisfies AA−1=A−1A=IAA^{-1} = A^{-1}A = I.

(AB)−1=B−1A−1,(abcd)−1=1ad−bc(d−b−ca)(AB)^{-1} = B^{-1}A^{-1}, \qquad \begin{pmatrix}a & b\\ c & d\end{pmatrix}^{-1} = \frac{1}{ad - bc}\begin{pmatrix}d & -b\\ -c & a\end{pmatrix}

Symmetric matrix – AA is symmetric when A=A⊤A = A^\top. Covariance matrices are symmetric.

Rank and subspaces

Linear independence – Vectors v1,…,vkv_1, \dots, v_k are linearly independent if no one of them is a weighted sum of the others.

Column space and null space – The column space of AA is the set of all vectors AxAx, meaning all weighted sums of its columns. The null space (or kernel) ker⁡A\ker A is the set of xx with Ax=0Ax = 0.

Rank – The rank of AA is the number of linearly independent columns, which always equals the number of independent rows. For A∈Rm×nA \in \mathbb{R}^{m \times n}, the rank–nullity theorem says

rank⁡A+dim⁡ker⁡A=n\operatorname{rank}A + \dim\ker A = n

rank⁡(AB)≤min⁡(rank⁡A,rank⁡B)\operatorname{rank}(AB) \le \min(\operatorname{rank}A, \operatorname{rank}B) and rank⁡(A⊤A)=rank⁡A\operatorname{rank}(A^\top A) = \operatorname{rank}A. A square matrix is invertible exactly when it has full rank.

Determinant and trace

Trace – The trace is the sum of the diagonal entries, tr⁡A=∑iAii\operatorname{tr}A = \sum_i A_{ii}. It is cyclic: tr⁡(ABC)=tr⁡(CAB)\operatorname{tr}(ABC) = \operatorname{tr}(CAB).

Determinant – The determinant det⁡A\det A is the factor by which AA scales volume. It is zero exactly when AA is not invertible, and det⁡(AB)=det⁡Adet⁡B\det(AB) = \det A \det B.

Eigenvalues and eigenvectors

Eigenvalue and eigenvector – A nonzero vector vv is an eigenvector of a square matrix AA, with eigenvalue λ\lambda, if AA only stretches it: Av=λvAv = \lambda v. The eigenvalues are the roots of the characteristic polynomial

det⁡(A−λI)=0\det(A - \lambda I) = 0

Example: for A=(2112)A = \begin{pmatrix}2 & 1\\ 1 & 2\end{pmatrix}, det⁡(A−λI)=(2−λ)2−1=0\det(A - \lambda I) = (2-\lambda)^2 - 1 = 0 gives λ=3\lambda = 3 with v=(1,1)v = (1, 1) and λ=1\lambda = 1 with v=(1,−1)v = (1, -1). Check: trace =4=3+1= 4 = 3 + 1 and determinant =3=3×1= 3 = 3 \times 1.

Link to trace and determinant – tr⁡A=∑iλi\operatorname{tr}A = \sum_i \lambda_i and det⁡A=∏iλi\det A = \prod_i \lambda_i.

Diagonalization – If AA has nn independent eigenvectors, stacking them into the columns of VV gives A=VΛV−1A = V\Lambda V^{-1}, where Λ\Lambda is the diagonal matrix of eigenvalues. Then Ak=VΛkV−1A^k = V\Lambda^kV^{-1}.

Orthogonal matrix – QQ is orthogonal if its columns are unit length and mutually perpendicular, so Q⊤Q=IQ^\top Q = I and Q−1=Q⊤Q^{-1} = Q^\top. Orthogonal matrices preserve lengths and have det⁡Q=±1\det Q = \pm 1. Rotations and reflections are examples.

Spectral theorem – Every real symmetric matrix has real eigenvalues and orthonormal eigenvectors, so

A=QΛQ⊤A = Q\Lambda Q^\top

Rayleigh quotient – For symmetric AA, the largest value of x⊤Axx^\top Ax over unit vectors xx is the largest eigenvalue λmax⁡\lambda_{\max}, attained at its eigenvector.

Power iteration – Repeatedly computing x←Ax/∥Ax∥x \leftarrow Ax/\lVert Ax\rVert converges to the top eigenvector, at a rate set by the ratio ∣λ2/λ1∣\lvert\lambda_2/\lambda_1\rvert of the two largest eigenvalues.

Positive semi-definite matrices

Definition – A symmetric matrix AA is positive semi-definite (PSD), written A⪰0A \succeq 0, if x⊤Ax≥0x^\top Ax \ge 0 for every xx. It is positive definite (A≻0A \succ 0) if the inequality is strict for every x≠0x \ne 0. Equivalent tests:

  • all eigenvalues are ≥0\ge 0 (or >0> 0 for positive definite),
  • A=B⊤BA = B^\top B for some matrix BB.

Covariance matrices and Gram matrices X⊤XX^\top X are always PSD.

Cholesky factorization – A positive definite AA factors as A=LL⊤A = LL^\top with LL lower triangular. It is the fastest way to solve Ax=bAx = b for such matrices.

Singular value decomposition

SVD – Every matrix A∈Rm×nA \in \mathbb{R}^{m \times n}, square or not, factors as

A=UΣV⊤A = U\Sigma V^\top

where UU and VV are orthogonal and Σ\Sigma is diagonal with non-negative singular values σ1≥σ2≥⋯≥0\sigma_1 \ge \sigma_2 \ge \dots \ge 0. The singular values are the square roots of the eigenvalues of A⊤AA^\top A, and the rank of AA is the number of nonzero ones.

Best low-rank approximation (Eckart–Young) – Keeping only the top kk singular values and their vectors gives the rank-kk matrix closest to AA.

Principal component analysis (PCA) – For a data matrix XX whose columns have been centred to mean zero, the principal directions are the columns of VV. The variance along direction ii is σi2/(n−1)\sigma_i^2/(n-1), for nn data points.

Pseudoinverse – A+=VΣ+U⊤A^+ = V\Sigma^+U^\top, where Σ+\Sigma^+ inverts the nonzero singular values. A+bA^+b is the smallest-norm xx minimizing ∥Ax−b∥\lVert Ax - b\rVert.

Condition number – κ(A)=σmax⁡/σmin⁡\kappa(A) = \sigma_{\max}/\sigma_{\min} measures how much AA amplifies relative errors. Solving Ax=bAx = b loses roughly log⁡10κ\log_{10}\kappa digits of precision.

Norms

Vector norm – The Euclidean norm is ∥x∥2=∑ixi2\lVert x\rVert_2 = \sqrt{\sum_i x_i^2}. Two vectors are orthogonal when x⊤y=0x^\top y = 0.

Matrix norms

NormDefinitionIn terms of singular values
Spectral ∥A∥2\lVert A\rVert_2largest stretch, max⁡∥x∥=1∥Ax∥\max_{\lVert x\rVert = 1}\lVert Ax\rVertσmax⁡\sigma_{\max}
Frobenius ∥A∥F\lVert A\rVert_F∑ijAij2=tr⁡A⊤A\sqrt{\sum_{ij}A_{ij}^2} = \sqrt{\operatorname{tr}A^\top A}∑iσi2\sqrt{\sum_i\sigma_i^2}
Nuclear ∥A∥∗\lVert A\rVert_*∑iσi\sum_i\sigma_i

The nuclear norm is the standard convex stand-in for rank when fitting low-rank models.

Projections

Projection – A matrix PP is a projection if P2=PP^2 = P, meaning applying it twice changes nothing. An orthogonal projection also has P=P⊤P = P^\top. The orthogonal projection onto the column space of AA is

P=A(A⊤A)−1A⊤P = A(A^\top A)^{-1}A^\top

which is P=QQ⊤P = QQ^\top when the columns of QQ are orthonormal. I−PI - P projects onto the perpendicular complement.

QR decomposition – A=QRA = QR with QQ having orthonormal columns and RR upper triangular. It is Gram–Schmidt orthogonalization written as matrices.

Woodbury identity – Updates a known inverse after a rank-kk change at O(k3)O(k^3) extra cost:

(A+UCV)−1=A−1−A−1U(C−1+VA−1U)−1VA−1(A + UCV)^{-1} = A^{-1} - A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1}

Computational cost

OperationCost
Matrix–vector product, n×nn \times nO(n2)O(n^2)
Matrix product (m×k)(k×n)(m \times k)(k \times n)2mnk2mnk floating-point operations
Inverse, solve, LU, Cholesky, QR, eigen, SVDO(n3)O(n^3)
Rank-rr factorization UV⊤UV^\top of an m×nm \times n matrixr(m+n)r(m+n) numbers instead of mnmn