Exercises — LU decomposition (numerical)

• $P$: entries above the diagonal are $0$ → lower triangular. Diagonal is $(1,1)$ → yes, a valid Doolittle $L$.
• $Q$: entries below the diagonal are $0$ → upper triangular. (A $U$, not an $L$.)
• $R$: below-diagonal entry $1\ne 0$, above-diagonal entry $0$ → lower triangular, but diagonal is $(2,2)\ne (1,1)$ → not a Doolittle $L$ (it would be a Crout-style $L$, see Crout Decomposition).
• $S$: has nonzero entries both above and below → neither.

The determinant of a triangular matrix is the product of its diagonal (see Determinants). So $\det L=1\cdot 1\cdot 1=1,\det U=5\cdot 3\cdot (-2)=-30.$ In Doolittle form $\det L=1$ always, which is exactly why $\det A=\det U=\prod u_{ii}$.

Row 1 of $U$ (top row of $L$ is $(1,0)$): $u_{11}=4$, $u_{12}=3$. Column 1 of $L$: ${\ell }_{21}=a_{21}/u_{11}=8/4=2$. Row 2 of $U$: $u_{22}=a_{22}-{\ell }_{21}{u}_{12}=7-2\cdot 3=1$. $L=\left(\begin{array}{cc}1& 0\\ 2& 1\end{array}\right),U=\left(\begin{array}{cc}4& 3\\ 0& 1\end{array}\right).$ Check: $LU=\left(\begin{array}{cc}4& 3\\ 8& 7\end{array}\right)=A.$ ✓

Forward solve $L\mathbf{y}=\mathbf{b}$ (top-down, one unknown per row): $y_1=10$; $2y_1+y_2=18\Rightarrow y_2=18-20=-2$. Back solve $U\mathbf{x}=\mathbf{y}$ (bottom-up): $1\cdot x_2=-2\Rightarrow x_2=-2$; $4x_1+3x_2=10\Rightarrow 4x_1=10-3(-2)=16\Rightarrow x_1=4$. $\boxed{\mathbf{x}=(4,-2{)}^{\top }}$ Sanity: $A\mathbf{x}=(4\cdot 4+3(-2),8\cdot 4+7(-2))=(10,18)=\mathbf{b}.$ ✓

Row 1 of $U$: $u_{11}=2,u_{12}=1,u_{13}=1$. Column 1 of $L$: ${\ell }_{21}=4/2=2$, ${\ell }_{31}=8/2=4$. Row 2 of $U$: $u_{22}=3-2\cdot 1=1$, $u_{23}=3-2\cdot 1=1$. Column 2 of $L$: ${\ell }_{32}=\frac{a_{32}-{\ell }_{31}{u}_{12}}{u_{22}}=\frac{7-4\cdot 1}{1}=3$. Row 3 of $U$: $u_{33}=a_{33}-{\ell }_{31}{u}_{13}-{\ell }_{32}{u}_{23}=9-4\cdot 1-3\cdot 1=2$. $L=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 4& 3& 1\end{array}\right),U=\left(\begin{array}{ccc}2& 1& 1\\ 0& 1& 1\\ 0& 0& 2\end{array}\right).$ Check: $LU=A$ (multiply to confirm). ✓

Failure: $u_{11}=a_{11}=0$, so ${\ell }_{21}=a_{21}/u_{11}=3/0$ — division by zero. Plain LU dies even though $A$ is perfectly invertible; the problem is purely the zero pivot, not singularity. Repair: swap the rows so the larger-magnitude entry ($3>0$) sits on the pivot. The swap is the permutation matrix (see Permutation Matrices) $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),PA=\left(\begin{array}{cc}3& 1\\ 0& 2\end{array}\right).$ Now Doolittle on $PA$: $u_{11}=3,u_{12}=1$; ${\ell }_{21}=0/3=0$; $u_{22}=2-0\cdot 1=2$. $L=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),U=\left(\begin{array}{cc}3& 1\\ 0& 2\end{array}\right),PA=LU.$ To solve $A\mathbf{x}=\mathbf{b}$ you'd solve $L\mathbf{y}=P\mathbf{b}$ then $U\mathbf{x}=\mathbf{y}$.

$|a_{21}|=3>|a_{11}|=1$, so swap rows: $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, $PA=\left(\begin{array}{cc}3& 4\\ 1& 2\end{array}\right)$. $u_{11}=3,u_{12}=4$; ${\ell }_{21}=1/3$; $u_{22}=2-\frac{1}{3}\cdot 4=\frac{2}{3}$. $L=\left(\begin{array}{cc}1& 0\\ \frac{1}{3}& 1\end{array}\right),U=\left(\begin{array}{cc}3& 4\\ 0& \frac{2}{3}\end{array}\right).$ Multiplier $|{\ell }_{21}|=\frac{1}{3}\le 1$. ✓ Without pivoting we'd have had ${\ell }_{21}=3/1=3>1$ — pivoting made the multiplier small, which is exactly what keeps rounding errors bounded (see Condition Number and Numerical Stability).

$A=LU$ (no swaps used there), so $\det A=\det L\cdot \det U$. In Doolittle form $\det L=1$ (product of ones). Thus $\det A=\det U={\prod }_i{u}_{ii}$. If $k$ row swaps were used, each swap flips the sign once, giving the $(-1{)}^k$ factor. For Exercise 2.3: $u_{11}{u}_{22}{u}_{33}=2\cdot 1\cdot 2=4$, and no swaps, so $\det A=4$.

This is the whole point of LU: factor once, solve many (see Gaussian Elimination).

RHS 1. Forward $L\mathbf{y}={\mathbf{b}}^{(1)}$: $y_1=5$; $2\cdot 5+y_2=13\Rightarrow y_2=3$; $4\cdot 5+3\cdot 3+y_3=29\Rightarrow y_3=29-20-9=0$. Back $U\mathbf{x}=\mathbf{y}$: $2x_3=0\Rightarrow x_3=0$; $x_2+x_3=3\Rightarrow x_2=3$; $2x_1+x_2+x_3=5\Rightarrow 2x_1=5-3=2\Rightarrow x_1=1$. ${\mathbf{x}}^{(1)}=(1,3,0{)}^{\top }.$

RHS 2. Forward: $y_1=2$; $2\cdot 2+y_2=6\Rightarrow y_2=2$; $4\cdot 2+3\cdot 2+y_3=16\Rightarrow y_3=16-8-6=2$. Back: $2x_3=2\Rightarrow x_3=1$; $x_2+x_3=2\Rightarrow x_2=1$; $2x_1+x_2+x_3=2\Rightarrow 2x_1=2-2=0\Rightarrow x_1=0$. ${\mathbf{x}}^{(2)}=(0,1,1{)}^{\top }.$ Notice we reused $L,U$ for both — no elimination redone.