ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 24 Apr 2020 09:44:34 +0200Projection along affine hullhttps://ask.sagemath.org/question/35487/projection-along-affine-hull/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?Tue, 08 Nov 2016 20:09:57 +0100https://ask.sagemath.org/question/35487/projection-along-affine-hull/Comment by jipilab for <p>Let <code>n_1,...,n_r</code> be integral points in a polyhedron <code>P</code>. The paper I am reading refers to "the projection of <code>P</code> along <code>aff(n_1,...,n_r)</code>". Here <code>aff(n_1,...,n_r)</code> is the affine hull of <code>n_1,...,n_r</code>. Can I accomplish this projection in sage?</p>
https://ask.sagemath.org/question/35487/projection-along-affine-hull/?comment=39098#post-id-39098Could we have a precise definition of what is meant by "projection of `P` along the affine hull"? This would make the question more precise.Tue, 10 Oct 2017 19:55:27 +0200https://ask.sagemath.org/question/35487/projection-along-affine-hull/?comment=39098#post-id-39098Answer by jipilab for <p>Let <code>n_1,...,n_r</code> be integral points in a polyhedron <code>P</code>. The paper I am reading refers to "the projection of <code>P</code> along <code>aff(n_1,...,n_r)</code>". Here <code>aff(n_1,...,n_r)</code> is the affine hull of <code>n_1,...,n_r</code>. Can I accomplish this projection in sage?</p>
https://ask.sagemath.org/question/35487/projection-along-affine-hull/?answer=39099#post-id-39099Here 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))Tue, 10 Oct 2017 20:51:09 +0200https://ask.sagemath.org/question/35487/projection-along-affine-hull/?answer=39099#post-id-39099Answer by Jonathan Kliem for <p>Let <code>n_1,...,n_r</code> be integral points in a polyhedron <code>P</code>. The paper I am reading refers to "the projection of <code>P</code> along <code>aff(n_1,...,n_r)</code>". Here <code>aff(n_1,...,n_r)</code> is the affine hull of <code>n_1,...,n_r</code>. Can I accomplish this projection in sage?</p>
https://ask.sagemath.org/question/35487/projection-along-affine-hull/?answer=50967#post-id-50967In 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 verticesThu, 23 Apr 2020 18:54:21 +0200https://ask.sagemath.org/question/35487/projection-along-affine-hull/?answer=50967#post-id-50967Comment by jipilab for <p>In sage 9.1+ matrices act on polyhedra as linear transformation. This makes it easy.</p>
<p>Let me explain how to project the 3-dimensional permutahedron <code>P</code> to the affine span of <code>[(3, 2, 4, 1), (4, 1, 3, 2), (1, 2, 3, 4)]</code>. By translation, we can reduce the problem to a linear one. We can instead linearly project <code>P1 = P - vector((3, 2, 4, 1))</code> to the linear span of <code>[((1, -1, -1, 1), (-2, 0, -1, 3))]</code>.</p>
<p>Obtaining <code>P1</code>:</p>
<pre><code>sage: P = polytopes.permutahedron(4) # dim 3 and ambient dim 4
sage: P1 = P - vector((3, 2, 4, 1))
</code></pre>
<p>To do this we use the right kernel:</p>
<pre><code>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]
</code></pre>
<p>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.</p>
<p>Now we want to linearly transform <code>P</code> such that the vectors corresponding to the first and second row get mapped to themselves and the others to zero. That's linear algebra:</p>
<pre><code>sage: P2 = B*Matrix([[1,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,0,0]])*B.inverse()*P1
</code></pre>
<p>Finally, we add the vector again:</p>
<pre><code>sage: P2 + vector((3, 2, 4, 1))
A 2-dimensional polyhedron in QQ^4 defined as the convex hull of 10 vertices
</code></pre>
https://ask.sagemath.org/question/35487/projection-along-affine-hull/?comment=50985#post-id-50985Perhaps you could complete this answer with the code to obtain P?Fri, 24 Apr 2020 09:39:58 +0200https://ask.sagemath.org/question/35487/projection-along-affine-hull/?comment=50985#post-id-50985Comment by Jonathan Kliem for <p>In sage 9.1+ matrices act on polyhedra as linear transformation. This makes it easy.</p>
<p>Let me explain how to project the 3-dimensional permutahedron <code>P</code> to the affine span of <code>[(3, 2, 4, 1), (4, 1, 3, 2), (1, 2, 3, 4)]</code>. By translation, we can reduce the problem to a linear one. We can instead linearly project <code>P1 = P - vector((3, 2, 4, 1))</code> to the linear span of <code>[((1, -1, -1, 1), (-2, 0, -1, 3))]</code>.</p>
<p>Obtaining <code>P1</code>:</p>
<pre><code>sage: P = polytopes.permutahedron(4) # dim 3 and ambient dim 4
sage: P1 = P - vector((3, 2, 4, 1))
</code></pre>
<p>To do this we use the right kernel:</p>
<pre><code>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]
</code></pre>
<p>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.</p>
<p>Now we want to linearly transform <code>P</code> such that the vectors corresponding to the first and second row get mapped to themselves and the others to zero. That's linear algebra:</p>
<pre><code>sage: P2 = B*Matrix([[1,0,0,0],[0,1,0,0],[0,0,0,0],[0,0,0,0]])*B.inverse()*P1
</code></pre>
<p>Finally, we add the vector again:</p>
<pre><code>sage: P2 + vector((3, 2, 4, 1))
A 2-dimensional polyhedron in QQ^4 defined as the convex hull of 10 vertices
</code></pre>
https://ask.sagemath.org/question/35487/projection-along-affine-hull/?comment=50986#post-id-50986Sure. Thanks.Fri, 24 Apr 2020 09:44:34 +0200https://ask.sagemath.org/question/35487/projection-along-affine-hull/?comment=50986#post-id-50986