I am stucked at this problem:
Prove by induction that if the leading principal minors of an $n\times n$ nonsingular matrix $A$ are all nonzero then the matrix $A$ has $LU$ factorization.
(The $k$-th leading principal minor of an $n\times n$ matrix $A$ is the determinant of its upper-left $k \times k$ sub-matrix)
My intuition is that we can perform Gaussian elimination on the matrix $A$ without row interchanges (and so $A$ will have $LU$ factorization) , but I wasn't able to formalize it in the induction.
Thanks for any hint/help.
Best Answer
Here's a hint. Let $A$ be a $k\times k$ matrix whose leading principal minors are nonzero. In block form
$$ A = \left[ \begin{array}{cc} \hat{A} & a\\ b^T & a_{kk}\\ \end{array}\right] $$
It follows that $\hat{A}$ is a $(k-1)\times(k-1)$ matrix whose leading principal minors are all nonzero. Thus, by the induction hypothesis $\hat{A}$ has an LU factorization $\hat{A} = \hat{L}\hat{U}$ with the important property that $\hat{U}$ has nonzero elements on its main diagonal.