4
$\begingroup$

If A and B are real matrices, with A being symmetric, B having at least as many columns as rows, and

the matrix C defined as: $$ \begin{bmatrix} A & B^T \\ B & 0 \\ \end{bmatrix} $$

how can I prove that:

1) C is invertible, if A is positive definite and B of full rank

and,

2) Is C always invertible, if A is invertible and B of full rank?

My attempt so far was to sketch the block matrices.

For part 1) I let A be of size $nxn$. Since A is positive definite, it is invertible, and thus has full rank. I let B be of size $(k-(n+1)+1)x(p)$ = $(k-n)x(p)$, so that $B^T$ is of size $(p)x(k-n)$. Then C is of size $kxk$. Then I try to argue that, this $kxk$ square matrix has full rank, with rank = k, which implies that C is invertible. B has full row rank, and $B^T$ has full column rank.

Am I sort of close to the answer? I'm basically trying to avoid the usage of determinants of block matrices, as I'm not all that comfortable with that method - but perhaps it's necessary for this question.

For part 2) My work for part 1), if it's correct, would imply that, yes, C is always invertible if A is invertible and B of full rank. I get the feeling, though, that there is a counterexample.

Thanks in advance for your help,

$\endgroup$
0
$\begingroup$

Since $A$ is nonsingular, consider the following block factorization of $C$: $$ C=\pmatrix{A&B^T\\B&0} = \pmatrix{I&0\\BA^{-1}&I}\pmatrix{A&0\\0&S}\pmatrix{I&A^{-1}B^T\\0&I}, $$ where $S:=-BA^{-1}B^T$. Since the triangular blocks are nonsingular, the matrix $C$ is nonsingular iff the Schur complement matrix $S$ is nonsingular.

Now if $A$ is SPD, it is easy to see that $S$ is SPD as well. First, the definiteness of $A$ implies that $A^{-1}$ is SPD. For a nonzero $x$, $B^Tx\neq 0$ since has $B$ has full row rank, and $$x^T(BA^{-1}B^T)x=(B^Tx)^TA^{-1}(B^Tx)>0.$$

Another way to see that $C$ is nonsingular if $A$ is SPD and $B$ has full row rank is as follows. Assume that $Cz=0$ for some nonzero $z=(x^T,y^T)^T$. Hence $$\tag{1} Ax+B^Ty=0, \quad Bx=0. $$

None of the block components can be zero. If $x=0$ and $y\neq 0$ then $B^Ty=0$ which is impossible since $B$ has full row rank. If $x\neq 0$ and $y=0$ then $Ax=0$ which is impossible since $A$ is SPD. Hence both $x\neq 0$ and $y\neq 0$. Multiply the first equation in (1) with $x^T$ and the second with $y^T$ to get $$ x^TAx+x^TB^Ty=0, \quad y^TBx=0. $$ Since $x^TB^Ty=y^TBx=0$, we have $x^TAx=0$, which gives again a contradiction.

It is not sufficient that $A$ is nonsingular and $B$ of full rank for $S$ being nonsingular. Consider, $$ A=\pmatrix{1 & 0 \\ 0 & -1}, \quad B=(1,1). $$ It is easy to verify that $C$ is singular (actually $S=0$).

$\endgroup$
  • $\begingroup$ Hi @AlgebraicPavel - I really like your second method of proof. However, after constructing the set of two equations and deriving the contradictions, how can we conclude that C is, in fact, nonsingular? It seems that we've only established that if Cz=0 then z must be zero, i.e., C is injective, so it must have full column rank. Do we need to say something about the size of the matrix C? Should we argue that C should be a kxk square matrix (as in my work above), and since row rank = column rank, the rank of C = k, which implies that C is nonsingular? $\endgroup$ – User001 Nov 13 '14 at 22:39
  • $\begingroup$ And I'd also like to ask, for your first method of proof, how you got this block factorization of C? Is it a standard algorithm, and if so, what's the name of it? Thanks.. $\endgroup$ – User001 Nov 13 '14 at 23:16
  • $\begingroup$ @LebronJames Since $Cz=0$ implies $z=0$, $C$ is nonsingular. I thought it was obvious that $C$ is $k\times k$ (square). It is well known that the row rank = column rank, that is why we use just the rank. The block factorization is no algorithm. It's just block $LU$ factorization (or block $LDL^T$ if you like). $\endgroup$ – Algebraic Pavel Nov 14 '14 at 1:42
  • $\begingroup$ Ok, got it. Thanks so much, @AlgebraicPavel. $\endgroup$ – User001 Nov 14 '14 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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