Gaussian elimination. Remember where you subtract multiples of one row from another, in order to get zeros below the diagonal? That way you can back-solve a sys

Gaussian elimination. Remember where you subtract multiples of one row from another, in order to get zeros below the diagonal? That way you can back-solve a system of equations by reading off solutions starting with the bottom-right corner. The result of carrying out the elimination steps is a triangular matrix with all zeros below the main diagonal. Call it U, for "upper". The elimination steps themselves can be encoded as a matrix, rather than describing them in words. For instance, "subtract 2 times row 1 from row 2" is the matrix: [ 1 0 0] [-2 1 0] [ 0 0 1] So, to solve the system, you can perform elimination on A x = b, which gives you two matrices (U, and the elimination steps L). In some sense, you've factored A in to L and U. Example: Using Strang's terminology, let's call the matrix that "eliminates (i.e. sets to 0) the (i,j) entry" Eij So, to solve a 3x3 system A x = b, you want to do elimination as: (E32 E31 E21) A = U I.e. 1) Take A and subtract some multiple of row 2 from row 1, to put 0 in (2,1) 2) Take the result and subtract some multiple of row 3 from row 1 to put 0 in (3,1) 3) Take the result and subtract some multiple of row 3 from row 2 to put 0 in (3,2) Now the goal of elimination is to get an uppper-triangular matrix U. I.e. if you were solving some system of equations in x, y, z, then because U is triangular, you could just read off the answer to z. Then plug that into the equation for row 2 to solve for y, then plug that into the equation for row 1 to solve for x. That's back-substitution. BUT, let's return to our operations. We have: E32 E31 E21 A = U (E32 E31 E21) A = U inverse(E32 E31 E21) (E32 E31 E21) A = inverse(E32 E31 E21) U I A = inverse(E32 E31 E21) U Now, it just so happens that the inverse of (E32 E31 E21) is lower-triangular. I.e. all entries above the diagonal are zero, so let's call it L. I A = L U A = L U LU-decomposition. Or "factorization", since we've factored A into two matrices: L, and U.