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.<p>The result of carrying out the elimination steps is a triangular matrix with all zeros below the main diagonal. Call it U, for "upper".<p>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:<p>[ 1 0 0]<p>[-2 1 0]<p>[ 0 0 1]<p>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.<p>Example:<p>Using Strang's terminology, let's call the matrix that "eliminates (i.e. sets to 0) the (i,j) entry" Eij<p>So, to solve a 3x3 system A x = b, you want to do elimination as: (E32 E31 E21) A = U<p>I.e.<p>1) Take A and subtract some multiple of row 2 from row 1, to put 0 in (2,1)<p>2) Take the result and subtract some multiple of row 3 from row 1 to put 0 in (3,1)<p>3) Take the result and subtract some multiple of row 3 from row 2 to put 0 in (3,2)<p>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.<p>BUT, let's return to our operations. We have:<p>E32 E31 E21 A = U<p>(E32 E31 E21) A = U<p>inverse(E32 E31 E21) (E32 E31 E21) A = inverse(E32 E31 E21) U<p>I A = inverse(E32 E31 E21) U<p>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.<p>I A = L U<p>A = L U<p>LU-decomposition. Or "factorization", since we've factored A into two matrices: L, and U.