# What are the extreme points of this polytope?

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$$?

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$$.

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$$.

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.

• I have read the definition of $A_z$ (and added it to the answer), but I still do not see why the submatrix $A_z$ has these properties. Commented Dec 19, 2020 at 17:43
• I updated it. Hope it helps. It is very technical to write it out, unfortunately. Commented Dec 20, 2020 at 16:56
• Thanks a lot for the detailed explanation. Commented Dec 20, 2020 at 18:42