Conic hull of outer products

Question

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

---

I have found the solution of this exercise but I have quesions on that. So I will start writing the solution step by step and make the relevant questions for each step.

1. Why $XX^T$ is expressed as an outer product?
2. We have $XX^T \geq 0$ and $rank(XX^T) = k$ (using SVD on X). Why it is that?
3. A positive linear combination of such matrices can have $rank$ up to n, but never less than k. Is there specific theorem about that?
4. Then a proof follows on 3: Let $A,B\geq 0$ of $rank$ k. (This came from the exercise definition.) With $rank(A+B)=r\leq k$. We know that $rank(A+B) \leq rank(A) + rank(B) = 2k$. Why $rank(A+B)=r\leq k$ holds?
5. Let $V\in R^{n \times (n-r)}$ such that $\mathcal{R}(V) = \mathcal{N(A+B)}$. Why it is that? We have $V: R^{n-r}\to R^n$ and $A: R^k \to R^n$, $\mathcal{N(A+B) \subseteq R^n}$ and $\mathcal{R(V) \subseteq R^n}$.
6. Since $A,B \geq 0$, this means $V^TAV = V^TBV = 0$, which implies that $rank(A)\leq r$ and $rank(A)\leq r$, which is a contradiction. Why the last two inequalities hold?
7. Then they conclude that $rank(A+B) \geq k$ for any $A$, $B$ such that $rank(A)=rank(B)=k$ and $A,B \geq 0$. (This is because of 4.)
8. Conversely, any non-zero matrix of $rank$ at least k can be written as the sum of several matrices of $rank$ k (using SVD decomposition for of $A = XX^T = UΣV^T$ and note that the diagonal of Σ has at least k positive entries). How is that contribute to the proof?
9. Concludes that, that the conic hull of the set of $rank$-k outer products is the set of positive semi-definite matrices of $rank$ greater than or equal to k, along with the zero matrix. How they come up with his idea? And more specifically, how the zero matrix is involved on that.

Any help on each of them is highly appreciated. It is even more appreciated a good reference, i.e., a book. Thank you!

^{These steps mentioned here.}

Answer 1

This is problem 2.13 from Boyd & Vandenberghe's Convex Optimization. Since many of the above questions are individually answered on MSE, I will try to just add pointers towards those answers.

First some notations - $\mathcal{N}(A)$ is the nullspace of matrix $A$ and $\mathcal{R}(V)$ is the range (i.e. span of column vectors) of the matrix $V$

Answering some of the straightforward questions:

1. $XX^T$ is always positive semi definite (psd). Here, we are looking at whether the conic sum of two psd matrices (of the form $XX^T$) increases the rank or not.
2. The rank of $XX^T$ is $k$ because $\operatorname{rank}\left(A^{\mathrm{T}} A\right)=\operatorname{rank}\left(A A^{\mathrm{T}}\right)=\operatorname{rank}(A)=\operatorname{rank}\left(A^{\mathrm{T}}\right)$
3. The dimension of $XX^T$ is $n \times n$. So, rank can be utmost $n$.

Next, we look at the proof why the sum of two psd matrices can only increase the rank. Let $A,B$ be two psd matrices which can be expressed as $\left\{X X^{T} | X \in \mathbf{R}^{n \times k}, \operatorname{rank} X=k\right\}$.

Assume that $rank(A+B)= r < k$. Let $V \in \Bbb{R}^{n\times(n-r)}$ be matrix with $\mathcal{R}(V) = \mathcal{N}(A+B)$ - meaning when we multiply $V$ by a column vector $c$, the resulting vector $Vc \in \mathcal{N}(A+B) $ . Then we have

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

Now, if $ V^{T}(A+B) V=V^{T} A V+V^{T} B V=0 $, it implies that $V^{T} A V =0$ and $V^{T} B V=0$

Now, $$ V^{T} A V=0 \Rightarrow (X^TV)^{T} X^T V=0 \Rightarrow X^T V=0 \Rightarrow XX^T V=0 \Rightarrow AV=0 $$

Similarly, $$\quad V^{T} B V=0 \Rightarrow BV=0$$

Essentially, we showed that if matrix $V$ spans the nullspace of $A+B$, then span of $V$ must also be in the nullspace of $A$ and $B$. In simpler words, any vector $v$ that belongs to the nullspace of $A+B$ has to be in both the nullspace of $A$ and $B$. Now, the dimension of nullspace is $n-k$ for both $A$ and $B$. This implies that the dimension of nullspace of $A+B$ can be utmost $n-k$. Then, by Rank-Nullity theorem, we have that the rank of $A+B$ is at least $k$.

A much simpler solution is available here: