When does a Square Matrix have an LU Decomposition?

Question

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:

1. LUP always exists (We can use this to quickly figure out the determinant).
2. 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.
3. 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?

Answer 1

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})$$