28.1 Solving systems of linear equations

28.1-1

Solve the equation

$$ \begin{pmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ -6 & 5 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 3 \\ 14 \\ -7 \end{pmatrix} $$

by using forward substitution.

$$ \begin{pmatrix} 3 \\ 14 - 4 \cdot 3 \\ -7 - 5 \cdot (14 - 4 \cdot 3) - (-6) \cdot 3 \end{pmatrix} = \begin{pmatrix} 3 \\ 2 \\ 1 \end{pmatrix} . $$

28.1-2

Find an $\text{LU}$ decomposition of the matrix

$$ \begin{pmatrix} 4 & -5 & 6 \\ 8 & -6 & 7 \\ 12 & -7 & 12 \end{pmatrix} . $$

$$ \begin{pmatrix} 4 & -5 & 6 \\ 8 & -6 & 7 \\ 12 & -7 & 12 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 2 & 1 \end{pmatrix} \begin{pmatrix} 4 & -5 & 6 \\ 0 & 4 & -5 \\ 0 & 0 & 4 \end{pmatrix} . $$

28.1-3

Solve the equation

$$ \begin{pmatrix} 1 & 5 & 4 \\ 2 & 0 & 3 \\ 5 & 8 & 2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 12 \\ 9 \\ 5 \end{pmatrix} $$

by using forward substitution.

We have

$$ \begin{aligned} A & = \begin{pmatrix} 1 & 5 & 4 \\ 2 & 0 & 3 \\ 5 & 8 & 2 \end{pmatrix} , \\ b & = \begin{pmatrix} 12 \\ 9 \\ 5 \end{pmatrix} , \end{aligned} $$

and we with to solve for the unknown $x$. The $\text{LUP}$ decomposition is

$$ \begin{aligned} L & = \begin{pmatrix} 1 & 0 & 0 \\ 0.2 & 1 & 0 \\ 0.4 & -\frac{3.2}{3.4} & 1 \end{pmatrix} , \\ U & = \begin{pmatrix} 5 & 8 & 2 \\ 0 & 3.4 & 3.6 \\ 0 & 0 & 2.2 + \frac{11.52}{3.4} \end{pmatrix} , \\ P & = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} . \end{aligned} $$

Using forward substitution, we solve $Ly = Pb$ for $y$:

$$ \begin{pmatrix} 1 & 0 & 0 \\ 0.2 & 1 & 0 \\ 0.4 & -\frac{3.2}{3.4} & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 12 \\ 9 \end{pmatrix} , $$

obtaining

$$ y = \begin{pmatrix} 5 \\ 11 \\ 7 + \frac{35.2}{3.4} \end{pmatrix} $$

by computing first $y_1$, then $y_2$, and finally $y_3$. Using back substitution, we solve $Ux = y$ for $x$:

$$ \begin{pmatrix} 5 & 8 & 2 \\ 0 & 3.4 & 3.6 \\ 0 & 0 & 2.2 + \frac{11.52}{3.4} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 11 \\ 7 + \frac{35.2}{3.4} \end{pmatrix} , $$

thereby obtaining the desired answer

$$ x = \begin{pmatrix} -\frac{3}{19} \\ -\frac{1}{19} \\ \frac{49}{19} \end{pmatrix} $$

by computing first $x_3$, then $x_2$, and finally $x_1$.

28.1-4

Describe the $\text{LUP}$ decomposition of a diagonal matrix.

The $\text{LUP}$ decomposition of a diagonal matrix $D$ is $D = IDI$ where $I$ is the identity matrix.

28.1-5

Describe the $\text{LUP}$ decomposition of a permutation matrix $A$, and prove that it is unique.

(Omit!)

28.1-6

Show that for all $n \ge 1$, there exists a singular $n \times n$ matrix that has an $\text{LU}$ decomposition.

The zero matrix always has an $\text{LU}$ decomposition by taking $L$ to be any unit lower-triangular matrix and $U$ to be the zero matrix, which is upper triangular.

28.1-7

In $\text{LU-DECOMPOSITION}$, is it necessary to perform the outermost for loop iteration when $k = n$? How about in $\text{LUP-DECOMPOSITION}$?

For $\text{LU-DECOMPOSITION}$, it is indeed necessary. If we didn't run the line 6 of the outermost for loop, $u_{nn}$ would be left its initial value of $0$ instead of being set equal to $a_{nn}$. This can clearly produce incorrect results, because the $\text{LU-DECOMPOSITION}$ of any non-singular matrix must have both $L$ and $U$ having positive determinant. However, if $u_{nn} = 0$, the determinant of $U$ will be $0$ by problem D.2-2.

For $\text{LUP-DECOMPOSITION}$, the iteration of the outermost for loop that occurs with $k = n$ will not change the final answer. Since $\pi$ would have to be a permutation on a single element, it cannot be non-trivial. and the for loop on line 16 will not run at all.