Prove by contradiction that the matrix [1 2 3;2 4 1;4 6 7] does not have a LU decomposition.?

Question

Prove by contradiction that the matrix [1 2 3;2 4 1;4 6 7] does not have a LU decomposition.?

Answer 1

You can do this by "brute force"  (although it's not very elegant).

So assume there is a LU decomposition and let:

L = [a 0 0;b c 0;d e f]    (semicolons end the rows)

U =[g h i;0 j k;0 0 l]

Let A be the given matrix.

Now multiply out LU (write this out so you can follow along) and set it equal to A. Thus corresponding entries of LU and A must be equal. This gives 9 equations and we have to manipulate them to get a contradiction. There are several ways to do it and here is one:

First note that by comparing the 1st row of LU to A and the 1st column, we see that none of a,b,d,g,h,i can be zero. So we can divide by these if we need to. In what follows, I'll write  "2,3" to indicate the row 2 colm 3 entry of LU and A:

2,2 implies that bh+cj=4

but 1,2 implies h=2/a

and 2,1 and 1,1 say (by eliminating g) that b=2a

So bh+cj= (2a)(2/a)+cj=4 . So cj=0

Thus either c or j must be zero.

We'll now show that in fact neither can be zero:

If c=0, then 2,3 says bi+ck=bi=1.

But 1,3 says i=3/a (and per above b=2a)

So bi=(2a)(3/a) = 6 =1 which is a contradiction.

So we must have j=0

But then 3,2 says dh+ej=dh=6

But from 3,1 and 1,1 we get d=4a (by eliminating g)

So dh=(4a)(2/a) = 8 = 6 a contradiction.

Therefore, there can be no such decomposition.

If you work with it, you can probably find a quicker set of steps to force a contradiction. But the general idea is that to do a proof by contradiction, you assume the result is possible and then try to show that it leads to something that can't be.