If A is an invertible matrix then a necessary and sufficient condition for the LU Factorization to exist is :
If A is invertible, then it admits an LU (or LDU) factorization if and only if all its leading principal minors are nonsingular
Source : https://en.wikipedia.org/wiki/LU_decomposition
How should one go about proving this ?
Thanks in advance
Best Answer
The principle minor of a $n\times n$ matrix $$M=\begin{bmatrix} a_{11}&\dots&a_{1n}\\ \vdots&\ddots&\vdots\\ a_{n1}&\dots&a_{nn}\\ \end{bmatrix}$$ is a $k\times k$ ($1\ge k\ge n$) matrix obtained by deletion of the last $n-k$ rows and columns, i.e $$A=\begin{bmatrix} a_{11}&\dots&a_{1k}\\ \vdots&\ddots&\vdots\\ a_{k1}&\dots&a_{kk}\\ \end{bmatrix}$$
Rewrite $M$ as a block matrix, i.e. $$M=\begin{bmatrix} A&B\\ C&D\\ \end{bmatrix}$$ where $A$ is a principle minor of $M$.
From this point I would try to show that the lower triangular matrix $L^M$ such that $L^MU^M=M$ can be written as a block matrix with a principle minor $L^A$ such that $L^AU^A=A$, i.e. $$L^M=\begin{bmatrix} L^A&0\\ C'&D'\\ \end{bmatrix}$$
From this I would conclude that if a principle minor $A$ is singular we would have no $L^AU^A=A$ decomposition.