Skip to content

2.3-exam1-1997-strang

Quiz 1, 1997 (strang) · Section 2.3: Matrix Computations and A = LU Source: exam1_1.pdf, pp. 8-9

Problem

2. (27 points = 3 times 9) Suppose \(A\) is a square invertible \(n\) by \(n\) matrix.

(a) What is its column space and what is its nullspace?

(b) Suppose \(A\) can be factored into \(A = LU\):

\[ A = \begin{bmatrix} 1 & 0 & 0 \\ 5 & 1 & 0 \\ 7 & 3 & 1 \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix} \]

Describe the first elimination step in reducing \(A\) to \(U\). How do you know that \(U\) is also invertible?

(c) Find a specific 3 by 3 invertible matrix \(A\) that can not be factored into this \(LU\) form. What factorization is still possible for your example? (You don't have to find the factors.) How do you know your \(A\) is invertible?

Solution (a) The column space is all of \(R^n\) (the \(n\) independent columns span \(R^n\)). The nullspace contains only the zero vector: \(N(A) = \{0\}\). (b) The first elimination step subtracts 5 times row 1 from row 2; the multiplier 5 is recorded in the \((2,1)\) entry of \(L\). The matrix \(U\) is invertible because \(U = L^{-1}A\) is a product of invertible matrices: \(A\) is given invertible, and \(L\), being lower triangular with 1's on the diagonal, has determinant 1. Equivalently, the pivots \(u_{11}, u_{22}, u_{33}\) are all nonzero. (c) Any matrix that needs a row exchange, for example the permutation matrix \[ A = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \] cannot be factored as \(A = LU\) (its first pivot is 0). The factorization that is still possible is \(PA = LU\) with a permutation matrix \(P\), i.e. \(A = P^T LU\). This \(A\) is invertible because it is a permutation matrix: its columns are the standard basis in another order (independent), so its determinant is \(\pm 1 \neq 0\).

Keywords: invertible matrix, LU factorization, elimination, permutation matrix