Elementary matrices and the LU factorisation
Every row operation is multiplication by a simple matrix. Recording these operations explains why row reduction works and leads to the LU factorisation used by solvers.
Elementary matrices
An elementary matrix is obtained by performing one elementary row operation on the identity. Multiplying A on the left by an elementary matrix E performs that same row operation on A. For example, the 3 x 3 matrix with a -2 in position (2, 1) and otherwise the identity subtracts twice row 1 from row 2.
Inverses of elementary matrices
Every elementary matrix is invertible, and its inverse is the elementary matrix of the reverse operation: the inverse of 'subtract 2 times row 1 from row 2' is 'add 2 times row 1 to row 2'; the inverse of a row swap is the same swap; the inverse of scaling a row by c is scaling by 1/c.
Row reduction as a product
Row reducing an invertible A to I means \(E_k \cdots E_2E_1A = I\). Therefore \(A^{-1} = E_k \cdots E_1\), and \(A = E_1^{-1}E_2^{-1}\cdots E_k^{-1}\): every invertible matrix is a product of elementary matrices. This is exactly why the \([A \mid I]\) method produces the inverse.
LU factorisation
If A can be reduced to an upper triangular U using only 'add a multiple of a higher row to a lower row' operations, then \(A = LU\), where L is lower triangular with 1s on the diagonal, holding the multipliers used in elimination, and U is the echelon form. Solving \(A\mathbf{x} = \mathbf{b}\) becomes two easy triangular solves: \(L\mathbf{y} = \mathbf{b}\) by forward substitution, then \(U\mathbf{x} = \mathbf{y}\) by back substitution.
Why LU is useful
Factorising A costs about n^3/3 multiplications once; each additional right-hand side then costs only about n^2 operations for the two triangular solves. Engineering simulations often solve the same system with many different b vectors, such as different loads on a structure, so LU saves enormous time over repeating elimination.
Pivoting and PA = LU
When a zero or very small pivot appears, rows must be swapped. Including the swaps gives PA = LU, where P is a permutation matrix, the identity with rows reordered. Standard numerical libraries such as LAPACK compute this pivoted LU factorisation, and it is what most software uses to solve general square systems.
Triangular matrices
Products and inverses of lower triangular matrices are lower triangular, and similarly for upper triangular ones. The determinant of a triangular matrix is the product of its diagonal entries, so after LU factorisation the determinant of A is easy to compute from U's diagonal, adjusted for any row swaps.
Worked example
Factor \(A = \begin{bmatrix} 2 & 1 \\ 6 & 8 \end{bmatrix}\). Subtract 3 times row 1 from row 2: \(U = \begin{bmatrix} 2 & 1 \\ 0 & 5 \end{bmatrix}\), with multiplier 3 stored in \(L = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}\). Check: \(LU = \begin{bmatrix} 2 & 1 \\ 6 & 3 + 5 \end{bmatrix} = A\). To solve with \(\mathbf{b} = (3, 14)\): \(y_1 = 3\), \(y_2 = 14 - 9 = 5\); then \(5x_2 = 5\) gives \(x_2 = 1\), and \(2x_1 + 1 = 3\) gives \(x_1 = 1\).
Key takeaways
Elementary matrices come from one row operation on I, and left-multiplying by one performs that operation. Each is invertible, with the reverse operation as its inverse. Row reducing A to I gives A^{-1} as a product of elementary matrices, and every invertible matrix is such a product. LU factorisation writes A = LU with unit lower triangular L storing multipliers and upper triangular U; solving becomes forward then back substitution. Factor once at about n^3/3 cost, then each right-hand side costs about n^2. Row swaps give PA = LU, as LAPACK computes. Triangular determinants are diagonal products.
Flashcard
Identity after one row operation
Check your understanding
Why do engineers factor A = LU once when solving many systems Ax = b with different b?
