A quadratic function bounded from below

Question

Let $A\in\mathbb{R}^{n\times n}$ be a symmetric matrix such that the quadratic function $$f(x)=x^\top Ax-2(x_1+\ldots+x_n)$$ is uniformly bounded from below by a constant. Does it imply that $A$ is positive definite?

By using the eigenvalue decompostion of $A$ and making orthogonal transformations for $x$, we can easily show that $A$ must be positive semidefinite. Is it necessary that $A$ is positive definite in this case?

Answer 1

No, $A$ does not need to be positive definite. Consider the matrix $$A=\begin{bmatrix} 1 & 1 \\ 1 & 1\end{bmatrix}$$

This matrix is symmetric with $$f(x,y)=x(x+y)+y(x+y)-2(x+y)=(x+y-2)(x+y)$$

This functions is bounded below. Letting $c=x+y$, then this reads $f(x,y)=c^2-2c$, which attains a minimum of $-1$ when $c=1$, so $f$ is bounded below. However, $A$ is not positive definite, since one of its eigenvalues is $0$. In particular, for $x=\begin{bmatrix} 1 \\ -1\end{bmatrix}$ satisfies $x^TAx=0$.

Answer 2

The function $g_{A,b}(x):=x^tAx+b^tx$ (with $A$ symmetric) is bounded below if and only if $A$ is positive semidefinite and $\ker A\subseteq b^{\perp}$. In fact, let $x\in(\ker A)\setminus b^{\perp}$ (positive semidefiniteness is clearly necessary). Then, $b^tx\ne 0$, $x^tAx=0$, and $\lim\limits_{\lambda\to-\infty} g(\lambda (b^tx)x)=-\infty$. On the other hand, if $\ker A\subseteq b^{\perp}$, then consider a subspace $W$ such that $W\oplus \ker A=\Bbb R^n$. Then, $$\inf_{x\in\Bbb R^n}g_{A,b}(x)\stackrel{\text{since }\forall x\in\ker A,\ b^tx=0}=\inf_{x\in W}g_{A,b}(x)=\\=\inf_{x\in W} x^tAx+b^tx=\inf_{x\in W\\ \lVert x\rVert=1\\ \lambda\ge0} \lambda^2x^tAx+\lambda b^tx\ge\\\ge\inf_{\lambda\ge 0}\left(\lambda^2\left(\min_{x\in W\\ \lVert x\rVert=1}x^tAx\right)+\lambda\left(\min_{x\in W\\ \lVert x\rVert=1} b^tx\right)\right)$$

Since $W\cap \ker A=\{0\}$ and $A$ is positive semidefinite, the quantity $\alpha:=\min_{x\in W\\ \lVert x\rVert=1}x^tAx$ is strictly positive. If $\beta:=\min_{x\in W\\ \lVert x\rVert=1} b^tx$, we have bounded below $g_{A,b}(x)$ by the quantity $\min\limits_{\lambda\in\Bbb R}\alpha\lambda^2+\beta\lambda=-\frac{\beta^2}{4\alpha}$.