Matrix Decompositions

Go to: Introduction, Notation, Index

Cholesky Decomposition

Iff A is hermitian positive definite there exists a non-singular upper triangular U with positive real diagonal entries such that U^HU=A . This is the Cholesky decomposition of A.

• If A is real, then U is unique and real.
• We can also decompose A as L^HL=A where L is lower triangular. If V^HV=B is the Cholesky decomposition of B=JAJ, then L^HL=A where L=JVJ. [Note: J is the exchange matrix.]
• A=S^HS iff S_[m#n]=Q[U; 0] for some unitary Q.
• For A_[n#n], the calculation of U requires n³/6 flops and is numerically well conditioned.
  • A numerically and computationally good way to solve Ax = b, is to calculate U, then solve U^Hy=b and finally solve Ux = y.

Dual Conjunctive Diagonalization

[A,B:n#n, hermitian] If B is positive definite there exists X such that X^HBX=I and X^HAX=D where X and D may be obtained from the eigendecomposition B^-1A=XDX^-1 with D=DIAG(d) a diagonal matrix of eigenvalues in non-increasing order. [4.10]

• If A and B are real then so are X and d. [4.10]
• If S is the +ve definite hermitian square root of B^-1 (i.e. S²B=I), then the eigendecomposition of the hermitian matrix SAS is SAS=WDW^H where W=S^-1X is unitary. [4.10]

Hermite Normal Form or Row-Echelon Form

Every matrix A_[m#n] can be expressed as A=BCP where B_[m#m] is non-singular, P_[n#n] is a permutation matrix and C_[m#n] is of the form [I D;0] for some D. The matrix C is the row-echelon or Hermite-normal form of A.

• The matrix C is uniquely determined by A.
• The number of non-zero rows of C equals the rank of A.

k^th Root of a Hermitian Matrix

If A is hermitian +ve semidefinite, then for any integer k>0, there exists a unique +ve semidefinite B such that A=B^k.

• AB = BA
• rank(B) = rank(A)
• B is +ve definite iff A is.
• B is real iff A is.
• B=p(A) for some polynomial p().

Jordan Normal Form

For any A_[n#n], there exists X such that A=X^-1BX where B is of the following form:

1. B is upper bidiagonal and its main diagonal consists of the eigenvalues of A repeated according to their algebraic multiplicities.
2. B = DIAG(X,Y,…) where each square block X, Y, … has one of A's eigenvalues repeated along its main diagonal, 1's along the diagonal above it and 0's elsewhere (these blocks are hypercompanion matrices).

• The matrix B is unique except for the ordering of the blocks in DIAG(X, Y, …).
• Two matrices are similar iff they have the same Jordan form for some ordering of the blocks in DIAG(X, Y, …).
• The matrix B may be complex even if A is real.
• Each distinct eigenvalue of A corresponds to one or more blocks in B that have that eigenvalue along their diagonal:
  • Its algebraic multiplicity equals the sum of the sizes of the blocks and equals its multiplicity in the characteristic polynomial of A.
  • Its geometric multiplicity equals the number of blocks; this equals the number of distinct eigenvectors corresponding to the eigenvalue.
  • Its multiplicity in the minimum polynomial equals the size of the largest block.
• The matrix B is diagonal iff A is non-defective, i.e. the geometric and algebraic multiplicities are equal for each eigenvalue, i.e. each block is of size 1.
• The minimum polynomial is equal to the characteristic polynomial iff all eigenvalues have a geometric multiplicity of 1, i.e. there is only one distinct eigenvector for each eigenvalue.
• Some authors call A irreducible iff B is a hypercompanion matrix (i.e. it consists of a single block) but a more common definition of reducible is here.

Finding the Jordan form of a defective or nearly defective matrix is numerically ill-conditioned.

LDU Decomposition

Every non-singular square matrix A can be expressed as A=PLDU where P is a permutation matrix, L is unit lower triangular, D is diagonal and U is unit upper triangular.

• If A is hermitian then U=L^H.
• You can also decompose as A=PUDL by expressing  JAJ=(JPJ)(JUJ)(JDJ)(JLJ).  [Note: J is the exchange matrix.]

LU Decomposition

Every A_[n#n] can be expressed as A=PLU where P is a permutation matrix, L is a unit lower triangular matrix and U is upper triangular.

• This decomposition is the standard way of solving the simultaneous equations Ax = b.
• You can also decompose as A=LUP where U is unit upper triangular by expressing A^T=P^TU^TL^T or alternatively A^H=P^HU^HL^H.
• You can also decompose as A=PUL where U is unit upper triangular by expressing JAJ=(JPJ)(JUJ)(JLJ).  [Note: J is the exchange matrix.]

Polar Factorisation

Every A_[n#n] can be expressed as A=UH=KV with U, V unitary and H, K positive semidefinite hermitian. H and K are unique; U and V are unique iff A is nonsingular. If A is real then H and K are real and U and V may be taken to be real.

• H²=A^HA and K² = AA^H
• A is normal iff UH = HU iff KV = VK. If A is normal and nonsingular then U=V and H=K.

QR Decomposition

For any A_[m#n], A=QR for Q_[m#m] unitary and R_[m#n] upper triangular. If A is real then Q and R may be taken to be real [1.9].

• For any A_[m#n] with m>=n, A=Q_[m#n]R_[n#n] with Q^HQ=I and R upper triangular. If A is real then Q and R may be taken to be real [1.9].
• You can also decompose as A=RQ  by decomposing JA^TJ=(JQ^TJ)(JR^TJ).  [Note: J is the exchange matrix.]
• You can also decompose as A=QL where L is lower triangular by decomposing JAJ=(JQJ)(JLJ).
• You can also decompose as A=LQ where L is lower triangular by decomposing A^T=Q^TL^T. 

Schur Decomposition

Every square matrix A is unitarily similar to an upper triangular matrix T with A=U^HTU.

• The main diagonal of T contains the eigenvalues of A repeated according to their algebraic multiplicities.
  • The eigenvalues may be chosen to occur in any order along the diagonal of T and for each possible order the matrix U is unique.
• T is diagonal iff A is normal. The sum of the squares of the absolute values of the off-diagonal elements of T is A's departure from normality.

Schur Decomposition, Real

Every square real matrix A is orthogonally similar to an upper block triangular matrix T with A=Q^TTQ where each block of T is either a 1#1 matrix or a 2#2 matrix having complex conjugate eigenvalues.

• T is diagonal iff A is symmetric.

Schur Decomposition, Generalized

For A_[n#n] and B_[n#n], there exist unitary U and V and upper triangular S and T such that A=U^HSV and B=U^HTV.

Schur Decomposition, Generalized Real

If A_[n#n] and B_[n#n] are real, then there exist orthogonal U and V and upper block triangular S and T such that A=U^TSV and B=U^TTV  where each block of S and T is either a 1#1 matrix or else a 2#2 matrix having complex conjugate eigenvalues.

Singular Value Decomposition (SVD)

Every matrix A_[m#n] can be expressed as A=UDV^H where U_[m#m] and V_[n#n] are unitary and D_[m#n] is real, non-negative and diagonal with its diagonal elements arranged in non-increasing order (i.e. d_i,i <= d_j,j for i < j). The singular values of A are the diagonal elements of D (or to some people, the non-zero diagonal elements of D).

• If A is real then U and V can be chosen to be real orthogonal matrices.
• The matrix D is unique but the matrices U and V are not.
• A=LDM^H is an alternative singular value decomposition of A iff U^HL = DIAG(Q₁, Q₂, ..., Q_k, R) and V^HM = DIAG(Q₁, Q₂, ..., Q_k, S) where Q₁, Q₂, ..., Q_k are unitary matrices whose sizes are given by the multiplicities of the corresponding distinct non-zero singular values and R and S are unitary matrices whose size equals the number of zero singular values [1.14]
  • If the singular values are all distinct and non-zero then L = U Q and M= V Q where Q is a diagonal matrix whose diagonal elements have unit magnitude. In the case of a real SVD of a real matrix A, the diagonal elements of Q equal +-1.
• The non-zero singular values of A are the square roots of the non-zero eigenvalues of A^HA.
• A is non-singular iff all its singular values are > 0.
• The rank of A is the number of non-zero singular values. If the rank of A is r, then the first r columns of U form a basis for the range of A and the last n-r columns of V form a basis for the null space of A.
• [Real, Symmetric, 2#2] A=[a b; b d]=RDR^T where R=[cos(t) -sin(t); sin(t) cos(t)] and t=½tan^-1(2b/(a-d)) and D is diagonal with D=DIAG([ 1 cos(2t) sin(2t); 1 -cos(2t) -sin(2t)] *[ (a+d)/2; (a-d)/2; b]).

See also: Singular Value

Takagi Decomposition (SVD)

Every symmetric (possibly complex) matrix A can be expressed as A=UDU^T where U is unitary and D is real, non-negative and diagonal with its diagonal elements arranged in non-increasing order (i.e. d_i,i <= d_j,j for i < j). This is a special case of the singular value decomposition.