Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
You probably mean knowing wether a matrix has LU decomposition "without trying to calculate it", since one way to check if the decomposition exists would be to just try to decompose it (you wouldn't need any exponential algorithms or anything like that...) – Jay Feb 24 '13 at 10:21

Necessary and Sufficient conditions in terms of rank inequalities are given in:

Even though it has been a while, I hope it helps!

share|cite|improve this answer
Too good an answer to be "easily understandable".. ;-) – Qwerty Feb 20 at 14:04
I would love to see the main points of that article summarized. – jvriesem Apr 1 at 18:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.