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.

  • $\begingroup$ You also need that there is only one vertex for each choice of $k$ linearly independent columns. Did they prove that? $\endgroup$ – Chris Custer Sep 8 '19 at 5:16
  • $\begingroup$ @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 :) $\endgroup$ – 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.

Here is the link to Michel Goemans note that mention that bound and in fact provided an even tighter bound.

The loose upper bound could possibly due to some result that have not been proven in the lecture linking BFS to definition of a vertex.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.