LU Factorization Homework Solution

[BubblesAreUs]

Homework Statement

Let

A =

4 -4 -1
4 -4 0
4 0 0

Use the criterion from the lectures to show that A does not have an LU factorisation such that A = LU with lower and upper triangular matrices L and U.

How can you re-arrange the matrix rows such that it is evident without much computation that the permuted matrix does have an LU factorisation.

Homework Equations

A = LU

L =
I11 0 0
I21 I22 0
I31 I32 I33

U =
U11 U12 U13
0 U22 U22
0 0 U33

The Attempt at a Solution

I solved part 1, but taking a 2x2 sub-matrix and showing that its determinant is zero. [-4 0 ; 0 0] ----> det =0

The second part where I have to show that A has an LU factorisation, I merely took A = LU and expanded upon that...

4 -4 -1 = I11 0 0 U11 U12 U13
4 -4 0 I21 I22 0 x 0 U22 U23
4 0 0 I31 I32 I32 0 0 U33

= I11U11 I11U12 U13
I21U11 I21U12 + I22U22 I21U13 + U22
I21U11 I31U12 + I32U22 I31U13 + I32U23 + U33

Let I11 = I22 = I33 = 1

= U11 I11U12 U13
I21U11 I21U13 + U22 I21U13 + U22
I31U11 I31U12 + I32U22 I31U13 + I32U23 + I33U33

Substituting the values of A into the LU, we get

=
U11 = 4 I11U12 = -4 U13 = -1
I21U11 = 4 I21U13 + U22 = -4 I21U13 + U22 = 0
I31U11 = 4 I31U12 + I32U22 = 0 I31U13 + I32U23 + I33U33 = 0

Now at this form, it's becoming obvious that row 1 and row 3 needs to be swapped. There is a single pivot on the left-most side of the third row, and that'll allow for an LU factorisation. Unfortunately, I can't really rationalise my position outside of that...

 

[RUber]

The second part asks how you can rearrange the matrix rows to make it clear.
You have found that you need to swap rows 1 and 3, looking at the original matrix, does that make sense?
$A= \begin{bmatrix} 4&-4&-1\\4&-4&0\\4&0&0\end{bmatrix}, \hat A = \begin{bmatrix} 4&0&0\\4&-4&0\\4&-4&-1\end{bmatrix},$
By making that switch, you have made A into a lower triangular matrix from the outset. Your U in this case would just be the identity.

 

[BubblesAreUs]

The second part asks how you can rearrange the matrix rows to make it clear.
You have found that you need to swap rows 1 and 3, looking at the original matrix, does that make sense?
$A= \begin{bmatrix} 4&-4&-1\\4&-4&0\\4&0&0\end{bmatrix}, \hat A = \begin{bmatrix} 4&0&0\\4&-4&0\\4&-4&-1\end{bmatrix},$
By making that switch, you have made A into a lower triangular matrix from the outset. Your U in this case would just be the identity.

Yes, I get that. It seems like the rest of the stuff I did earlier is probably not required.

Thanks RUber!

 

[Ray Vickson]

Yes, I get that. It seems like the rest of the stuff I did earlier is probably not required.

Actually, it MAY be required. What you have shown so far is that if you permute the rows there is, indeed, an LU factorization. The first part asks you to show the opposite: if you do not change the matrix (eg., do not permute the rows) there is no LU decomposition. That seems much harder.

 

[BubblesAreUs]

Actually, it MAY be required. What you have shown so far is that if you permute the rows there is, indeed, an LU factorization. The first part asks you to show the opposite: if you do not change the matrix (eg., do not permute the rows) there is no LU decomposition. That seems much harder.

Yes, for the first part, I essentially grabbed a sub-matrix and showed that its determinant is zero. To go any further than that would probably be quite tricky.

Thanks Ray

 

[Ray Vickson]

Yes, for the first part, I essentially grabbed a sub-matrix and showed that its determinant is zero. To go any further than that would probably be quite tricky.

Thanks Ray

I could not follow the argument you presented.