2.3-exam1-2007-johnson¶
Quiz 1, 2007 (johnson) · Section 2.3: Matrix Computations and A = LU Source: exam1_1.pdf, pp. 175-177
Problem¶
2 (30 pts.) In class, we learned how to do "downwards" elimination to put a matrix \(A\) in upper-triangular (or echelon) form \(U\): not counting row swaps, we subtracted multiples of pivot rows from subsequent rows to put zeros below the pivots, corresponding to multiplying \(A\) by elimination matrices.
Instead, we could do elimination "leftwards" by subtracting multiples of pivot columns from leftwards columns, again to get an upper-triangular matrix \(U\). For example, let:
We could subtract twice the third column from the first column to eliminate the 2, so that we get zeros to the left of the "pivot" 1 at the lower right.
(i) Continue this "leftwards" elimination to obtain an upper-triangular matrix \(U\) from the \(A\) above, and write \(U\) in terms of \(A\) multiplied by a sequence of matrices corresponding to each leftwards-elimination step.
(ii) Suppose we followed this process for an arbitrary \(A\) (not necessarily square or invertible) to get an echelon matrix \(U\). Which of the column space and null space, if any, are the same between \(A\) and \(U\), and why?
(iii) Is the \(U\) that we get by leftwards elimination always the same as the \(U\) we get from ordinary downwards elimination? Why or why not?
Solution
(i) The "leftwards" elimination procedure is \[ A = \begin{bmatrix} 7 & 6 & 4 \\ 6 & 3 & 12 \\ 2 & 0 & 1 \end{bmatrix} \to \begin{bmatrix} -1 & 6 & 4 \\ -18 & 3 & 12 \\ 0 & 0 & 1 \end{bmatrix} \to \begin{bmatrix} 35 & 6 & 4 \\ 0 & 3 & 12 \\ 0 & 0 & 1 \end{bmatrix} = U, \] where the first step sent (col 1) \(\to\) (col 1) \(- 2\)(col 3) and the second step sent (col 1) \(\to\) (col 1) \(+ 6\)(col 2). Since these operations are linear combinations of the columns, they correspond to multiplying on the *right* by elimination matrices: \[ U = \begin{bmatrix} 35 & 6 & 4 \\ 0 & 3 & 12 \\ 0 & 0 & 1 \end{bmatrix} = A \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 6 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}. \] (One way to get these elimination matrices, as usual, is to do the corresponding operation on the \(3 \times 3\) identity matrix.) (ii) As above, \(U = AE\) (the elimination matrices multiply on the *right*). It follows that the column space of \(A\) is the same as the column space of \(U\), but the null spaces are different. Informally, by multiplying \(E\) on the *right*, we modify the *input* vectors of \(A\) (changing the null space), but the output vectors are still made of columns of \(A\) (preserving the column space). To be more careful, we need the fact that \(E\) is invertible (as elimination always is); otherwise, \(C(AE)\) could be a smaller subspace of \(C(A)\). More precisely, since \(U = AE\) above, where \(E\) are the elimination matrices, any \(x = Uy = A(Ey)\), so any \(x\) in \(C(U)\) is in \(C(A)\). Also vice-versa, since \(A = UE^{-1}\). So \(C(U) = C(A)\). However, if \(x\) is in the null space \(N(U)\) (i.e. \(Ux = 0 = AEx\)), this only means \(Ex\) is in \(N(A)\), not \(x\). So the null spaces are different in general (but have the same dimension). [Compare to the case of ordinary elimination, which preserves \(N(A)\) but changes \(C(A)\). Left elimination is equivalent to "upwards" elimination on \(A^T\) — this preserves the row space of \(A^T\), meaning that the column space of \(A\) is preserved etc.] (iii) The \(U\)'s are *not* the same in general (although of course there are special cases where they are the same, such as when \(A\) is upper-triangular to start with). There are several ways to see this. The simplest way is to give any counterexample: e.g., apply downwards elimination to \(A\) above and you will get a different result. For example, downward elimination never changes the upper-left corner (7), but the upper-left corner was changed (to 35) by leftwards elimination above. Abstractly, we know from class that downwards elimination always preserves the null space, whereas we just saw that upwards elimination does not. So, they cannot be the same. It is *not* sufficient to simply say that left-elimination does different sorts of operations than down-elimination — there are lots of problems where you can do a different sequence of operations and still get the same result. (For example, we could use left elimination to find \(A^{-1}\), and of course there is only one possible \(A^{-1}\) if it exists at all.)Keywords: elimination matrices, column space, nullspace, LU factorization