Combinations, vertices and LPs

Question

This suggests the following (I know it is a very inefficient one)

This will work but there would be many vertices. In fact for $Ax \leq b, \ x \geq 0$ there can be $\binom {n+m}{m}$ vertices.

I cannot understand why it is $\binom {n+m}{m}$ vertices, I just cannot where $n$ and $m$ would come from and why we are definitely choosing $m$ of them.

So if $m=n$ then the number of vertices is of order $(2n)^n$ which increases exponentially in $n$.

I cannot see why the power $n$ is used.

Answer 1

For the first part of the question, I suppose that the matrix $A$ is $m$-by-$n$.

Then observe that the set of such x that $Ax\leq b, x\geq{0}$ is just the intersection of $n+m$ halfspaces: one for each of $m$ rows of $A$ and another $n$ for the coordinatewise non-negativity of $x$ - it is equivalent to $x$ belonging to a non-negative cone, which is the intersection of $n$ (space dimensionality) halfspaces spanned by coordinate planes.

Now, in an $n$ - dimensional space $n$ planes "usually" (not considering degenerate cases such as collinearity) intersect by a point. Thus, choosing a vertex from our polygon of interest is equivalent to choosing $n$ planes that, upon intersection, produce this point, from a set of $n+m$ planes. The number of such choices is, by definition, equal to $C_{n+m}^n=C_{n+m}^m$.

For the second part, I may be making a mistake here somewhere but my calculations show a slightly different answer, although, indeed, exponential in $n$. Stirling's approximation gives $$ C_{2n}^n=\frac{(2n)!}{n!n!}\approx\frac{(2n)^{2n}e^{-2n}}{n^nn^ne^{-2n}}=4^n $$

Answer 2

It's a simple counting argument. Indeed, your polyhedron can be written in the form $\mathcal P := \{x \in \mathbb R^m | Bx \le b\}$ where $B$ is an $(n + m) \times m$ matrix and $b$ is an $(m+n)$-dimensional vector. Now, each vertex of $\mathcal P$ corresponds to a solution of $m$ of the $n + m$ linear equations $B_i x = b_i$, where $B_i$ is the $i$th row of $B$. Thus there are at most ${n+m}\choose{m}$ vertices.

I leave it as an exercise to you, the construction of a polyhedron which saturates this upper bound.