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 $B \in \mathbb{R}^{n \times n}, C \in \mathbb{R}^{m \times n}, m \leq n$ and $\operatorname{rank} C = m$

Suppose for every $v \neq 0$ with $Cv=0$ it is $v^TBv > 0$.

Show: then $A = \begin{pmatrix}B & C^T \\ C & 0 \end{pmatrix}$ is invertible.


Clearly the columns of $\begin{pmatrix}C^T \\ 0 \end{pmatrix}$ are linearly independent, since $\operatorname{rank} C = \operatorname{rank} C^T$. (or somethin like $dim Im(C) = dim Ker(C^T)$ ?)

Then the columns of $\begin{pmatrix}B \\ C \end{pmatrix}$ are linearly independent, since for every $v \neq 0$ with $Cv=0$ it is $v^TBv > 0$ which already requires $Bv \neq 0$ and therefore the kernel is trivial.

But how to conclude now that these first n columns are idependent from the other m columns and therefore that $A$ is invertible?

share|improve this question
    
A nice way to solve the exercise is to think as if $B$ and $C$ were numbers. How would you find the inverse in this case? Apply "the same formula" here. –  Quimey Jan 23 '13 at 19:49
    
Well, but wouldn't i need $B$ to be invertible for the first block? –  fritz Jan 23 '13 at 19:53
    
Don't really get somewhere trying to think about it this way.. –  fritz Jan 23 '13 at 20:27
add comment

1 Answer

$A$ is a square matrix, so invertibility is equivalent to the kernel being trivial. So what you can do is suppose that $v \in \mathbb{R}^{n + m}$ is nonzero, and show that $Av$ is nonzero. You can do this by breaking down $v = (v_1, v_2) \in \mathbb{R}^n \oplus \mathbb{R}^m$, in other words you analyze the problem by matrix multiplying $$ \begin{bmatrix} B & C^T \\ C & 0 \end{bmatrix}\begin{bmatrix} v_1 \\ v_2 \end{bmatrix}$$ It is also useful to know that since $\mathrm{rank}(C) = m$, then the linear map $x \mapsto Cx$ is onto, so then the linear map $y \mapsto C^T y$ is one-to-one.

Edit: Here is a more fleshed out solution. Consider the matrix product given above. If $v$ is nonzero, we will show that $Av$ is nonzero. Multiplying out the matrix product, we obtain $$ Av = \begin{bmatrix} Bv_1 + C^T v_2 \\ Cv_1 \end{bmatrix} $$ If $Cv_1 \neq 0$, then we are done, so assume that $Cv_1 = 0$. Now, suppose that $v_1 = 0$. Then $v_2 \neq 0$, in which case $Av = \begin{bmatrix} C^T v_2 \\ 0 \end{bmatrix}$. Since $y \mapsto C^T y$ is a 1-1 linear map, then $C^T v_2 \neq 0$, so then $Av \neq 0$. Now, alternatively suppose that $v_1 \neq 0$, but still $Cv_1 = 0$. Then, by the hypothesis, it must be that $v_1^T B v_1 > 0$. Therefore

$$ v_1^T (Bv_1 + C^T v_2) = v_1^T Bv_1 + v_1^T C^T v_2 > v_1^T C^T v_2 = (v_2^T Cv_1)^T = 0,$$ where the last expression is $0$ since $Cv_1 = 0$. Thus the first entry in the vector is nonzero, and hence $Av \neq 0$ in this case as well. Thus we have shown that $A$ has a trivial kernel, and hence is an invertible matrix.

share|improve this answer
    
Thanks for this approach. I considered the following cases: a) $v=(v_1,0)$: so it's either $Cv_1=0$ but then it follows that $Bv_1 \neq 0$ (since $v_1^TBv_1 > 0$) or it is already $Cv_1 \neq 0$, done. b) $v=(0,v_2)$: since $y \mapsto C^Ty$ is one-to-one it is clear that $C^Tv_2 \neq 0$, done. c) $v=(v_1,v_2)$: ??? –  fritz Jan 23 '13 at 21:15
    
There doesn't need to be a third case. The two cases are (1) $v_1$ is nonzero, and (2) $v_2$ is nonzero. These cases are not mutually exclusive; all we require is that $v = (v_1, v_2)$ is not zero, so at least one case holds. –  Christopher A. Wong Jan 23 '13 at 21:17
    
Okay, I screwed it up at this point. I focused on $Bv_1 + C^T v_2 = 0$ which I thought might be possible for $v_1$ with $Cv_1 = 0$ and therefore $Bv_1 \neq 0$ and then thought about why $v_2$ can't be choosen in a way so that $Bv_1 = - C^T v_2$. It would be nice to resolve this mistake, when starting thinking like this? –  fritz Jan 23 '13 at 21:23
    
Yes, you need to deal with this case. Perhaps in a short while I will post a more detailed solution. –  Christopher A. Wong Jan 23 '13 at 21:27
    
Thanks a lot. Minor note: Am I right, that you actually can't conclude that the first entry in the vector is greater than zero but just that it is different from zero? $v_1^T(Bv_1 + C^Tv_2) > 0 \not{\implies} (Bv_1 + C^Tv_2) > 0$? –  fritz Jan 24 '13 at 6:27
show 1 more comment

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.