Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Digital systems, linear algebra, introduction to formal proof / 6

An elementary matrix acts on rows by multiplication on the left. Apply the desired elementary row operation to the identity matrix to construct it. In the order requested, the three elementary matrices and their inverse matrices areThe inverse operations halve row 1, add twice row 1 to row 3, and interchange rows 2 and 3 again, respectively.

Use $R_2\leftarrow R_2+2R_1$ and $R_3\leftarrow R_3-3R_1$, followed by $R_3\leftarrow R_3+R_2$. These elementary row operations giveThe elimination multipliers are $m_{21}=-2$, $m_{31}=3$, $m_{32}=-1$. Record them in the unit lower triangular matrix $L$:To see the elementary matrix relation directly, let $F_{21}=I+2e_{21}$, $F_{31}=I-3e_{31}$ and $F_{32}=I+e_{32}$, where $e_{ij}$ has a single 1 in position $(i,j)$. Then $U=F_{32}{F}_{31}{F}_{21}A$, and reversing and inverting these operations gives $L=F_{21}^{-1}{F}_{31}^{-1}{F}_{32}^{-1}$. Direct matrix multiplication also verifies the stated LU decomposition.

Solve two triangular linear systems, rather than forming an inverse matrix:For this LU decomposition, forward substitution gives $y_1=b_1$, $y_2=b_2+2y_1$ and $y_3=b_3-3y_1+y_2$. Then back substitution givesAll diagonal entries used as divisors are nonzero. The same LU decomposition can be reused for many right-hand vectors, with only these two triangular solves repeated.

A triangular matrix has determinant equal to the product of its diagonal entries. Since $L$ is a unit lower triangular matrix, $\det L=1$. ThusEquivalently, the elimination used only row additions, which leave the determinant unchanged; there were no row swaps or row scalings to account for.