# How can I tell if a matrix can be LU decomposed without actually finding the L, U?

I've seen quite a few problems like that.

For example, suppose we have the following A matrix:

\begin{pmatrix} 5 & 1 & 1 & 1 & 0 &1\\ 2 & 6 & -1 & 0 & -1 &1\\ {1} & {3} & {-9} & {2} & {-1} &1\\ {2} & {3} & {4} & {12} & {-1} &0\\ {1} & {1} & {1} & {2} & {9} &8\\ {0} & {0} & {0} & {0} & {-3} &0 \end{pmatrix}

and the problem given is to find out without actually doing the calculations to find the L & U, that the matrix can be decomposed to a LU product (A=LU) without doing any row exchanges (which means there's no P matrix used (or P=I if you will)).

The only hint given is that one should use the last row of the matrix to find out that the determinant of the matrix isn't 0.

Now, as far as I understand:

a) If the determinant of a A matrix is not 0, then the A matrix is invertible.

b) If a A matrix is invertible and the determinants of the A[1...k, 1...k] matrices are not 0 (which makes those invertible as well), then the A matrix can be decomposed to LU.

So, if per the suggestion, I use the last row to find the determinant of the matrix, due to the zeroes, I get

detA=-3*detA$_{65}$ (where detA$_{65}$ is the determinant of the matrix A if we remove row 6 and column 5)

right?

Now that determinant still requires a bit of work (which troubles me I am not solving this right..), but anyway, if I continue the calculations, its value is non 0.

But still that only proved that A is invertible.

Now I have to find the determinants of 6 matrices:

1)

\begin{pmatrix}5 \end{pmatrix}

2)

\begin{pmatrix} 5 & 1 \\ 2 & 6 \end{pmatrix}

3)

\begin{pmatrix} 5 & 1 & 1\\ 2 & 6 & -1\\ 2 & 6 & -9\\ \end{pmatrix}

.......

and if none of those are 0, then and only then I can answer that the A matrix can be decomposed to LU, right?

Now, that's quite a lot of work, which makes me think I am not solving correctly the problem. Any ideas?

PS Excuse me for the crappy typesetting at times, this is my first time here and I did my best to learn and use LaTeX but I still have a lot to learn.

-

From $A$, extract the matrix $B$ formed by the first $4$ lines and the first $4$ columns. $B$ is a strictly diagonally dominant matrix and, consequently, your $4$ first determinants are non-zero. Using the last line, one has $\det(A)=3\det(C)$, where $C$ is a strictly diagonally dominant matrix, and we are done !