LU Factorization
Problem 1. \(\,\)
Prove that the inverse of a non-singular lower (upper) triangular matrix
is also a lower (upper) triangular matrix.
Proof. \(\,\)
Let \(\,\boldsymbol{L}\,\) be a non-singular lower triangular matrix
of size \(\,n\,\) over a field \(\,K,\ \) and
\[\begin{split}\boldsymbol{L}^{-1}\ =\
\left[\,\boldsymbol{x}_1\,|\,\boldsymbol{x}_2\,|\,\ldots\,|\,
\boldsymbol{x}_n\,\right]\ =\
[x_{ij}]_{\,n\times n}\,,
\quad\text{where}\quad
\boldsymbol{x}_j\ =\
\left[\begin{array}{c}
x_{1j} \\ x_{2j} \\ \ldots \\ x_{nj}
\end{array}\right],
\quad j=1,2,\ldots,n.\end{split}\]
Using the Column Rule of Matrix Multiplication, we may write
\[ \begin{align}\begin{aligned}\boldsymbol{L}\,\boldsymbol{L}^{-1}\ =\ \boldsymbol{I}_n\,,\\\boldsymbol{L}\
\left[\,\boldsymbol{x}_1\,|\,\boldsymbol{x}_2\,|\,\ldots\,|\,
\boldsymbol{x}_n\,\right]\ =\
\left[\,\boldsymbol{e}_1\,|\,\boldsymbol{e}_2\,|\,\ldots\,|\,
\boldsymbol{e}_n\,\right]\,,\\\left[\,
\boldsymbol{L}\boldsymbol{x}_1\,|\,
\boldsymbol{L}\boldsymbol{x}_2\,|\,\ldots\,|\,
\boldsymbol{L}\boldsymbol{x}_n\,\right]\ =\
\left[\,\boldsymbol{e}_1\,|\,\boldsymbol{e}_2\,|\,\ldots\,|\,
\boldsymbol{e}_n\,\right]\,,\\\boldsymbol{L}\,\boldsymbol{x}_j\ =\ \boldsymbol{e}_j\,,
\qquad j=1,2,\ldots,n.\end{aligned}\end{align} \]
Here \(\,\boldsymbol{e}_j\,\) is a column vector with unity
in the \(\,j\)-th row and zeros elsewhere.
According to the Cramer’s rule we get
\[\begin{split}x_{ij}\ =\ \,\frac{D_{ij}}{D}\,,
\qquad\text{where}\quad
\begin{array}{l}
D_{ij}=\det{\boldsymbol{L}_{ij}}\,, \\ D\ =\ \det{\boldsymbol{L}}\,;
\end{array}
\quad
i,j=1,2,\ldots,n.\end{split}\]
\(\boldsymbol{L}_{ij}\ \) is a matrix obtained from \(\boldsymbol{L}\,\)
by replacing the \(\,i\)-th column with \(\boldsymbol{e}_j\,:\)
\[\boldsymbol{L}_{ij}\ =\
\left[\,
\boldsymbol{x}_1\,|\,\ldots\,|\,
\boldsymbol{x}_{i-1}\,|\,
\boldsymbol{e}_j\,|\,
\boldsymbol{x}_{i+1}\,|\,\ldots\,|\,
\boldsymbol{x}_n\,\right]\,,
\qquad i,j=1,2,\ldots,n.\]
Remembering that \(\boldsymbol{L}\,\) is a lower triangular matrix,
it’s easy to realize that \(\,D_{ij}=0\,\) for \(\,i<j.\ \) Thus
\[x_{ij} = 0\quad\text{for}\quad i<j,\ \ i,j=1,2,\ldots,n,\]
hence \(\boldsymbol{L}^{-1}\,\) is a lower triangular matrix.
\(\quad\bullet\)
Exercise 1. \(\,\)
The Sage code below constructs a random matrix
\(\,\boldsymbol{A}\in M_{m\times n}(Q)\,\)
and returns its decomposition
\(\,\boldsymbol{A} = \boldsymbol{P}\,\boldsymbol{L}\,\boldsymbol{U}.\,\)
write down additional commands to verify the decomposition;
set various dimensions \(\,m\,\)
and \(\,n\,\) of matrix \(\,\boldsymbol{A};\)
try another pivoting strategy (pivot = ‘nonzero’) \(\\\)
or another format of the output (format = ‘compact’).
