Let $P\geq0$, $P\in\mathbb{R}^{n\times n}$. For every $A\in\mathbb{R}^{n\times n}$ there exists $c\geq0$: $A^\top P+PA\leq cP$.

Question

I want to prove/disprove the following claim.

Claim. Let $P\geq0$, $P\in\mathbb{R}^{n\times n}$. For every $A\in\mathbb{R}^{n\times n}$ there exists $c\geq0$: $$A^\top P+PA\leq cP.$$

Draft of the proof. Let $x\in\mathbb{R}^n$. Either $x\in\mathrm{Ker}\hspace{.5mm} P$, i.e., $x^\top Px=0$, or $x\notin\mathrm{Ker}\hspace{.5mm}P$, i.e., $x^\top Px>0$. If $x\in\mathrm{Ker}\hspace{.5mm}P$, then $c=0$ satisfies the above. If $x\notin\mathrm{Ker}\hspace{.5mm}P$, then the above is equivalent to $$\frac{x^\top(A^\top P+PA)x}{x^\top Px}\leq c\dots$$

Then, I guess that from here I need to play with estimates, but I do not know how exactly.

Answer 1

The claim is not true. Take $ P = \begin{pmatrix} 1 & 0 \\ 0 & 0\end{pmatrix}$ and $A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$. Then, \begin{align} A^T P + P A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}. \end{align} For $c \geq 0$, \begin{align} c P - (A^T P + P A) = \begin{pmatrix} c & -1 \\ -1 & 0 \end{pmatrix}. \end{align} The eigenvalues of this matrix are $\frac{c \pm \sqrt{c^2 + 4}}{2}$. Hence, there is always a negative eigenvalue.

Answer 2

This is false. E.g. $$ A=\pmatrix{1&1\\ 1&1},\quad P=\pmatrix{1&0\\ 0&0} \implies cP-(A^\top P+PA)=\pmatrix{c-2&-1\\ -1&0} $$ but the latter is indefinite for every real number $c$.