LU decomposition
- I'm leaving out a lot of the conditions that need to be met to make the below true
- Take a square matrix \(A\)
- Let's say you can apply only adding multiples of rows together to put \(A\) in row echelon form. Each one of these operations can be written as a matrix \(E_i\). Let \(L^{-1}\) be the product of all these operations. That is, hitting \(A\) with \(L^{-1}\) will put \(A\) in echelon form: \(L^{-1}A = U\). Then, \(A=LU\).
- If we want to solve \(Ax = LUx = b\), first we find \(y\) such that \(Ly = b\). That is, we find \(y\) such that \(y = L^{-1}b\). Conceptually, we hit \(b\) with all the operations that put \(A\) into echelon form. This is what would happen if we were doing Gaussian elimination on the augmented matrix \([A \mid b]\). Then, we find \(x\) such that \(Ux = y\) by substitution, which is what we would have done after putting the augmented matrix in row echelon form to solve the system of equations.