2.3-exam1-2009¶
Quiz 1, 2009 · Section 2.3: Matrix Computations and A = LU Source: exam1_1.pdf, pp. 205-207
Problem¶
Problem 1: Your classmate, Nyarlathotep, performed the usual elimination steps to convert \(A\) to echelon form \(U\), obtaining:
(a) Find a set of vectors spanning the nullspace \(N(A)\).
(b) If \(U\vec{y} = \begin{bmatrix} 9 \\ -12 \\ 0 \end{bmatrix}\), find the complete solution \(\vec{y}\) (i.e. describe all possible solutions \(\vec{y}\)).
(c) Nyarla gave you a matrix
and told you that \(A = LU\). Describe the complete sequence of elimination steps that Nyarla performed, assuming that she did elimination in the usual way starting with the first column and eliminating downwards. That is, Nyarla first subtracted ___ times the first row from the second row, then subtracted ___ times the first row from the third row, then subtracted ___. (Be careful about signs: adding a multiple of a row is the same as subtracting a negative multiple of that row.)
(d) If \(A\vec{x} = \begin{bmatrix} 0 \\ 2 \\ 6 \end{bmatrix}\), then \(U\vec{x} = \_\_\_\).
Solution
(a) The pivots are in the first two columns of \(U\), so \(x_3\) and \(x_4\) are the free variables. Setting \(x_3 = 1\), \(x_4 = 0\), we get (from the second row of \(U\vec{x} = 0\)) \(x_2 = -1\) and (from the first row) \(x_1 = 1 - 4x_2 = 5\); setting \(x_3 = 0\), \(x_4 = 1\), we get (from the second row) \(x_2 = 3\) and (from the first row) \(x_1 = -3 - 4x_2 = -15\). Hence, \(N(A)\) is spanned by two special solutions as follows: \[ N(A) = x_3 \begin{bmatrix} 5 \\ -1 \\ 1 \\ 0 \end{bmatrix} + x_4 \begin{bmatrix} -15 \\ 3 \\ 0 \\ 1 \end{bmatrix} \quad \text{for all } x_3, x_4 \in \mathbb{R}. \] (b) First, we need to find a particular solution. For this, we may set the free variables to \(y_3 = y_4 = 0\). Thus (from the second row of \(U\vec{y} = b\)) \(y_2 = -6\) and (from the first row) \(y_1 = 9 - 4y_2 = 33\). Hence, all the solutions to the equation are given by the sum of the particular solution and any vector in the nullspace (all linear combinations of the special solutions): \[ \vec{y} = y_3 \begin{bmatrix} 5 \\ -1 \\ 1 \\ 0 \end{bmatrix} + y_4 \begin{bmatrix} -15 \\ 3 \\ 0 \\ 1 \end{bmatrix} + \begin{bmatrix} 33 \\ -6 \\ 0 \\ 0 \end{bmatrix} \quad \text{for all } y_3, y_4 \in \mathbb{R}. \] (c) Nyarla first subtracted 2 times the first row from the second row, then subtracted -1 times the first row from the third row, then subtracted 3 times the second row from the third row. There are a couple of ways to solve this problem. The easiest is to remember that the \(L\) matrix, the product of the inverses of the elimination matrices, is simply composed of the multipliers for each of the elimination steps below each column. Under the first column of \(L\) we have 2 and -1, and these are thus the multiples of the first row that get subtracted from rows 2 and 3. Under the second column of \(L\) we have a 3, and this is the multiple of the second row that gets subtracted from the third row. The other way to solve it is to just multiply \(L\) by \(U\) to get \(A = LU\), and re-do the elimination process. Obviously, this is a bit more work, but is not too bad. (d) Applying the same elimination operations in (c) to \(A\vec{x}\) should give \(U\vec{x}\). So, we have \[ \begin{bmatrix} 0 \\ 2 \\ 6 \end{bmatrix} \leadsto \begin{bmatrix} 0 \\ 2 \\ 6 \end{bmatrix} \leadsto \begin{bmatrix} 0 \\ 2 \\ 0 \end{bmatrix}. \] Alternatively, we can just solve \(U\vec{x}\) from \(A\vec{x}\) as follows. Let \(\vec{v} = U\vec{x}\). Then \[ L\vec{v} = L(U\vec{x}) = A\vec{x} = \begin{bmatrix} 0 \\ 2 \\ 6 \end{bmatrix}. \] Thus, we can solve from the top as follows: \(v_1 = 0\), \(v_2 = 2 - 2v_1 = 2\), and \(v_3 = 6 - 3v_2 + v_1 = 0\). Hence, \(U\vec{x} = \vec{v} = \begin{bmatrix} 0 \\ 2 \\ 0 \end{bmatrix}\). REMARK: Some students realized that \(U\vec{x} = L^{-1}(A\vec{x})\). But several of these students did not get \(L^{-1}\) correctly. Be careful that the inverse of \(\begin{bmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{bmatrix}\) is *not* \(\begin{bmatrix} 1 & 0 & 0 \\ -l_{21} & 1 & 0 \\ -l_{31} & -l_{32} & 1 \end{bmatrix}\); the lower left entry should be \(l_{21}l_{32} - l_{31}\). (Only for elimination matrices, which have nonzero entries below only a single diagonal, can you always invert just by flipping signs.) More generally, if you find yourself inverting a matrix, you should realize that there is probably an easier way to do it: to compute \(\vec{v} = L^{-1}(A\vec{x})\), it is easier to solve \(L\vec{v} = A\vec{x}\) for \(\vec{v}\) by elimination (especially since \(L\) is triangular, so you can just do forward substitution as above).Keywords: LU factorization, elimination matrices, nullspace, complete solution