# Bounding the rank of matrix after adding one row and one column

I have a matrix \begin{align} Y = \left( \begin{array}{cc} c & \mathbf{b}^{\top} \newline \mathbf{b} & X \end{array} \right) \end{align} Both $X$ and $Y$ are positive semi-definite matrices sized $n$-by-$n$ and $(n+1)$-by-$(n+1)$ respectively. $\mathbf{b}$ is an $n$ dimensional vector.

Is it true that $$rank(Y) - rank(X) \in \{0, 1\}$$ ?

In addition, if I fix $X$ and $\mathbf{b}$, but tune the scalar $c$ so as to minimize $c$ while still keeping $Y$ positive semi-definite. Then at the minimal $c$ is it true that $rank(Y) = rank(X)$?

-

I will write "positive" for "positive semidefinite". The first thing to note is that

If $Y$ is positive then $b$ must be in the range of $X$.

Proof: (Throughout this proof, if $A$ is $p \times p$ and $B$ is $q \times q$ I write $A \oplus B$ for the $(p+q) \times (p+q)$ matrix with $A$ as its upper leftmost $p \times p$ block, and $B$ as its lower rightmost $q \times q$ block, and zeros everywhere else.) Let $r$ denote the rank of $X$. There is a unitary $U$ so that $U^* X U$ takes the form $D \oplus 0_{n-r}$, where $D$ is an invertible and diagonal $r \times r$ matrix and $0_{n-r}$ denotes the $(n-r) \times (n-r)$ zero matrix. Then $Y' = (1 \oplus U^*) Y (1 \oplus U)$ resembles $Y$, only it has $U^* b$ in place of $b$ and $U^* X U$ in place of $X$. Note that $Y'$ is also a positive matrix since it has the form $M^* Y M$ with $Y$ positive.

It is generally true that if the $j$th diagonal entry of a positive matrix $P$ is $0$, then the $j$th column (and row) of $P$ is zero. (Let $e_j$ denote the $j$th standard basis vector. If the $j$th diagonal entry $(P e_j) \cdot e_j = (P^{1/2} e_j) \cdot (P^{1/2} e_j) = \|P^{1/2} e_j\|^2$ is $0$, then $P^{1/2} e_j = 0$, and hence $P e_j = P^{1/2} P^{1/2} e_j = P^{1/2} 0 = 0$, so the $j$th column of $P$ is $0$. The $j$th row of $P$ is zero because $P = P^*$.)

Since $U^* X U = D \oplus 0_{n-r}$, the last $n-r$ diagonal entries of $Y'$ are all zero. From the observation just made, the last $n-r$ rows of $Y'$ are zero, so the last $n-r$ entries of its first column $U^* b$ are zero. Since the range of $U^* X U = D \oplus 0_{n-r}$ is clearly the set of all $n \times n$ column vectors whose last $n-r$ entries are zero, we conclude that there is an $n \times 1$ vector $v$ with $U^* b = U^* X U v$. Applying $U$ to both sides of this equation we deduce that $b = X(Uv)$ is in the range of $X$. End of proof of claim.

So if $Y$ is positive there is a vector $w$ so that $Y$ takes the form $$Y = \begin{pmatrix} c & (Xw)^* \\ Xw & X \end{pmatrix}$$ Since $Xw$ is in the column space of $X$, the $n \times (n+1)$ matrix $\begin{pmatrix} Xw & X \end{pmatrix}$ has the same rank as $X$. Since the rank of $Y$ is the dimension of its row space, we therefore see that either $\operatorname{rank}(Y) = \operatorname{rank}(X)$ or $\operatorname{rank}(Y) = \operatorname{rank}(X) + 1$, depending on whether or not $\begin{pmatrix} c & (Xw)^* \end{pmatrix}$ is in the row space of $\begin{pmatrix} Xw & X \end{pmatrix}$.

If you care, the fact used above is a consequence of the general assertion

If $C$ and $X$ are positive, then the block matrix $\begin{pmatrix} C & B^* \\ B & X \end{pmatrix}$ is positive if and only if $B = X^{1/2} K C^{1/2}$ for some contraction $K$.

["Contraction" here meaning that $K^* K \leq I$, where $\leq$ denotes the usual ordering on positive matrices and $I$ is the identity matrix of the appropriate size. Note that this is and "if and only if". It generalizes what we proved above because it implies that if the block matrix is positive, then the range of $B$ is contained in the range of $X^{1/2}$, which is equal to the range of $X$.]

For your second question, first let's handle the case where $X$ is invertible. In this case, it is generally true that if $X$ is positive, then the block matrix $$\begin{pmatrix} C & B^* \\ B & X \end{pmatrix}$$ is positive if and only if $C \geq B^* X^{-1} B$, where $\geq$ denotes the usual ordering on positive matrices. (For a proof, see e.g. Rajendra Bhatia's Positive Definite Matrices, which also contains a proof of the fact mentioned without proof above. Or, knowing what to prove may help you prove the special case you need, when $C$ is $1 \times 1$.)

We know that if $Y$ is positive definite, then the vector $b$ must be of the form $Xw$ for some $w$. The general assertion just mentioned has the consequence that, if the invertible positive $X$ and the vector $b = Xw$ are fixed, then the minimal value of $c$ for which $Y$ is positive definite is the number $(Xw)^* X^{-1} Xw = (Xw)^* w$. But then $Y$ takes the form $$Y = \begin{pmatrix} (Xw)^* w & (Xw)^* \\ Xw & X \end{pmatrix}.$$ Since the first column of $Y$ is clearly in the column space of $\begin{pmatrix} (Xw)^* \\ X \end{pmatrix}$ (generally: if $M$ is $p \times q$ and $v$ is $q \times 1$, then the vector $Mv$ is in the column space of $M$), we see that the rank of $Y$ is equal to the rank of $\begin{pmatrix} (Xw)^* \\ X \end{pmatrix}$. But the first row of this matrix is $(Xw)^* = w^* X$, which is in the row space of $X$ (generally, if $M$ is $p \times q$ and $v$ is $p \times 1$, then $v^* M$ is in the row space of $M$), so we see that the rank of $\begin{pmatrix} (Xw)^* \\ X \end{pmatrix}$ is equal to the rank of $X$. This shows that when $c$ is chosen minimally, you have $\operatorname{rank}(Y) = \operatorname{rank}(X)$, at least when $X$ is invertible.

When $X$ is not invertible, there is a unitary $U$ with the property that $U^* X U$ takes the form $D \oplus 0_{n-r}$ (where $D$ is diagonal and invertible, and $r$ denotes the rank of $X$). Passing from $Y$ to $(1 \oplus U)^* Y (1 \oplus U)$, or going the other way around, does not change the positivity, or the upper leftmost entry, so we see that it suffices to prove the desired result in the case where $X$ has the form $D \oplus 0_{n-r}$ with $D$ diagonal and invertible. But then, as we observed earlier, the last $n-r$ rows and columns of $Y$ are $0$, so the desired result follows from applying what we just proved about the invertible case to the upper leftmost $(r+1) \times (r+1)$ block of $Y$.

-