Given $V \in \mathbb{R}^{n\times(n-r)}$, why $V^TAV = 0$ implies $\operatorname{rank}(A) \leq r$?

Question

I am doing a problem from convex optimization written by Stephen P Boyd. I am having trouble understanding the solution.

The original problem statement and solution is as follow:

2.13 Conic hull of outer products. Consider the set of rank-k outer products, defined as $\left\{X X^{T} \mid X \in \mathbf{R}^{n \times k}, \ \textbf{rank} X=k\right\} .$ Describe its conic hull in simple terms.

Solution. We have $X X^{T} \succeq 0$ and $\textbf{rank}\left(X X^{T}\right)=k .$ A positive combination of such matrices can have rank up to $n,$ but never less than $k .$ Indeed, Let $A$ and $B$ be positive semidefinite matrices of rank $k,$ with $\textbf{rank}(A+B)=r<k .$ Let $V \in \mathbf{R}^{n \times(n-r)}$ be a matrix with $\mathcal{R}(V)=\mathcal{N}(A+B),$ i.e.

$$V^{T}(A+B) V=V^{T} A V+V^{T} B V=0$$

since $A, B \succeq 0,$ this means

$$V^{T} A V=V^{T} B V=0$$ which implies that $\textbf{rank} A \leq r$ and $\textbf{rank} B \leq r .$ We conclude that $\textbf{rank}(A+B) \geq k$ for any $A, B$ such that $\textbf{rank}(A, B)=k$ and $A, B \succeq 0$.

It follows that the conic hull of the set of rank- $k$ outer products is the set of positive semidefinite matrices of rank greater than or equal to $k,$ along with the zero matrix.

In the solution above, there are two steps that I don't understand.

1. Why $\mathcal{R}(V) = \mathcal{N}(A+B)$ implies $V^T(A+B)V = 0$? (The notation here, $\mathcal{R,N}$ means range and nullspace, respectively.)

2. Why $V^TAV = 0$ implies $\textbf{rank} A \leq r$?

Answer 1

If ${\cal R} V = \ker(A+B)$ then $(A+B)V x = 0$ for all $x$ hence $(A+B)V=0$.

Hence it follows that $V^T(A+B)V = 0$.

Note that if $A$ is symmetric positive semi definite then using the spectral decomposition we can write $A = C^T C$ for some $C$.

So, if $V^TAV = 0$ then $(CV)^T(CV) = 0$ and so $CV =0$ and so $C^TCV=AV = 0$.

Also, note that the proof as you have shown only establishes that matrices in the conic hull have rank $\ge k$, but does not show that for any $r =k+1,...,n$ that there is a conical combination that has rank $r$. It is not hard to demonstrate but the above is not a complete proof.

Pick $A\ge 0$ of rank $r \in \{k,...,n\}$ and suppose that $U$ is an orthogonal matrix such that $U^TAU = \Lambda = \operatorname{diag} \{\lambda_1,...,\lambda_r,0,..., 0\}$, where the $\lambda_1,...,\lambda_r$ are all the strictly positive eigenvalues.

If $b \in \{0,1\}^r$, let $\Lambda_b = \operatorname{diag} \{ b_1 \lambda_1,..., b_r \lambda_r, 0,..., \}$.

Let $B= \{ b \in \{0,1\}^r | \text{exactly }k\text{ of the }b_i\text{ are 1}\}$ and note that if $b \in B$ then $\Lambda_b$ has rank $k$ and hence so does $U \Lambda_b U^T$.

Finally, note tha $\Lambda = {r \over k}{1 \over \binom{r}{k} }\sum_{b \in B} \Lambda_b$ and so $A = {r \over k}{1 \over \binom{r}{k} }\sum_{b \in B} U \Lambda_b T^T$