Linear program maximal amount of vertices

Question

In the lectures I'm attending we have a linear problem: $$\min_{x\in\mathbb{R}^n}c^Tx$$ under $$Ax = b, x\geq0, A\in\mathbb{R}^{m\times n}, b\in\mathbb{R}^m.$$ Also, $rank(A) = m$. Here, $x\geq0$ means that all coordinates of $x$ are non-negative. We also have a lemma that states: $x^*$, s.t. $Ax^* = b, x^*\geq 0$, is a vertice of feasible region iff the columns of $A$, that are marked by non-zero coordinates of $x^*$, are linearly independent. After this lemma, not necessarily as a consequence of it, it is stated that the maximal amount of vertices in the feasible region is $\binom{n}{m}$. But it is my understanding that there could potentially be as much as $\sum_{i=1}^m \binom{n}{i}$ vertices, i.e. one for every combination of not more than $m$ linearly independent vectors. Is my understanding correct, or is this boundary due to other reasoning?
Also there is a special kind of these vertices (nicht entartete in German, I couldn't find the translation), who have exactly $m$ non-zero coordinates, but the statement is about all vertices of the feasible region.

Answer 1

$\binom{n}{m}$ is a valid upperbound.

Consider the case where you pick more than $n-m$ indices and set them to zero and the system remain consistent. Let's assume that the variables that are not determined yet be $\{n_1, \ldots, n_r\}$.

You can actually extend the set to $\{n_1, \ldots, n_r, n_{r+1}, \ldots, n_m\}$ and the columns remain independent, if we can't find such columns, we would violate the condition that it is of full row rank and we find that the solution is unique.

That is just by choosing to set $n-m$ variables to $0$ at each time and solving for the other variables, we can enumerate all the vertices.

Remark:

If you are familiar with the more general definition of BFS without considering the structure of the standard form, it might be easier to see. The first $m$ rows are active and independent, we just have to set $n-m$ inequalities to be active.