Ask Your Question
2

Projection along affine hull

asked 2016-11-08 13:09:57 -0600

done_with_fish gravatar image

Let n_1,...,n_r be integral points in a polyhedron P. The paper I am reading refers to "the projection of P along aff(n_1,...,n_r)". Here aff(n_1,...,n_r) is the affine hull of n_1,...,n_r. Can I accomplish this projection in sage?

edit retag flag offensive close merge delete

Comments

Could we have a precise definition of what is meant by "projection of P along the affine hull"? This would make the question more precise.

jipilab gravatar imagejipilab ( 2017-10-10 12:55:27 -0600 )edit

2 answers

Sort by ยป oldest newest most voted
1

answered 2020-04-23 11:54:21 -0600

Jonathan Kliem gravatar image

updated 2020-04-24 02:43:33 -0600

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
edit flag offensive delete link more

Comments

Perhaps you could complete this answer with the code to obtain P?

jipilab gravatar imagejipilab ( 2020-04-24 02:39:58 -0600 )edit

Sure. Thanks.

Jonathan Kliem gravatar imageJonathan Kliem ( 2020-04-24 02:44:34 -0600 )edit
1

answered 2017-10-10 13:51:09 -0600

jipilab gravatar image

Here is an example. It requires to load the Projection function:

sage: from sage.geometry.polyhedron.plot import Projection

Let's say we have the following polytope:

sage: P = Polyhedron(vertices=[[-2,0,3],[2,0,3],[0,2,1],[0,-2,1]])

and we are interested in the affine space spanned by the points

sage: affine_basis = [vector([1,1,2]),vector([1,-1,2]),vector([-1,-1,2])]

we first get a linear subspace and create the projection matrix:

sage: linear_subspace = [ap - affine_points[0] for ap in affine_basis[1:]]
sage: VS = VectorSpace(QQ,3)
sage: proj_matrix = matrix([sum([v.inner_product(lv)*lv/(lv.inner_product(lv)) for lv in linear_subspace]) for v in VS.basis()]).transpose()

Then, we create a function that will emulate the affine projection (notice the addition of the first element of the affine basis).

sage: def my_proj(x): return proj_matrix*x + affine_basis[0]

Then, we project the polytope and use the transformed coordinates of the vertices to create a new polytope.

sage: proj_p = Projection(P,proj=my_proj)
sage: projected_P = Polyhedron(vertices=proj_p.transformed_coords)

Now, we can see the difference between

sage: P
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: P.vertices()
(A vertex at (-2, 0, 3),
 A vertex at (0, -2, 1),
 A vertex at (0, 2, 1),
 A vertex at (2, 0, 3))

and the resulting polytope:

sage: projected_P
A 2-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices
sage: projected_P.vertices()
(A vertex at (0, -2, 2),
 A vertex at (0, 0, 2),
 A vertex at (2, 2, 2),
 A vertex at (2, 4, 2))
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-11-08 13:09:57 -0600

Seen: 400 times

Last updated: Apr 24