# show blockmatrix is invertible

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?

-
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

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