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

Let $U,V$ be $n\times n$ upper triangular matrices. For an entry below the diagonal, $i>j$, matrix multiplication givesIf $k<i$, then $U_{ik}=0$. If $k\ge i$, then $k>j$, so $V_{kj}=0$. Every summand is zero, givingThus $UV$ is an upper triangular matrix. Equivalently, a potentially nonzero summand would require $i\le k\le j$, impossible below the diagonal.

Suppose an invertible matrix has two LU factorizations, $A=L_1{U}_1=L_2{U}_2$, with $L_1,L_2$ unit lower triangular matrices and $U_1,U_2$ upper triangular matrices. All four factors are invertible matrices, since their square products are invertible. Multiplication by the appropriate inverse matrices givesBy the supplied closure properties, the left side is a unit lower triangular matrix and the right side is an upper triangular matrix. A matrix of both types is diagonal; its diagonal entries are all one. Thus both sides are the identity matrix, whenceQualification of the printed wording: this establishes uniqueness if the specified LU factorization exists. Invertibility alone does not guarantee an unpivoted LU factorization. For example $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ is invertible, but in a product $\left(\begin{array}{cc}1& 0\\ \ell & 1\end{array}\right)\left(\begin{array}{cc}{u}_{11}& u_{12}\\ 0& u_{22}\end{array}\right)$, the zero top-left entry forces $u_{11}=0$, making the bottom-left entry $\ell u_{11}=0$ as well, contrary to the required value one. A permutation matrix is needed in general, as in PLU factorization.

Use Gaussian elimination without row exchanges. First apply $R_2\leftarrow R_2-3R_1$ and $R_3\leftarrow R_3-2R_1$; then apply $R_3\leftarrow R_3-R_2$:The elimination multipliers are $m_{21}=3$, $m_{31}=2$ and $m_{32}=1$. Put them below the diagonal of a unit lower triangular matrix:To see why these multipliers reconstruct the rows, row 2 of $LU$ is three times row 1 of $U$ plus row 2 of $U$, giving $(3,8,14)$. Row 3 of $LU$ is twice row 1 plus row 2 plus row 3 of $U$, giving $(2,6,13)$. This directly verifies the LU factorization.

The elementary row operations used above add multiples of other rows, so preserve the determinant. The determinant of an upper triangular matrix is the product of its diagonal entries. HenceEquivalently, $\det L=1$ and multiplicativity of the determinant gives $\det A=\det L\det U=6$.