Practice / Linear algebra

Positive-definite matrices and quadratic forms

Ten problems on positive-definite matrices: classifying 2×2 matrices by eigenvalues and by a test vector, the eigenvalue characterisation and what it says about determinants and inverses, Sylvester's criterion by completing the square, Gram matrices and ridge, a 3×3 Cholesky factorisation by hand with a solve, the gradient, Hessian and minimiser of a quadratic, Hessian PSD if and only if convex, the symmetric square root and the ellipsoid of a quadratic form, the step-size condition and convergence rate of gradient descent on a quadratic, and why a quadratic form sees only the symmetric part, with worked solutions and the mistakes that read definiteness off a determinant, trust the eigenvalues of a non-symmetric matrix, sample with the transposed Cholesky factor, assume the normal equations have a unique solution, or pick the step size from the smallest eigenvalue.

Before you start

A positive-definite matrix is one whose quadratic form is a bowl: $x^\top Ax > 0$ in every direction. Every covariance matrix, every Gram matrix $X^\top X$ with independent columns, every Hessian at a strict minimum and every kernel matrix is one, and the properties that make them useful, a Cholesky factor, an inverse that is also positive definite, a square root, a condition number that sets the step size of gradient descent, all come from that one inequality. These ten problems classify small matrices by hand, prove the eigenvalue test and Sylvester's criterion, factor a $3\times3$ matrix by Cholesky and solve a system with it, minimise a quadratic by completing the square, show that a convex function is exactly one with a PSD Hessian, compute a symmetric square root, derive the step size and rate of gradient descent on a quadratic, and end with the fact that a quadratic form never sees the antisymmetric part of its matrix. The five mistakes at the end are the ones that survive a glance: a positive determinant read as positive definite, positive eigenvalues of a non-symmetric matrix, the Cholesky factor used transposed, normal equations assumed solvable, and a step size chosen from the wrong eigenvalue.

$A$ is a real symmetric $n\times n$ matrix unless a problem says otherwise, $I$ is the identity, and vectors are columns. $A$ is positive definite (PD, written $A \succ 0$ if $x^\top Ax > 0$ for every $x \neq 0$ positive semidefinite (PSD, $A \succeq 0$ if $x^\top Ax \ge 0$ for every $x$ and indefinite if $x^\top Ax$ takes both signs.
A symmetric $A$ has an orthonormal eigenbasis: $A = Q\Lambda Q^\top$ with $Q^\top Q = I$ $\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ and $Aq_i = \lambda_iq_i$ for the columns $q_i$ of $Q$ (the eigenvalues page). Equivalently $A = \sum_i\lambda_iq_iq_i^\top$ $\lambda_{\max}$ and $\lambda_{\min}$ are the largest and smallest eigenvalues and $\kappa = \lambda_{\max}/\lambda_{\min}$ is the condition number of a PD matrix.
A Cholesky factorisation of a PD matrix is $A = LL^\top$ with $L$ lower-triangular and $L_{jj} > 0$ Computed column by column: $L_{jj} = \sqrt{A_{jj} - \sum_{k<j}L_{jk}^2}$ and, for $i > j$ $L_{ij} = \big(A_{ij} - \sum_{k<j}L_{ik}L_{jk}\big)/L_{jj}$
For $X \in \mathbb{R}^{N\times d}$ the Gram matrix is $X^\top X$ $\|v\|^2 = v^\top v$ The singular values of $X$ are $\sigma_i$ (the least-squares page).
Gradients are columns: for scalar $f(x)$ $\nabla f \in \mathbb{R}^n$ and the Hessian $\nabla^2f$ is the $n\times n$ matrix of second partials, so for symmetric $A$ $\nabla(x^\top Ax) = 2Ax$ and $\nabla(b^\top x) = b$ (the matrix-calculus page). A twice-differentiable $f$ is convex when $f(\lambda x + (1 - \lambda)y) \le \lambda f(x) + (1 - \lambda)f(y)$ for all $x, y$ and $\lambda \in [0, 1]$ (the Jensen page).
Gradient descent with step $\eta$ is $x_{k+1} = x_k - \eta\nabla f(x_k)$ $e_k = x_k - x^*$ is the error after $k$ steps.

Builds on: Eigenvalues and eigenvectors by hand, Matrix calculus conventions

Problems

·
Classify $A = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ $B = \begin{bmatrix}1&2\\2&1\end{bmatrix}$ and $C = \begin{bmatrix}1&2\\2&4\end{bmatrix}$ as positive definite, positive semidefinite or indefinite using their eigenvalues. For $B$ exhibit a vector $v$ with $v^\top Bv < 0$ for $C$ a nonzero vector with $v^\top Cv = 0$
··
For symmetric $A = \sum_i\lambda_iq_iq_i^\top$ show that $x^\top Ax = \sum_i\lambda_i(q_i^\top x)^2$ and hence that $A$ is PD if and only if every $\lambda_i > 0$ Deduce that a PD matrix has $\det A > 0$ and $\operatorname{tr}A > 0$ is invertible, and that $A^{-1}$ is PD.
··
By completing the square in $x^\top Ax = ax^2 + 2bxy + cy^2$ show that the symmetric $A = \begin{bmatrix}a&b\\b&c\end{bmatrix}$ is PD if and only if $a > 0$ and $ac - b^2 > 0$ For which $t$ is $\begin{bmatrix}2&t\\t&2\end{bmatrix}$ positive definite?
··
For $X \in \mathbb{R}^{N\times d}$ show that $X^\top X$ is PSD, that it is PD if and only if the columns of $X$ are linearly independent, and that $X^\top X + \lambda I$ is PD for every $\lambda > 0$ with eigenvalues $\sigma_i^2 + \lambda$ where the $\sigma_i$ are the singular values of $X$ (zero for $i > \operatorname{rank}X$
··
Compute the Cholesky factor $L$ of $A = \begin{bmatrix}4&2&2\\2&5&3\\2&3&6\end{bmatrix}$ verify $LL^\top = A$ and use it to solve $Ax = b$ for $b = (8, 10, 11)^\top$ by two triangular solves. What is $\det A$
··
Let $f(x) = \tfrac12x^\top Ax - b^\top x + c$ with $A$ symmetric and PD. Compute $\nabla f$ and $\nabla^2f$ show that $f(x) = \tfrac12(x - x^*)^\top A(x - x^*) + f(x^*)$ with $x^* = A^{-1}b$ and $f(x^*) = c - \tfrac12b^\top A^{-1}b$ and conclude that $x^*$ is the unique minimiser. Evaluate for $A = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ $b = (1, 2)^\top$ $c = 0$ What happens if $A$ has a negative eigenvalue?
···
Let $f$ be twice differentiable on $\mathbb{R}^n$ and, for fixed $x$ and $v$ let $g(t) = f(x + tv)$ Show that $g''(t) = v^\top\nabla^2f(x + tv)\,v$ and use it to prove that $f$ is convex if and only if $\nabla^2f(x) \succeq 0$ for every $x$ Conclude that $\tfrac12x^\top Ax$ is convex exactly when $A \succeq 0$
··
For PD $A = Q\Lambda Q^\top$ define $A^{1/2} = Q\Lambda^{1/2}Q^\top$ Show that $A^{1/2}$ is symmetric PD with $(A^{1/2})^2 = A$ and that $A^{-1/2}AA^{-1/2} = I$ Compute $A^{1/2}$ for $A = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ and describe the ellipse $\{x : x^\top Ax = 1\}$
···
For $f(x) = \tfrac12x^\top Ax - b^\top x$ with $A \succ 0$ show that gradient descent satisfies $e_{k+1} = (I - \eta A)e_k$ that it converges from every start if and only if $0 < \eta < 2/\lambda_{\max}$ and that the error component along $q_i$ shrinks by the factor $\lvert 1 - \eta\lambda_i\rvert$ per step. Find the $\eta$ that minimises the worst factor and the resulting rate in terms of $\kappa$ Evaluate for $A = \operatorname{diag}(1, 10)$
··
For any square matrix $M$ not necessarily symmetric, show that $x^\top Mx = x^\top Sx$ with $S = \tfrac12(M + M^\top)$ Show that $M = \begin{bmatrix}1&4\\0&1\end{bmatrix}$ has both eigenvalues equal to $1$ and yet $v^\top Mv < 0$ for some $v$ Why does the eigenvalue test of Problem 2 not apply?

Answers

$A \succ 0$ (eigenvalues $3, 1$ $B$ indefinite (eigenvalues $3, -1$ $v = (1, -1)^\top$ gives $-2$ $C \succeq 0$ but not PD (eigenvalues $5, 0$ $v = (2, -1)^\top$ gives $0$
$x^\top Ax = \sum_i\lambda_i(q_i^\top x)^2$ $A \succ 0 \iff$ all $\lambda_i > 0$ then $\det A > 0$ $\operatorname{tr}A > 0$ $A$ is invertible and $A^{-1} \succ 0$
$\begin{bmatrix}a&b\\b&c\end{bmatrix} \succ 0 \iff a > 0$ and $ac - b^2 > 0$ $\begin{bmatrix}2&t\\t&2\end{bmatrix} \succ 0 \iff \lvert t\rvert < 2$
$X^\top X \succeq 0$ always; $X^\top X \succ 0 \iff \operatorname{rank}X = d$ $X^\top X + \lambda I \succ 0$ for $\lambda > 0$ with eigenvalues $\sigma_i^2 + \lambda$
$L = \begin{bmatrix}2&0&0\\1&2&0\\1&1&2\end{bmatrix}$ $LL^\top = A$ $x = (1, 1, 1)^\top$ $\det A = 64$
$\nabla f = Ax - b$ $\nabla^2f = A$ $f(x) = \tfrac12(x - x^*)^\top A(x - x^*) + f(x^*)$ with $x^* = A^{-1}b$ and $f(x^*) = c - \tfrac12b^\top A^{-1}b$ the unique minimiser; for the example $x^* = (0, 1)^\top$ $f(x^*) = -1$ with a negative eigenvalue $f$ is unbounded below
$g''(t) = v^\top\nabla^2f(x + tv)\,v$ $f$ convex $\iff \nabla^2f(x) \succeq 0$ for all $x$ $\tfrac12x^\top Ax$ convex $\iff A \succeq 0$
$A^{1/2} = Q\Lambda^{1/2}Q^\top \succ 0$ with $(A^{1/2})^2 = A$ and $A^{-1/2}AA^{-1/2} = I$ for the example $A^{1/2} = \tfrac12\begin{bmatrix}\sqrt3 + 1&\sqrt3 - 1\\\sqrt3 - 1&\sqrt3 + 1\end{bmatrix}$ $x^\top Ax = 1$ is an ellipse with semi-axes $1/\sqrt3$ along $(1, 1)^\top/\sqrt2$ and $1$ along $(1, -1)^\top/\sqrt2$
$e_{k+1} = (I - \eta A)e_k$ convergence from every start $\iff 0 < \eta < 2/\lambda_{\max}$ the $q_i$ component scales by $\lvert 1 - \eta\lambda_i\rvert$ $\eta^* = \dfrac2{\lambda_{\min} + \lambda_{\max}}$ with rate $\dfrac{\kappa - 1}{\kappa + 1}$ for $\operatorname{diag}(1, 10)$ $\eta^* = 2/11$ rate $9/11$
$x^\top Mx = x^\top\tfrac12(M + M^\top)x$ $M = \begin{bmatrix}1&4\\0&1\end{bmatrix}$ has eigenvalues $1, 1$ but $(1, -1)M(1, -1)^\top = -2$ the eigenvalue test needs a symmetric matrix

Worked solutions

Problem 1

Classify $A = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ $B = \begin{bmatrix}1&2\\2&1\end{bmatrix}$ and $C = \begin{bmatrix}1&2\\2&4\end{bmatrix}$ as positive definite, positive semidefinite or indefinite using their eigenvalues. For $B$ exhibit a vector $v$ with $v^\top Bv < 0$ for $C$ a nonzero vector with $v^\top Cv = 0$

$A$ $\det(A - \lambda I) = (2 - \lambda)^2 - 1 = 0$ gives $\lambda = 3, 1$ both positive: PD.The eigenvalues page's Problem 1; Problem 2 below shows why positive eigenvalues mean PD.
$B$ $(1 - \lambda)^2 - 4 = 0$ gives $1 - \lambda = \pm 2$ $\lambda = 3, -1$ indefinite.One eigenvalue of each sign.
$v = (1, -1)^\top$ $v^\top Bv = 1 - 2 - 2 + 1 = -2 < 0$ $v$ is the eigenvector for $\lambda = -1$ since $B(1, -1)^\top = (1 - 2, 2 - 1)^\top = -(1, -1)^\top$ its quadratic form is $\lambda\|v\|^2 = -2$
$C$ $(1 - \lambda)(4 - \lambda) - 4 = \lambda^2 - 5\lambda = 0$ gives $\lambda = 5, 0$ PSD but not PD.A zero eigenvalue means $x^\top Cx = 0$ for a nonzero $x$ so the form is never negative but is not always positive.
$v = (2, -1)^\top$ $Cv = (2 - 2, 4 - 4)^\top = 0$ so $v^\top Cv = 0$ The null vector of $C$ $C$ has rank one, $C = (1, 2)^\top(1, 2)$
$A \succ 0$ (eigenvalues $3, 1$ $B$ indefinite (eigenvalues $3, -1$ $v = (1, -1)^\top$ gives $-2$ $C \succeq 0$ but not PD (eigenvalues $5, 0$ $v = (2, -1)^\top$ gives $0$ All three have positive diagonal entries and positive trace, and $B$ even has all entries positive, so none of those tests decides anything; $B$ 's determinant is $-3$ and $C$ 's is $0$ which rule them out, but a positive determinant would not have ruled them in (Mistake 1). $A$ is the covariance matrix of the Gaussian page's Problem 1, and $C$ is what a covariance looks like when one coordinate is twice the other.

Problem 2

For symmetric $A = \sum_i\lambda_iq_iq_i^\top$ show that $x^\top Ax = \sum_i\lambda_i(q_i^\top x)^2$ and hence that $A$ is PD if and only if every $\lambda_i > 0$ Deduce that a PD matrix has $\det A > 0$ and $\operatorname{tr}A > 0$ is invertible, and that $A^{-1}$ is PD.

$x^\top Ax = x^\top\Big(\sum_i\lambda_iq_iq_i^\top\Big)x = \sum_i\lambda_i(x^\top q_i)(q_i^\top x) = \sum_i\lambda_i(q_i^\top x)^2$ Distribute $x^\top$ and $x$ over the sum; $x^\top q_i = q_i^\top x$ is a scalar.
If every $\lambda_i > 0$ and $x \neq 0$ then some $q_i^\top x \neq 0$ so $x^\top Ax > 0$ The $q_i$ are an orthonormal basis, so $x = \sum_i(q_i^\top x)q_i$ if every coefficient were zero, $x$ would be zero. All terms are $\ge 0$ and at least one is $> 0$
If $A$ is PD, then $\lambda_i = q_i^\top Aq_i > 0$ for every $i$ Take $x = q_i$ in the definition: $q_i^\top Aq_i = q_i^\top(\lambda_iq_i) = \lambda_i\|q_i\|^2 = \lambda_i$
$\det A = \prod_i\lambda_i > 0$ and $\operatorname{tr}A = \sum_i\lambda_i > 0$ no eigenvalue is zero, so $A$ is invertible.The eigenvalues page's Problem 5, extended to $n\times n$ by $\det(Q\Lambda Q^\top) = \det\Lambda$ and $\operatorname{tr}(Q\Lambda Q^\top) = \operatorname{tr}(\Lambda Q^\top Q) = \operatorname{tr}\Lambda$ a matrix is singular exactly when $0$ is an eigenvalue.
$A^{-1} = Q\Lambda^{-1}Q^\top = \sum_i\dfrac1{\lambda_i}q_iq_i^\top$ with every $1/\lambda_i > 0$ so $A^{-1}$ is PD by step 2. $(Q\Lambda Q^\top)(Q\Lambda^{-1}Q^\top) = Q\Lambda\Lambda^{-1}Q^\top = I$ because $Q^\top Q = I$ the inverse has the same eigenvectors and reciprocal eigenvalues.
$x^\top Ax = \sum_i\lambda_i(q_i^\top x)^2$ $A \succ 0 \iff$ all $\lambda_i > 0$ then $\det A > 0$ $\operatorname{tr}A > 0$ $A$ is invertible and $A^{-1} \succ 0$ In the eigenbasis the quadratic form is a weighted sum of squares, and definiteness is the sign pattern of the weights: all $> 0$ is PD, all $\ge 0$ is PSD, mixed is indefinite. The converses of step 4 fail: $\det > 0$ and $\operatorname{tr} > 0$ together do not give PD in three dimensions ( $\operatorname{diag}(4, -1, -1)$ and in two dimensions they do only because two eigenvalues with positive product and positive sum are both positive, which is Problem 3's criterion. Step 5 is why the precision matrix $\Sigma^{-1}$ of a Gaussian is PD whenever the covariance is.

Problem 3

By completing the square in $x^\top Ax = ax^2 + 2bxy + cy^2$ show that the symmetric $A = \begin{bmatrix}a&b\\b&c\end{bmatrix}$ is PD if and only if $a > 0$ and $ac - b^2 > 0$ For which $t$ is $\begin{bmatrix}2&t\\t&2\end{bmatrix}$ positive definite?

For $a \neq 0$ $ax^2 + 2bxy + cy^2 = a\Big(x + \dfrac bay\Big)^2 + \Big(c - \dfrac{b^2}a\Big)y^2 = a\Big(x + \dfrac bay\Big)^2 + \dfrac{ac - b^2}{a}y^2$ Expand $a(x + \tfrac bay)^2 = ax^2 + 2bxy + \tfrac{b^2}ay^2$ and subtract the extra $\tfrac{b^2}ay^2$
If $a > 0$ and $ac - b^2 > 0$ both coefficients are positive, so the form is $\ge 0$ and it is $0$ only when $y = 0$ and then $x + \tfrac bay = x = 0$ A positive combination of two squares vanishes only when both squares vanish.
If $A$ is PD: $x = (1, 0)^\top$ gives $a > 0$ and $x = (-\tfrac ba, 1)^\top$ gives $\dfrac{ac - b^2}{a} > 0$ so $ac - b^2 > 0$ Two test vectors, chosen to kill one square each in step 1; $a > 0$ lets the inequality be multiplied through.
$\begin{bmatrix}2&t\\t&2\end{bmatrix}$ $a = 2 > 0$ and $ac - b^2 = 4 - t^2 > 0$ exactly when $\lvert t\rvert < 2$ Step 2 with $a = c = 2$ $b = t$
$\begin{bmatrix}a&b\\b&c\end{bmatrix} \succ 0 \iff a > 0$ and $ac - b^2 > 0$ $\begin{bmatrix}2&t\\t&2\end{bmatrix} \succ 0 \iff \lvert t\rvert < 2$ This is Sylvester's criterion: all leading principal minors positive, the $1\times1$ minor $a$ and the $2\times2$ minor $\det A$ Completing the square is the $2\times2$ Cholesky factorisation in disguise, $L = \begin{bmatrix}\sqrt a&0\\b/\sqrt a&\sqrt{(ac - b^2)/a}\end{bmatrix}$ and the criterion fails exactly where a square root in Problem 5's algorithm would go negative. At $t = \pm 2$ the matrix is PSD with the null vector $(1, \mp 1)^\top$ and for $\lvert t\rvert > 2$ it is indefinite despite its positive diagonal and positive trace. For a covariance $\begin{bmatrix}\sigma_1^2&\rho\sigma_1\sigma_2\\\rho\sigma_1\sigma_2&\sigma_2^2\end{bmatrix}$ the condition is $\rho^2 < 1$

Problem 4

For $X \in \mathbb{R}^{N\times d}$ show that $X^\top X$ is PSD, that it is PD if and only if the columns of $X$ are linearly independent, and that $X^\top X + \lambda I$ is PD for every $\lambda > 0$ with eigenvalues $\sigma_i^2 + \lambda$ where the $\sigma_i$ are the singular values of $X$ (zero for $i > \operatorname{rank}X$

$v^\top X^\top Xv = (Xv)^\top(Xv) = \|Xv\|^2 \ge 0$ Group the product as $(Xv)^\top(Xv)$ a squared norm is nonnegative.
$v^\top X^\top Xv = 0 \iff Xv = 0$ A norm is zero only for the zero vector.
$X^\top X \succ 0 \iff Xv \neq 0$ for every $v \neq 0 \iff$ the columns of $X$ are linearly independent. $Xv = \sum_jv_jx_j$ with $x_j$ the columns, and $Xv = 0$ for some $v \neq 0$ is exactly a linear dependence among them. That needs $N \ge d$ with $N < d$ some nonzero $v$ always has $Xv = 0$
$v^\top(X^\top X + \lambda I)v = \|Xv\|^2 + \lambda\|v\|^2 > 0$ for $v \neq 0$ Step 1 plus $\lambda\|v\|^2 > 0$ the second term is positive even when the first is zero.
With $X = U\Sigma V^\top$ $X^\top X = V\Sigma^\top\Sigma V^\top$ so its eigenvalues are $\sigma_i^2$ with eigenvectors the right singular vectors $v_i$ and $(X^\top X + \lambda I)v_i = (\sigma_i^2 + \lambda)v_i$ $U^\top U = I$ and $\Sigma^\top\Sigma$ is diagonal with entries $\sigma_i^2$ (the least-squares page); adding $\lambda I$ adds $\lambda$ to every eigenvalue without moving the eigenvectors.
$X^\top X \succeq 0$ always; $X^\top X \succ 0 \iff \operatorname{rank}X = d$ $X^\top X + \lambda I \succ 0$ for $\lambda > 0$ with eigenvalues $\sigma_i^2 + \lambda$ Every Gram matrix, covariance matrix ( $\tfrac1{N-1}X^\top HX$ on the variance page) and kernel matrix is PSD for the reason in step 1, and PD only when nothing is collinear. The normal equations $X^\top Xw = X^\top y$ have a unique solution exactly in the PD case (Mistake 4); ridge regression's $X^\top X + \lambda I$ is always invertible, with condition number $(\sigma_{\max}^2 + \lambda)/(\sigma_{\min}^2 + \lambda)$ which $\lambda$ pulls towards $1$ and that is what makes ridge both solvable and well-conditioned. The bias–variance page prices the shrinkage this costs.

Problem 5

Compute the Cholesky factor $L$ of $A = \begin{bmatrix}4&2&2\\2&5&3\\2&3&6\end{bmatrix}$ verify $LL^\top = A$ and use it to solve $Ax = b$ for $b = (8, 10, 11)^\top$ by two triangular solves. What is $\det A$

Column 1: $L_{11} = \sqrt{A_{11}} = 2$ $L_{21} = A_{21}/L_{11} = 1$ $L_{31} = A_{31}/L_{11} = 1$ The algorithm with no earlier columns to subtract.
Column 2: $L_{22} = \sqrt{A_{22} - L_{21}^2} = \sqrt{5 - 1} = 2$ $L_{32} = (A_{32} - L_{31}L_{21})/L_{22} = (3 - 1)/2 = 1$ Subtract the contribution of column 1 before taking the root and dividing.
Column 3: $L_{33} = \sqrt{A_{33} - L_{31}^2 - L_{32}^2} = \sqrt{6 - 1 - 1} = 2$ Both earlier columns contribute to the $(3, 3)$ entry.
$L = \begin{bmatrix}2&0&0\\1&2&0\\1&1&2\end{bmatrix}$ and $LL^\top = \begin{bmatrix}4&2&2\\2&1 + 4&1 + 2\\2&1 + 2&1 + 1 + 4\end{bmatrix} = A$ Entry $(i, j)$ of $LL^\top$ is the dot product of rows $i$ and $j$ of $L$
Forward solve $Ly = b$ $y_1 = 8/2 = 4$ $y_2 = (10 - 1\cdot 4)/2 = 3$ $y_3 = (11 - 1\cdot 4 - 1\cdot 3)/2 = 2$ Row by row from the top; each row has one new unknown.
Back solve $L^\top x = y$ $x_3 = 2/2 = 1$ $x_2 = (3 - 1\cdot 1)/2 = 1$ $x_1 = (4 - 1\cdot 1 - 1\cdot 1)/2 = 1$ $L^\top$ is upper-triangular, so solve from the bottom; $Ax = LL^\top x = Ly = b$
$\det A = \det L\,\det L^\top = (\det L)^2 = (2\cdot 2\cdot 2)^2 = 64$ The determinant of a triangular matrix is the product of its diagonal, and $\det L^\top = \det L$
$L = \begin{bmatrix}2&0&0\\1&2&0\\1&1&2\end{bmatrix}$ $LL^\top = A$ $x = (1, 1, 1)^\top$ $\det A = 64$ Check: $A(1, 1, 1)^\top = (8, 10, 11)^\top$ The three square roots were of $4$ $4$ and $4$ all positive, which is the proof that $A$ is PD: Cholesky succeeds exactly when every pivot $A_{jj} - \sum_{k<j}L_{jk}^2$ is positive, and it is how software tests definiteness, at a third of the cost of an eigendecomposition. The Gaussian page uses $L$ to sample, $x = \mu + L\varepsilon$ (and not $L^\top\varepsilon$ Mistake 3), and $\log\det\Sigma = 2\sum_j\log L_{jj}$ is how its normaliser is computed without forming the determinant.

Problem 6

Let $f(x) = \tfrac12x^\top Ax - b^\top x + c$ with $A$ symmetric and PD. Compute $\nabla f$ and $\nabla^2f$ show that $f(x) = \tfrac12(x - x^*)^\top A(x - x^*) + f(x^*)$ with $x^* = A^{-1}b$ and $f(x^*) = c - \tfrac12b^\top A^{-1}b$ and conclude that $x^*$ is the unique minimiser. Evaluate for $A = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ $b = (1, 2)^\top$ $c = 0$ What happens if $A$ has a negative eigenvalue?

$\nabla f = Ax - b$ and $\nabla^2f = A$ $\nabla(\tfrac12x^\top Ax) = Ax$ for symmetric $A$ and $\nabla(b^\top x) = b$ (the matrix-calculus page); the Hessian is the Jacobian of $Ax - b$
$\tfrac12(x - x^*)^\top A(x - x^*) = \tfrac12x^\top Ax - x^\top Ax^* + \tfrac12x^{*\top}Ax^*$ Expand; the two cross terms are equal because $A$ is symmetric.
With $Ax^* = b$ $x^\top Ax^* = b^\top x$ and $x^{*\top}Ax^* = b^\top A^{-1}b$ so $\tfrac12(x - x^*)^\top A(x - x^*) = \tfrac12x^\top Ax - b^\top x + \tfrac12b^\top A^{-1}b = f(x) - c + \tfrac12b^\top A^{-1}b$ Substitute $Ax^* = b$ and $x^* = A^{-1}b$ compare with the definition of $f$
$f(x) = \tfrac12(x - x^*)^\top A(x - x^*) + f(x^*)$ with $f(x^*) = c - \tfrac12b^\top A^{-1}b$ the first term is $> 0$ for $x \neq x^*$ and $0$ at $x^*$ Rearrange step 3; $A \succ 0$ applied to the vector $x - x^*$
$A^{-1} = \tfrac13\begin{bmatrix}2&-1\\-1&2\end{bmatrix}$ $x^* = \tfrac13(2 - 2, -1 + 4)^\top = (0, 1)^\top$ $f(x^*) = -\tfrac12b^\top x^* = -\tfrac12(0 + 2) = -1$ The $2\times2$ inverse with $\det A = 3$ $b^\top A^{-1}b = b^\top x^*$ Check: $f(0, 1) = \tfrac12\cdot 2 - 2 = -1$ and $\nabla f(0, 1) = (1, 2)^\top - (1, 2)^\top = 0$
If $Av = \lambda v$ with $\lambda < 0$ $f(tv) = \tfrac12\lambda t^2\|v\|^2 - t\,b^\top v + c \to -\infty$ as $t \to \infty$ Along an eigenvector the quadratic term is $\tfrac12\lambda t^2\|v\|^2$ and a negative quadratic beats a linear term for large $t$
$\nabla f = Ax - b$ $\nabla^2f = A$ $f(x) = \tfrac12(x - x^*)^\top A(x - x^*) + f(x^*)$ with $x^* = A^{-1}b$ and $f(x^*) = c - \tfrac12b^\top A^{-1}b$ the unique minimiser; for the example $x^* = (0, 1)^\top$ $f(x^*) = -1$ with a negative eigenvalue $f$ is unbounded belowCompleting the square in $n$ dimensions: the bowl is centred at $x^*$ and shaped by $A$ Setting $\nabla f = 0$ finds the same $x^*$ but only step 4 says it is a minimum rather than a saddle, and only PD makes it unique: a PSD $A$ with $Av = 0$ leaves $f$ constant along $v$ (a valley of minimisers if $b \perp v$ no minimiser at all otherwise), which is Mistake 4 in the least-squares setting. Newton's method is exactly this calculation applied to the quadratic model of a general $f$ which the Newton page takes up.

Problem 7

Let $f$ be twice differentiable on $\mathbb{R}^n$ and, for fixed $x$ and $v$ let $g(t) = f(x + tv)$ Show that $g''(t) = v^\top\nabla^2f(x + tv)\,v$ and use it to prove that $f$ is convex if and only if $\nabla^2f(x) \succeq 0$ for every $x$ Conclude that $\tfrac12x^\top Ax$ is convex exactly when $A \succeq 0$

$g'(t) = \nabla f(x + tv)^\top v$ Chain rule: the derivative of $f$ along the curve $x + tv$ whose velocity is $v$ (the Jacobians page).
$g''(t) = v^\top\nabla^2f(x + tv)\,v$ Differentiate $\sum_i\partial_if(x + tv)\,v_i$ again: each $\partial_if$ contributes $\sum_j\partial_{ij}f\,v_j$ giving $\sum_{ij}v_i\,\partial_{ij}f\,v_j$
If $\nabla^2f \succeq 0$ everywhere, then $g'' \ge 0$ for every $x, v$ so each $g$ is convex: $f(\lambda y + (1 - \lambda)z) = g(\lambda)$ with $x = z$ $v = y - z$ and $g(\lambda) = g(\lambda\cdot 1 + (1 - \lambda)\cdot 0) \le \lambda g(1) + (1 - \lambda)g(0) = \lambda f(y) + (1 - \lambda)f(z)$ The Jensen page's Problem 2: a one-variable function with nonnegative second derivative is convex; the segment from $z$ to $y$ is the line $z + t(y - z)$ for $t \in [0, 1]$
Conversely, if $f$ is convex then every $g$ is convex, so $g''(0) \ge 0$ that is $v^\top\nabla^2f(x)\,v \ge 0$ for every $v$ Restricting a convex function to a line keeps the chord inequality, and a convex twice-differentiable function of one variable has $g'' \ge 0$ if $g''(0) < 0$ then $g(h) + g(-h) - 2g(0) = g''(0)h^2 + o(h^2) < 0$ for small $h$ contradicting the midpoint chord inequality.
$f(x) = \tfrac12x^\top Ax$ has $\nabla^2f = A$ at every $x$ so $f$ is convex exactly when $A \succeq 0$ Problem 6, step 1; the Hessian is constant.
$g''(t) = v^\top\nabla^2f(x + tv)\,v$ $f$ convex $\iff \nabla^2f(x) \succeq 0$ for all $x$ $\tfrac12x^\top Ax$ convex $\iff A \succeq 0$ Convexity in $n$ dimensions is convexity along every line, and the second derivative along a line is the Hessian's quadratic form in that direction, so PSD everywhere is the whole story. It has to be everywhere (the Jensen page's Mistake 5) and PSD is enough: PD gives strict convexity, but the converse fails ( $x^4$ is strictly convex with $f''(0) = 0$ This is the test that certifies least squares (Hessian $2X^\top X$ Problem 4), ridge, logistic regression (Hessian $\tfrac1NX^\top DX$ on the Hessians page) and cross-entropy with softmax (the Jensen page's Problem 7) as convex, and it is what a neural network with a hidden layer fails.

Problem 8

For PD $A = Q\Lambda Q^\top$ define $A^{1/2} = Q\Lambda^{1/2}Q^\top$ Show that $A^{1/2}$ is symmetric PD with $(A^{1/2})^2 = A$ and that $A^{-1/2}AA^{-1/2} = I$ Compute $A^{1/2}$ for $A = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ and describe the ellipse $\{x : x^\top Ax = 1\}$

$(A^{1/2})^\top = Q\Lambda^{1/2}Q^\top = A^{1/2}$ and its eigenvalues $\sqrt{\lambda_i}$ are positive, so $A^{1/2} \succ 0$ $\Lambda^{1/2}$ is diagonal, hence symmetric; Problem 2's test.
$(A^{1/2})^2 = Q\Lambda^{1/2}Q^\top Q\Lambda^{1/2}Q^\top = Q\Lambda Q^\top = A$ $Q^\top Q = I$ in the middle and $\Lambda^{1/2}\Lambda^{1/2} = \Lambda$
$A^{-1/2} = Q\Lambda^{-1/2}Q^\top$ and $A^{-1/2}AA^{-1/2} = Q\Lambda^{-1/2}\Lambda\Lambda^{-1/2}Q^\top = QQ^\top = I$ The same cancellation; $\Lambda^{-1/2}\Lambda\Lambda^{-1/2} = I$ entrywise, and $QQ^\top = I$ for a square orthogonal matrix.
For the example, $Q = \dfrac1{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$ $\Lambda = \operatorname{diag}(3, 1)$ so $A^{1/2} = \sqrt3\,q_1q_1^\top + 1\cdot q_2q_2^\top = \dfrac{\sqrt3}2\begin{bmatrix}1&1\\1&1\end{bmatrix} + \dfrac12\begin{bmatrix}1&-1\\-1&1\end{bmatrix} = \dfrac12\begin{bmatrix}\sqrt3 + 1&\sqrt3 - 1\\\sqrt3 - 1&\sqrt3 + 1\end{bmatrix}$ The eigenvalues page's Problem 8 for $Q$ and $\Lambda$ $A^{1/2} = \sum_i\sqrt{\lambda_i}\,q_iq_i^\top$ with $q_1 = (1, 1)^\top/\sqrt2$ and $q_2 = (1, -1)^\top/\sqrt2$
Check: $\big(A^{1/2}\big)^2$ has diagonal $\tfrac14\big((\sqrt3 + 1)^2 + (\sqrt3 - 1)^2\big) = \tfrac14(8) = 2$ and off-diagonal $\tfrac14\cdot 2(\sqrt3 + 1)(\sqrt3 - 1) = \tfrac14\cdot 4 = 1$ $(\sqrt3 \pm 1)^2 = 4 \pm 2\sqrt3$ and $(\sqrt3 + 1)(\sqrt3 - 1) = 2$
With $y = Q^\top x$ $x^\top Ax = y^\top\Lambda y = 3y_1^2 + y_2^2 = 1$ an ellipse with semi-axis $1/\sqrt3$ along $q_1$ and $1$ along $q_2$ Problem 2's sum of squares in the eigenbasis; $\lambda_iy_i^2 = 1$ on the axis gives $y_i = 1/\sqrt{\lambda_i}$
$A^{1/2} = Q\Lambda^{1/2}Q^\top \succ 0$ with $(A^{1/2})^2 = A$ and $A^{-1/2}AA^{-1/2} = I$ for the example $A^{1/2} = \tfrac12\begin{bmatrix}\sqrt3 + 1&\sqrt3 - 1\\\sqrt3 - 1&\sqrt3 + 1\end{bmatrix}$ $x^\top Ax = 1$ is an ellipse with semi-axes $1/\sqrt3$ along $(1, 1)^\top/\sqrt2$ and $1$ along $(1, -1)^\top/\sqrt2$ A PD matrix has two useful square roots: the symmetric $A^{1/2}$ here and the triangular Cholesky $L$ of Problem 5, with $A = A^{1/2}A^{1/2} = LL^\top$ Either one turns $\mathcal{N}(0, I)$ into $\mathcal{N}(0, A)$ by multiplication, and either inverse whitens, which is the variance page's $W = \Lambda^{-1/2}Q^\top$ up to a rotation. The ellipse is the unit ball of the norm $\|x\|_A = \sqrt{x^\top Ax}$ and the level set of the Gaussian with precision $A$ long axes where the eigenvalue is small, and Problem 9 shows that the ratio of its axes, $\sqrt\kappa$ is what slows gradient descent.

Problem 9

For $f(x) = \tfrac12x^\top Ax - b^\top x$ with $A \succ 0$ show that gradient descent satisfies $e_{k+1} = (I - \eta A)e_k$ that it converges from every start if and only if $0 < \eta < 2/\lambda_{\max}$ and that the error component along $q_i$ shrinks by the factor $\lvert 1 - \eta\lambda_i\rvert$ per step. Find the $\eta$ that minimises the worst factor and the resulting rate in terms of $\kappa$ Evaluate for $A = \operatorname{diag}(1, 10)$

$x_{k+1} - x^* = x_k - \eta(Ax_k - b) - x^* = (x_k - x^*) - \eta A(x_k - x^*)$ so $e_{k+1} = (I - \eta A)e_k$ $\nabla f = Ax - b$ (Problem 6) and $b = Ax^*$ so $Ax_k - b = A(x_k - x^*)$
With $e_k = \sum_ic_i^{(k)}q_i$ $c_i^{(k+1)} = (1 - \eta\lambda_i)c_i^{(k)}$ so $c_i^{(k)} = (1 - \eta\lambda_i)^kc_i^{(0)}$ $(I - \eta A)q_i = q_i - \eta\lambda_iq_i$ the eigenvectors decouple the iteration into $n$ scalar recurrences.
$e_k \to 0$ for every $e_0$ $\iff \lvert 1 - \eta\lambda_i\rvert < 1$ for every $i$ $\iff 0 < \eta\lambda_i < 2$ for every $i$ $\iff 0 < \eta < 2/\lambda_{\max}$ A geometric sequence tends to zero exactly when its ratio has modulus below $1$ the binding constraint is the largest eigenvalue, since $\eta\lambda_i < 2$ for all $i$ is $\eta\lambda_{\max} < 2$ and $\eta > 0$ is needed for $\lambda_{\min}$
The worst factor is $\rho(\eta) = \max_i\lvert 1 - \eta\lambda_i\rvert = \max\big(1 - \eta\lambda_{\min},\ \eta\lambda_{\max} - 1\big)$ For $0 < \eta < 2/\lambda_{\max}$ the values $1 - \eta\lambda_i$ lie between $1 - \eta\lambda_{\max}$ and $1 - \eta\lambda_{\min}$ and the largest modulus is at one of the two ends.
$\rho$ is minimised where the two branches are equal: $1 - \eta\lambda_{\min} = \eta\lambda_{\max} - 1$ so $\eta^* = \dfrac{2}{\lambda_{\min} + \lambda_{\max}}$ and $\rho(\eta^*) = 1 - \dfrac{2\lambda_{\min}}{\lambda_{\min} + \lambda_{\max}} = \dfrac{\lambda_{\max} - \lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} = \dfrac{\kappa - 1}{\kappa + 1}$ One branch decreases in $\eta$ and the other increases, so the maximum of the two is smallest where they cross; divide numerator and denominator by $\lambda_{\min}$
$A = \operatorname{diag}(1, 10)$ $\kappa = 10$ $\eta^* = 2/11$ rate $9/11 \approx 0.818$ with $\eta = 1/\lambda_{\max} = 0.1$ the factors are $0.9$ and $0$ rate $0.9$ with $\eta = 0.3 > 2/10$ the stiff component grows by $\lvert 1 - 3\rvert = 2$ per step.Step 5 with $\lambda_{\min} = 1$ $\lambda_{\max} = 10$ the other two step sizes from step 4.
$e_{k+1} = (I - \eta A)e_k$ convergence from every start $\iff 0 < \eta < 2/\lambda_{\max}$ the $q_i$ component scales by $\lvert 1 - \eta\lambda_i\rvert$ $\eta^* = \dfrac2{\lambda_{\min} + \lambda_{\max}}$ with rate $\dfrac{\kappa - 1}{\kappa + 1}$ for $\operatorname{diag}(1, 10)$ $\eta^* = 2/11$ rate $9/11$ The step size is set by the stiffest direction and the speed by the flattest: at $\eta^*$ the error shrinks by $(\kappa - 1)/(\kappa + 1) \approx 1 - 2/\kappa$ per step, so reaching accuracy $\epsilon$ takes about $\tfrac\kappa2\log(1/\epsilon)$ steps, linear in the condition number. For a general smooth $f$ the same analysis applies to the Hessian at the minimum, which is why conditioning is the quantity that normalisation, preconditioning and Adam's per-coordinate scaling attack, and why Newton's method, which multiplies by $A^{-1}$ and makes every $\lambda_i$ effectively $1$ converges in one step on a quadratic. Mistake 5 chooses $\eta$ from the wrong eigenvalue.

Problem 10

For any square matrix $M$ not necessarily symmetric, show that $x^\top Mx = x^\top Sx$ with $S = \tfrac12(M + M^\top)$ Show that $M = \begin{bmatrix}1&4\\0&1\end{bmatrix}$ has both eigenvalues equal to $1$ and yet $v^\top Mv < 0$ for some $v$ Why does the eigenvalue test of Problem 2 not apply?

$x^\top Mx = (x^\top Mx)^\top = x^\top M^\top x$ A $1\times1$ matrix equals its transpose, and $(x^\top Mx)^\top = x^\top M^\top x$
$x^\top Mx = \tfrac12\big(x^\top Mx + x^\top M^\top x\big) = x^\top\,\tfrac12(M + M^\top)\,x = x^\top Sx$ Average the two equal expressions and factor out $x^\top$ and $x$
$M$ is upper-triangular with diagonal $(1, 1)$ so its eigenvalues are $1, 1$ The eigenvalues of a triangular matrix are its diagonal entries (the eigenvalues page's Problem 4).
$S = \tfrac12\Big(\begin{bmatrix}1&4\\0&1\end{bmatrix} + \begin{bmatrix}1&0\\4&1\end{bmatrix}\Big) = \begin{bmatrix}1&2\\2&1\end{bmatrix}$ Problem 1's $B$ indefinite with eigenvalues $3, -1$ Add $M$ to its transpose and halve.
$v = (1, -1)^\top$ $v^\top Mv = 1\cdot 1 + 4\cdot 1\cdot(-1) + 0 + 1\cdot 1 = -2$ Expand $x^\top Mx = M_{11}x_1^2 + M_{12}x_1x_2 + M_{21}x_2x_1 + M_{22}x_2^2$ with $x = (1, -1)^\top$ it agrees with $v^\top Sv = -2$ from Problem 1.
$x^\top Mx = x^\top\tfrac12(M + M^\top)x$ $M = \begin{bmatrix}1&4\\0&1\end{bmatrix}$ has eigenvalues $1, 1$ but $(1, -1)M(1, -1)^\top = -2$ the eigenvalue test needs a symmetric matrixA quadratic form sees only the symmetric part of its matrix; the antisymmetric part $\tfrac12(M - M^\top)$ contributes $x^\top Kx = 0$ because $x^\top Kx = -x^\top K^\top x = -x^\top Kx$ Problem 2 used $M = Q\Lambda Q^\top$ with orthonormal $Q$ which non-symmetric matrices do not have: $M$ here has a single eigenvector direction (it is a shear) and no orthogonal eigenbasis, so its eigenvalues say nothing about its quadratic form (Mistake 2). This is also why the matrix-calculus page's $\nabla(x^\top Mx) = (M + M^\top)x$ has the symmetrised matrix in it, and why the Hessians page symmetrises $A$ before reading off definiteness.

Where this goes wrong

1. Reading positive definite off a positive determinant

Sylvester's criterion is remembered as “the determinant is positive”, which is the last of its conditions and not the first.

$\begin{bmatrix}a&b\\b&c\end{bmatrix} \succ 0 \iff a > 0$ and $ac - b^2 > 0$ Right so far: Problem 3.
“The determinant is what decides it: positive determinant, positive definite.”The shortcut that causes the mistake: Problem 3's proof needed the leading entry $a > 0$ first, and the determinant only afterwards.
$A = \begin{bmatrix}-1&0\\0&-1\end{bmatrix}$ has $\det A = 1 > 0$ so $A \succ 0$ $x^\top Ax = -\|x\|^2 < 0$ for every $x \neq 0$ negative definite. The determinant is the product of the eigenvalues, and two negative eigenvalues multiply to a positive number; $\operatorname{diag}(4, -1, -1)$ does the same in three dimensions with a positive trace too. The criterion needs every leading principal minor positive, $a$ and then $ac - b^2$ which for $\operatorname{diag}(-1, -1)$ fails at the first. The cheapest decisive test is Problem 5's: attempt the Cholesky factorisation and watch for a non-positive pivot, which here fails at $\sqrt{-1}$

2. Trusting the eigenvalues of a non-symmetric matrix

Positive eigenvalues mean positive definite, and the matrix at hand is not checked for symmetry before the test is applied.

$A = Q\Lambda Q^\top \succ 0 \iff$ every $\lambda_i > 0$ Right so far: Problem 2, for symmetric $A$
“Eigenvalues are eigenvalues; compute them and look at the signs.”The habit that causes the mistake: Problem 2's proof wrote $x^\top Ax = \sum_i\lambda_i(q_i^\top x)^2$ which needs an orthonormal eigenbasis, and only symmetric matrices are guaranteed one.
$M = \begin{bmatrix}1&4\\0&1\end{bmatrix}$ has eigenvalues $1, 1 > 0$ so $x^\top Mx > 0$ for all $x \neq 0$ $(1, -1)M(1, -1)^\top = -2$ (Problem 10). The quadratic form of $M$ is the quadratic form of $\tfrac12(M + M^\top) = \begin{bmatrix}1&2\\2&1\end{bmatrix}$ whose eigenvalues are $3$ and $-1$ so the form is indefinite. The right procedure for a non-symmetric matrix is to symmetrise first and then test; a Jacobian $\partial f/\partial x$ of a non-gradient vector field is the usual place this comes up, and the Hessians page's $\tfrac12(A + A^\top)$ is the same step taken for the Hessian of $\tfrac12x^\top Ax$

3. Sampling with the transposed Cholesky factor

$A = LL^\top$ and $A = L^\top L$ look alike, and whichever factor is to hand gets multiplied onto the noise.

$A = LL^\top$ with $L = \begin{bmatrix}2&0&0\\1&2&0\\1&1&2\end{bmatrix}$ and $x = \mu + L\varepsilon$ has covariance $LL^\top = A$ for $\varepsilon \sim \mathcal{N}(0, I)$ Right so far: Problem 5 and the Gaussian page's Problem 7.
“ $L$ and $L^\top$ are the same factor, just written the other way.”The habit that causes the mistake: the covariance of $M\varepsilon$ is $MM^\top$ and the order of the two factors is not optional.
$x = \mu + L^\top\varepsilon$ has covariance $A$ Its covariance is $L^\top(L^\top)^\top = L^\top L = \begin{bmatrix}6&3&2\\3&5&2\\2&2&4\end{bmatrix} \neq A$ the first coordinate now has variance $6$ instead of $4$ $L^\top L$ and $LL^\top$ share eigenvalues and determinant ( $64$ in both cases), so a check on those would not catch it; a check on $\operatorname{Var}(x_1)$ would. The same slip in the other direction happens in the whitening step, $L^{-1}(x - \mu)$ against $L^{-\top}(x - \mu)$ and in software it is the difference between a library returning the lower factor and one returning the upper. Problem 8's symmetric root $A^{1/2}$ has no such ambiguity, which is one reason to prefer it when cost is not the issue.

4. Assuming the normal equations have a unique solution

$X^\top X$ is positive semidefinite and usually positive definite, and the usual case becomes the only case.

$X^\top X \succeq 0$ for every $X$ with $v^\top X^\top Xv = \|Xv\|^2$ Right so far: Problem 4, step 1.
“A Gram matrix is positive definite, so $(X^\top X)^{-1}$ exists and $w = (X^\top X)^{-1}X^\top y$ ”The habit that causes the mistake: Problem 4 made PD conditional on linearly independent columns, and nothing has been said about the columns.
$w^* = (X^\top X)^{-1}X^\top y$ is the unique least-squares solution for any $X$ If two features are collinear, or there are more features than examples ( $d > N$ some $v \neq 0$ has $Xv = 0$ $X^\top X$ has a zero eigenvalue and is singular, and every $w^* + tv$ fits equally well: a whole line (or more) of minimisers, as in Problem 6's PSD case. Problem 1's $C = \begin{bmatrix}1&2\\2&4\end{bmatrix}$ is $X^\top X$ for the single row $X = (1, 2)$ and its null vector $(2, -1)^\top$ is the direction along which the fit cannot tell the features apart. Ridge adds $\lambda I$ and restores a unique solution (Problem 4), and the least-squares page's pseudoinverse picks the minimiser of smallest norm; both are choices, not consequences of the normal equations.

5. Choosing the gradient-descent step from the smallest eigenvalue

The slow direction is the one with the small eigenvalue, and the step is enlarged to speed it up.

The component of the error along $q_i$ scales by $1 - \eta\lambda_i$ per stepRight so far: Problem 9, step 2.
“The slowest direction is $\lambda_{\min}$ so pick $\eta$ to make $1 - \eta\lambda_{\min}$ small.”The habit that causes the mistake: Problem 9's convergence condition is on $\lambda_{\max}$ the step that is right for the flattest direction is far too long for the stiffest.
For $A = \operatorname{diag}(1, 10)$ take $\eta = 1 = 1/\lambda_{\min}$ which kills the slow component in one stepThe stiff component scales by $1 - 10 = -9$ after $k$ steps it is $(-9)^k$ times its start, so the iteration diverges, oscillating across the valley in ever larger swings. Any $\eta \ge 2/\lambda_{\max} = 0.2$ does this. The admissible range is $0 < \eta < 0.2$ the best choice is $\eta^* = 2/11$ (Problem 9), and the slow direction then shrinks by only $9/11$ per step: with a single step size the slow direction cannot be sped up without breaking the fast one, and that gap, $\kappa$ is what momentum (the optimisers page) and preconditioning exist to close.

Print this set: positive-definite-matrices-and-quadratic-forms.pdf (problems, answers, and worked solutions on separate pages).