Past exam of the options II course of the University of Oxford / 2005 / P / 3

The elementary elimination step replaces row $i$ by row $i$ minus a multiple $m_{ij}$ of an earlier pivot row $j$. With coordinate vectors $e_i$, its premultiplication matrix isand its inverse is $I+m_{ij}{e}_i{e}_j^T$, since $(e_i{e}_j^T{)}^2=0$. Choose $m_{ij}$ as the current entry below the pivot divided by the current pivot. Required pivots are assumed nonzero, consistently with elimination without row interchanges.

For dimension 4, first eliminate positions $(2,1),(3,1),(4,1)$, then $(3,2),(4,2)$, then $(4,3)$. ThusThe rightmost operation acts first, and every multiplier is computed from the matrix at its own stage. For general $n$, the numbers of eliminations in successive columns are $n-1,n-2,\dots ,1$, totaling $n(n-1)/2$; a zero multiplier simply gives an identity operation.

The product $E$ is unit lower triangular and $U=EA$ is upper triangular. Its inverse $L=E^{-1}$ is unit lower triangular, soThe stored multiplier in position $(i,j)$ is the corresponding subdiagonal entry of $L$, as follows by reversing the pivot-row subtractions column by column.

If $A$ is upper Hessenberg, only the first subdiagonal can be nonzero below the diagonal. At stage $j$ only position $(j+1,j)$ needs elimination. Subtracting row $j$ cannot create lower entries further down because its entries before its pivot are already zero. Hence only $n-1$ operations are needed. The inverse factors occur in increasing column order, and their cross products vanish, givingwhich is lower bidiagonal; $U$ is upper triangular, possibly dense above its diagonal.

If the Hessenberg matrix is also symmetric, it is tridiagonal. At each elimination step the pivot row has no entries past its immediate superdiagonal, so the updated matrix retains that upper bandwidth. Thus $L$ is lower bidiagonal and $U$ is upper bidiagonal, with at most two nonzero entries in each row, as required.