Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 5 / b / ii / Solution

The gradient vanishes at $0$. Decompose any vector as $x=tb+w$, with $w\perp b$. Symmetry of $A$ and $Ab=\frac{1}{2}b$ imply $b^{T}Aw=(Ab{)}^{T}w=0$. Since $\Vert b\Vert =1$,If $d\ge 2$, choose a nonzero $w\perp b$. Arbitrarily close to zero, the direction $b$ gives negative values and the direction $w$ gives positive values. Thus $0$ is a saddle point for $d\ge 2$. Equivalently, the Hessian matrix has one negative eigenvalue and all its other eigenvalues positive.

The dimension matters: if $d=1$, the orthogonal complement is zero-dimensional and $g(tb)=-t^2/2$. In that case $0$ is the unique global maximum. This edge case is not excluded by the stated hypotheses. The decomposition is a rank-one downdate along an eigenvector.