2.5 Exercises

20 points · 4 extra credit

Matrix Factorizations

1. 1. (3 pts) Find an LU factorization $A = LU$ (with $L$ unit lower triangular and $U$ upper triangular) for

   $A = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{bmatrix},$

   recording the row-reduction multipliers in $L$.

   #

2. 2. (3 pts) Using the factorization from Problem 1, solve $A\mathbf{x} = \mathbf{b}$ for $\mathbf{b} = \begin{bmatrix} 1 \\ 1 \\ 3 \end{bmatrix}$ by forward substitution ($L\mathbf{y} = \mathbf{b}$) followed by back substitution ($U\mathbf{x} = \mathbf{y}$).

   #

3. 3. (3 pts) Find an LU factorization of

   $A = \begin{bmatrix} 3 & -1 & 1 \\ 9 & -1 & 4 \\ -6 & 4 & 1 \end{bmatrix}.$

   #

4. 4. (2 pts) Suppose you must solve $A\mathbf{x} = \mathbf{b}$ for the same $n\times n$ matrix $A$ but many different right-hand sides $\mathbf{b}$. Explain why computing an LU factorization once, then reusing it, is more efficient than row reducing $[\,A\mid\mathbf{b}\,]$ from scratch each time.

   #

5. 5. (3 pts) State whether each is true or false, and justify.

   (a) Every square matrix has an LU factorization.

   (b) In an LU factorization with $L$ unit lower triangular, where each elimination step has the form $R_i \to R_i - m\,R_j$, the entries of $L$ below the diagonal are the negatives of the multipliers $m$.

   (c) If $A = LU$ with $U$ having no zero on its diagonal, then $A$ is invertible.

   #

6. 6. (3 pts) Explain why, when $A$ can be reduced to echelon form using only row-replacement operations that add a multiple of a higher row to a lower row (no interchanges, no scaling), the resulting factorization $A = LU$ has $L$ unit lower triangular.

   #

7. 7. (3 pts) The matrix $A = \begin{bmatrix} 0 & 1 \\ 2 & 3 \end{bmatrix}$ has no LU factorization with $L$ unit lower triangular. Explain why, and give a permutation matrix $P$ so that $PA$ does have such a factorization; exhibit $PA = LU$.

   #

8. 8. (4 pts ••) Prove that an LU factorization is unique in the following sense: if $A = L_1 U_1 = L_2 U_2$, where $L_1, L_2$ are unit lower triangular and $U_1, U_2$ are invertible upper triangular, then $L_1 = L_2$ and $U_1 = U_2$.

   #