Convexity of $\{x\in \mathbb R^n,\;x^TAx\leq t\}$ for all $t$ implies that $A$ is p.s.d.

Question

Let $A\in \mathbb R^{n\times n}$ be symmetric and such that for all $t\in \mathbb R$, the set $\{x\in \mathbb R^n,\;x^TAx\leq t\}$ is convex. Prove that $A$ is positive semi-definite.

It suffices to prove that the eigenvalues of $A$ are $\geq 0$. Consider $\lambda$ an eigenvalue of $A$ and $x$ an eigenvector with unit norm. Then the hypothesis rewrites as $(\lambda\leq t )\;\wedge (y^TAy\leq t) \implies \forall \mu \in [0,1], (1-\mu)^2\lambda +2 \mu(1-\mu)x^TAy + \mu^2y^TAy\leq t$.

If $y$ is an eigenvector with unit norm associated to some other eigenvalue $\lambda'$ with $\lambda'\leq t$, this rewrites as $(1-\mu)^2\lambda + \mu^2 \lambda'\leq t$. This is redundant as it already follows from $\lambda\leq t$ and $\lambda'\leq t$.

I don't see how to prove $\lambda\geq 0$ from $\forall \mu \in [0,1], (1-\mu)^2\lambda +2 \mu(1-\mu)x^TAy + \mu^2y^TAy\leq t$.

Answer 1

You don't need to consider two different eigenvalues. Let $\lambda_\min$ be the minimum eigenvalue of $A$ and $u$ be a corresponding unit eigenvector. Then $\{u,-u\}\subset C=\{x: x^TAx\le\lambda_\min\}$. However, by assumption, $C$ is convex. Therefore $x=\frac{u+(-u)}{2}=0\in C$, meaning that $0\le\lambda_\min$. Hence $A$ is positive semidefinite.

Answer 2

Suppose $y^TAy < 0$ and $L=\{x | x^T Ax \le y^TAy \}$ is convex. Since $(-y)^TA(-y) = y^TAy < 0$ then ${1 \over 2} (y+(-y)) = 0 \in L$, but this is a contradiction hence $y^T A y \ge 0$ for all $y$.