Hi everybody I have got a polytope described by a set of inequalities. I do not have any equality constraints and I do not think that such equality constraints exist at all for this problem. I wonder, if there any algorithmic or analytical method which can help proving that there is no equality constraints such that I can easily conclude my polytope's dimension. Well, the problem is not a toy size instance, it a huge one. regards, Shahin asked 24 Dec '12, 09:59 ShahinG Matthew Salt... ♦ 
The common method for verifying that a polytope has a particular dimension \(d\) (actually the dimension of the affine hull of a polytope) is to exhibit a set of \(d+1\) affinely independent points contained in the polytope. For a fulldimensional polytope in \(R^n\), that is a set of \(n+1\) points \({x^0, x^1, \dots, x^n}\) such that \(x^1  x^0, x^2  x^0, \dots, x^n  x^0\) are linearly independent. For a manydimensional polytope, you'll need to have a systematic way of generating those points. Note that if the origin is feasible, you can take it as \(x^0\), which might simplify the problem. answered 24 Dec '12, 17:18 Matthew Salt... ♦ many thanks, well, I was searching for a different method. Finding those n+1 points is quite tricky. That "systematic way" is not always trivial. Any article for an alternative method? any tutorial ? any generic/algorithmic way? through introducing an equality/inequality with generic coefficients?
(24 Dec '12, 17:28)
ShahinG
1
To prove full dimensionality, all you really need is a point in the strict interior. Polytopes of lower dimension don't have a strict interior. Once you have that, you can use it as the first point and add small multiples of the n unit vectors to get the remaining points.
(24 Dec '12, 17:46)
Matthew Salt... ♦
Thanks. Any article doing similar? By the way, such a strictly interior point does the same job as a origin which (we suppose) is an extreme point?
(25 Dec '12, 03:59)
ShahinG
1
That's a basic resultyou can probably find it in any nonlinear programming book. Any feasible point can serve as x^0 in the affine independence test. If you have the origin, the test just reduces to linear independence of the remaining points, with no translation needed.
(25 Dec '12, 08:54)
Matthew Salt... ♦

In general, the problem of computing a polyhedron's dimension is at least as hard as solving an LP. Fortunately, there are polynomial time algorithms. For example, Section 3 of Brick decompositions and the matching rank of graphs by Edmonds, Pulleyblank, and Lovász provides a very general algorithm. answered 16 Oct '13, 02:00 Austin Buchanan 