Conditions for non-negativity of 2nd-order polynomial with several variables Sorry, if I forget to specify something, I am an engineer and we are usually not very specific when we try to talk math. I am familiar with positive definite matrices and basic linear algebra. I am interested in scalar valued non-negative 2nd-order polynomials $p(x)$ with several variables $x \in \mathbb{R}^n$, expressed as
\begin{equation}
p(x)
=
x^T A x + b^T x
\geq 0 \ \forall x
\end{equation}
with the matrix $A \in \mathbb{R}^{n \times n}$ and the vector $b \in \mathbb{R}^{n}$. I am interested in the conditions for the non-negativity of the polynomial. For $b=0$, I know that $A$ has to be positive semidefinite. But for $b \neq 0$, what are the conditions for $A$ and $b$? 
My attempt is to complete the square, which, defining $(A+A^T)y = b$, gives
\begin{equation}
p(x) 
=
(x+y)^TA(x+y) - y^T Ay \geq 0 \ \forall x \ . 
\end{equation} 
From this perspective, I think that $A$ has to be positive semidefinite and $-y^T Ay = - b^T(A+A^T)^{-T}A(A+A^T)^{-1}b \geq 0$ is the coupling condition which $A$ and $b$ have to fulfill. Is there any other condition that I might be missing? My perspective is still somehow bizarre, since, if I restrict myself to positive definite and symmetric $A$, then $(A+A^T)^{-T}A(A+A^T)^{-1}$ is positive definite and there exists no $b$ (besides ($b=0$) to ensure non-negativity. Am I doing something wrong? Thanks!
EDIT (after Hagen's answer)
I prefer to edit this question, instead of creating a new one. If we extend the polynomial by a constant $c$ as
$$
q(x) = x^T A x + b^T x + c \geq 0 \quad \forall x
$$
for a general (not necessarily symmetric or even diagonalizable) real matrix $A \in \mathbb{R}^{n \times n}$, the vector $b \in \mathbb{R}^{n}$ and the real constant $c \in \mathbb{R}$, what are the conditions on $A,b$ and $c$? 
1) As Hagen pointed out, if $c=0$, then $b=0$ is necessary and the condition on $A$ is positive semidefiniteness. 
2) For $c>0$, the square might be completed as above with $b = (A+A^T)y$ as
$$
q(x)
=
(x+y)^TA(x+y) + (c-y^TAy) \geq 0 \quad \forall x 
$$
which is fulfilled if $A$ is positive semidefinite and a $b$ exists fulfilling $c \geq y^T A y = b^T (A+A^T)^{-T}A(A+A^T)^{-1}b > 0$. But here I am not able to see, under which conditions for $A$ such $b$ even exists, since, e.g., the matrix
$$
A = 
\begin{bmatrix}
1 & 3 \\
0 & 1
\end{bmatrix}
$$
is non-diagonalizable, positive definite (eigenvalues $\{1,1\}$), its symmetric part $A+A^T$ is invertible (eigenvalues $\{5,-1\}$), but the matrix $(A+A^T)^{-T}A(A+A^T)^{-1}$ is negative definite (eigenvalues $\left\{-\frac{1}{5},-\frac{1}{5}\right\}$) such that no $b$ exist for this exemplary $A$. 
So, what are the full conditions on $A,b$ and $c$ such that $q(x) \geq 0 \forall x$?
Last edit
Sorry, I had the property of positive definiteness wrong in my head. The exemplary $A$ given above is NOT positive definite, since its symmetric part is indefinite.
I just realized that for homogeneous polynomials $x^T A x$ only the symmetric part of $A$ is relevant, i.e., we have to consider only symmetric $A$ (assumed from this point on). If $A$ is symmetric, then it is diagonalizable. I can consider now the change of basis $x = R \xi, R \in \mathbb{R}^{n \times n}, \xi \in \mathbb{R}^n$, with the diagonal matrix $\Lambda = R^T A R$ having the eigenvalues $\lambda_i$ of $A$. The polynomial $q$ is then expressed as
$$
q 
= x^T A x + b^T x + c
= \xi^T \Lambda \xi + \beta^T \xi + c
= \left(
\sum_{i=1}^n \lambda_i \xi_i^2 + \beta_i \xi_i
\right) + c
$$
with $\beta = R^T b$. For $A$, let the last $m$ eigenvalues vanish. We can reformuate $q$ now as
\begin{eqnarray}
q
&=& 
\left(
\sum_{i=1}^{n-m} \lambda_i \xi_i^2 + \beta_i \xi_i
\right) + c
+
\sum_{i=n-m+1}^{n} \beta_i \xi_i
\\
&=&
\left(
\sum_{i=1}^{n-m} \lambda_i \left[\xi_i + \frac{\beta_i}{2 \lambda_i}\right]^2 
\right) 
+ 
\left(
c
-
\sum_{i=1}^{n-m}
\frac{\beta_i^2}{4 \lambda_i}
\right)
+
\sum_{i=n-m+1}^{n} \beta_i \xi_i
\geq 0 \quad \forall \xi
\end{eqnarray}
It is then visible, that the non-vanishing eigenvalues of $A$ have to be positive and that the $b$ have to fulfill $\beta_i = 0 , i \in \{n-m+1,\dots,n\}$ and $\sum_{i=1}^{n-m} \beta_i^2/(4\lambda_i) \in [0,c]$ for $0\leq c$. Did I miss anything?
 A: If $b\ne 0$, then 
$p(-cb)=c^2\cdot b^TAb-c\cdot b^Tb\sim -cb^Tb<0$ for small positive $c$, hence $b=0$ is necessary.
But if $b=0$, then the desired property id by definition equivalent to $A$ being positive semi-definite.
A: First, note that $A+A^T$ must be positive semi-definite (p.s.d.), since:
$$q(x)=\frac{1}{2} x^T ( A + A^T ) x + b^T x + c,$$
so if $( A + A^T )$ has a negative eigenvalue with corresponding eigenvector $v$, then $q(k v)\rightarrow -\infty$ as $k\rightarrow \infty$.
Given that $( A + A^T )$ is p.s.d., all the stationary points of $q$ are global minima, and if $q$ has no stationary points, then $q$ is unbounded.
Now, the stationary points of $q$ satisfy:
$$0=\frac{d q(x)}{d x} = x^T ( A + A^T ) + b^T$$
i.e.:
$$( A + A^T )x=-b.$$
By the Schur decomposition and the spectral properties of p.s.d. symmetric matrices, there exists an orthogonal matrix $U$ and a diagonal matrix $D$ with weakly positive elements, decreasing in magnitude, such that:
$$A+A^T=U D U^T.$$
Hence:
$$U D U^T x=-b.$$
Now partition $U$ as $U=\begin{bmatrix}U_{\cdot 1} & U_{\cdot 2}\end{bmatrix}$, where the number of columns of $U_{\cdot 1}$ is the same as the number of non-zero elements of $D$. Likewise, partition $D$ as $D=\begin{bmatrix}D_{11} & 0 \\ 0 & 0\end{bmatrix}$. Then:
$$U_{\cdot 1} D_{11} U_{\cdot 1}^T x=-b.$$
Since $U$ is orthogonal, $U_{\cdot 1}^T U_{\cdot 1}=I$ (as it is the upper left block of $U^T U$) and $U_{\cdot 2}^T U_{\cdot 1}=0$ (as it is the lower left block of $U^T U$). Thus:
$$U_{\cdot 1}^T x=-D_{11}^{-1} U_{\cdot 1}^T b,$$
$$0 = U_{\cdot 2}^T b.$$
If the second condition is violated (e.g. when $q(x,y)=x^2+y$), then there can be no stationary points of $q$, hence $q$ is unbounded (and certainly not always positive). Suppose then that the second condition is satisfied.
Now, as $U$ is full rank, we can find $d,e,y,z$ such that $x=U_{\cdot 1} y + U_{\cdot 2} z$ and $b=U_{\cdot 1} d + U_{\cdot 2} e$. Thus the previous two conditions become:
$$U_{\cdot 1}^T ( U_{\cdot 1} y + U_{\cdot 2} z )=y=-D_{11}^{-1} U_{\cdot 1}^T b,$$
$$0 = U_{\cdot 2}^T (U_{\cdot 1} d + U_{\cdot 2} e) =e,$$
so $z$ is unrestricted, and:
$$y=-D_{11}^{-1} U_{\cdot 1}^T U_{\cdot 1} d=-D_{11}^{-1} d.$$
Finally, to see if $q$ is always positive when $b=U_{\cdot 1} d$, pick an arbitrary $z$ (e.g. $z=0$) and substitute the expression for the stationary point into $q$. If the result is positive then $q$ is always positive. I.e. assuming $b=U_{\cdot 1} d$, $q$ is always positive if and only if:
$$\frac{1}{2} d^T D_{11}^{-1} U_{\cdot 1}^T U_{\cdot 1} D_{11} U_{\cdot 1}^T U_{\cdot 1} D_{11}^{-1} d - d^T U_{\cdot 1}^T U_{\cdot 1} D_{11}^{-1} d + c\ge 0$$
i.e. if and only if:
$$c\ge \frac{1}{2} d^T D_{11}^{-1} d.$$
To conclude then, we have three conditions to check. $q(x)\ge 0$ for all $x$ if and only if:


*

*$A+A^T$ is p.s.d..

*$c\ge \frac{1}{2} b^T U_{\cdot 1} D_{11}^{-1} U_{\cdot 1}^T b$.

*$0 = U_{\cdot 2}^T b$.

