Consider a PSD matrix of the form $$M = \begin{pmatrix} A & B \\ B^\top & C \end{pmatrix}$$ with positive definite $A\in\mathbb{R}^{k_1\times k_1}$. $B\in\mathbb{R}^{k_1\times k_2}$ and $C\in\mathbb{R}^{k_2\times k_2}$. Assume $k_1\leq k_2$ and $$\mbox{rank}(A) = \mbox{rank}(C) = k_1$$ what can we say about the rank of $M$? Is it smaller than $2k_1$?
What if $C = \mu B^\top A^{-1}B$ with a constant $\mu\geq 1$? Is the rank of $M$ smaller than $2k_1$?
Best Answer
Claim: The rank of $M$ is less or equal to $2k_1$.
One way to see this is by using the Schur product $(A\odot B)$.
Let $u\in \mathbb{R}^{k_1+k_2}$ be the column vector with all coordinates equal to 1.
Lemma: Let $F\in \mathbb{R}^{k_1+k_2\times k_1+k_2}$ be a psd matrix such that $u\in \operatorname{Image}(F)$. If $G\in \mathbb{R}^{k_1+k_2\times k_1+k_2}$ is another psd matrix then $\operatorname{rank}(G\odot F)\geq \operatorname{rank}(G)$.
Proof of the Lemma:
There is $\epsilon>0$ such that $F-\epsilon uu^t$ is psd.
Since $G$ is also psd, $G\odot (F-\epsilon uu^t)$ is psd by a well known property of the Schur product.
Now, $$G\odot F=G\odot (F-\epsilon uu^t)+\epsilon\ G\odot uu^t=G\odot (F-\epsilon uu^t)+\epsilon\ G.$$
Finally, since $G\odot (F-\epsilon uu^t)$ and $G$ are psd, $\operatorname{rank}(G\odot F)\geq \operatorname{rank}(G)$.$\square$
Proof of the Claim:
Let $E=\begin{pmatrix} 1_{k_1\times k_1} & 0 \\ 0 & 1_{k_2\times k_2} \end{pmatrix}$, where $1_{k_i\times k_i}$ is the matrix of order $k_i$ with all coordinates equal to 1.
Note that $u\in \operatorname{Image}(E)$, $E$ is psd and $M\odot E=\begin{pmatrix} A & 0 \\ 0 & C\end{pmatrix}$.
Then, by our Lemma, $2k_1=\operatorname{rank}(M\odot E)\geq \operatorname{rank}(M)$. $\square$