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

Left multiplication by an elementary matrix adds a multiple of row one to its designated target row. The first-column entries below the pivot are $1,2,-1$, so $a=-1$, $b=-2$, $c=1$. The corresponding row operations are $R_2\leftarrow R_2-R_1$, $R_3\leftarrow R_3-2R_1$, and $R_4\leftarrow R_4+R_1$. Since none changes row one, their sequential application gives the required three eliminated first-column entries and the displayed remaining entries.

The second pivot is two. Row three has second entry two, so subtract row two; row four has second entry minus two, so add row two. Therefore $d=-1$, $e=1$. Their trailing row pairs become $(0,4)$ and $(3,5)$, respectively; the zero in the third pivot position is why a later row interchange is needed.

Let $e_{ij}$ denote the matrix unit with one at position $(i,j)$ and zero elsewhere. The five inverses areThus each is the identity matrix with only the indicated off-diagonal matrix entry altered. These inverses reverse the corresponding row additions; no row scaling or permutation is involved.

The permutation matrix isRows three and four of the identity matrix have been interchanged, so left multiplication interchanges those rows of any matrix.

Left multiplication by $E$ interchanges rows three and four; applying it twice restores every row. Equivalently, it sends the standard basis vectors $e_3,e_4$ to each other and fixes $e_1,e_2$, so its square fixes a basis. $E^2=I$.

Since $E^2=I$, the same matrix is both a left and a right inverse. $E^{-1}=E$.

The $j$th column of $AE$ is $A(E{e}_j)$. The permutation matrix fixes $e_1,e_2$ and interchanges $e_3,e_4$, so these columns are $A{e}_1,A{e}_2,A{e}_4,A{e}_3$. They are exactly the first, second, fourth and third columns of $A$. Thus right multiplication by $E$ interchanges columns three and four, leaving the others unchanged.

The first left multiplication swaps rows three and four. The final right multiplication swaps columns three and four, restoring the two diagonal ones to their diagonal positions while exchanging the earlier entries of the two rows. ThereforeThe two specified zeros at positions $(3,4)$ and $(4,3)$ are important. Conjugation by this permutation matrix preserves this restricted lower triangular pattern; it would not preserve lower triangularity for an arbitrary matrix with a nonzero $(4,3)$ entry.

Write $U=E{E}_5{E}_4{E}_3{E}_2{E}_{1}M$ and put $F_i=E{E}_{i}E$. Inserting $E^2=I$ between adjacent elimination matrices givesEach $E_i^{-1}$ has the restricted lower triangular pattern in part (b)(v). Also $F_i^{-1}=E{E}_i^{-1}E$, as direct multiplication verifies. Hence every $F_i^{-1}$ is lower triangular. Their product is lower triangular by the allowed closure property, proving the required Pivoted LU decomposition with $L=F_1^{-1}\cdots F_5^{-1}$.

Explicitly,The multipliers in rows three and four of $L$ are permuted along with the rows of $M$; simply keeping the unpermuted elimination multipliers would give the wrong product. This is the mechanism in conjugating elimination matrices across a row permutation.