# Convex hull of the Stiefel manifold with non-negativity constraints

Consider the Stiefel manifold

$$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$

where $I_k$ is the $k$-dimensional identity matrix. It is well known that

$$\mathrm{conv} \left( \mathrm{St}(n,k) \right) = \{X \in \mathbb{R}^{n\times k} : \|X\|_2 \leq 1\}$$

where $\|\cdot\|_2$ is induced $2$-norm.

Question: Is there a characterization for the convex hull of the Stiefel manifold with non-negativity constraints:

$$\mathrm{conv}(\mathrm{St}(n,k) \cap \mathbb{R}^{n\times k}_+)$$

where $\mathbb{R}^{n \times k}_+$ is the set of all $n \times k$ matrices with non-negative elements?

• In the special case k=1 it seems to be the intersection of the unit sphere with the halfspace \sum_i x_i>=1. – user35593 Apr 4 '18 at 14:07
• In the special case k=n, the Stiefel manifold with non-negativity constraints is equal to the set of all permutation matrices, and it is known that the convex hull of permutation matrices yields exactly the stochastic matrices. – Mahdi Apr 6 '18 at 11:02
• @ Mahdi The convex hull of permutation matrices yields exactly the doubly stochastic matrices, not the stochastic matrices. – Mark L. Stone Jun 5 '18 at 1:19

Here we consider the case $k=1$. Then $\text{St}(n,1)=\{x\in\mathbb{R}^n:x^Tx=1\}$ represents the unit sphere in $\mathbb{R}^n$. It follows $$\text{St}(n,1)\cap\mathbb{R}^n_+=\{x\in\mathbb{R}^n_+:x^Tx=1\}$$ represents the part of the unit circle in the first quadrant of $\mathbb{R}^n$. Let $a^T:=(1,1,...,1)$ define $$V:=\{x\in\mathbb{R}^n_+: x^Ta\geqslant 1\}$$ Hence the set $V$ represents whatever is in the first quadrant not below the simplex. First we show that $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)=\text{convSt}(n,1)\cap V$$ By definition $\text{convSt}(n,1)=\{x\in\mathbb{R}^n:x^Tx\leqslant 1\}$ is a convex set (the closed unit ball) so is the set $V$. Hence $\text{convSt}(n,1)\cap V$ is a convex set because it is the intersection of two such sets. Moreover $\text{St}(n,1)\cap\mathbb{R}^n_+\subseteq \text{convSt}(n,1)\cap V$ since $x\in\text{St}(n,1)\cap\mathbb{R}^n_+$ would imply $x^Tx=1$ and $1\geqslant x_m\geqslant 0$ for all $m=1,2,...,n$ which in turn yields $$1=x^Tx=x_1^2+...x^2_n\leqslant x_1+...+x_n=x^Ta$$ and hence $x\in \text{convSt}(n,1)\cap V$. On the other hand $\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)$ is the smallest convex set which includes $\text{St}(n,1)\cap\mathbb{R}^n_+$ thus we get $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)\subseteq \text{convSt}(n,1)\cap V$$ By definition of a convex hull we have $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)\\=\{y\in\mathbb{R}^n_+: y=\sum_k\lambda_kx_k,\hspace{0.1cm}\lambda_k\geqslant 0, \sum_k\lambda_k=1, x_k\in \text{St}(n,1)\cap\mathbb{R}^n_+\}$$ From this definition it follows that the simplex $$V_0:=\{x\in\mathbb{R}^n_+: x^Ta= 1\}\subseteq \text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)$$ as well as any line segment joining any two points in $\text{St}(n,1)\cap\mathbb{R}^n_+$. Therefore by construction we get the equality $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)= \text{convSt}(n,1)\cap V$$ So for the case $k=1$ we get the characterization $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)=\{x\in\mathbb{R}^n_+:x^Tx\leqslant 1, x_1+....+x_n\geqslant 1\}$$ For $k>1$ one needs to find an appropriate definition for a simplex. The above idea should work.

• Thanks, but k=1 is very special case of the problem. – Mahdi Apr 6 '18 at 7:03

@Arian has supplied the solution for $k = 1$. It is a known result that for $k = n$, the desired convex hull is the set of all $n$ by $n$ doubly stochastic matrices.

I offer this conjecture for the solution for general $k$, as the following extension of the answer by @Arian .The remainder of this post is conjecture:

$$\mathrm{conv}(\mathrm{St}(n,k) \cap \mathbb{R}^{n\times k}_+) = \{X\in\mathbb{R}^{n\times k}_+:\|X\|_2 \le 1, \Sigma_{j=1}^n X_{ij} \ge 1\ \forall i\}$$

$\{X\in\mathbb{R}^{n\times k}_+:\|X\|_2 \le 1, \Sigma_{j=1}^n X_{ij} \ge 1\ \forall i\}$ implies $\|X\|_2 \ge \sqrt{\frac{k}{n}}$ and $\sqrt{n-k+1} \ge \Sigma_{j=1}^n X_{ij}, \forall i$.

So putting it altogether, we can state $\mathrm{conv}(\mathrm{St}(n,k) \cap \mathbb{R}^{n\times k}_+) =$ $$\{X\in\mathbb{R}^{n\times k}_+: \sqrt{\frac{k}{n}} \le \|X\|_2 \le 1, \sqrt{n-k+1} \ge \Sigma_{j=1}^n X_{ij} \ge 1\ \forall i\}$$

When $k = n$, $\|X\|_2 = 1, \Sigma_{j=1}^n X_{ij} = 1\ \forall i$ must hold, and this reduces exactly to the set of all $n$ by $n$ doubly stochastic matrices, thereby matching the known result for square $X$.

• Thanks, Mark. that conjecture can be a constructive progress in solving the problem. – Mahdi Jun 9 '18 at 20:15
• $$\mathrm{conv}(\mathrm{St}(n,k) \cap \mathbb{R}^{n\times k}_+) = \{X\in\mathbb{R}^{n\times k}_+:\|X\|_2 \le 1, \Sigma_{j=1}^n X_{ij} \ge 1\ \forall i\}$$ is conjecture (low confidence). However, I am very confident based on semidefinite optimization results that the RHS of that implies all the following claims made in the post., even though I haven't proved those claims. I can state quite confidently that my conjectured convex hull is convex - do you have a way to try to test whether it is correct for some 1 < k < n cases? Maybe @Arian can give it a try? – Mark L. Stone Jun 9 '18 at 20:39