Hypersimplex coefficients

Question

The $(n,k)$-hypersimplex is the intersection of the unit hypercube with the hyperplane $\sum_i x_i = k$. It contains all the points in $\text{conv}\{ 1_S: S\subset[n], |S|=k \}$ i.e., the convex hull of all binary $n$-dimensional vectors with $k$ nonzero entries.

My question is, for any given hypercube point $\mathbf{x} \in [0,1]^n$ (whose coordinates sum to $k$), how can we express the coordinates of that point in terms of the corners of a $(n,k)$-hypersimplex (for arbitrarily chosen $k$)? In other words, suppose I fix $k$ to some number, $\mathbf{x}$ can be written as a convex combination of $\binom{n}{k}$ binary vectors, each having $k$ ones. I am interested in ways of finding such convex combinations (their coefficients).

In the case of the simplex, there are known ways of expressing any hypercube point in barycentric coordinates. Is there something similar for the hypersimplex?

My first thought is to stack all $\binom{n}{k}$ indicator vectors on a matrix $\mathbf{A} \in \{0,1\}^{n \times \binom{n}{k}}$ and find the coordinates of $\mathbf{y}\in [0,1]^{ \binom{n}{k}}$ such that $\mathbf{Ay} = \mathbf{x}$ and $\sum_{i}y_i=1$. I suppose this could be done with linear programming but it seems kind of expensive in the sense that the linear program will end up having a ton of constraints. Computationally, maybe I could just randomly sample a bunch of them until I get a matrix of sufficiently high rank and then go on to formulate a linear program?

Are there known constructions where the coefficients can be found in a more clever way (either analytically or computationally) without having to deal with all $\binom{n}{k}$ binary vectors?

Answer 1

A naive idea that may work.

Let $x$ be in $[0,1]^n$ with coordinates adding up to $k$. Then $x$ has at most $n-k$ zeroes and at most $k$ ones,

If $x$ has at exactly $n-k$ zeroes or exactly $k$ ones, then $x$ is one of the extremal points $1_S$ with $|S|=k$.

Otherwise, let $i_1<\ldots<i_k$ be the indexes corresponding to the greatest $k$ coordinates of $x$, and let $S = \{i_1,\ldots,i_k\}$. Note that $x_i<1$ for every $i \in S^c$. We choose the largest $t \ge 0$ such that the vector $y = (1-t)^{-1}(x-t1_S)$ belongs to $[0,1]^n$. Since this condition is equivalent to $t \le \min\{x_i : i \in S\}$ and $1-t \ge \max\{x_i : i \in S^c\}$, we set $$t := \min(\min\{x_i : i \in S\},\min\{1-x_i : i \in S^c\}) \in ]0,1[.$$ By construction, the vector $y := (1-t)^{-1}(x-t1_S)$ belongs to $[0,1]^n$ and its coordinates add up to $k$. Moreover, $y$ has at least one more zero or one than $x$. Indeed, $$x_i = 0 \implies (i \notin S \text{ and } y_i=0),$$ $$x_i = 1 \implies (i \in S \text{ and } y_i=1),$$ and we have $t=x_i$ for some $i \in S$ or $t=1-x_i$ for some $i \in S^c$, so $y_i=0$ for some $i \in S$ or $y_i=1$ for some $i \in S^c$.

Hence we may write $x=t1_S+(1-t)y$ and apply a recursive algorithm.

Answer 2

Not a full answer, only a draft of a method; not sure it works and anyway there is still much work to do.
Edit And actually I mixed up "convex combination" (in the OP; means all coefficients $c_i \in [0, 1]$ and $\sum_i c_i = 1$) with "convex cone" ($c_i \ge 0$). Thanks Mike Earnest for spotting that.

The idea is the following:

• $(n,p)$-hypersimplex vertices, with $p>k$, can be expressed as a positive linear combination of $(n,k)$-hypersimplex vertices (see below). So we'll look at a way to express any point into those $(n,p)$-hypersimplex vertices, then convert back to the $(n,k)$-hypersimplex vertices.
• For $p=n-1$, there are $n$ vertices in the $(n,n-1)$ hypersimplex: it is a regular $n-1$ simplex (also called $n$-cell), i.e. an equilateral triangle for $n=3$, tetrahedron for $n=4$, hypertetrahedron for $n=5$, etc.
• By adding one point in its center, this $n-1$ simplex is decomposed into $n$ smaller $n-1$ simplexes. Each point in the simplex belongs to one of those smaller $n-1$ simplexes (and only one, except for their faces). I have not looked at how to easily find which one.
• The point can then be expressed as a positive linear combination of the smaller simplex vertices. I have not looked at how to do that; one can solve a $(n \times n)$ linear system, if no better way. These vertices include some vertices of the $(n,n-1)$ hypersimplex, and the $(n,n-1)$ hypersimplex center. This $(n,n-1)$ hypersimplex center can be expressed as a positive linear combination of all the $(n,n-1)$ hypersimplex vertices: that's $\frac {1} {n-1}$ of their sum.
• Now, the way to get from any point in the cube, to a point in the $(n,n-1)$ hypersimplex interior:

1. Transfer the point into the $(n,n-1)$ hypersimplex cone. For this, express point $\mathbf{x}$ in the cube as $\mathbf{x} = \lambda \mathbf{d} + \mathbf{x_1}$, where $\mathbf{d}$ is the principal diagonal vector = $(1,\dots,1)$, and $\mathbf{x_1}$ orthogonal to $\mathbf{d}$.
   Then pose $\mathbf{x_2} = \lambda \mathbf{d} + \mu \mathbf{x_1}$, with $\mu>0$ sufficiently small so that $\mathbf{x_2}$ is in the $(n,n-1)$ hypersimplex cone (whose center axis is $\mathbf{d}$). Here the reverse operation may introduce negative coefficients. The hope (not proven) is that when converting back into the $(n,k)$-hypersimplex vertices, those negative coefficients disappear, if the original point was in the $(n,k)$-hypersimplex cone of course.
2. Pose $\mathbf{x_3} = \nu \mathbf{x_2}$ such that $\mathbf{x_3}$ is in the $\sum_{i=1}^n x_{3,i} = k$ hyperplane.

---

First bullet point above: we want to express $\mathbf{x} \in [0,1]^n$, which has $p$ ones and $n-p$ zeros, with the corners of an $(n,k)$-hypersimplex, i.e. with vectors $\mathbf{y} \in [0,1]^n$ which have $k$ ones and $n-k$ zeros.

If p < k
There is no solution: $\mathbf{x}$ is not in the convex cone made by the $\mathbf{y}$ in $(n,k)$-hypersimplex.
This is because the angle $\theta$ between any of these $\mathbf{y}$ and the principal diagonal, i.e. the vector with $n$ ones, which is also the center of all cones, is such that
$\cos \theta \sqrt k \sqrt n = k$
$\cos \theta = \sqrt {\frac k n}$
while the angle $\phi$ between $\mathbf{x}$ and the principal diagonal is such that
$\cos \phi = \sqrt {\frac p n}$
$\cos \phi < \cos \theta$, so $\phi > \theta$,
$\mathbf{x}$ is not in the cone made by the $\mathbf{y}$.

If p > k
We express $\mathbf{x}$ as convex combination of the $\mathbf{y}$ that have their $k$ ones only in the places where $\mathbf{y}$ has a one.
There are ${p \choose k}$ such $\mathbf{y}$. We give them the same coefficient $\alpha$.
This will produce a vector with the same non-null value on all the places where $\mathbf{x}$ has a one. The sum of all these values is $\alpha$ times the number of ones in a $\mathbf{y}$, times the number of $\mathbf{y}$ we use. And we want that to be equal to the number of ones in $\mathbf{x}$.
So
$\alpha k {p \choose k} = p$
$\alpha = \frac {p} {k {p \choose k}}$
$\alpha = \frac {1} {{p-1} \choose {k-1}}$

As an example, $(1,1,1,0) = \frac 1 2 (1,1,0,0) + \frac 1 2 (1,0,1,0) + \frac 1 2 (0,1,1,0)$
where $\frac 1 2 = \frac 1 {{3-1} \choose {2-1}}$