If $Q$ is positive semidefinite and $x^TPx>0$, $\forall x\neq 0$ with $x^TQx=0$, then $P+cQ$ is positive definite if $c$ is sufficiently large?

Question

The following is Lemma 3.2.1 in Nonlinear Programming, 2nd edition by Dimitri P. Bertsekas.

---

---

Let $P$ and $Q$ be two symmetric matrices. Assume that $Q$ is positive semidefinite and $P$ is positive definite on the nullspace of Q, that is, $x^TPx>0$, for all $x\neq 0$ with $x^TQx=0$, then there exists a scalar $\bar{c}$ such that $P+cQ$ is positive definite, $\forall c>\bar{c}$.

For proof, the author first assumes the contrary and says:

Then for every integer $k$, there exists a vector $x^k$ with $\|x^k\|=1$ such that $$(x^k)^T P x^k + k (x^k)^T Q x^k \leq 0$$

But I think the contrary of this lemma should be: For any $\bar{c}$, there exists a $c>\bar{c}$ such that $P+cQ$ is not positive definite, instead of: $P+kQ$ is not positive definite for any integer $k$. Did the author make a mistake?

Answer 1

As noted in the comments, if $P + cQ$ is positive definite for some $c$ then $P + c'Q = (P + cQ) + (c' - c) Q$ is positive definite for every $c' \ge c$. So the conclusion of the lemma is equivalent to: $P + cQ$ is positive definite for some $c$.

Answer 2

Here is a more direct proof.

First consider the equation $ax^2-bxy+c y^2$ with $c>0$. Then there exists some $\overline{a}$ such that if $a > \overline{a}$, then $ax^2 -|b||xy|+c y^2 > 0$ for all $x,y$ such that $x^2+y^2 = 1$.

To see this, note that $({|b| \over \sqrt{2c}}|x|-\sqrt{c \over 2}|y)^2 = {b^2 \over 2c} x^2 -|b||xy| + {c \over 2} y^2 \ge 0$. Choose $\overline{a} = {b^2 \over 2c}$, then, if $a > \overline{a}$, then $ax^2 -|b||xy|+c y^2 = (a-{b^2 \over 2c}) x^2 + {c \over 2} y^2 + ({|b| \over \sqrt{2c}}|x|-\sqrt{c \over 2}|y)^2 \ge \min(a-\overline{a},{c \over 2}) > 0$.

Now choose a basis consisting of $(\ker Q)^\bot$ and $\ker Q$. Then $Q,P$ have the form $Q=\begin{bmatrix} Q_{11} & 0 \\ 0 & 0 \end{bmatrix}$ and $P=\begin{bmatrix} P_{11} & P_{12} \\ P_{12} & P_{22} \end{bmatrix}$, where $Q_{11}>0, P_{22} >0$.

Note that we can write any unit vector $x=x_1+x_2$ where $x_1 \bot \ker Q, x_2 \in \ker Q$ and $\|x_1\|^2 + \|x_2\|^2 = 1$.

Then \begin{eqnarray} x^T(P+cQ)x &=& x_1^T (P_{11}+cQ_{11})x_1 + 2x_1 P_{12}x_2 + x_2^T P_{22} x_2 \\ &\ge& (\underline{\lambda} P_{11}+c \underline{\lambda} Q_{11}) \|x_1\|^2-2\|P_{12}\| \|x_1\| \|x_2\| + (\underline{\lambda} P_{22}) \|x_2\|^2 \end{eqnarray} Then the above shows that there is some $\overline{c}$ such that if $c> \overline{c}$, then $x^T(P+cQ)x >0$ for all $\|x\|=1$.