the LU factorization

When you run Gaussian elimination you throw a lot of arithmetic at the matrix and end up with a triangular system. The LU factorization is the simple but powerful realization that all that work can be saved as two triangular matrices: a lower-triangular L (with 1s on its diagonal, holding the multipliers you used) and an upper-triangular U (the result of the elimination). Their product reconstructs the original: A = L U. It is the elimination, bottled up so you can reuse it.

Here is why L and U appear. Each elimination step 'subtract m_i1 times row 1 from row i' is itself a simple lower-triangular operation, and undoing them (putting the multipliers m_i1 back) builds L. So if you store every multiplier m_ij = a_ij / a_jj used to zero entry (i, j), you get L exactly, while U is the upper-triangular matrix left behind. To then solve A x = b you split it into two easy triangular solves: first L y = b by forward substitution (work top-down), then U x = y by back substitution (work bottom-up). The factorization costs about 2 n^3 / 3 flops; each triangular solve costs only about n^2.

The payoff is factor-once, solve-many: if you must solve A x = b for many different right-hand sides b (common in simulation, optimization, and time-stepping), you pay the cubic cost ONCE to get L and U, then each new b costs only O(n^2). The LU factorization also hands you the determinant (the product of the diagonal of U, times the sign of the row swaps) almost for free, and it is the standard route a library like LAPACK takes to solve a dense system. In practice it comes with pivoting, so what is actually computed is P A = L U for a permutation matrix P.