# Positive semi-definiteness result

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.

• You omit what about the mentioned answer "doesn't seem to be correct." The problem you pose seems to be asking for a proof of an if-and-only-if statement. Does one direction of the implications seem easier than the other? In short please add what work you've already done on this. Commented Nov 5, 2019 at 13:43

## 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$$.

• Nice find, I spent some time proving it but obviously without much success :) My two approaches where splitting up $x$ in two orthogonal parts (with one part in the kernel), and relating it to Appendix A.5.5. Commented Nov 7, 2019 at 20:14