# LU Split

1. Aug 18, 2004

### niko2000

Hi,
Does anybody know the procedure for splitting a square matrix into lower and upper triangular matrix?
LU=A
Thank you.
Regards,
Niko

2. Aug 18, 2004

### HallsofIvy

Staff Emeritus
Write the identity matrix and your given matrix side by side.

Use "row operations" to reduce one column at a time to zeros below the diagonal.
Use the "opposite" row operation on the "identity" matrix. (opposite: if you mult a row by a number and then added, multiply by that number and the subtract.
Also don't apply that operation left of the diagonal.

example: reducing the matrix
[1 1 1]
[1 2 0]
[2 0 1]

to LU form:
[1 0 0] [1 1 1]
[0 1 0] [1 2 0]
[0 0 1] [2 0 1]

To reduce the first column, subtract the first row from the second and then subtract twice the first row from the third.
That means on the identity matrix on the left, we must add the first row to the second add add twice the first row to the third. We get:
[1 0 0] [1 1 1]
[1 1 0] [0 1 -1]
[2 0 1] [0 -2-1]

Now add twice the second row to the third row in the matrix on the right. Subtract twice the second row from the third row in the matrix on the left. (and [b not the first column. we get:
[1 0 0] [1 1 1]
[1 1 0] [0 1-1]
[2 2 1] [0 0-1]
the LU decomposition of the original matrix.

3. Aug 19, 2004

### niko2000

Thank you!

4. Aug 19, 2004

### niko2000

I have tried this procedure on this one:
[3 2 5 1]
[6 6 15 3]
[-3 4 13 1]
[-6 6 15 15]
and I couldn't come to a right solution
After first step I got this:
[1 0 0 0] [3 2 5 1]
[2 1 0 0] [0 2 5 1]
[-1 0 1 0] [0 6 18 2]
[-2 0 0 1] 0 10 25 7]

After second step I get L and U, but LU isn't equal to the first matrix.
Any correction of my possible error would be helpful.

5. Aug 19, 2004

### Hurkyl

Staff Emeritus
Showing what you have at the second step would be helpful. :tongue:

BTW, HoI, if you add the first row to the second row on the right matrix, aren't you supposed to subtract the second column from the first column on the left matrix?

6. Aug 19, 2004

### niko2000

I have already found a mistake: I have changed first column too instead of leave it unchanged.

7. Aug 19, 2004

### niko2000

I have done the way HallsofIvy has shown me and it works. This question is out of place here, but anyway...I have listened to the discusions on the forum and I must say your answers are really practical and easy to understand. Before giving this question I was looking at my notes to find an answer and it seemed more difficult.
What I wanted to ask....what way do you take classes? As I can see your learning is based on much more practical work then theory work.
We take quite a lot of theory and I think it should be explained on more practical problems.

8. Aug 21, 2004

### HallsofIvy

Staff Emeritus
Learn the theory- DO the practical problems. If all you do is "practical problems" then you
learn to do those problems but may not learn how to handle problems that are slightly
different. If you learn the theory, you should be able to apply it to all problems.
The course should be a mix of theory and practice but if time is limited, it may well be better for
your instructor to concentrate on the theory and let YOU figure out the applications.

No, although I can't without using several pages, explain why except to say that it works!

A very nice, somewhat more theoretical explanation by Wong, is in a slightly newer thread here:

9. Aug 21, 2004

### Hurkyl

Staff Emeritus
I've never bothered learning LU decomposition; I imagine I probably should sometime. I was trying to figure out why it works...

If we write A = BC (of course, for the first step, B=I and C=A), then we can multiply inside by an elementary matrix and its inverse: A = B E^-1 E C.

Adding the first row to the second is the same as left multiplying by

Code (Text):

1 0 0
1 1 0
0 0 1

Whose inverse is

Code (Text):

1 0 0
-1 1 0
0 0 1

and right-multiplying a matrix by this is the same as subtracting the second column from the first.

I'll work through an example, maybe, later today to see why this interpretation does/doesn't work.