Linear Algebra, Computing · Siblings

A matrix decomposition writes a matrix in terms of simpler matrices. Most are products: LU, PLU, and Cholesky decompositions use triangular factors, QR and singular value decompositions use orthogonal factors, and eigendecompositions, Schur decompositions, and Jordan normal forms are similarities $A = P M P^{-1}$ to a simpler matrix $M$ (diagonal, triangular, or made of Jordan blocks). In contrast, the Jordan–Chevalley decomposition is a sum of commuting diagonalizable and nilpotent parts, and the Toeplitz decomposition is a sum $H + K$ of a symmetric matrix $H$ and a skew-symmetric matrix $K$.

Definitions

LU decomposition

Undergraduate

Consider a square matrix $A$. An LU decomposition of $A$ is a factorization $A = L U$, where $L$ is lower triangular (usually with ones on its diagonal) and $U$ is upper triangular.

Examples
Properties
  • Gaussian elimination without row exchanges computes an LU decomposition: $U$ is the resulting echelon form, and $L$ records the multiples of rows that were subtracted.
  • Not every invertible matrix has an LU decomposition. With a permutation matrix $P$ that reorders the rows, every square matrix has a PLU decomposition $A = P L U$.
  • Once $A = L U$ is known, $A x = b$ can be solved quickly by solving $L y = b$ and then $U x = y$, each by substitution.

PLU decomposition

Undergraduate

Consider a square matrix $A$. A PLU decomposition of $A$ is a factorization

\[A = P L U,\]

where

  1. $P$ is a permutation matrix (the identity matrix with its rows reordered),
  2. $L$ is lower triangular with ones on its diagonal, and
  3. $U$ is upper triangular.
Examples
Properties
  • Every square matrix has a PLU decomposition, unlike an LU decomposition, which need not exist.
  • Gaussian elimination with row exchanges computes a PLU decomposition: $P$ records the row exchanges, $U$ is the resulting echelon form, and $L$ records the multiples of rows that were subtracted.
  • The PLU decomposition of a matrix is not unique in general, because different row exchanges can be chosen. Partial pivoting, which brings the entry of largest absolute value in each column to the pivot position, makes the multipliers in $L$ at most $1$ in absolute value, which limits the growth of rounding errors.

Cholesky decomposition

Undergraduate

Consider a symmetric matrix $A$ whose eigenvalues are all positive (that is, $A$ is positive definite). The Cholesky decomposition of $A$ is the factorization

\[A = L L^{\top},\]

where $L$ is lower triangular with positive diagonal entries.

Examples
Properties
  • A real square matrix $A$ has a Cholesky decomposition exactly when $A$ is symmetric positive definite, and then the decomposition is unique.
  • Computing a Cholesky decomposition takes about half the work of an LU decomposition, and it needs no row exchanges.
  • If $z$ is a vector of independent standard normal random variables and $\Sigma = L L^{\top}$, then $\mu + L z$ is normally distributed with mean $\mu$ and covariance $\Sigma$.

QR decomposition

Undergraduate

Consider an $m \times n$ matrix $A$. A QR decomposition of $A$ is a factorization $A = Q R$, where the columns of $Q$ are orthonormal and $R$ is upper triangular.

Examples
Non-examples
Properties
  • Every matrix has a QR decomposition. Applying the Gram–Schmidt process to the columns of $A$ produces one.
  • QR decompositions are used to solve least-squares problems and to compute eigenvalues (the QR algorithm).

singular value decomposition

Undergraduate

Consider an $m \times n$ real matrix $A$. A singular value decomposition of $A$ is a factorization

\[A = U \Sigma V^{\top},\]

where $U$ and $V$ are orthogonal matrices and $\Sigma$ is an $m \times n$ diagonal matrix whose diagonal entries $\sigma_1 \geq \sigma_2 \geq \dots \geq 0$ are the singular values of $A$.

Examples
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : $\Sigma = \operatorname{diag}\bigl(\sqrt{15 + \sqrt{221}}, \sqrt{15 - \sqrt{221}}\bigr) \approx \operatorname{diag}(5.46, 0.37)$
    The singular values of \(A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) are the square roots of the eigenvalues $15 \pm \sqrt{221}$ of \(A^{\top} A = \begin{bmatrix} 20 & 14 \\ 14 & 10 \end{bmatrix}\). Their product is $\abs{\det A} = 2$.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : $\Sigma = \Lambda$, $U = V = Q$, as in the eigendecomposition
    The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric positive definite, so its eigendecomposition $A = Q \Lambda Q^{\top}$ is also a singular value decomposition.
  • The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) : $\Sigma = \operatorname{diag}(\varphi, 1 / \varphi)$
    Here $\varphi = \frac{1 + \sqrt{5}}{2}$ is the golden ratio. The singular values of \(A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) are the golden ratio $\varphi$ and $1 / \varphi$, the square roots of the eigenvalues $\frac{3 \pm \sqrt{5}}{2}$ of \(A^{\top} A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\). Both eigenvalues of $A$ are $1$, so the singular values differ from the eigenvalues. # TODO: Check the singular values.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : $U = A$, $\Sigma = I$, $V = I$
Non-examples
Properties
  • Every matrix has a singular value decomposition. The singular values are the square roots of the eigenvalues of $A^{\top} A$.
  • The rank of $A$ is the number of nonzero singular values.
  • Geometrically, every linear map is a rotation (or reflection), followed by stretching along perpendicular axes, followed by another rotation (or reflection).

eigendecomposition

Undergraduate

Consider a square matrix $A$. An eigendecomposition of $A$ is a factorization

\[A = P D P^{-1},\]

where $P$ is invertible and $D$ is diagonal. The diagonal entries of $D$ are eigenvalues of $A$, and the columns of $P$ are corresponding eigenvectors.

Examples
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : \(P = \begin{bmatrix} 1 & 1 \\ \frac{1 + \sqrt{17}}{2} & \frac{1 - \sqrt{17}}{2} \end{bmatrix}\), $D = \operatorname{diag}\bigl(\frac{5 + \sqrt{17}}{2}, \frac{5 - \sqrt{17}}{2}\bigr)$
    The matrix \(A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) has the distinct eigenvalues $\lambda = \frac{5 \pm \sqrt{17}}{2}$, with eigenvectors $(1, \lambda - 2)$, so it has an eigendecomposition. The eigenvectors are not perpendicular, because $A$ is not symmetric.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : $\Lambda = \operatorname{diag}\bigl(\frac{7 + \sqrt{17}}{2}, \frac{7 - \sqrt{17}}{2}\bigr)$, with $Q$ orthogonal
    The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric positive definite, so it has every decomposition in the table, including a Cholesky decomposition. Its eigendecomposition, Schur decomposition, Jordan normal form, and singular value decomposition all coincide, and its polar and Toeplitz decompositions are trivial.
  • The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) : None
    The matrix \(A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) has no eigendecomposition, because its only eigenvalue is $1$ and its eigenvectors are the multiples of $(1, 0)$, so it does not have two independent eigenvectors.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : \(Q = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\), $\Lambda = \operatorname{diag}(1, -1)$
    The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) is symmetric, so it has an eigendecomposition with an orthogonal $Q$: it fixes $(1, 1)$ and flips $(1, -1)$.
Properties
  • A square matrix $A$ has an eigendecomposition exactly when $A$ is diagonalizable, that is, when $A$ has $n$ linearly independent eigenvectors, where $A$ is $n \times n$. If the $n$ eigenvalues of $A$ are distinct, then $A$ is diagonalizable.
  • If $A$ is real and symmetric, then $A$ has an eigendecomposition $A = Q \Lambda Q^{\top}$ with $Q$ orthogonal and $\Lambda$ real (the spectral theorem).
  • An eigendecomposition turns powers and functions of $A$ into powers and functions of numbers: $A^k = P D^k P^{-1}$ and $e^{A t} = P e^{D t} P^{-1}$.

Schur decomposition

Undergraduate (real matrices with real eigenvalues)

Consider a square real matrix $A$ whose eigenvalues are all real. A Schur decomposition of $A$ is a factorization

\[A = Q T Q^{\top},\]

where $Q$ is orthogonal and $T$ is upper triangular.

Graduate (complex matrices)

Consider a square complex matrix $A$. A Schur decomposition of $A$ is a factorization $A = Q T Q^$, where $Q$ is unitary ($Q^ Q = I$) and $T$ is upper triangular.

Examples
Properties
  • Every square complex matrix has a Schur decomposition, but it is not unique. The diagonal entries of $T$ are the eigenvalues of $A$.
  • The upper triangular factor $T$ is diagonal exactly when $A$ is normal ($A A^* = A^* A$). For a real symmetric matrix, a Schur decomposition is an eigendecomposition $A = Q \Lambda Q^{\top}$.
  • Unlike an eigendecomposition, a Schur decomposition exists for every matrix and uses an orthogonal (or unitary) $Q$, so it can be computed stably. The QR algorithm for eigenvalues computes a Schur decomposition.

Jordan normal form

Undergraduate (complex matrices)

A Jordan block is a square matrix with a number $\lambda$ on its diagonal, $1$ on the diagonal just above it, and $0$ elsewhere, such as

\[\begin{bmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{bmatrix}.\]

Consider a square complex matrix $A$. A Jordan normal form of $A$ is a factorization

\[A = P J P^{-1},\]

where $P$ is invertible and $J$ is block diagonal with Jordan blocks on its diagonal.

Examples
Properties
  • Every square complex matrix $A$ has a Jordan normal form, and $J$ is unique up to the order of the blocks. The numbers $\lambda$ in the blocks are the eigenvalues of $A$.
  • The matrix $A$ is diagonalizable exactly when every Jordan block in $J$ is $1 \times 1$, and then the Jordan normal form is an eigendecomposition.
  • Splitting $J$ into its diagonal and the $1$s above the diagonal gives the Jordan–Chevalley decomposition of $A$.
  • The Jordan normal form is not continuous in $A$: an arbitrarily small change in $A$ can change the sizes of the blocks. For this reason, it is not computed numerically; the Schur decomposition is used instead.

Jordan–Chevalley decomposition

Undergraduate (complex matrices)

The Jordan–Chevalley decomposition of a square matrix $A$ writes it as a sum $A = D + N$, where $D$ is diagonalizable, $N$ is nilpotent ($N^k = 0$ for some $k$), and $D N = N D$.

Graduate (linear maps over a perfect field)

The Jordan–Chevalley decomposition of a linear map $T$ on a finite-dimensional vector space writes it as $T = S + N$, where $S$ is semisimple, $N$ is nilpotent, and $S$ and $N$ commute.

Examples
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : $D = A$, $N = 0$
    The matrix \(A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) has distinct eigenvalues, so it is diagonalizable. Thus its Jordan–Chevalley decomposition has $D = A$ and $N = 0$.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : $D = A$, $N = 0$
    The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric positive definite, so it has every decomposition in the table, including a Cholesky decomposition. Its eigendecomposition, Schur decomposition, Jordan normal form, and singular value decomposition all coincide, and its polar and Toeplitz decompositions are trivial.
  • The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) : \(D = I\), \(N = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}\)
    The matrix \(A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) is a Jordan block, which is not diagonalizable, so its Jordan–Chevalley decomposition has a nonzero nilpotent part $N = A - I$. $I$ commutes with every matrix, so $D = I$ and $N$ commute.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : $D = A$, $N = 0$
    $A$ is orthogonal, so its QR decomposition is $A \cdot I$, its singular value decomposition is $A \cdot I \cdot I$, and its Jordan–Chevalley decomposition has $N = 0$ because $A$ is diagonalizable.
Properties
  • The decomposition exists and is unique. Both $D$ and $N$ are polynomials in $A$.
  • In a Jordan normal form, $D$ is the diagonal part and $N$ is the part above the diagonal.

Toeplitz decomposition

Undergraduate (real matrices)

Consider a square real matrix $A$. The Toeplitz decomposition of $A$ is a sum

\[A = H + K\]

where $H$ is a symmetric matrix and a $K$ is skew-symmetric.

Examples
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : \(H = \begin{bmatrix} 2 & 5/2 \\ 5/2 & 3 \end{bmatrix}\), \(K = \begin{bmatrix} 0 & -3/2 \\ 3/2 & 0 \end{bmatrix}\)
    The Toeplitz decomposition of \(A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) splits $A$ into its symmetric part $H = \frac{1}{2}(A + A^{\top})$ and its skew-symmetric part $K = \frac{1}{2}(A - A^{\top})$, which average and split the off-diagonal entries $1$ and $4$.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : $H = A$, $K = 0$
    The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric positive definite, so it has every decomposition in the table, including a Cholesky decomposition. Its eigendecomposition, Schur decomposition, Jordan normal form, and singular value decomposition all coincide, and its polar and Toeplitz decompositions are trivial.
  • The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) : \(H = \begin{bmatrix} 1 & 1/2 \\ 1/2 & 1 \end{bmatrix}\), \(K = \begin{bmatrix} 0 & 1/2 \\ -1/2 & 0 \end{bmatrix}\)
    The Toeplitz decomposition of \(A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) has the symmetric part \(H = \begin{bmatrix} 1 & 1/2 \\ 1/2 & 1 \end{bmatrix}\) and the skew-symmetric part \(K = \begin{bmatrix} 0 & 1/2 \\ -1/2 & 0 \end{bmatrix}\). $H$ and $K$ do not commute, because $A$ is not normal.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : $H = A$, $K = 0$
    The Toeplitz decomposition of \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) has $H = A$ and $K = 0$, because $A$ is symmetric.
Properties
  • The Toeplitz decomposition exists and is unique.
  • The Toeplitz decomposition of a square matrix $A$ is \[A = \frac{1}{2}(A + A^{\top}) + \frac{1}{2}(A - A^{\top})\]
  • The matrix $A$ is normal ($A A^\top = A^\top A$) exactly when $H$ and $K$ commute.

Examples

Each cell is the ___ of the matrix $A$ in that row, when it is easy to write down.

The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\)

LU decomposition \(L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix}\)
PLU decomposition $P = I$, with $L$ and $U$ as in the LU decomposition
Cholesky decomposition None
singular value decomposition $\Sigma = \operatorname{diag}\bigl(\sqrt{15 + \sqrt{221}}, \sqrt{15 - \sqrt{221}}\bigr) \approx \operatorname{diag}(5.46, 0.37)$
eigendecomposition \(P = \begin{bmatrix} 1 & 1 \\ \frac{1 + \sqrt{17}}{2} & \frac{1 - \sqrt{17}}{2} \end{bmatrix}\), $D = \operatorname{diag}\bigl(\frac{5 + \sqrt{17}}{2}, \frac{5 - \sqrt{17}}{2}\bigr)$
Schur decomposition \[T = \begin{bmatrix} \frac{5 + \sqrt{17}}{2} & -3 \\ 0 & \frac{5 - \sqrt{17}}{2} \end{bmatrix}\]
Jordan normal form $J = D$, as in the eigendecomposition
Jordan–Chevalley decomposition $D = A$, $N = 0$
Toeplitz decomposition \(H = \begin{bmatrix} 2 & 5/2 \\ 5/2 & 3 \end{bmatrix}\), \(K = \begin{bmatrix} 0 & -3/2 \\ 3/2 & 0 \end{bmatrix}\)

The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\)

The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric positive definite, so it has every decomposition in the table, including a Cholesky decomposition. Its eigendecomposition, Schur decomposition, Jordan normal form, and singular value decomposition all coincide, and its polar and Toeplitz decompositions are trivial.

LU decomposition \(L = \begin{bmatrix} 1 & 0 \\ 1/2 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 4 & 2 \\ 0 & 2 \end{bmatrix}\)
PLU decomposition $P = I$, with $L$ and $U$ as in the LU decomposition
Cholesky decomposition \[L = \begin{bmatrix} 2 & 0 \\ 1 & \sqrt{2} \end{bmatrix}\]
singular value decomposition $\Sigma = \Lambda$, $U = V = Q$, as in the eigendecomposition
eigendecomposition $\Lambda = \operatorname{diag}\bigl(\frac{7 + \sqrt{17}}{2}, \frac{7 - \sqrt{17}}{2}\bigr)$, with $Q$ orthogonal
Schur decomposition $T = \Lambda$, as in the eigendecomposition
Jordan normal form $J = \Lambda$, as in the eigendecomposition
Jordan–Chevalley decomposition $D = A$, $N = 0$
Toeplitz decomposition $H = A$, $K = 0$

The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\)

LU decomposition None, without exchanging rows
PLU decomposition $P = A$, $L = I$, $U = I$
Cholesky decomposition None
QR decomposition $Q = A$, $R = I$
singular value decomposition $U = A$, $\Sigma = I$, $V = I$
eigendecomposition \(Q = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\), $\Lambda = \operatorname{diag}(1, -1)$
Schur decomposition $T = \Lambda$, as in the eigendecomposition
Jordan normal form $J = \Lambda$, as in the eigendecomposition
Jordan–Chevalley decomposition $D = A$, $N = 0$
Toeplitz decomposition $H = A$, $K = 0$

The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\)

LU decomposition $L = I$, $U = A$
PLU decomposition $P = I$, $L = I$, $U = A$
Cholesky decomposition None
QR decomposition $Q = I$, $R = A$
singular value decomposition $\Sigma = \operatorname{diag}(\varphi, 1 / \varphi)$
eigendecomposition None
Schur decomposition $Q = I$, $T = A$
Jordan normal form $P = I$, $J = A$
Jordan–Chevalley decomposition \(D = I\), \(N = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}\)
Toeplitz decomposition \(H = \begin{bmatrix} 1 & 1/2 \\ 1/2 & 1 \end{bmatrix}\), \(K = \begin{bmatrix} 0 & 1/2 \\ -1/2 & 0 \end{bmatrix}\)

Missing example: diagonal_split_not_jc

A polar decomposition $A = Q S$, with $Q$ orthogonal and $S$ symmetric positive semidefinite (definition)

QR decomposition ✗

An eigendecomposition $A = P D P^{-1}$, with $D$ diagonal (definition)

singular value decomposition ✗

What each decomposition is for

  • LU: solving $A x = b$ for many right-hand sides $b$. LU is Gaussian elimination, recorded.

  • PLU: the same as LU except it works for every square matrix due to permuting the rows of $A$. PLU is Gaussian elimination with row exchanges, recorded.

  • QR: least-squares problems and the QR algorithm for eigenvalues. QR is the Gram–Schmidt process, recorded.

  • SVD: rank, low-rank approximation, and the geometry of a linear map.

  • Cholesky: solving $A x = b$ when $A$ is symmetric positive definite, as in least squares and optimization, at half the cost of LU, and sampling from a multivariate normal distribution.

  • Eigendecomposition: computing powers and exponentials of a diagonalizable matrix, and decoupling linear systems into independent modes.

  • Schur: computing eigenvalues stably; it exists for every matrix, unlike an eigendecomposition.

  • Jordan normal form: classifying matrices up to similarity, and computing $e^{A t}$ for matrices that are not diagonalizable, by hand.

  • Jordan–Chevalley: separating the diagonalizable part of a matrix from its nilpotent part, as in computing $e^{A t} = e^{D t} e^{N t}$.

  • Toeplitz: separating the symmetric part $H$ of a matrix $A$, which alone determines the quadratic form $x^{\top} A x = x^{\top} H x$, as in energy and stability arguments.

See also

All distinctions · All definitions