Polytopes and Linear Maps [polymake wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Polytopes and Linear Maps =====

polymake works with [[coordinates|homogeneous coordinates]], which is why //projective// linear transformations are natural to apply to polytopes. Affine transformations are a special case. By the way, a //transformation// is always bijective, by definition.

==== Transformations ====

We start out with a regular 3-cube ...

<code perl>
> $c=cube(3);
> print $c->VERTICES;
1 -1 -1 -1
1 1 -1 -1
1 -1 1 -1
1 1 1 -1
1 -1 -1 1
1 1 -1 1
1 -1 1 1
1 1 1 1
</code>
... and a homethetic image:

<code perl>
> $T=new Matrix<Rational>([[1,0,0,0],[0,2,0,0],[0,0,3,0],[0,0,0,4]]);
> $ct=transform($c,$T);
> print $ct->VERTICES;
1 -2 -3 -4
1 2 -3 -4
1 -2 3 -4
1 2 3 -4
1 -2 -3 4
1 2 -3 4
1 -2 3 4
1 2 3 4
</code>
Our points are row vectors, so (projective) linear transformations are applied by multiplying the corresponding matrix from the right. In the above example the first column of the matrix T is the vector [1,0,0,0] which means that T acts as an affine map on //R³//. Also the first row reads [1,0,0,0], and this says that T fixes the origin. This is to say, T acts linearly.

The purpose of the function transform used above is not only to work on the VERTICES but also on the FACETS (if available).

<code perl>
> print $c->FACETS;
1 1 0 0
1 -1 0 0
1 0 1 0
1 0 -1 0
1 0 0 1
1 0 0 -1
> print $ct->FACETS;
1 1/2 0 0
1 -1/2 0 0
1 0 1/3 0
1 0 -1/3 0
1 0 0 1/4
1 0 0 -1/4
</code>
If we also read the FACETS as row vectors then the corresponding action is given by the transpose of the inverse of T.

==== Non-Bijective Linear Maps ====

Sometimes we are interested in images of polytopes under a linear map which is not bijective. An interesting case are projections, for instance, onto a coordinate subspace.

<code perl>
> $A=new Matrix<Rational>([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,0]]);
</code>
Using transform would not work in this case:

<code>
# polytope > transform($c,$A);
polymake:  ERROR: matrix not invertible
</code>
The above error says that transform is not the proper function to deal with this situation as the linear map given by A is not invertible.

To produce the image the following command works:

<code perl>
> $ca=new Polytope<Rational>(POINTS=>$c->VERTICES*$A);
> print $ca->VERTICES;
1 1 -1 0
1 1 1 0
1 -1 -1 0
1 -1 1 0
</code>
Since we are applying a non-bijective map, the images of VERTICES do not have to be VERTICES. Moreover, even if this is the case, multiple VERTICES may be mapped to the same (like two onto one as in the example above). If a polytope already has a double description, that is, both VERTICES and FACETS are known, then the VERTICES and FACETS of the image under a transformation (that is, a bijective map) cane be read off right away. However, in the non-bijective case a convex hull computation is required to compute the FACETS of the image.

==== Special Examples of Linear Maps to Apply ====

[to be continued]