]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/cone/rearrangement.py
b868dd854a5e4945594d860a869e150e01870401
3 def rearrangement_cone(p
,n
):
5 Return the rearrangement cone of order ``p`` in ``n`` dimensions.
7 The rearrangement cone in ``n`` dimensions has as its elements
8 vectors of length ``n``. For inclusion in the cone, the smallest
9 ``p`` components of a vector must sum to a nonnegative number.
11 For example, the rearrangement cone of order ``p == 1`` has its
12 single smallest component nonnegative. This implies that all
13 components are nonnegative, and that therefore the rearrangement
14 cone of order one is the nonnegative orthant.
16 When ``p == n``, the sum of all components of a vector must be
17 nonnegative for inclusion in the cone. That is, the cone is a
18 half-space in ``n`` dimensions.
22 - ``p`` -- The number of components to "rearrange."
24 - ``n`` -- The dimension of the ambient space for the resulting cone.
28 A polyhedral closed convex cone object representing a rearrangement
29 cone of order ``p`` in ``n`` dimensions.
33 .. [HenrionSeeger] Rene Henrion and Alberto Seeger.
34 Inradius and Circumradius of Various Convex Cones Arising in
35 Applications. Set-Valued and Variational Analysis, 18(3-4),
36 483-511, 2010. doi:10.1007/s11228-010-0150-z
38 .. [GowdaJeong] Muddappa Seetharama Gowda and Juyoung Jeong.
39 Spectral cones in Euclidean Jordan algebras.
40 Linear Algebra and its Applications, 509, 286-305.
41 doi:10.1016/j.laa.2016.08.004
43 .. [Jeong] Juyoung Jeong.
44 Spectral sets and functions on Euclidean Jordan algebras.
48 sage: from mjo.cone.rearrangement import rearrangement_cone
52 The rearrangement cones of order one are nonnegative orthants::
54 sage: rearrangement_cone(1,1) == Cone([(1,)])
56 sage: rearrangement_cone(1,2) == Cone([(0,1),(1,0)])
58 sage: rearrangement_cone(1,3) == Cone([(0,0,1),(0,1,0),(1,0,0)])
61 When ``p == n``, the resulting cone will be a half-space, so we
62 expect its lineality to be one less than ``n`` because it will
63 contain a hyperplane but is not the entire space::
65 sage: rearrangement_cone(5,5).lineality()
68 All rearrangement cones are proper::
70 sage: all( rearrangement_cone(p,n).is_proper()
71 ....: for n in xrange(10)
72 ....: for p in xrange(n) )
75 The Lyapunov rank of the rearrangement cone of order ``p`` in ``n``
76 dimensions is ``n`` for ``p == 1`` or ``p == n`` and one otherwise::
78 sage: all( rearrangement_cone(p,n).lyapunov_rank() == n
79 ....: for n in xrange(2, 10)
80 ....: for p in [1, n-1] )
82 sage: all( rearrangement_cone(p,n).lyapunov_rank() == 1
83 ....: for n in xrange(3, 10)
84 ....: for p in xrange(2, n-1) )
89 The rearrangement cone is permutation-invariant::
91 sage: n = ZZ.random_element(2,10).abs()
92 sage: p = ZZ.random_element(1,n)
93 sage: K = rearrangement_cone(p,n)
94 sage: P = SymmetricGroup(n).random_element().matrix()
95 sage: all( K.contains(P*r) for r in K )
101 v
= [1]*n
# Create the list of all ones...
102 v
[j
] = 1 - p
# Now "fix" the ``j``th entry.
105 V
= VectorSpace(QQ
, n
)
106 G
= V
.basis() + [ d(j
) for j
in xrange(n
) ]
110 def has_rearrangement_property(v
, p
):
112 Test if the vector ``v`` has the "rearrangement property."
114 The rearrangement cone of order ``p`` in `n` dimensions has its
115 members vectors of length `n`. The "rearrangement property,"
116 satisfied by its elements, is to have its smallest ``p`` components
117 sum to a nonnegative number.
119 We believe that we have a description of the extreme vectors of the
120 rearrangement cone: see ``rearrangement_cone()``. This function is
121 used to test that conic combinations of those extreme vectors are in
122 fact elements of the rearrangement cone. We can't test all conic
123 combinations, obviously, but we can test a random one.
125 To become more sure of the result, generate a bunch of vectors with
126 ``random_element()`` and test them with this function.
130 - ``v`` -- An element of a cone suspected of being the rearrangement
133 - ``p`` -- The suspected order of the rearrangement cone.
137 If ``v`` has the rearrangement property (that is, if its smallest ``p``
138 components sum to a nonnegative number), ``True`` is returned. Otherwise
139 ``False`` is returned.
143 sage: from mjo.cone.rearrangement import (has_rearrangement_property,
144 ....: rearrangement_cone)
148 Every element of a rearrangement cone should have the property::
150 sage: set_random_seed()
151 sage: all( has_rearrangement_property(
152 ....: rearrangement_cone(p,n).random_element(),
155 ....: for n in xrange(2, 10)
156 ....: for p in xrange(1, n-1)
161 components
= sorted(v
)[0:p
]
162 return sum(components
) >= 0