LU decomposition

#oct-28

Let A be a matrix we want to decompose A into a lover triangle matrix with diagonal entries 1 and a upper triangle matrix , ie

A row echelon is matrix is such that the

all non-zero rows are at the bottom
the first non-zero elements of a row it to the left of the first non-zero elements of row i+1 at the bottom
Let A be a nxn matrix so that A can be reduced to a row echelon form by only using the row operation adding a row with a scalar multiplier of another row ie. A can be reduced to row echelon form by multiplying A from the left by elementary matrices of type I ie,

is a lower triangle matrix and product of them is a lower triangle matrix with diagonal 1

Theorem.

For matrix A which can be reduced to row echelon form without interchanging the row then there exit a lower triangle matrix with diagonal entries and an matrix such that

Let A be a matrix such that A can be reduced to row echelon form, without row interchanges so there exist a lower triangular and such that
so, let we solve

Let be a solution then we solve for

Suppose A is a square matrix and A admits a LU decomposition has all diagonal entries 1

Let then we mutliply the ith row of by and produce an upper triangle matrix with dioganal entries 1
we create nxxn diagonal matrix with

hence where

is lower triangular with dioganal entries 1
is upper triangular with diagonal entries 1
is diagonal matrix with diagonals entries non-zero

invertible matrices admit a LU decomposition if all its leading principal minor are non-zero
A singular matrix of rank admits a LU decompsition if the first leading principal minors are non-zero

If a is a matrix such that we need to use a row interchange to bring it to its row echelon form then we multiply A by a suitable permutation matrix from left so that PA (which has a rearrangement of the rows of A) uses no row interchange to get its row echelon form and then