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.

Let $\begin{bmatrix} A_{1} &B_1 \\ B_1' &C_1 \end{bmatrix}$, $\begin{bmatrix} A_2 &B_2 \\ B_2' &C_2 \end{bmatrix}$ be symmetric positive definite matrices and be conformably partitioned. If $\begin{bmatrix} A_{1} &B_1 \\ B_1' &C_1 \end{bmatrix}-\begin{bmatrix} A_2 &B_2 \\ B_2' &C_2 \end{bmatrix}$ is positive semidefinite, is it true $(A_1-B_1C^{-1}_1B_1')-(A_2-B_2C^{-1}_2B_2')$ also positive semidefinite? Here $X'$ means the transpose of $X$.

share|improve this question
1  
The more common term is "conformably partitioned". ;) –  J. M. Sep 2 '11 at 15:08
    
Thanks, changed. –  Sunni Sep 2 '11 at 15:44
    
My guess is either the answer is yes, or it become yes if you invert the order of subtraction. –  Michael Hardy Sep 2 '11 at 18:25
    
This is making me realize that my understanding of Wishart matrices is rusty. If $W_1$ and $W_2$ are independent matrix valued random variables with a Wishart distribution, then their sum is Wishart-distributed as well. So if $W_1$ and $W_2-W_1$ are Wishart-distributed and independent, then $W_2$ is Wishart distributed. And Schur complements within Wishart matrices are also Wishart-distributed. That much I'm sure of, and looking at en.wikipedia.org/wiki/Wishart_distribution, I'm surprised that the term "Schur complement" does not appear anywhere in the article. –  Michael Hardy Sep 2 '11 at 18:33
    
Note from alex' answer that the condition that the full matrices be individually positive definite can be weakened; it suffices that $C_2$ (and hence $C_1$) is positive definite. This condition, however, is required, since $$\begin{pmatrix}1&1\\1&1\end{pmatrix}-\begin{pmatrix}0&1\\1&-1\end{pmatrix}=\begi‌​n{pmatrix}1&0\\0&2\end{pmatrix}$$ would be a counterexample without it. –  joriki Sep 2 '11 at 19:42

3 Answers 3

up vote 4 down vote accepted

Yes, it does. The assumption $$\begin{bmatrix} A_{1} &B_1 \\ B_1^T &C_1 \end{bmatrix}-\begin{bmatrix} A_2 &B_2 \\ B_2^T &C_2 \end{bmatrix} \geq 0$$ implies that for any vector $\begin{pmatrix} x & y \end{pmatrix}$,

$$ \begin{pmatrix} x^T & y^T \end{pmatrix} \begin{bmatrix} A_{1} &B_1 \\ B_1^T &C_1 \end{bmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \geq \begin{pmatrix} x^T & y^T \end{pmatrix} \begin{bmatrix} A_2 &B_2 \\ B_2^T &C_2 \end{bmatrix} \begin{pmatrix} x \\ y \end{pmatrix}~~~~~(*)$$ But for any partitioned matrix,

$$\begin{pmatrix} x^T & y^T \end{pmatrix} \begin{bmatrix} A &B \\ B^T &C \end{bmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = (x + A^{-1} B y)^T A (x + A^{-1} B y) + y^T(C-B^T A^{-1} B)y.$$ Moreover, if the partitioned matrix on the left-hand side is positive definite, then each of the two terms on the right=hand side is positive. Thus picking arbitrary $y$ and $x = -A_1^{-1}B_1y$ in (*) gives

$$y^T(C_1-B_1^T A_1^{-1} B_1)y \geq \mbox{ something positive} + y^T(C_2-B_2^T A_2^{-1} B_2)y,$$ which implies

$$y^T(C_1-B_1^T A_1^{-1} B_1)y \geq y^T(C_2-B_2^T A_2^{-1} B_2)y,$$

which implies the conclusion you want.

share|improve this answer
    
Oops - I seem to have worked out the other Schur complement, i.e. the Schur complement of the $(2,2)$ block with respect to the $(1,1)$ block. I'm too lazy to rewrite, and this is of course equivalent to the question you ask. –  alex Sep 2 '11 at 18:38
    
Interesting -- if I understand correctly, "something positive" is positive because $A_2$ is positive definite -- it seems you've only used the positive definiteness of $A_2$ but not that of the full second matrix and not that of the first matrix? –  joriki Sep 2 '11 at 19:19
    
@joriki - good catch; you are right. I hope my proof is not wrong; it seems like it proves a little too much, but I looked through it again and I do not see an error. I suppose that because $A_2 \geq 0$ implies $A_1 \geq 0$ under the assumptions of the question, it does seem plausible. –  alex Sep 2 '11 at 19:29
    
I wasn't implying that there's something wrong -- in fact I'd looked for counterexamples before realizing that the full matrices are individually assumed to be positive definite, and the counterexample I found did have (in your swapped version) $A_1$ and $C_2$ positive definite but $A_2$ negative definite, so it makes sense that the positive definiteness of $A_2$ is the crucial requirement. –  joriki Sep 2 '11 at 19:38
    
Nice proof. Thanks. –  Sunni Sep 2 '11 at 22:29

For a general block matrix $X=\begin{pmatrix}A&B\\C&D\end{pmatrix}$, the Schur complement $S$ to the block $D$ satisfies $$ \begin{pmatrix}A&B\\C&D\end{pmatrix} =\begin{pmatrix}I&BD^{-1}\\&I\end{pmatrix} \begin{pmatrix}S\\&D\end{pmatrix} \begin{pmatrix}I\\D^{-1}C&I\end{pmatrix}. $$ So, when $X$ is Hermitian, $$ \begin{pmatrix}A&B\\B^\ast&D\end{pmatrix} =\begin{pmatrix}I&Y^\ast\\&I\end{pmatrix} \begin{pmatrix}S\\&D\end{pmatrix} \begin{pmatrix}I\\Y&I\end{pmatrix}\ \textrm{ for some } Y. $$ Hence $$ \begin{eqnarray} &&\begin{pmatrix}A_1&B_1\\B_1^\ast&D_1\end{pmatrix} \ge\begin{pmatrix}A_2&B_2\\B_2^\ast&D_2\end{pmatrix} \\ &\Rightarrow& \begin{pmatrix}S_1\\&D_1\end{pmatrix} \ge \begin{pmatrix}I&Z^\ast\\&I\end{pmatrix} \begin{pmatrix}S_2\\&D_2\end{pmatrix} \begin{pmatrix}I\\Z&I\end{pmatrix}\ \textrm{ for some } Z\\ &\Rightarrow& (x^\ast,0)\begin{pmatrix}S_1\\&D_1\end{pmatrix}\begin{pmatrix}x\\0\end{pmatrix} \ge (x^\ast,\ x^\ast Z^\ast) \begin{pmatrix}S_2\\&D_2\end{pmatrix} \begin{pmatrix}x\\Zx\end{pmatrix},\ \forall x\\ &\Rightarrow& x^\ast S_1 x \ \ge\ x^\ast S_2 x + (Zx)^\ast D_2 (Zx) \ \ge\ x^\ast S_2 x,\ \forall x\\ &\Rightarrow& S_1\ge S_2. \end{eqnarray} $$

Edit: In hindsight, this is essentially identical to alex's proof.

share|improve this answer
    
This would be a standard proof. –  Sunni Sep 2 '11 at 22:29

In control theory, this kind of inequalities is ubiquitous and handled via going back and forth using Schur complements. For completeness, here is the non-strict version of Schur complement formula, it is an overkill but the question is a particular special case, so here it goes:

Formula: Let $Q,R$ be symmetric matrices. Then following are equivalent:

  1. $$ \begin{pmatrix} Q &S\\ S^T &R \end{pmatrix} \succeq 0 $$

  2. $$\begin{align} R &\succeq 0\\ Q -SR^\dagger S^T &\succeq 0\\ S(I-RR^\dagger) &= 0 \end{align} $$ where $R^\dagger$ is the Pseudoinverse of $R$.


Now if renaming your hypothesis involving the matrix difference as $$ M_1 - M_2 := \begin{pmatrix} A_1 &B_1\\ B_1^T &C_1 \end{pmatrix} - \begin{pmatrix} A_2 &B_2\\ B_2^T &C_2 \end{pmatrix}\succeq 0$$

we can reformulate the hypothesis as the following via the second item of the formula ($Q=M_1,S=I,R=M_2^{-1}$): $$\begin{align} M_2^{-1} &\succeq 0 \quad \text{by definition}\\ M_1 - M_2 &\succeq 0\\ I (I-M_2M_2^{-1}) &= 0 \end{align} $$ hence we have $$ \begin{pmatrix} M_1 &I\\I&M_2^{-1} \end{pmatrix}\succeq 0 $$ Also, from the inverse of a matrix formula, we have $$ M_2^{-1} = \begin{pmatrix} (A_2 - B_2C_2^{-1}B_2^T)^{-1} &\star\\ \star &\star \end{pmatrix} $$ As user1551 showed, you can bring the matrix $M_1$ in the form of the following by a congruence transformation and some reshuffling: $$\begin{pmatrix} M_1 &I\\I&M_2^{-1} \end{pmatrix} \leadsto \left( \begin{array}{cc|cc} (A_1 - B_1C_1^{-1}B_1^T) &I &0 &0\\ I &(A_2 - B_2C_2^{-1}B_2^T)^{-1} &0 &\star\\ \hline 0 &0 &C_1 &I\\ 0&\star&I&\star \end{array}\right) \succeq 0 $$ The $(1,1)$ block matrix has the desired result if we apply the nonstrict Schur complement formula again but in the reverse direction.

Last minute addition: Now that I look at it, it is not as good as I thought it to be initially but I did not want to waste the whole thing so I hope it helps an $\epsilon$.

share|improve this answer
    
Thanks, I can see a simplest proof: Using $M_1\ge M_2$ is equivalent to $M_2^{-1}\ge M_1^{-1}$. Thus $M_2^{-1} = \begin{pmatrix} (A_2 - B_2C_2^{-1}B_2^T)^{-1} &\star\\ \star &\star \end{pmatrix}$... –  Sunni Sep 6 '11 at 0:03
    
@Sunni : Ah, yes. That's a clever shortcut. –  user13838 Sep 6 '11 at 8:35

Your Answer

 
discard

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.