Polytopes defined by $x_i \ge0, Ax = b$ are generic ? (Understanding simplex method)

Question

Consider polytopes in $\mathbb R^n$ defined by

$x_i \ge 0, Ax = b$, for $b > 0$. Assume $A$ is of full rank $r$ and $Ax=b$ has solutions.

The following properties seems to be correct. I would be thankful for confirming my understanding is correct.

1. All vertices of polytope can be described as points $(x_1\ldots x_n)$ with $n-r$ coordinates equal to zero, other $r$ coordinates can be found solving $Ax=b$. So there are $ (\frac {n}{n-r} )$ vertices.

2. From each vertex there are $n-r$ outgoing edges (1-dimensional facets). This means that such polytopes are generic, since in general there can be many edges outgoing from each edge.

The edges outgoing some vertex with $n-r$ coordinates equal to zero, can be described by changing any of these coordinates away from zero.

---

Motivation is coming from simplex-method in linear-programming, where from constraints $Ax \le b$ one passes to constrains $Ax + Id s = b$, adding additional variables $s_i \ge 0$. As far as I understand the geometric meaning of such transform is to get more tractable polytope. Since initial polytope $ Ax \le b, x_i\ge0$ does not have clear description of vertices, neither clear description of edges, which are both crucial for simplex method since the idea of algorithm is to pass from of vertex to another by the edge joining them.

---

Additional question – consider convex polytope $Ax \le b$ in $R^n$, are there explicit algebraic conditions for $A,b$ such that polytope would be generic i.e. it does not change under small pertrubation, (in particular number of edges outgoing each vertex would be equal $n$ ).

Answer 1

Your point (1) is not correct. There can be at most $C(n,r)$ vertices, but it is easy to formulate LP's in which some basic solutions are infeasible because the corresponding point doesn't have $x \geq 0$. Furthermore, there are degenerate LP's in which a basic variable is 0 in the basic solution. In this situation, different bases can easily correspond to the same vertex.

You should read up on degeneracy in linear programming.