Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 \begin{equation} (K^T K)^{-1}K^TAK(K^TK)^{-1}-(K^TJK)^{-1} \end{equation} is positive semi-definite. I'd like to prove that \begin{equation} A-K(K^TJK)^{-1}K^T \end{equation} 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.

share|improve this question

1 Answer 1

$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$.


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$$


Using these ideas you should be able to finish it.

share|improve this answer
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
@JLamprong Edited to answer your question. –  Your Ad Here Jan 29 '14 at 11:01
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.