22
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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...) $\endgroup$ – Jay Feb 24 '13 at 10:21
6
$\begingroup$

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

http://arxiv.org/pdf/math/0506382v1.pdf

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

$\endgroup$
  • 1
    $\begingroup$ Too good an answer to be "easily understandable".. ;-) $\endgroup$ – Qwerty Feb 20 '16 at 14:04
  • 6
    $\begingroup$ I would love to see the main points of that article summarized. $\endgroup$ – jvriesem Apr 1 '16 at 18:42
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ what do you mean by A11 and A21 and A12 , sorry im a newby $\endgroup$ – mahdi Mar 31 '18 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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