What are the extreme points of this polytope?

Question

Let $n, k$ be positive integers with $n\geq k$.

Let $P_{n,k}$ be the set of vectors $x$ in $[0,1]^n$ for which

$$ \sum_{i=1}^n x_i = k $$

$P_{n,k}$ is defined by linear equations, so it is a polytope. What are its corners (extreme points)?

My guess is that the corners are the "$k$-binary" vectors - the vectors with exactly $k$ ones and $n-k$ zeros. To prove this, it is sufficient to prove (I think) that every vector in $P_{n,k}$ is a convex combination of $k$-binary vectors. Is this correct?

Note: when $k=1$, $P_{n,1}$ is just the standard simplex in $\mathbb{R}^n$. Does it have a name when $k > 1$?

Answer 1

We prove that every $x$ in $P_{n,k}$ -- i.e. with $x_i\in[0,1]$ and $x\cdot \vec{1}=k$ -- is in the convex hull of the integer vectors in $P_{n,k}$, by induction on the number of non-integer components of $x$ (of course all integer components have values $0$ or $1$).

If all $x_i$ are integers we are done. Now suppose some component of $x$ is non-integer. Then since the sum of them is integer, there are at least two non-integer components, $x_i$ and $x_j$. First, let's decrease $x_i$ and increase $x_j$ until one of them becomes integer. Call the resulting vector $x_l$. Then let's increase $x_i$ and decrease $x_j$ until one of them becomes integer. Call the resulting vector $x_u$. Then $x$ is a convex combination of $x_l$ and $x_u$ (Proof: Denoting by $d$ the vector with $1$ in $i$th coordinate and $-1$ at $j$the coordinate, $x_u=x+t_ud$ and $x_l=x-dt_l$ for some positive $t_u, t_l$ so $x$ is on the segment between $x_u$ and $x_l$, as wanted). Of course, both $x_l$ and $x_u$ are in $P_{n,k}$.

Now by induction hypothesis, $x_l$ and $x_u$ are both convex combinations of integer points in $P_{n,k}$, and hence so is $x$.

Answer 2

To find its corners, let $\mathbf{x} = (x_i)_{i=1}^n \in P_{n,k}$. Let the elementary vector $\mathbf{e}_i \in \mathbb{R}^n$ be a vector whose $i$-th component is $1$, and $0$ elsewhere.

It's easy to see that if there exists $i$ such that $x_i \in (0,1)$, then $\mathbf{x}$ isn't a corner, as we also have another index $i' \ne i$ such that $x_{i'} \in (0,1)$. (Otherwise, if $i$ is the only non-integer index, the sum of components $\sum_i x_i \notin \mathbb{Z}$, contradicting $\sum_i x_i = k \in \mathbb{Z}$.) It remains to construct the interval containing $\mathbf{x}$. Choose a sufficiently small $\epsilon > 0$ such that $\mathbf{x}$ is the midpoint of the interval $[\mathbf{x} - \epsilon \mathbf{e}_i + \epsilon \mathbf{e}_{i'}, \mathbf{x} + \epsilon \mathbf{e}_i - \epsilon \mathbf{e}_{i'}] \subseteq P_{n,k}$. That's possible as $\mathbf{x}$ has finitely many components.

As a result, we can restrict the possible candidates to $\{0,1\}^n$. The equality constraint $\sum_i x_i = k$ tells us everything, so that the proof is finished.

N.B. If $x_i = 1$, then the $i$-th component of $\mathbf{x} + \epsilon \mathbf{e}_i - \epsilon \mathbf{e}_{i'}$ would be $x_i + \epsilon > 1$, contradicting our choice of $\mathbf{x} \in [0,1]^n$.

Answer 3

From the course notes A Course in Combinatorial Optimization from Alexander Schrijver (= Lex Schrijver) we find

Theorem 2.2. Let $P = \{ x \space | \space Ax \le b \}$ be a polyhedron in $\mathbb{R}^{n}$ and let $z \in P$. Then $z$ is a vertex of $P$ if and only if $\text{rank}(A_{z}) = n$.

Where they also explain the terminology about a vertex and what $A_{z}$ means: $A_z$ is the submatrix of $A$ consisting of those rows $a_i$ of $A$ for which $a_i z=b_i$.

So the question gives this polyhedron

$\begin{equation*} Ax = \begin{bmatrix} 1 & 1 & \cdots & 1 \\ -1 & -1 & \cdots & -1 \\ 1 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1 \\ -1 & & & \\ & -1 & & \\ & & \ddots & \\ & & & -1 \\ \end{bmatrix} x \le \begin{bmatrix} k \\ -k\\ 1 \\ 1\\ \vdots \\ 1 \\ 0 \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} = b. \end{equation*}$

It is not difficult to see that a vertex $z$ with $k$ ones and $n - k$ zeros gives raise to a submatrix $A_{z}$ which has rank $n$ so those points are vertices. It is obvious $a_{1}z = k = b_{1}$ and $a_{2}z = -k = b_{2}$ because $z$ has $k$ ones. So you keep those rows. Now an arbitrary $z_{i}$ equals $1$ or $0$. So look at column $i$ of $A$. If $z_{i} = 1$ you keep the row with $1$ in the diagonal, otherwise if $z_{i} = 0$ you keep the row with the $-1$ in the diagonal because $-1 \cdot 0 = 0 = b_{q}$. So you will end up with a matrix $A_{z}$ with $a_{1}$ and $a_{2}$ on top and a diagonal with $\pm 1$ below. Obviously $\text{rank}(A_{z}) = n$, you have $n$ pivots after all. So we conclude $z$ is a vertex.

Any other $z$ in the polyhedron must have a $z_{i}$ with $0 < z_{i} < 1$ so that also implies there is a $z_{j}$ with $i \ne j$ with $0 < z_{j} < 1$, because $z_{1} + \dots + z_{n} = k$ after all. Again $a_{1}z = k = b_{1}$ and $a_{2}z = -k = b_{2}$. However at column $i$ of $A$ you will multiply with $z_{i} \ne 0, 1$ and therefore you drop the row from the matrix $A$ with $1$ on the diagonal but also the row with $-1$ on the diagonal, because at those rows it must equal $1$ or $0$, those are the values in $b$ at the corresponding positions. This applies to column $j$ as well (note $j \ne i$). So from both diagonals (the one with $1$'s and the one with $-1$'s) you will keep at most $n - 2$ rows with a $\pm 1$. However the first two rows are still there, however they can only supply you with at most 1 pivot so $\text{rank}(A_{z}) \le n - 1$ so those $z$ are not vertices.

It is important to understand at column $i$ from $A$ you can pick at most one row from $A$ corresponding to the $b_{q}$ where $b_{q} = 1$ or $b_{q} = 0$. Try $n = 4$ and $k = 2$ for example if you need some extra help understanding it. Concrete examples are good for that.