Cases when LU decomposition is possible.

I had already visited below link but was unable to grasp it.

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?

• The short answer is yes, although it might take some time to proof. – Just_a_newbie Nov 18 '18 at 12:21