Let A∈F n×pA\in\mathbb{F}^{\,n\times p} be a matrix. A matrix decomposition or matrix factorisation of AA is an expression of AA as a product of matrices with special structure, such as triangular, diagonal or orthogonal matrices. The diagonalisation A=PΛP−1A=P\Lambda P^{-1} of a non-defective square matrix is a matrix decomposition.

Let A∈R n×nA\in\mathbb{R}^{\,n\times n} be a real symmetric matrix. The spectral theorem states that AA has nn real eigenvalues λ1,…,λn,\lambda_1,\ldots,\lambda_n, repeated according to algebraic multiplicity, and an eigen-basis of Rn\mathbb{R}^n that is an orthonormal set.

Let A∈R n×nA\in\mathbb{R}^{\,n\times n} be a real symmetric matrix, Q∈R n×nQ\in\mathbb{R}^{\,n\times n} be the orthogonal matrix whose columns q‾1,…,q‾n\underline{q}_1,\ldots,\underline{q}_n are an orthonormal eigen-basis of AA and Λ\Lambda be the diagonal matrix of the corresponding eigenvalues. The spectral decomposition of AA is the diagonalisation of AA with respect to this eigen-basis.

A=QΛQ⊺=∑i=1nλi q‾iq‾i⊺A=Q\Lambda Q^\intercal=\sum_{i=1}^n\lambda_i\,\underline{q}_i\underline{q}_i^\intercal

The spectral decomposition has the following properties:

  • a real symmetric matrix is positive definite if and only if all of its eigenvalues are positive;
  • a real symmetric matrix is positive semi-definite if and only if all of its eigenvalues are non-negative;
  • a Hermitian matrix A∈C n×nA\in\mathbb{C}^{\,n\times n} has real eigenvalues and a spectral decomposition A=UΛU∗A=U\Lambda U^* with UU unitary.

Let A∈F n×nA\in\mathbb{F}^{\,n\times n} be a square matrix and k∈{1,…,n}.k\in\{1,\ldots,n\}. The leading principal sub-matrix of order k,k, written Ak∈F k×k,A_k\in\mathbb{F}^{\,k\times k}, is the matrix formed from the first kk rows and the first kk columns of A.A. The leading principal minor of order kk is the determinant ∣Ak∣.\lvert A_k\rvert.

Let A∈F n×nA\in\mathbb{F}^{\,n\times n} be a square matrix. An LU decomposition of AA is a factorisation of AA into a lower triangular matrix L∈F n×nL\in\mathbb{F}^{\,n\times n} with diagonal elements equal to one and an upper triangular matrix U∈F n×n.U\in\mathbb{F}^{\,n\times n}.

A=LUA=LU

The LU decomposition has the following properties:

  • if AA is invertible then an LU decomposition exists if and only if every leading principal minor ∣Ak∣,\lvert A_k\rvert, k=1,…,n−1,k=1,\ldots,n-1, is non-zero, and it is then unique;
  • the factors are produced by Gaussian elimination, in which UU is the result of eliminating the elements below the diagonal column by column using row operations and LL records the multipliers used.

Let n≥1.n\geq 1. A permutation matrix P∈F n×nP\in\mathbb{F}^{\,n\times n} is a matrix obtained by reordering the rows of the identity matrix In.I_n. The product PAPA reorders the rows of AA in the same way. A permutation matrix is orthogonal, so P−1=P⊺,P^{-1}=P^\intercal, and ∣P∣=±1.\lvert P\rvert=\pm 1.

Let A∈F n×nA\in\mathbb{F}^{\,n\times n} be a square matrix. A PLU decomposition of AA is a factorisation of a row-reordered copy of AA into a permutation matrix P,P, a lower triangular matrix LL with diagonal elements equal to one and an upper triangular matrix U.U.

PA=LUPA=LU

The PLU decomposition has the following properties:

  • every square matrix has a PLU decomposition, obtained by swapping rows during Gaussian elimination so that each diagonal element used for elimination is non-zero;
  • the determinant is ∣A∣=∣P∣∏i=1nuii;\lvert A\rvert=\lvert P\rvert\prod_{i=1}^n u_{ii};
  • the system Ax‾=b‾A\underline{x}=\underline{b} is solved by the two triangular systems Ly‾=Pb‾L\underline{y}=P\underline{b} and Ux‾=y‾U\underline{x}=\underline{y} by forward and back substitution.

Let A∈F n×pA\in\mathbb{F}^{\,n\times p} be a matrix with rank r≥1.r\geq 1. A rank factorisation of AA is a factorisation of AA into a matrix C∈F n×rC\in\mathbb{F}^{\,n\times r} and a matrix F∈F r×pF\in\mathbb{F}^{\,r\times p} that both have rank r.r.

A=CFA=CF

The rank factorisation has the following properties:

  • every matrix of rank r≥1r\geq 1 has a rank factorisation, in which the columns of CC are any basis of the column space of AA and the columns of FF are the coordinates of the columns of AA in that basis;
  • the factorisation is not unique, since A=(CM)(M−1F)A=\left(CM\right)\left(M^{-1}F\right) for any invertible M∈F r×r;M\in\mathbb{F}^{\,r\times r};
  • rr is the smallest inner dimension for which AA factorises as a product of two matrices.

Let A∈R n×nA\in\mathbb{R}^{\,n\times n} be a real symmetric positive definite matrix. The Cholesky decomposition of AA is the factorisation of AA into a lower triangular matrix L∈R n×nL\in\mathbb{R}^{\,n\times n} with positive diagonal elements and its transpose.

A=LL⊺A=LL^\intercal

The Cholesky decomposition has the following properties:

  • it exists and is unique if and only if AA is symmetric positive definite, so attempting to compute it is a test for positive definiteness;
  • for a Hermitian positive definite matrix the decomposition is A=LL∗;A=LL^*;
  • the elements of LL are computed column by column from
ljj=ajj−∑k=1j−1ljk2,lij=1ljj(aij−∑k=1j−1likljk)  ∀ i>j;l_{jj}=\sqrt{a_{jj}-\sum_{k=1}^{j-1}l_{jk}^2},\qquad l_{ij}=\frac{1}{l_{jj}}\left(a_{ij}-\sum_{k=1}^{j-1}l_{ik}l_{jk}\right)\,\,\forall\,i>j;
  • the determinant is ∣A∣=∏i=1nlii2;\lvert A\rvert=\prod_{i=1}^n l_{ii}^2;
  • a symmetric positive semi-definite matrix also factorises as LL⊺LL^\intercal with non-negative diagonal elements, but not necessarily uniquely.

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix with n≥p.n\geq p. A thin QR decomposition of AA is a factorisation of AA into a matrix Q∈R n×pQ\in\mathbb{R}^{\,n\times p} with orthonormal columns and an upper triangular matrix R∈R p×p.R\in\mathbb{R}^{\,p\times p}.

A=QRA=QR

The matrix QQ is orthogonal when n=pn=p and semi-orthogonal when n>p.n>p. A full QR decomposition of AA extends QQ to an orthogonal matrix in R n×n\mathbb{R}^{\,n\times n} by appending n−pn-p further orthonormal columns and extends RR to a matrix in R n×p\mathbb{R}^{\,n\times p} by appending n−pn-p rows of zeros. The QR decomposition has the following properties:

  • every real matrix has a QR decomposition;
  • if AA has rank pp then the thin QR decomposition with positive diagonal elements of RR is unique, and it is given by Gram-Schmidt orthonormalisation of the columns a‾1,…,a‾p\underline{a}_1,\ldots,\underline{a}_p of A:A: the columns q‾1,…,q‾p\underline{q}_1,\ldots,\underline{q}_p of QQ are the orthonormalised vectors and rij=⟨a‾j,q‾i⟩r_{ij}=\langle\underline{a}_j,\underline{q}_i\rangle for i≤j,i\leq j, so that a‾j=∑i=1jrijq‾i;\underline{a}_j=\sum_{i=1}^j r_{ij}\underline{q}_i;
  • the columns of QQ are an orthonormal basis of the column space of A;A;
  • the complex analogue has unitary QQ and uses the conjugate transpose.

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix and b‾∈Rn.\underline{b}\in\mathbb{R}^n. The least squares problem is the problem of minimising ∥Ax‾−b‾∥\lVert A\underline{x}-\underline{b}\rVert over x‾∈Rp.\underline{x}\in\mathbb{R}^p. If AA has rank pp and thin QR decomposition A=QRA=QR then the least squares problem is solved by the triangular system Rx‾=Q⊺b‾.R\underline{x}=Q^\intercal\underline{b}.

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix. The matrix A⊺A∈R p×pA^\intercal A\in\mathbb{R}^{\,p\times p} is symmetric positive semi-definite, since v‾⊺A⊺Av‾=∥Av‾∥2≥0,\underline{v}^\intercal A^\intercal A\underline{v}=\lVert A\underline{v}\rVert^2\geq 0, so by the spectral theorem its eigenvalues λ1≥…≥λp≥0\lambda_1\geq\ldots\geq\lambda_p\geq 0 are real and non-negative. The singular values of AA are the square roots of the eigenvalues of A⊺AA^\intercal A in decreasing order.

σi:=λi,σ1≥σ2≥…≥σmin⁡{n,p}≥0\sigma_i:=\sqrt{\lambda_i},\qquad\sigma_1\geq\sigma_2\geq\ldots\geq\sigma_{\min\{n,p\}}\geq 0

The matrices A⊺AA^\intercal A and AA⊺AA^\intercal share their non-zero eigenvalues, so AA has min⁡{n,p}\min\{n,p\} singular values. The number of non-zero singular values of AA is the rank of A.A.

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix. A singular value decomposition (SVD) of AA is a factorisation of AA into an orthogonal matrix U∈R n×n,U\in\mathbb{R}^{\,n\times n}, a matrix Σ∈R n×p\Sigma\in\mathbb{R}^{\,n\times p} with the singular values σ1,…,σmin⁡{n,p}\sigma_1,\ldots,\sigma_{\min\{n,p\}} along its diagonal and zeros elsewhere, and an orthogonal matrix V∈R p×p.V\in\mathbb{R}^{\,p\times p}.

A=UΣV⊺A=U\Sigma V^\intercal

The columns u‾1,…,u‾n\underline{u}_1,\ldots,\underline{u}_n of UU are the left singular vectors of AA and the columns v‾1,…,v‾p\underline{v}_1,\ldots,\underline{v}_p of VV are the right singular vectors of A.A. The singular value decomposition has the following properties:

  • every real matrix has a singular value decomposition, and the singular values are unique although UU and VV are not;
  • A⊺A=VΣ⊺ΣV⊺A^\intercal A=V\Sigma^\intercal\Sigma V^\intercal and AA⊺=UΣΣ⊺U⊺,AA^\intercal=U\Sigma\Sigma^\intercal U^\intercal, so the right singular vectors are orthonormal eigenvectors of A⊺AA^\intercal A and the left singular vectors are orthonormal eigenvectors of AA⊺;AA^\intercal;
  • Av‾i=σiu‾iA\underline{v}_i=\sigma_i\underline{u}_i and A⊺u‾i=σiv‾iA^\intercal\underline{u}_i=\sigma_i\underline{v}_i for all i≤min⁡{n,p};i\leq\min\{n,p\};
  • if AA is symmetric positive semi-definite then its singular value decomposition coincides with its spectral decomposition;
  • the complex analogue has unitary UU and VV and uses the conjugate transpose.

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix with rank r.r. The thin singular value decomposition of AA is the factorisation that keeps only the rr non-zero singular values and the corresponding singular vectors, Ur∈R n×r,U_r\in\mathbb{R}^{\,n\times r}, Σr∈R r×r\Sigma_r\in\mathbb{R}^{\,r\times r} and Vr∈R p×r.V_r\in\mathbb{R}^{\,p\times r}.

A=UrΣrVr⊺=∑i=1rσi u‾iv‾i⊺A=U_r\Sigma_rV_r^\intercal=\sum_{i=1}^r\sigma_i\,\underline{u}_i\underline{v}_i^\intercal

The thin singular value decomposition expresses AA as a sum of rr rank-one matrices. The left singular vectors u‾1,…,u‾r\underline{u}_1,\ldots,\underline{u}_r are an orthonormal basis of the column space of A,A, and the right singular vectors v‾r+1,…,v‾p\underline{v}_{r+1},\ldots,\underline{v}_p are an orthonormal basis of the kernel of A,A, the set of x‾\underline{x} with Ax‾=0‾.A\underline{x}=\underline{0}.

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix. The Frobenius norm of AA is the square root of the sum of the squares of its elements.

∥A∥F:=∑i=1n∑j=1paij2=tr(A⊺A)=∑i=1min⁡{n,p}σi2\lVert A\rVert_F:=\sqrt{\sum_{i=1}^n\sum_{j=1}^p a_{ij}^2}=\sqrt{\mathrm{tr}\left(A^\intercal A\right)}=\sqrt{\sum_{i=1}^{\min\{n,p\}}\sigma_i^2}

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix with rank rr and k<r.k<r. The truncated singular value decomposition of AA of rank kk is the sum of the first kk terms of the thin singular value decomposition.

Ak:=∑i=1kσi u‾iv‾i⊺A_k:=\sum_{i=1}^k\sigma_i\,\underline{u}_i\underline{v}_i^\intercal

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix with rank rr and k<r.k<r. The Eckart–Young theorem states that the truncated singular value decomposition AkA_k is the matrix of rank at most kk that is closest to AA in Frobenius norm.

∥A−Ak∥F=∑i=k+1rσi2=min⁡rank B≤k∥A−B∥F\lVert A-A_k\rVert_F=\sqrt{\sum_{i=k+1}^r\sigma_i^2}=\min_{\mathrm{rank}\,B\leq k}\lVert A-B\rVert_F

A low-rank approximation of AA is a matrix of rank at most kk that approximates A,A, of which AkA_k is the best in Frobenius norm.

Let A∈R n×pA\in\mathbb{R}^{\,n\times p} be a real matrix with singular value decomposition A=UΣV⊺,A=U\Sigma V^\intercal, and let Σ+∈R p×n\Sigma^+\in\mathbb{R}^{\,p\times n} be the matrix with 1σi\frac{1}{\sigma_i} in the diagonal positions where Σ\Sigma has non-zero σi\sigma_i and zeros elsewhere. The Moore–Penrose pseudo-inverse of AA is the matrix formed by inverting the non-zero singular values and transposing the singular vector matrices.

A+:=VΣ+U⊺∈R p×nA^+:=V\Sigma^+U^\intercal\in\mathbb{R}^{\,p\times n}

The pseudo-inverse has the following properties:

  • it is the unique matrix satisfying AA+A=A,AA^+A=A, A+AA+=A+,A^+AA^+=A^+, (AA+)⊺=AA+\left(AA^+\right)^\intercal=AA^+ and (A+A)⊺=A+A;\left(A^+A\right)^\intercal=A^+A;
  • if AA is invertible then A+=A−1;A^+=A^{-1};
  • if AA has rank pp then A+=(A⊺A)−1A⊺;A^+=\left(A^\intercal A\right)^{-1}A^\intercal;
  • if AA has rank nn then A+=A⊺(AA⊺)−1;A^+=A^\intercal\left(AA^\intercal\right)^{-1};
  • the vector x‾=A+b‾\underline{x}=A^+\underline{b} is the solution of the least squares problem that has the smallest norm ∥x‾∥;\lVert\underline{x}\rVert;
  • the matrix AA+AA^+ projects Rn\mathbb{R}^n orthogonally onto the column space of A.A.