# Maximum number of vertices a polyhedron can have?

During my linear programming class we saw this theorem:

Theorem: Let $$A \in \mathbb{R}^{m \times n}$$ where $$\operatorname{rank}{(A)} = m \leq n$$ and let $$b \in \mathbb{R}^m-\{\bar{0}\}.$$ Then the vector $$\hat{x} \in \Omega = \{x \in \mathbb{R}^n : Ax = b, x \geq 0 \}$$ is a vertex of $$\Omega$$ if and only if the columns of $$A$$ corresponding to the positive components of $$\hat{x}$$ are linearly independent.

and the definition of vertex was given as follows:

Definition: Let $$\Omega \subseteq \mathbb{R}^n$$ be a convex subset. A point $$\hat{x} \in \Omega$$ is said to be a vertex of $$\Omega$$ if and only if there do not exist elements $$x,y \in \Omega$$ and $$\lambda \in (0,1)$$ such that $$\hat{x} = \lambda y + (1- \lambda)x$$ where $$\hat{x} \neq x, \hat{x} \neq y.$$

Everything is good up until here. But then we saw a Corollary:

Corollary: The number of vertices of $$\Omega = \{x \in \mathbb{R}^n : Ax = b, x \geq 0 \}$$ is finite and is bounded above by $$\alpha^* =\binom{n}{0} +\binom{n}{1}+ \ldots+ \binom{n}{m}.$$

This is the part I don't understand.

According to my intuition, since $$\operatorname{rank}(A) = m$$, then the maximum number of linearly independent columns of $$A$$ is $$m$$. But there are a total of $$n$$ columns, so we can pick these columns in $$\binom{n}{m}$$ possible ways. Where would the other terms come from?

If anyone could explain to me how to find the bound for the number of vertices of $$\Omega$$, I would greatly appreciate it.

• You also need that there is only one vertex for each choice of $k$ linearly independent columns. Did they prove that? – Chris Custer Sep 8 '19 at 5:16
• @ChrisCuster Hmm, interesting, I don't think we did. But then, if the number of linearly independent columns of $A$ cannot be more than $m$, does it hold that each unique vertex cannot have more than $m$ positive components? Feel free to leave an answer :) – Thomas Bladt Sep 8 '19 at 6:40

You are right, actually $$\binom{n}{m}$$ is a tighter upper bound and you have mentioned the reason.