Last modified 2017-09-25 00:25:11 CDT

# Ax=b and A=LU

To solve $$Ax=b$$, first factorize:

$A = LU$

Then solve:

$Lc = b$ $c = L^{-1}b$

Then solve:

$Ux = c$ $x = U^{-1}c$

which makes sense since $$x = U^{-1}L^{-1} b = (LU)^{-1} b = A^{-1} b$$.

Solving the systems $$Lc=b$$ and $$Ux=c$$ is fast, since the matrices $$L$$ and $$U$$ are triangular. It’s just forward and back substitution to solve.

Solving $$Lc=b$$ brings the vector b to vector c, which is what it would have transformed to if you manipulated the augmented matrix into row echelon form, that is $$[\bf{A} b]$$ into $$[\bf{U} c]$$. In other words, $$L^{-1}$$ carries out the row operations that bring $$A$$ to $$U$$.

Solving $$Ux=c$$ brings the vector c to vector x, which is what you would have solved for if you manipulated the augmented matrix into row-reduced echelon form, that is $$[\bf{A} b]$$ to $$[\bf{U} c]$$ to $$[\bf{I} x]$$ (for invertible n$$\times$$n A). In other words, $$U^{-1}$$ carries out the row operations that bring $$U$$ to $$I$$.

Finding the matrix inverse $$A^{-1}$$ is for suckers: Don’t invert that matrix!

$$A = LU$$ also immediately gives you the determinant of $$A$$. If a zero pivot was encountered during elimination of $$A$$ (factorizing into $$LU$$), then you know $$det(A) = 0$$. If $$A$$ successfully factorizes into $$LU$$, then $$det(A)$$ is just the product of the pivots which sit on the diagonal of $$U$$: $$det(A) = u_{11} u_{22} u_{33} \ldots$$.