Linear Algebra – Matrices – Matrix factorizations

A factorization of a matrix \(A\) is an equation that expresses \(A\) as a product of two or more matrices. For the moment we only consider the \(LU\) factorization.

The \(LU\) factorization

Let \(A\) be an \(m\times n\) matrix that can be row reduced to echelon form without row interchanges. Then \(A\) can be written in the form \(A=LU\), where \(L\) is an \(m\times m\) lower triangular matrix with only \(1\)'s on the main diagonal and \(U\) is an \(m\times n\) echelon form of \(A\). Such a factorization is called an \(LU\) factorization (or decomposition). Note that by the (left) multiplication by \(L\) the echelon form \(U\) is transformed back to \(A\).

When \(A=LU\), the equation \(A\mathbf{x}=\mathbf{b}\) can be written as \(L(U\mathbf{x})=\mathbf{b}\). Writing \(U\mathbf{x}=\mathbf{y}\), we can find \(\mathbf{x}\) by solving the pair of equations \(L\mathbf{y}=\mathbf{b}\) and \(U\mathbf{x}=\mathbf{y}\). First solve \(L\mathbf{y}=\mathbf{b}\) for \(\mathbf{y}\), and then solve \(U\mathbf{x}=\mathbf{y}\) for \(\mathbf{x}\). Each equation is easy to solve because \(L\) and \(U\) are triangular.

Example: Consider \(A\mathbf{x}=\mathbf{b}\) with \(A=\begin{pmatrix}-2&1&3\\1&-1&-2\\-1&2&1\end{pmatrix}\) and \(\mathbf{b}=\begin{pmatrix}-5\\3\\-6\end{pmatrix}\). Then we have (without row interchanges):

\[A=\begin{pmatrix}-2&1&3\\1&-1&-2\\-1&2&1\end{pmatrix}\sim\begin{pmatrix}-2&1&3\\0&-\frac{1}{2}&-\frac{1}{2}\\0&\frac{3}{2}&-\frac{1}{2}\end{pmatrix} \sim\begin{pmatrix}-2&1&3\\0&-\frac{1}{2}&-\frac{1}{2}\\0&0&-2\end{pmatrix}=U.\]

Then \(L=\begin{pmatrix}1&0&0\\a&1&0\\b&c&0\end{pmatrix}\). Note that \(a\), \(b\) and \(c\) are exactly at the positions where we have created zeros in order to obtain the echelon form \(U\). The values of \(a\), \(b\) and \(c\) must be the opposite values of those that we used to create the zero at the appropriate position. We conclude that \(a=-\frac{1}{2}\), \(b=\frac{1}{2}\) and \(c=-3\). Hence we have \(L=\begin{pmatrix}1&0&0\\-\frac{1}{2}&1&0\\\frac{1}{2}&-3&1\end{pmatrix}\). It is easily checked that

\[LU=\begin{pmatrix}1&0&0\\-\frac{1}{2}&1&0\\\frac{1}{2}&-3&1\end{pmatrix}\begin{pmatrix}-2&1&3\\0&-\frac{1}{2}&-\frac{1}{2}\\0&0&-2\end{pmatrix} =\begin{pmatrix}-2&1&3\\1&-1&-2\\-1&2&1\end{pmatrix}=A.\]

Now we have (starting at the top):

\[L\mathbf{y}=\mathbf{b}:\quad\left(\left.\begin{matrix}1&0&0\\-\frac{1}{2}&1&0\\\frac{1}{2}&-3&1\end{matrix}\,\right|\,\begin{matrix}-5\\3\\-6\end{matrix}\right) \quad\Longrightarrow\quad\mathbf{y}=\begin{pmatrix}-5\\\frac{1}{2}\\-2\end{pmatrix}\]

and then (starting at the bottom):

\[U\mathbf{x}=\mathbf{y}:\quad\left(\left.\begin{matrix}-2&1&3\\0&-\frac{1}{2}&-\frac{1}{2}\\0&0&-2\end{matrix}\,\right|\,\begin{matrix}-5\\\frac{1}{2}\\-2\end{matrix}\right) \quad\Longrightarrow\quad\mathbf{x}=\begin{pmatrix}3\\-2\\1\end{pmatrix}.\]

Note that a permutation of the rows in the system of equations given by \(A\mathbf{x}=\mathbf{b}\) would lead to nicer computations. Sometimes it is even impossible to row reduce the matrix \(A\) to echelon form without row interchanges even though the system \(A\mathbf{x}=\mathbf{b}\) is consistent. Then, instead of the usual \(A=LU\) factorization a \(PA=LU\) factorization is used, where \(P\) denotes some permutation matrix. For instance, in our example let \(P=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}\). Then \(PA\mathbf{x}=P\mathbf{b}\) is equivalent to \(A\mathbf{x}=\mathbf{b}\) and

\[PA=\begin{pmatrix}1&-1&-2\\-1&2&1\\-2&1&3\end{pmatrix}\sim\begin{pmatrix}1&-1&-2\\0&1&-1\\0&-1&7\end{pmatrix} \sim\begin{pmatrix}1&-1&-2\\0&1&-1\\0&0&-2\end{pmatrix}=U\quad\Longrightarrow\quad L=\begin{pmatrix}1&0&0\\-1&1&0\\-2&-1&1\end{pmatrix}.\]

Now we have (starting at the top):

\[L\mathbf{y}=P\mathbf{b}:\quad\left(\left.\begin{matrix}1&0&0\\-1&1&0\\-2&-1&1\end{matrix}\,\right|\,\begin{matrix}3\\-6\\-5\end{matrix}\right) \quad\Longrightarrow\quad\mathbf{y}=\begin{pmatrix}3\\-3\\-2\end{pmatrix}\]

and then (starting at the bottom):

\[U\mathbf{x}=\mathbf{y}:\quad\left(\left.\begin{matrix}1&-1&-2\\0&1&-1\\0&0&-2\end{matrix}\,\right|\,\begin{matrix}3\\-3\\-2\end{matrix}\right) \quad\Longrightarrow\quad\mathbf{x}=\begin{pmatrix}3\\-2\\1\end{pmatrix}.\]

---

Last modified on March 29, 2021