Question about infimum of a quadratic form

Question

Let $A$ a symmetric real matrix. Consider $$ q(x)=x^T A x +b^T x $$ for $x \in \mathbb R^n$. I want to prove that $\inf_{x} q(x)>-\infty$ iff $A$ Is semi definite positive matrix and $b\in \mbox{range}(A)$.

It is plausible to see that if A is not semi definite positive, then since $x^T A x$ grows faster than the linear term, $q(x)$ is more and more negative, but I need to find a formal argument for this. And I am not sure why $b$ has to be in the range of $A$. Any help will be appreciated.

Answer 1

Following your ideas, suppose $A$ is not semipositive-definite, and take $x$ such that $x^T A x<0.$ Then for any positive number $t,$ we have $$ (tx)^T A (tx) + b^T (tx) = (x^T A x)t^2 + (b^Tx) t, $$ which is a quadratic polynomial of $t$ with negative coefficient at the quadratic term, so it does not admit finite infimum.

For the second condition, suppose $b$ does not belong to the range of $A.$ By the argument above, we know $A$ is semipositive-definite. As a result we know that $A$ could not be positive-definite, or the range of $A$ would be the whole space. Therefore, $A$ admits non-trivial kernel. Note that since $A$ is symmetric, we have $$ {\rm im }~A = (\ker A)^\perp. $$ As a result, there exists $x\in\ker A$ such that $b^T x\neq 0$ (or $b$ would belong to the range of $A$). Then for any real number $t,$ $$ (tx)^T A (tx) + b^T (tx) = t (b^T x) $$ could be arbitrary large and small.

Answer 2

There exists a real invertible matrix $P$ such that $P^TAP$ is diagonal. Let $x=Py$. Then $$x^TAx+b^Tx=y^TP^TAPy+(P^Tb)^Ty.$$ Note that $b$ is in the range of $A$ iff $b$ is in the range of $AP$ iff $P^Tb$ is in the range of $P^TAP.$ Let $M=P^TAP.$ Let $$S=\{\nu_1, ... ,\nu_{\rho}\}=\{i|m_{ii}=0\}.$$ (If $A$ is positive-definite, $S$ is empty. ) The range of $P^TAP$ consists exactly of those column-vectors whose $i-$ th entry is 0 for $i \in S.$ When the expression $y^TP^TAPy+(P^Tb)^Ty$ is written as $$m_{11}y_1^2+...+m_{nn}y_{n}^2+c_1y_1+...+c_ny_n$$ we say that a term $c_i$ is $orphaned$ if $m_{ii}=0 \text { and } c_i \ne 0.$ Thus there are no orphaned terms iff $b$ is in the range of $A.$ Now suppose that $A$ is positive semi-definite and $b$ is in the range of $A.$ Then in the expression $$m_{11}y_1^2+...+m_{nn}y_{n}^2+c_1y_1+...+c_ny_n$$ we can 'complete the square' in each variable $y_i$ and so obtain a lower bound. Conversely, suppose that $A$ is not positive semi-definite or that $b$ is not in the range of $A.$ First we deal with the case that $b$ is not in the range of $A.$ Then there exists $i$ such that $m_{ii}=0 \text { and } c_i \ne 0.$ Let $y_j=0$ for $j \ne i.$ Then by making $y_i$ positive enough or negative enough, depending on the sign of $c_i$ we can make the whole expression arbitrarily negative. Now we look at the case that $A$ is not positive semi-definite. Then $m_{ii}<0$ for some $i.$ Let $y_j=0$ for $j \ne i.$ By completing the square in $y_i$ we can choose $y_i$ so as to make the whole expression arbitrarily negative.