2,925 views

https://math.stackexchange.com/questions/218770/when-does-a-square-matrix-have-an-lu-decomposition.

I made some form of self-analysis, let me know if I am in the correct direction.

After working on some problems, I found out that LU decomposition of nxn square matrix is not possible, when we don't have full set of n pivots along the main diagonal.

What I do is, I take the input matrix A, try to convert it into Echelon form  to obtain U by row transformations and apply reverse row transformations to form the matrix L.Obviously LU should be equal A.

Consider below matrix A as

$\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}$

$R_2=R_2+(-4R_1)$

$\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}$=U

Now L should be of form

$\begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}$=L

The first row of L tells, take the first row of U and add with $0^{th}$ multiple of the second row of U to produce the 1st row of A.

Second Row of L tells, $4*R_1(of\,U)+R_2(of\,U)=R_2(of\,A)$

And in U I have full set of 2 pivots so LU decomposition was possible.

Consider another matrix

A=
$\begin{bmatrix} 1 & 2 &3 \\ 2 & 4 &5\\ 1&3&4\\ \end{bmatrix}$

Now I try to obtain U using Row transformations $R_2=R_2-2R_1,R_3=R_3-R_1$

$\begin{bmatrix} 1 & 2 &3 \\ 0 & 0 &-1\\ 0&1&1\\ \end{bmatrix}$

The pivot in the second row has disappeared. I can interchange $R_2,R_3$ to fix this but that would also change the structure of matrix L, and I think this matrix does not have LU decomposition.

So, what I summarized is that if the matrix on being transformed to U through row reductions, loses a pivot, and if such cannot be fixed without a row shuffle operation, then LU decomposition is not possible.

Am I correct?

I donot understand, why u r doing row column elimination in LU
@srestha-My main point I want to ask is when I reduce a matrix A to Echelon form(U), and suppose I loose a pivot in any row while doing so, then that matrix won't be LU factorizable na?

Page 7. there it is explained.

You already found this from Wikipedia but what it means like-

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.

bolded line says that if determinant(minor) of leading principal are non- zero then only a matrix admits LU factorization.

So now according to your examples-

1) $\begin{bmatrix} 2 &1 \\ 8 & 7 \end{bmatrix}$

principal submatrices are $\begin{bmatrix} 2 \end{bmatrix} , \begin{bmatrix} 7 \end{bmatrix}, \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}$

but leading principal submatrices are $\begin{bmatrix} 2 \end{bmatrix} ,\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}$

and determinant of all are 2, 6 which are non zero so above matrix admits the LU factorization.

2) $\begin{bmatrix} 1 &2 & 3\\ 2 & 4 & 5 \\ 1 & 3 & 4\end{bmatrix}$

principal submatrices are $\begin{bmatrix} 1 \end{bmatrix} , \begin{bmatrix} 4 \end{bmatrix}, \begin{bmatrix} 4 \end{bmatrix},\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix},\begin{bmatrix} 1 & 3 \\ 1 & 4 \end{bmatrix},\begin{bmatrix} 4 & 5 \\ 3 & 4 \end{bmatrix},\begin{bmatrix} 1 &2 & 3\\ 2 & 4 & 5 \\ 1 & 3 & 4\end{bmatrix}$

but leading principal submatrices are $\begin{bmatrix} 1 \end{bmatrix}, \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix},\begin{bmatrix} 1 &2 & 3\\ 2 & 4 & 5 \\ 1 & 3 & 4\end{bmatrix}$

and determinant of 1st leading principal submatrix is 1 and , for 2nd it is 0 which are not non zero so above matrix does not admit the LU factorization.

So yes your statement is correct.