Matrix Decomposition
Definition
Expressing a given matrix as a product of other matrices that are simpler and have characteristic forms is called a matrix decomposition or matrix factorization.
Explanation
Although the definition speaks of a product, there are also cases where a matrix is decomposed into a sum. Breaking a given object into simpler pieces is a useful approach not only in mathematics but in many other fields as well. For matrices in particular, handling a matrix in a specific decomposed form often offers many computational advantages over handling the matrix as it is.
Below, the decompositions are classified according to whether the key matrix appearing in the decomposition is a triangular matrix or a diagonal matrix.
Triangular Decompositions
Triangularization
If a matrix $A$ is similar to a triangular matrix $U$, then $A$ is said to be triangularizable.
$$ A = P^{-1} U P $$
Triangularization itself is a kind of matrix decomposition. Every square matrix is triangularizable, that is, it can be decomposed into the form above. In particular, a nilpotent matrix is similar to an upper triangular matrix whose diagonal entries are all $0$.
Schur Decomposition
In triangularization, $P$ can be chosen to be a unitary matrix. That is, every square matrix $A \in M_{n}(\mathbb{C})$ can be decomposed as follows for a unitary matrix $Q$ and an upper triangular matrix $T$. This is called the Schur decomposition.
$$ A = Q T Q^{\ast} $$
Since a unitary matrix satisfies $Q^{-1} = Q^{\ast}$, there is no need to compute the inverse separately, which is an advantage over general triangularization.
LU Decomposition
If an invertible matrix $A \in M_{n}$ can be Gaussian-eliminated without row exchanges, then it can be decomposed as follows for a lower triangular matrix $L$ whose diagonal entries are all $1$ and an upper triangular matrix $U$. This is called the LU decomposition.
$$ A = LU $$
$L$ holds the multipliers used during the elimination process, and $U$ holds the result after the elimination is complete.
PLU Decomposition
Even when a pivot becomes $0$ during elimination and a row exchange is required, every invertible matrix $A$ can be decomposed as follows for a permutation matrix $P$, a lower triangular matrix $L$, and an upper triangular matrix $U$. This is called the PLU decomposition.
$$ A = PLU $$
LDU Decomposition
A symmetric invertible matrix $A$ that has an LU decomposition can be decomposed as follows for a lower triangular matrix $L$ whose diagonal entries are all $1$ and a diagonal matrix $D$. This is called the LDU decomposition.
$$ A = L D L^{\mathsf{T}} $$
When the diagonal entries are extracted from $U$ in the LU decomposition into $D$, the remaining upper triangular matrix becomes $L^{\mathsf{T}}$.
Cholesky Decomposition
A positive definite real symmetric matrix $A$ can be decomposed as follows for a lower triangular matrix $L$. This is called the Cholesky decomposition.
$$ A = L L^{\mathsf{T}} $$
Since the diagonal entries of $D$ in the LDU decomposition are all positive, this can be viewed as the form in which $D^{1/2}$ is absorbed into $L$.
QR Decomposition
An arbitrary matrix $A \in \mathbb{C}^{m \times n}$ can be decomposed as follows for a unitary matrix $Q \in \mathbb{C}^{m \times m}$ and an upper triangular matrix $R \in \mathbb{C}^{m \times n}$. This is called the QR decomposition.
$$ A = QR $$
The orthonormal vectors obtained by applying the Gram-Schmidt orthogonalization to the column vectors of $A$ become the column vectors of $Q$. A distinctive feature is that the matrix need not be square.
Diagonalization
Eigenvalue Decomposition
If a square matrix $A$ is similar to a diagonal matrix $D$, then $A$ is said to be diagonalizable.
$$ A = P^{-1} D P $$
An $n \times n$ matrix $A$ being diagonalizable is equivalent to it having $n$ linearly independent eigenvectors. In this case, since the diagonal entries of $D$ are the eigenvalues of $A$, this decomposition is also called the eigenvalue decomposition.
Orthogonal Diagonalization
If a real square matrix $A$ is similar to a diagonal matrix $D$ via an orthogonal matrix $P$, then $A$ is said to be orthogonally diagonalizable.
$$ A = P^{\mathsf{T}} D P $$
A real square matrix $A$ being orthogonally diagonalizable is equivalent to it being a symmetric matrix. Applying this to quadratic forms gives the principal axis theorem.
Unitary Diagonalization
If a complex square matrix $A$ is similar to a diagonal matrix $\Lambda$ via a unitary matrix $Q$, then $A$ is said to be unitarily diagonalizable.
$$ A = Q \Lambda Q^{\ast} $$
$A$ being unitarily diagonalizable is equivalent to it being a normal matrix. This is called the spectral theorem. In particular, a Hermitian matrix is unitarily diagonalizable, and in this case the diagonal entries of $\Lambda$ are all real.
Spectral Decomposition
Writing out the unitary diagonalization as a sum over the eigenvalues $\lambda_{k}$ and the orthonormal eigenvectors $\mathbf{e}_{k}$ is called the spectral decomposition.
$$ A = \sum_{k=1}^{n} \lambda_{k} \mathbf{e}_{k} \mathbf{e}_{k}^{\ast} $$
Singular Value Decomposition
An arbitrary matrix $A \in \mathbb{C}^{m \times n}$ can be decomposed as follows for unitary matrices $U \in \mathbb{C}^{m \times m}$, $V \in \mathbb{C}^{n \times n}$ and an $m \times n$ diagonal matrix $\Sigma$ whose diagonal entries are nonnegative real numbers. This is called the singular value decomposition or SVD.
$$ A = U \Sigma V^{\ast} $$
The diagonal entries of $\Sigma$ are called the singular values of $A$. Unlike diagonalization, which is possible only for square matrices, the singular value decomposition exists for every matrix. By allowing different unitary matrices on the two sides, it generalizes diagonalization to rectangular matrices.
Others
SN Decomposition
A complex square matrix $A \in M_{n}(\mathbb{C})$ can be decomposed as follows for a diagonalizable matrix $S$ and a nilpotent matrix $N$. This is called the SN decomposition.
$$ A = S + N, \qquad SN = NS $$
Such $S$ and $N$ are unique. This is a representative example of decomposition into a sum.
