Ask Your Question

Revision history [back]

In sage 9.1+ matrices act on polyhedra as linear transformation. This makes it easy.

Let me explain how to project the 3-dimensional permutahedron P to the affine span of [(3, 2, 4, 1), (4, 1, 3, 2), (1, 2, 3, 4)]. By translation, we can reduce the problem to a linear one. We can instead linearly project P1 = P - vector((3, 2, 4, 1)) to the linear span of [((1, -1, -1, 1), (-2, 0, -1, 3))].

To do this we use the right kernel:

sage: M = Matrix(((1, -1, -1, 1), (-2, 0, -1, 3)))
sage: B = M.stack(M.right_kernel_matrix()).transpose()
sage: B
[ 1 -2  1  0]
[-1  0  1  2]
[-1 -1  1 -3]
[ 1  3  1 -1]

The first two rows are spanning our linear space we want to map to. The third and fourth row are a base extension such that they are orthogonal to the first and second row.

Now we want to linearly transform P such that the vectors corresponding to the first and second row get mapped to themselves and the others to zero. That's linear algebra:

sage: P2 = B*Matrix([[1,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,0,0]])*B.inverse()*P1

Finally, we add the vector again:

sage: P2 + vector((3, 2, 4, 1))
A 2-dimensional polyhedron in QQ^4 defined as the convex hull of 10 vertices

In sage 9.1+ matrices act on polyhedra as linear transformation. This makes it easy.

Let me explain how to project the 3-dimensional permutahedron P to the affine span of [(3, 2, 4, 1), (4, 1, 3, 2), (1, 2, 3, 4)]. By translation, we can reduce the problem to a linear one. We can instead linearly project P1 = P - vector((3, 2, 4, 1)) to the linear span of [((1, -1, -1, 1), (-2, 0, -1, 3))].

Obtaining P1:

sage: P = polytopes.permutahedron(4)  # dim 3 and ambient dim 4
sage: P1 = P - vector((3, 2, 4, 1))

To do this we use the right kernel:

sage: M = Matrix(((1, -1, -1, 1), (-2, 0, -1, 3)))
sage: B = M.stack(M.right_kernel_matrix()).transpose()
sage: B
[ 1 -2  1  0]
[-1  0  1  2]
[-1 -1  1 -3]
[ 1  3  1 -1]

The first two rows are spanning our linear space we want to map to. The third and fourth row are a base extension such that they are orthogonal to the first and second row.

Now we want to linearly transform P such that the vectors corresponding to the first and second row get mapped to themselves and the others to zero. That's linear algebra:

sage: P2 = B*Matrix([[1,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,0,0]])*B.inverse()*P1

Finally, we add the vector again:

sage: P2 + vector((3, 2, 4, 1))
A 2-dimensional polyhedron in QQ^4 defined as the convex hull of 10 vertices