Dark Mode

Ayush Upadhyaya
asked
in Linear Algebra
Nov 18, 2018

2,925 views
3 votes

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

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?

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?

1 vote

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.