When can we split a square matrix (rows = columns) into it’s LU decomposition? The LUP (LU Decomposition with pivoting) always exists; however, a true LU decomposition does not always exist. How do we tell if it does/doesn't exist? (Note: decomposition and factorization are equivalent in this article)
From the Wikipedia article on LU decompositions:
Any square matrix $A$ admits an LUP factorization. If $A$ is invertible, then it admits an LU (or LDU) factorization if and only if all its leading principal minors are non-zero. If $A$ is a singular matrix of rank $k$, then it admits an LU factorization if the first $k$ leading principal minors are non-zero, although the converse is not true.
This implies that for a square matrix:
- LUP always exists (We can use this to quickly figure out the determinant).
- If the matrix is invertible (the determinant is not 0), then a pure LU decomposition exists only if the leading principal minors are not 0.
- If the matrix is not invertible (the determinant is 0), then we can't know if there is a pure LU decomposition.
The problem is this third statement here. “If $A$ is a singular matrix of rank $k$, then it admits an LU factorization if the first $k$ leading principal minors are non-zero”, gives us a way to find out if LU decomposition exists for a singular (non-invertible) matrix. However, it then says, “although the converse is not true”, implying that even if a leading principal minor is 0, that we could still have a valid LU decomposition that we can't detect.
This leads us back to the question: is there a way of truly knowing whether a matrix has an LU decomposition?
Best Answer
Main point from above mentioned article:
Matrix A (k-by-k) has LU factorization if: $$\mathsf Rank(A_{11})+k\geq Rank(\begin{bmatrix} A_{11} & A_{12} \end{bmatrix}) +Rank(\begin{bmatrix} A_{11} \\ A_{21} \end{bmatrix})$$