Skip to content

2.2-exam1-2003-dejong

Exam 1, 2003 (de-jong) · Section 2.2: Elimination Matrices and Inverse Matrices Source: exam1_1.pdf, pp. 92, 97

Problem

3 (35 pts.) The elimination algorithm explained in the course (with "row swapping after Gaussian elimination") was applied to the matrix \(A\). Suppose it yields the following equality:

\[ \begin{bmatrix} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 11 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 10 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} A = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 1 & 0 & 3 \\ 0 & 0 & 0 & 1 & 4 \end{bmatrix} \]

(a) Which row operations do the four elimination matrices in the product correspond to? Please write them down in words in the order in which they were performed on \(A\). Why is the upper left hand corner of \(A\) zero? (This is the (1,1) entry of \(A\).)

(b) The equation implies that \(A\) factors as \(A = LPUR\). Here \(R\) is the matrix on the right hand side of the = sign. The matrices \(U\), \(P\), and \(L\) are invertible \(4 \times 4\) matrices. The matrix \(U\) is upper triangular. The matrix \(P\) is a permutation matrix. And \(L\) is lower triangular. Find \(U\), \(P\), and \(L\), and explain how you got them.

Solution (a) The row operations, in the order in which they were performed: * add 10 times row 2 to row 3; * add 11 times row 3 to row 4; * swap rows 1 and 2; * add 4 times row 4 to row 1. The (1,1) entry of \(A\) (the upper left corner) is zero, since otherwise we would never have needed to swap rows 1 and 2. (b) The matrix \(U\) corresponds to the upward elimination. So we get \[ U = \begin{bmatrix} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 & 0 & -4 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}. \] The matrix \(P\) corresponds to the permutation of the first two rows. So we have \[ P = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}^{T} = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}. \] The matrix \(L\) corresponds to the first two elimination steps. So we have \[ L = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 10 & 1 & 0 \\ 0 & 110 & 11 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -10 & 1 & 0 \\ 0 & 0 & -11 & 1 \end{bmatrix}. \]

Keywords: elimination matrices, permutation matrix, LU factorization, row operations