Norm inequality of positive semidefinite linear functions

Question

Let $A, B$ be two $n\times n$ positive semi-definite matrix. Then there is some $c,d\ge 0$ such that

$$\left\|Ax\right\|\le c+d\left\|Ax+Bx\right\|\text{ for all }x\in\mathbb{R}^n,$$

where the norm using is Euclidean. This inequality is trivially true when $n=1$ since we can choose $c=0$, $d=1$. However, I do not know how to proceed with the case when $n\ge 2$.

Thanks a lot for your help.

Answer 1

Let $N= \ker (A+B)$. Note that $N \subset \ker A$.

Let $\beta = \min_{ x \in N^\bot, \|x\| = 1} \|(A+B)x\|$, note that $\beta >0$.

Let $x=x_1+x_2$ where $x_1 \in N, x_2 \bot x_1$. Then $\|Ax\| = \|Ax_2\|\le \|A\|\|x_2\| \le {\|A\| \over \beta} \|(A+B)x_2\| = {\|A\| \over \beta} \|(A+B)x\| $

Elaboration:

Suppose $x \in \ker (A+B)$, then $x^TAx + x^TBx = 0$ and so $x^TAx = 0$. Since $A$ is positive semidefinite we have $Ax=0$ and so $x \in \ker A$.

As further elaboration (stolen from http://www.seas.ucla.edu/~vandenbe/133B/lectures/psd.pdf) , if $x^TAx = 0$ and $A \ge 0$, then $f(t) = (x-tAx)^T A (x-tAx) = -2t \|Ax\|^2 + t^2 x^T A^3 x \ge 0$ for all $t$ and so $Ax=0$.

Answer 2

HINT:

First notice that for $A$,$B$ positive semidefinite, with $A\preceq B$, we have $\|\sqrt{A} x\|^2 = \langle A x, x\rangle \le \langle B x, x\rangle =\|\sqrt{B} x\|^2$ for all $x$.

Then notice notice that for $A$ positive semidefinite we have

$$\|A x\|^2 = \sum \lambda_i^2 (A)\, x_i^2 \\ \|\sqrt{A} x\|^2= \sum \lambda_i(A)\, x_i^2 $$

We get

$$\| A x\|^2 \le \lambda_{\textrm{max}}(A) \cdot \|\sqrt{A} x\|^2 \\ \|\sqrt{B} x\|^2 \le \frac{1}{\lambda_{\textrm{min} ^+}(B)} \|B x\|^2$$

so

$$\|A x\| \le \sqrt{\frac{\lambda_{\textrm{max}}(A)}{\lambda_{\textrm{min} ^+}(B)} }\cdot \|B x\|$$

where $\lambda_{\textrm{min} ^+}(B)$ is the smallest eigenvalue of $B$ that is not $0$.