# Proof of a matrix is positive semi-definite

For $\ i = 0, 1, \cdots m$, $f_{i}(x): R^n \rightarrow R$ is defined to be $$f_i(x) = x^TQ_ix + 2p_i^Tx + r_i$$ , where $Q_0 \cdots Q_m$ are real symmetric matrices, $p_0 \cdots p_m \in R^n$, and $r_0 \cdots r_m \in R$.

Now, for all $x$ in $R^n$, $f_{0}(x) \geq \sum_{i=1}^{m}t_if_i(x)$ holds ($t_1, \cdots, t_m \in R$).

Please show that the following matrix is positive semi-definite. $$\begin{pmatrix} Q_0 & p_0\\ p_0^T & r_0 \end{pmatrix} -\sum_{i=1}^{m}t_i \begin{pmatrix} Q_i & p_i\\ p_i^T & r_i \end{pmatrix}$$

• I think the essence of this problem is:$$\begin{pmatrix}x^T & 1 \end{pmatrix} \begin{pmatrix}Q & p\\p^T & r \end{pmatrix}\begin{pmatrix}x \\ 1 \end{pmatrix} \geq 0 \Leftrightarrow \begin{pmatrix}\xi^T & \eta \end{pmatrix} \begin{pmatrix}Q & p\\p^T & r \end{pmatrix}\begin{pmatrix}\xi \\ \eta \end{pmatrix} \geq 0$$, for all $x, \xi \in R^n, y \in R$. I have difficulty in showing $r=0\Rightarrow p=0$, which is very important part of my solution. – dazaga Aug 10 '14 at 8:50
• It follows from my proof. – Alexander Vigodner Aug 10 '14 at 15:09

EDITED version

You assume that $F(x)=x^TQx+2p^Tx+r\ge 0$ for all $x$ where $Q=Q_0-\sum_1^m t_iQ_i$, $p=p_0-\sum_1^m t_ip_i$, $r=r_0-\sum_1^m t_ir_i$. This implies

1. $F(0)=r\ge 0$.

2. $Q$ is positively semi-definite.

3. $p=QQ^+p$, namely $Qx=0$ implies $p^Tx=0$.

Thus $F(x)$ can be rewritten in the following from $$F(x)=(x+Q^+p)^TQ(x+Q^+p)+r-p^TQ^+p$$ Then $r\ge p^TQ^+p$. Now the property we want to prove that for for any $x,a$:

$$F(x,a)=x^TQx+2ap^Tx+a^2r\ge 0$$ We can rewrite: $$F(x,a)=(x+aQ^+p)^TQ(x+aQ^+p)+a^2r-a^2p^TQ^+p\ge a^2r-a^2p^TQ^+p=a^2(r-p^TQ^+p)\ge 0$$

• I can't figure out what Q^+ implies. Please tell me! – dazaga Aug 10 '14 at 2:05
• $Q^+$ is pseudo-inverse matrix of $Q$, generalization of inverse when $Q$ is singular. One of it's properties is $Q^+QQ^+=Q^+$ and if $Qy=p$ and $Qs=0$ iff $p^Ts=0$ then $QQ^+p=p$ and $y=Q^+p$. – Alexander Vigodner Aug 10 '14 at 2:35
• How do you find $Q$ is positive semi-definite? – dazaga Aug 10 '14 at 3:13
• In the symmetric case, it means that the minimum eigenvalue is zero or greater. – Michael Grant Aug 10 '14 at 3:18
• This may be trivial, but I think $r > 0$ is false and $r\geq0$ is true. – dazaga Aug 10 '14 at 7:02