Polytopes and Linear Maps

polymake works with 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.

We start out with a regular 3-cube …

> $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

… and a homethetic image:

> $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

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).

> 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

If we also read the FACETS as row vectors then the corresponding action is given by the transpose of the inverse of T.

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.

> $A=new Matrix<Rational>([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,0]]);

Using transform would not work in this case:

# polytope > transform($c,$A);
polymake:  ERROR: matrix not invertible

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:

> $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

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.

[to be continued]