= Matrix decomposition
{wiki}
= Matrix factorization
{synonym}
A <matrix decomposition> expresses a <matrix> as a <matrix product> of factors with simpler structure. An <LU decomposition> uses triangular factors, a <QR decomposition> uses an <orthogonal matrix> and a triangular factor, and a <singular value decomposition> separates input directions, stretching factors and output directions. The factorization is an identity; the chosen structure determines what it helps compute.
For an original two-by-two example,
$$
M=\begin{pmatrix}2&1\\1&3\end{pmatrix}
=\begin{pmatrix}1&0\\1/2&1\end{pmatrix}
\begin{pmatrix}2&0\\0&5/2\end{pmatrix}
\begin{pmatrix}1&1/2\\0&1\end{pmatrix}.
$$
The outer factors are a <lower triangular matrix> and an <upper triangular matrix>, each with unit diagonal as in a <unit triangular matrix>; the middle factor is a <diagonal matrix>. Their <matrix product> is $M$, and the final diagonal entry $5/2$ is the <Schur complement> of the first entry $2$. This is the scalar version of the factorization under <block elimination>.
To solve $Mz=(3,4)^T$, solve with the three factors in their displayed order from left to right: first the lower triangular factor, then the diagonal factor, then the upper triangular factor. The intermediate <vectors> are $(3,5/2)^T$ and $(3/2,1)^T$, giving the concise answer $z=(1,1)^T$. A new right-hand side uses the same factors. This is why <Reusing LU factors for multiple right-hand sides> is useful: factorization records work that otherwise would be repeated, while <forward substitution> and <back substitution> apply it cheaply.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§C.4.1, printed pp. 673–674: block factor-solve interpretation]{ref}
Different decompositions reveal different features. A <Cholesky decomposition> uses <positive definiteness> of a <symmetric matrix>, while a <singular value decomposition> also applies to rectangular <matrices> and exposes <matrix rank>. The existence and numerical behaviour of the factors depend on their own hypotheses; for example, an unpivoted <LU decomposition> can fail when a chosen <pivot element> is zero even though the <matrix> is an <invertible matrix>.
Back to article page
