31
$\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$
2
  • 2
    $\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
    Commented Feb 24, 2013 at 10:21
  • $\begingroup$ Necessary and Sufficient conditions in terms of rank inequalities are given in: arxiv.org/pdf/math/0506382v1.pdf Even though it has been a while, I hope it helps! $\endgroup$
    – Luke Skywalker
    Commented Aug 24, 2014 at 3:48

1 Answer 1

Reset to default
12
$\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$
3
  • 4
    $\begingroup$ what do you mean by A11 and A21 and A12 , sorry im a newby $\endgroup$
    – mahdi
    Commented Mar 31, 2018 at 11:13
  • 1
    $\begingroup$ yeah, what do they mean $\endgroup$
    – Jale'de jaled
    Commented Nov 12, 2020 at 19:46
  • 1
    $\begingroup$ @Jale'dejaled $A$ should be $n$-by-$n$ and has to be over a field. Then $A$ has an LU factorization if and only if the above holds for each $k = 1,\dotsc,n-1$ where $$ A = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix}, \text{ and } A_{11} \text{is a $k\times k$ Matrix}. $$ $\endgroup$
    – Matthias
    Commented Feb 9, 2021 at 22:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .