Matrix Reference Manual
Matrix Decompositions

Go to: Introduction, Notation, Index

Cholesky Decomposition

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

• If A is real, then there is a unique U with positive diagonal entries.
• If A is 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 tocalculate U, then solve U^Hy=b and finally solve Ux = y.

Dual Conjunctive Diagonalization

[A,B:n#n, hermitian] If A is positive definite there exists X such that X^HAX=I and X^HBX=DIAG(k) where k contains the eigenvalues of A^-1B.

• If A and B are real then so are X and k.
• If S is the +ve definite square root of A then k contains the eigenvalues of SBS.

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.

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, …).
• The geometric multiplicity of any eigenvalue is equal to the number of corresponding blocks.
• The matrix B is diagonal iff A is non-defective, i.e. the geometric and algebraic multiplicities are equal for each eigenvalue.

Finding the Jordan form of a defective or nearly defective matrix is numerically illconditioned.

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.

LU Decomposition

Every square matrix A 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.

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 with m>=n, A=QR for Q:m*m unitary and R:m*n upper triangular.

Schur Decomposition

Every square matrix A is unitarily similar to an upper triangular matrix T: 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: 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

If A and B are square matrices, then there exist unitary U and V and upper triangular S and T such that A=U^HSV and A=U^HTV.

Schur Decomposition, Generalized Real

If A and B are real square matrices, then there exist orthogonal U and V and upper block triangular S and T such that A=U^TSV and A=U^TTV  where each block of S and T is either a 1#1 matrix or 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 Vn#n are unitary and D:m#n is diagonal with real positive diagonal elements arranged in non-increasing order (i.e. if j>i then d(j,j) >= d(i,i)). The diagonal elements of D are the singular values of A.

• 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.