Positive semi-definiteness result

Question

Disclaimer: This question had already been asked here Proof for certain matrix results?. However, the only answer provided there doesn't seem to be correct, so I'm re-stating it here (if this is not the expected procedure, please let me know.)

---

In the book Convex Optimization (Boyd-Vanderberghe), Chapter 3, Exercise 3.9 b) there is a hint whose proof I would love to learn:

If $B\in S^n$ and $A\in{\Bbb R}^{p\times n}$, then $x^TBx\ge0$ for all $x\in{\rm ker}(A)$ if, and only if, there exists $\lambda$ such that $B+\lambda A^TA\succeq0$.

---

The if part can be verified easily, so the problem is with the only if one. Unfortunately, the answer given to the old question doesn't prove the result at all (clearly). I've tried to relate this result with the fact that the minimum eigenvalue of $B$ equals $\min x^TBx$ for $\Vert x\Vert = 1$ without luck.

More information. The solution to Exercise 3.44 a) published by the authors of the book includes a proof of this result for the particular case $p=1$, i.e., when $A$ is a row vector.

Unfortunately, the published proof (for $p=1$) has a mistake that renders the expression of the Schur complement incorrect.

Answer 1

The result is not true

Here is a counter-example for the case $n=2$, $p=1$: $$ B = \begin{pmatrix} -1 &0 \\ 0 &1 \end{pmatrix}, \qquad A = \begin{bmatrix}-1\\1\end{bmatrix}. $$ The hypothesis is satisfied because ${\rm ker}\, A$ is generated by $(1,1)^T$ and $$ (1,1)\,B\,{1\choose1} = (1,1){-1\choose1} = 0 \ge 0. $$ However, for any $\lambda$ $$ B + \lambda AA^T = \begin{pmatrix} -1 &0\\ 0 &1 \end{pmatrix} + \lambda\begin{pmatrix} 1 &-1\\ -1 & 1 \end{pmatrix} = \begin{pmatrix} -1+\lambda &-\lambda\\ -\lambda & 1 + \lambda \end{pmatrix} $$ whose characteristic polynomial $\chi(t) = t^2 -2\lambda t - 1$ has the negative root $\lambda - \sqrt{\lambda^2+1}$.

---

In the context of exercise 3.44 the counterexample corresponds to, e.g., $f(x,y)=-e^x + e^y$ at $(0,0)$.

---

In the context of exercise 3.9 a contraexample would be $f(x,y) = -e^x + e^y + x$, $A$ as above, $\hat{x} = (0,0)^T$ and $$ F = \begin{bmatrix} 1 &0 \\ 1 &0 \end{bmatrix}. $$ Then $$ Fz = (z_1, z_1)^T\qquad{\rm and}\qquad\tilde{f}(z) = z_1 $$ so $\nabla^2f(Fz+\hat{x})= B$ at $z=(0,0)^T$.