Removal of Lineality Space

[uramakrishna]

Hello Polymakers,

Are there any routines in Polymake to remove the lineality space from the input polyhedron (in constraint form), so that the resultant is a full dimensional one?

Is it right that a "gaussian elimination" algorithm should be able to do the same, with cubic complexity?

Thanks
Ramakrishna

[paffenholz]

Your question mixes two things, existence of a nontrivial LINEALITY_SPACE implies that the polyhedron is not pointed, while existence of a nontrivial LINEAR_SPAN (or AFFINE_HULL for polytopes) implies that the polyhedron is not full-dimensional in its ambient space. Probably you think of the latter. Anyway, here are methods for both:

- to project onto a full dimensional polyhedron there is a user function in polymake that does this for you, see

Code: Select all

help "projection_full";

for the correct call of this function and some explanations about what it does.
This function finds a coordinate projection onto a full dimensional polytope. If there are FACETS or INEQUALITIES given in the polytope, then it does Fourier-Motzkin elimination, unless you specify the "nofm" option. This is usually a good idea if you also know the vertices of your polytope, as Fourier-Motzkin elimination can be expensive (I think that is what you mean with "Gaussian elimination").

- For the other problem you could just define a new polytope with the VERTICES of the first, i.e.

Code: Select all

$q=new Polytope<Rational>(VERTICES=>$p->VERTICES);

I hope this answers your question.