# Inequality of two symmetric matrices

Given a full rank $n \times m$ matrix $K$ with $m<n$ and an invertible symmetric matrix $J$. Let $A$ be a symmetric positive semi-definite $n \times n$ matrix such that $$(K^T K)^{-1}K^TAK(K^TK)^{-1}-(K^TJK)^{-1}$$ is positive semi-definite. I'd like to prove that $$A-K(K^TJK)^{-1}K^T$$ is also positive semi-definite.

This is my investigation: \begin{align*} (K^T K)^{-1}K^TAK(K^TK)^{-1}\geq(K^TJK)^{-1}\iff K^TAK\geq K^T K(K^TJK)^{-1}K^T K \end{align*} by multiplying RHS by $K^T K$ from left and right. But, I am not sure if we can multiply bu such matrices and I don't know what I do then. Could anyone help me? Thanks in advance.

-

$K$ has full rank $m$, hence the $m\times m$ matrix $K^T K$ is invertible (has rank $m$), so talking about its inverse makes sense. Note that the $n\times n$ matrix $K K^T$ would not be invertible.

Yes, your operation is valid, since $U=(K^TK)^{-1}$ is a self-adjoint invertible matrix. Therefore

$$A\le B\,\Leftrightarrow\,UAU\le UBU$$

The right hand side means that $x^TU(B-A)Ux\ge 0$ for all $x$, but since $U=U^T$ that means with $y=Ux$

$$0\le (Ux)^T (B-A) Ux=y^T (B-A) y$$

for all $y$ (since $U$ is invertible).

Now let us try to prove that $A-K(K^TJK)^{-1}K^T$ is positive semidefinite. Let $B=(K^TJK)^{-1}$. Remember that $K$ is a linear map $\mathbb{R}^m\rightarrow\mathbb{R}^n$, sending $x\in\mathbb{R}^m$ to $Kx\in\mathbb{R}^n$. Let us denote the $m$-dimensional image of that map by $V=\mathrm{Im} K\subset\mathbb{R}^n$.

Then $\mathbb{R}^n=V\oplus V^\perp$.

For $y\in\mathbb{R}^n$ we write $y=y_0+y_1$ with $y_0\in V$ and $y_1\in V^\perp$.

We have to show that

$$y^T (A-KBK^T) y\ge 0\tag{1}$$

To prove this we will try to use the decomposition $y=y_0+y_1$ and our assumptions. We first prove two lemmas.

Claim 1: If $y_0\in V$, then $$y_0^T (A-KBK^T) y_0\ge 0$$

Proof: Since $y_0\in V$, we can write $y_0=Kx$ for some $x\in\mathbb{R}^m$. Therefore

$$y_0^T (A-KBK^T) y_0=x^T K^T(A-KBK^T)K x\ge 0$$

where the last inequality follows because we have already shown $K^T AK\ge K^T K B K^T K$.

$\square$

Claim 2: Let $y_0,y_1$ be as above. If $i=1$ or $j=1$, then $$y_i^T KBK^T y_j=0$$

Proof: Since $y_1\in V^\perp$, we have $0=\langle y_1, Kx\rangle=\langle K^T y_1, x\rangle$ for all $x\in\mathbb{R}^m$. Now let $i=1$ and $j\in\{0,1\}$. Then

$$y_1^T KBK^T y_j=(K^T y_1)^T (BK^T y_j)=\langle K^T y_1, BK^T y_j\rangle=0.$$

Now let $j=1$ and $i\in\{0,1\}$. Then

$$y_i^T KBK^T y_1=(KB^TK^T y_i)^T y_1=\langle KB^TK^T y_i, y_1\rangle=0$$

$\square$

Using these ideas you should be able to finish it.

-
Thanks @TooOldForMath. But, is my conjecture right? – Jlamprong Jan 29 '14 at 10:37
Thanks. So, how to derive to the inequality that will be proven? Any suggestion? – Jlamprong Jan 29 '14 at 10:59
Yes, I have read your edit. I mean that do you have any suggestion in proving $A\geq K(K^TJK)^{-1}K^T$ – Jlamprong Jan 29 '14 at 11:05
@Jlamprong: Yes, I noticed that. We end up with having to prove $y_0^T Ay_1+y_1^TAy_0+y_1A^Ty_1\ge 0$. Adding and subtracting $y_0A^Ty_0$ this is equivalent to $y^TAy\ge y_0^T Ay_0$. Considering the fact that all our estimates were sharp and we didn't let anything go to waste I assume that this is a necessary condition for the statement to be true, i.e. you need some more information about how $A$ and $K$ are related. – Your Ad Here Jan 29 '14 at 23:06