Matrix Decompositions
Let be a matrix. A matrix decomposition or matrix factorisation of is an expression of as a product of matrices with special structure, such as triangular, diagonal or orthogonal matrices. The diagonalisation of a non-defective square matrix is a matrix decomposition.
Let be a real symmetric matrix. The spectral theorem states that has real eigenvalues repeated according to algebraic multiplicity, and an eigen-basis of that is an orthonormal set.
Let be a real symmetric matrix, be the orthogonal matrix whose columns are an orthonormal eigen-basis of and be the diagonal matrix of the corresponding eigenvalues. The spectral decomposition of is the diagonalisation of with respect to this eigen-basis.
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 has real eigenvalues and a spectral decomposition with unitary.
Let be a square matrix and The leading principal sub-matrix of order written is the matrix formed from the first rows and the first columns of The leading principal minor of order is the determinant
Let be a square matrix. An LU decomposition of is a factorisation of into a lower triangular matrix with diagonal elements equal to one and an upper triangular matrix
The LU decomposition has the following properties:
- if is invertible then an LU decomposition exists if and only if every leading principal minor is non-zero, and it is then unique;
- the factors are produced by Gaussian elimination, in which is the result of eliminating the elements below the diagonal column by column using row operations and records the multipliers used.
Let A permutation matrix is a matrix obtained by reordering the rows of the identity matrix The product reorders the rows of in the same way. A permutation matrix is orthogonal, so and
Let be a square matrix. A PLU decomposition of is a factorisation of a row-reordered copy of into a permutation matrix a lower triangular matrix with diagonal elements equal to one and an upper triangular matrix
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
- the system is solved by the two triangular systems and by forward and back substitution.
Let be a matrix with rank A rank factorisation of is a factorisation of into a matrix and a matrix that both have rank
The rank factorisation has the following properties:
- every matrix of rank has a rank factorisation, in which the columns of are any basis of the column space of and the columns of are the coordinates of the columns of in that basis;
- the factorisation is not unique, since for any invertible
- is the smallest inner dimension for which factorises as a product of two matrices.
Let be a real symmetric positive definite matrix. The Cholesky decomposition of is the factorisation of into a lower triangular matrix with positive diagonal elements and its transpose.
The Cholesky decomposition has the following properties:
- it exists and is unique if and only if is symmetric positive definite, so attempting to compute it is a test for positive definiteness;
- for a Hermitian positive definite matrix the decomposition is
- the elements of are computed column by column from
- the determinant is
- a symmetric positive semi-definite matrix also factorises as with non-negative diagonal elements, but not necessarily uniquely.
Let be a real matrix with A thin QR decomposition of is a factorisation of into a matrix with orthonormal columns and an upper triangular matrix
The matrix is orthogonal when and semi-orthogonal when A full QR decomposition of extends to an orthogonal matrix in by appending further orthonormal columns and extends to a matrix in by appending rows of zeros. The QR decomposition has the following properties:
- every real matrix has a QR decomposition;
- if has rank then the thin QR decomposition with positive diagonal elements of is unique, and it is given by Gram-Schmidt orthonormalisation of the columns of the columns of are the orthonormalised vectors and for so that
- the columns of are an orthonormal basis of the column space of
- the complex analogue has unitary and uses the conjugate transpose.
Let be a real matrix and The least squares problem is the problem of minimising over If has rank and thin QR decomposition then the least squares problem is solved by the triangular system
Let be a real matrix. The matrix is symmetric positive semi-definite, since so by the spectral theorem its eigenvalues are real and non-negative. The singular values of are the square roots of the eigenvalues of in decreasing order.
The matrices and share their non-zero eigenvalues, so has singular values. The number of non-zero singular values of is the rank of
Let be a real matrix. A singular value decomposition (SVD) of is a factorisation of into an orthogonal matrix a matrix with the singular values along its diagonal and zeros elsewhere, and an orthogonal matrix
The columns of are the left singular vectors of and the columns of are the right singular vectors of The singular value decomposition has the following properties:
- every real matrix has a singular value decomposition, and the singular values are unique although and are not;
- and so the right singular vectors are orthonormal eigenvectors of and the left singular vectors are orthonormal eigenvectors of
- and for all
- if is symmetric positive semi-definite then its singular value decomposition coincides with its spectral decomposition;
- the complex analogue has unitary and and uses the conjugate transpose.
Let be a real matrix with rank The thin singular value decomposition of is the factorisation that keeps only the non-zero singular values and the corresponding singular vectors, and
The thin singular value decomposition expresses as a sum of rank-one matrices. The left singular vectors are an orthonormal basis of the column space of and the right singular vectors are an orthonormal basis of the kernel of the set of with
Let be a real matrix. The Frobenius norm of is the square root of the sum of the squares of its elements.
Let be a real matrix with rank and The truncated singular value decomposition of of rank is the sum of the first terms of the thin singular value decomposition.
Let be a real matrix with rank and The Eckart–Young theorem states that the truncated singular value decomposition is the matrix of rank at most that is closest to in Frobenius norm.
A low-rank approximation of is a matrix of rank at most that approximates of which is the best in Frobenius norm.
Let be a real matrix with singular value decomposition and let be the matrix with in the diagonal positions where has non-zero and zeros elsewhere. The Moore–Penrose pseudo-inverse of is the matrix formed by inverting the non-zero singular values and transposing the singular vector matrices.
The pseudo-inverse has the following properties:
- it is the unique matrix satisfying and
- if is invertible then
- if has rank then
- if has rank then
- the vector is the solution of the least squares problem that has the smallest norm
- the matrix projects orthogonally onto the column space of