Take the 2-minute tour ×
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.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.