Number of vertices of a partiuclar polytope

Question

Question: I would like to know the number (or a good approximation of it) of vertices of the polytope arising from the following constraints:

$\{ (a_{1,1},\ldots,a_{1,n}, a_{2,1}, \ldots a_{2,n},\ldots, a_{m,n}) \in [-1,1]^{m \times n} \ | \ \sum_{j=1}^{n} a_{i,j}=0 \ \forall i \in \{1,\ldots,m\} \}. $

I dont't have a strong background in computational geometry so I'm really stuck here. Any help would be great.

Motivation: I would like to find the maximum value of a convex function over the above described constraints. This can be achieved by evaluating the function over the vertices. If the number of vertices is not too big, this evaluation can be done efficiently.

Answer 1

Let $v(P)$ be the number of vertices for polytope $P$.

Let $X$ be the polytope at hand. It can be viewed as a $m$-fold Cartesian product of the $n-1$ polytope $X_n$.

$$X_n = \left\{ (x_1,\ldots,x_n) \in [-1,1]^n : \sum_{k=1}^n x_k = 0 \right\}$$

This implies $v(X) = v(X_n)^m$ and the problem reduces to finding the number of vertices for $X_n$.

Since $X_n$ is convex, its vertices are precisely its extreme points. Let $p = (x_1,\ldots,x_n)$ be an extreme point of $X_n$. We claim that at most one $x_i$ belongs to $(-1,1)$.

Assume the contrary, let's say $x_1, x_2 \in (-1,1)$, then for sufficiently small $\epsilon$, we have $$p_{\pm} \stackrel{def}{=} (x_1\pm\epsilon,x_2\mp\epsilon,x_3,\ldots,x_n) \in X_n \quad\text{ and }\quad p = \frac12(p_{+} + p_{-}) $$ This contradicts with the assumption that $p$ is an extreme point.

With this information, it is not hard to see the set of extreme points of $X_n$ has the form:

• When $n = 2k$ is even, exactly $k$ of $x_i$ is $+1$ while the rest is $-1$.
• When $n = 2k+1$ is odd, exactly $k$ of $x_i$ is $+1$, $k$ of $x_i$ is $-1$ and one $x_i = 0$.

As a result, we find $$v(X_n) = \begin{cases} \binom{2k}{k}, &\text{ when } n = 2k \text{ is even}\\ (2k+1) \binom{2k}{k}, &\text{ when } n = 2k+1 \text{ is odd} \end{cases} $$