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
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : \(L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix}\)
    Subtracting $2$ times row $1$ from row $2$ gives $U$, and $L$ records the multiplier $2$.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : \(L = \begin{bmatrix} 1 & 0 \\ 1/2 & 1 \end{bmatrix}\), \(U = \begin{bmatrix} 4 & 2 \\ 0 & 2 \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.
  • The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) : $L = I$, $U = A$
    $A$ is upper triangular, so its LU decomposition is $I \cdot A$, and its QR decomposition is $I \cdot A$. $A$ is not diagonalizable, so its Jordan–Chevalley decomposition has a nonzero nilpotent part $N$.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : None, without exchanging rows
    In any product $L U$, the top-left entry $0$ would force $L$ or $U$ to be singular, but $A$ is invertible. Exchanging the rows gives $P A = I = I \cdot I$.
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 $P$ is a permutation matrix (the identity matrix with its rows reordered), $L$ is lower triangular with ones on its diagonal, and $U$ is upper triangular.

Examples
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : $P = I$, with $L$ and $U$ as in the LU decomposition
    The matrix \(A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) has an LU decomposition, so $P = I$ works. With partial pivoting, the rows are exchanged first instead, because $4$ is larger than $2$.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : $P = I$, with $L$ and $U$ as in the LU decomposition
    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}\) : $P = I$, $L = I$, $U = A$
    $A$ is upper triangular, so its LU decomposition is $I \cdot A$, and its QR decomposition is $I \cdot A$. $A$ is not diagonalizable, so its Jordan–Chevalley decomposition has a nonzero nilpotent part $N$.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : $P = A$, $L = I$, $U = I$
    The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) has no LU decomposition, but it has the PLU decomposition $A = A \cdot I \cdot I$, because $A$ is itself the permutation matrix that exchanges the two rows.
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
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : None, since $A$ is not symmetric
    $A$ has an LU decomposition, because subtracting $2$ times row $1$ from row $2$ makes it upper triangular, and $L$ records the $2$. $A$ has the distinct eigenvalues $\frac{5 \pm \sqrt{17}}{2}$, so it is diagonalizable, and its Jordan–Chevalley decomposition has $D = A$ and $N = 0$.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : \[L = \begin{bmatrix} 2 & 0 \\ 1 & \sqrt{2} \end{bmatrix}\]
    The matrix \(A = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) is symmetric with positive eigenvalues $\frac{7 \pm \sqrt{17}}{2}$, so it has a Cholesky decomposition. Its factor $L$ is the LU factor $U$ with each row divided by the square root of its diagonal entry, transposed.
  • The matrix \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) : None, since $A$ is not symmetric
    $A$ is upper triangular, so its LU decomposition is $I \cdot A$, and its QR decomposition is $I \cdot A$. $A$ is not diagonalizable, so its Jordan–Chevalley decomposition has a nonzero nilpotent part $N$.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : None, since $A$ has the negative eigenvalue $-1$
    The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) is symmetric but has no Cholesky decomposition, because its eigenvalue $-1$ is negative, so it is not positive definite.
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
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).

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, since $A$ is not diagonalizable
    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
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : \[T = \begin{bmatrix} \frac{5 + \sqrt{17}}{2} & -3 \\ 0 & \frac{5 - \sqrt{17}}{2} \end{bmatrix}\]
    In the Schur decomposition of \(A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\), the first column of $Q$ is a unit eigenvector for $\frac{5 + \sqrt{17}}{2}$, and the second column is perpendicular to it. The entry $-3$ above the diagonal is nonzero because $A$ is not normal.
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : $T = \Lambda$, as in the eigendecomposition
    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}\) : $Q = I$, $T = A$
    $A$ is upper triangular, so its LU decomposition is $I \cdot A$, and its QR decomposition is $I \cdot A$. $A$ is not diagonalizable, so its Jordan–Chevalley decomposition has a nonzero nilpotent part $N$.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : $T = \Lambda$, as in the eigendecomposition
    $A$ has no LU decomposition without exchanging rows, because its top-left entry is $0$, even though $A$ is invertible, but it has the PLU decomposition $A = A \cdot I \cdot I$. $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
  • 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
  • The matrix \(\begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}\) : $J = D$, as in the eigendecomposition
    $A$ has an LU decomposition, because subtracting $2$ times row $1$ from row $2$ makes it upper triangular, and $L$ records the $2$. $A$ has the distinct eigenvalues $\frac{5 \pm \sqrt{17}}{2}$, so it is diagonalizable, and its Jordan–Chevalley decomposition has $D = A$ and $N = 0$.
  • The matrix \(\begin{bmatrix} 3 & 1 \\ -1 & 1 \end{bmatrix}\) : \(P = \begin{bmatrix} 1 & 1 \\ -1 & 0 \end{bmatrix}\), \(J = \begin{bmatrix} 2 & 1 \\ 0 & 2 \end{bmatrix}\)
    The matrix \(A = \begin{bmatrix} 3 & 1 \\ -1 & 1 \end{bmatrix}\) has the eigenvalue $2$ twice, but its eigenvectors are only the multiples of $(1, -1)$, so it is not diagonalizable, and $J$ is a single $2 \times 2$ Jordan block. The columns of $P$ are the eigenvector $v_1 = (1, -1)$ and a vector $v_2 = (1, 0)$ with $(A - 2I) v_2 = v_1$. To check, \(A P = P J = \begin{bmatrix} 2 & 3 \\ -2 & -1 \end{bmatrix}\).
  • The matrix \(\begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix}\) : $J = \Lambda$, as in the eigendecomposition
    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}\) : $P = I$, $J = A$
    The matrix \(A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) is already a Jordan block, so it is its own Jordan normal form.
  • The matrix \(A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) : $J = \Lambda$, as in the eigendecomposition
    $A$ has no LU decomposition without exchanging rows, because its top-left entry is $0$, even though $A$ is invertible, but it has the PLU decomposition $A = A \cdot I \cdot I$. $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
  • 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.

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 $\lvert \det A \rvert = 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)$, where $\varphi = \frac{1 + \sqrt{5}}{2}$
    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$
    $A$ has no LU decomposition without exchanging rows, because its top-left entry is $0$, even though $A$ is invertible, but it has the PLU decomposition $A = A \cdot I \cdot I$. $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.
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).

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$ has no LU decomposition without exchanging rows, because its top-left entry is $0$, even though $A$ is invertible, but it has the PLU decomposition $A = A \cdot I \cdot I$. $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}\)

$A$ has an LU decomposition, because subtracting $2$ times row $1$ from row $2$ makes it upper triangular, and $L$ records the $2$. $A$ has the distinct eigenvalues $\frac{5 \pm \sqrt{17}}{2}$, so it is diagonalizable, and its Jordan–Chevalley decomposition has $D = A$ and $N = 0$.

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, since $A$ is not symmetric
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
singular value decomposition $\Sigma = \operatorname{diag}\bigl(\sqrt{15 + \sqrt{221}}, \sqrt{15 - \sqrt{221}}\bigr) \approx \operatorname{diag}(5.46, 0.37)$
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}\]
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
singular value decomposition $\Sigma = \Lambda$, $U = V = Q$, 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}\)

$A$ has no LU decomposition without exchanging rows, because its top-left entry is $0$, even though $A$ is invertible, but it has the PLU decomposition $A = A \cdot I \cdot I$. $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.

LU decomposition None, without exchanging rows
PLU decomposition $P = A$, $L = I$, $U = I$
Cholesky decomposition None, since $A$ has the negative eigenvalue $-1$
QR decomposition $Q = A$, $R = 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
singular value decomposition $U = A$, $\Sigma = I$, $V = I$
Jordan–Chevalley decomposition $D = A$, $N = 0$
Toeplitz decomposition $H = A$, $K = 0$

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

$A$ is upper triangular, so its LU decomposition is $I \cdot A$, and its QR decomposition is $I \cdot A$. $A$ is not diagonalizable, so its Jordan–Chevalley decomposition has a nonzero nilpotent part $N$.

LU decomposition $L = I$, $U = A$
PLU decomposition $P = I$, $L = I$, $U = A$
Cholesky decomposition None, since $A$ is not symmetric
QR decomposition $Q = I$, $R = A$
eigendecomposition None, since $A$ is not diagonalizable
Schur decomposition $Q = I$, $T = A$
Jordan normal form $P = I$, $J = A$
singular value decomposition $\Sigma = \operatorname{diag}(\varphi, 1 / \varphi)$, where $\varphi = \frac{1 + \sqrt{5}}{2}$
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

Missing example: polar_decomposition

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

An eigendecomposition is not a singular value decomposition, because $P$ need not be orthogonal, and the entries of $D$ can be negative or complex.

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