# Different Methods for determining the dimension of a polytope

 1 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 281●2●13 accept rate: 0% Matthew Salt... ♦ 4.7k●3●10

 2 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 full-dimensional 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 many-dimensional 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... ♦ 4.7k●3●10 accept rate: 17% 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 result--you 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... ♦
 1 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 1.3k●3●13 accept rate: 42%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×27
×4
×2
×1