Proof. Nonsingularity. Suppose \(A\mathbf x = \mathbf 0\) with \(\mathbf x\neq \mathbf 0\), and let \(k\) be an index with \(|x_k| = \max _j|x_j|>0\). The \(k\)th equation gives \(a_{kk}x_k = -\sum _{j\neq k}a_{kj}x_j\), so \[|a_{kk}|\,|x_k|\leq \sum _{j\neq k}|a_{kj}|\,|x_j|\leq |x_k|\sum _{j\neq k}|a_{kj}| ,\] and \(|a_{kk}|\leq \sum _{j\neq k}|a_{kj}|\), contradicting strict diagonal dominance.

Elimination. The first pivot \(a_{11}\) is non-zero. After the first stage the remaining \((n-1)\times (n-1)\) matrix has entries \(a'_{ij} = a_{ij}-\frac {a_{i1}}{a_{11}}a_{1j}\), \(i,j\geq 2\). For \(i\geq 2\), \begin {align*} \sum _{j\geq 2,\,j\neq i}|a'_{ij}| &\leq \sum _{j\geq 2,\,j\neq i}|a_{ij}|+\frac {|a_{i1}|}{|a_{11}|}\sum _{j\geq 2,\,j\neq i}|a_{1j}|\\ &<\bigl (|a_{ii}|-|a_{i1}|\bigr )+\frac {|a_{i1}|}{|a_{11}|}\bigl (|a_{11}|-|a_{1i}|\bigr )\\ &= |a_{ii}|-\frac {|a_{i1}|\,|a_{1i}|}{|a_{11}|}\leq |a'_{ii}| . \end {align*}

So the reduced matrix is again strictly diagonally dominant, its first pivot is non-zero, and by induction every pivot is non-zero. For the stability claim, a similar estimate shows that the entries of the reduced matrices never exceed twice the largest entry of \(A\) in absolute value (a result due to Wilkinson); bounded growth of the entries is exactly what keeps round-off under control. Note that the multipliers themselves need not be smaller than \(1\) (Problem 4.6.5). □

Proof. If \(A = LL^T\) with \(L\) nonsingular, then for \(\mathbf x\neq \mathbf 0\), \(\mathbf x^TA\mathbf x = (L^T\mathbf x)^T(L^T\mathbf x) = \|L^T\mathbf x\|^2>0\).

Conversely, let \(A\) be positive definite; we use induction on \(n\), the case \(n = 1\) being \(a_{11} = \mathbf e_1^TA\mathbf e_1>0\), \(L = (\sqrt {a_{11}})\). Write \[A = \begin {pmatrix}a_{11}&\mathbf w^T\\ \mathbf w&B\end {pmatrix},\qquad a_{11}>0 .\] For \(\mathbf y\neq \mathbf 0\) in \(\mathbb R^{n-1}\), put \(\mathbf x = \left (-\frac {\mathbf w^T\mathbf y}{a_{11}},\,\mathbf y\right )\); a direct calculation gives \[0<\mathbf x^TA\mathbf x = \mathbf y^T\left (B-\frac {\mathbf w\mathbf w^T}{a_{11}}\right )\mathbf y ,\] so \(B-\frac {\mathbf w\mathbf w^T}{a_{11}}\) is positive definite, and by induction equals \(L_1L_1^T\). Then \[A = \begin {pmatrix}\sqrt {a_{11}}&\mathbf 0^T\\ \mathbf w/\sqrt {a_{11}}&L_1\end {pmatrix}\begin {pmatrix}\sqrt {a_{11}}&\mathbf w^T/\sqrt {a_{11}}\\ \mathbf 0&L_1^T\end {pmatrix},\] as is checked by multiplying out. Uniqueness follows because the formulas below determine each entry of \(L\) in turn. □

Solution. \(l_{11} = \sqrt 4 = 2\), \(l_{21} = \frac {-1}{2} = -0.5\), \(l_{31} = \frac 12 = 0.5\); \(l_{22} = \sqrt {4.25-0.25} = 2\), \(l_{32} = \frac {2.75-(0.5)(-0.5)}{2} = 1.5\); \(l_{33} = \sqrt {3.5-0.25-2.25} = 1\). So \[L = \begin {pmatrix}2&0&0\\-0.5&2&0\\0.5&1.5&1\end {pmatrix}.\] Forward substitution in \(L\mathbf y = \mathbf b\): \(y_1 = 2\), \(y_2 = \frac {6+0.5(2)}{2} = 3.5\), \(y_3 = 7.25-0.5(2)-1.5(3.5) = 1\). Backward substitution in \(L^T\mathbf x = \mathbf y\): \(x_3 = 1\), \(x_2 = \frac {3.5-1.5}{2} = 1\), \(x_1 = \frac {2+0.5-0.5}{2} = 1\). So \(\mathbf x = (1,1,1)^T\).

Solution. Here \(a_i = 2\), \(b_i = c_i = -1\), \(d = (1,0,0,1)\). The algorithm gives \[l = \left (2,\tfrac 32,\tfrac 43,\tfrac 54\right ),\qquad u = \left (-\tfrac 12,-\tfrac 23,-\tfrac 34\right ),\qquad z = \left (\tfrac 12,\tfrac 13,\tfrac 14,1\right ),\] and back substitution gives \(x_4 = 1\), \(x_3 = \frac 14+\frac 34 = 1\), \(x_2 = \frac 13+\frac 23 = 1\), \(x_1 = \frac 12+\frac 12 = 1\). The pattern \(l_i = \frac {i+1}{i}\) persists for any \(n\), so the same matrix of size \(1000\) costs about \(5000\) operations instead of \(3\times 10^8\).