Chapter 2.4, Problem 93E

In this exercise we will examine which invertible $n\times n$ matrices A admit an LU-factorization $A=LU$ , as discussed in Exercise 90. The following definition will be useful: For $m=1,\mathrm{...},n$ , the principal submatrix $A^{\left(m\right)}$ of A is obtained by omitting all rows and columns of A past the mth. For example, the matrix
$A=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 7\end{array}\right]$
has the principal submatrices
$A^{\left(1\right)}=\left[1\right],A^{\left(2\right)}=\left[\begin{array}{cc}1& 2\\ 4& 5\end{array}\right],A^{\left(3\right)}=A=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]$ .
We will show that an invertible $n\times n$ matrix A admits an LU-factorization $A=LU$ if (and only if) all its principal submatrices are invertible.
a. Let $A=LU$ be an LU-factorization of an $n\times n$ matrix A. Use block matrices to show that $A^{\left(m\right)}=L^{\left(m\right)}{U}^{\left(m\right)}$ for in $m=1,\mathrm{...},n$ .
b. Use part (a) to show that if an invertible $n\times n$ matrix A has an LU-factorization, then all its principal submatrices $A^{\left(m\right)}$ are invertible.
c. Consider an $n\times n$ matrix A whose principal submatrices are all invertible. Show that A admits an LU-factorization. Hint: By induction, you can assume that $A^{\left(n-1\right)}$ has an LU-factorization $A^{\left(n-1\right)}=L^{\prime }{U}^{\prime }$ . Use block matrices to find an LU-factorization for A. Alternatively, you can explain this result in terms of Gauss—Jordan elimination (if all principal submatrices are invertible, then no row swaps are required).