mjo/cone/rearrangement.py

   1 from sage.all import *
   2
   3 def rearrangement_cone(p,n):
   4     r"""
   5     Return the rearrangement cone of order ``p`` in ``n`` dimensions.
   6
   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.
  10
  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.
  15
  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.
  19
  20     INPUT:
  21
  22     - ``p`` -- The number of components to "rearrange."
  23
  24     - ``n`` -- The dimension of the ambient space for the resulting cone.
  25
  26     OUTPUT:
  27
  28     A polyhedral closed convex cone object representing a rearrangement
  29     cone of order ``p`` in ``n`` dimensions.
  30
  31     REFERENCES:
  32
  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
  37
  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
  42
  43     .. [Jeong] Juyoung Jeong.
  44        Spectral sets and functions on Euclidean Jordan algebras.
  45
  46     SETUP::
  47
  48         sage: from mjo.cone.rearrangement import rearrangement_cone
  49
  50     EXAMPLES:
  51
  52     The rearrangement cones of order one are nonnegative orthants::
  53
  54         sage: rearrangement_cone(1,1) == Cone([(1,)])
  55         True
  56         sage: rearrangement_cone(1,2) == Cone([(0,1),(1,0)])
  57         True
  58         sage: rearrangement_cone(1,3) == Cone([(0,0,1),(0,1,0),(1,0,0)])
  59         True
  60
  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::
  64
  65         sage: rearrangement_cone(5,5).lineality()
  66         4
  67
  68     All rearrangement cones are proper::
  69
  70         sage: all( rearrangement_cone(p,n).is_proper()
  71         ....:              for n in xrange(10)
  72         ....:              for p in xrange(1, n) )
  73         True
  74
  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::
  77
  78         sage: all( rearrangement_cone(p,n).lyapunov_rank() == n
  79         ....:              for n in xrange(2, 10)
  80         ....:              for p in [1, n-1] )
  81         True
  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) )
  85         True
  86
  87     TESTS:
  88
  89     The rearrangement cone is permutation-invariant::
  90
  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 )
  96         True
  97
  98     The smallest ``p`` components of every element of the rearrangement
  99     cone should sum to a nonnegative number (this tests that the
 100     generators really are what we think they are)::
 101
 102         sage: set_random_seed()
 103         sage: def _has_rearrangement_property(v,p):
 104         ....:     return sum( sorted(v)[0:p] ) >= 0
 105         sage: all( _has_rearrangement_property(
 106         ....:      rearrangement_cone(p,n).random_element(),
 107         ....:      p
 108         ....:    )
 109         ....:    for n in xrange(2, 10)
 110         ....:    for p in xrange(1, n-1)
 111         ....: )
 112         True
 113
 114     The rearrangenent cone of order ``p`` is contained in the
 115     rearrangement cone of order ``p + 1``::
 116
 117         sage: set_random_seed()
 118         sage: n = ZZ.random_element(2,10)
 119         sage: p = ZZ.random_element(1,n)
 120         sage: K1 = rearrangement_cone(p,n)
 121         sage: K2 = rearrangement_cone(p+1,n)
 122         sage: all( x in K2 for x in K1 )
 123         True
 124
 125     The order ``p`` should be between ``1`` and ``n``, inclusive::
 126
 127         sage: rearrangement_cone(0,3)
 128         Traceback (most recent call last):
 129         ...
 130         ValueError: order p=0 should be between 1 and n=3, inclusive
 131         sage: rearrangement_cone(5,3)
 132         Traceback (most recent call last):
 133         ...
 134         ValueError: order p=5 should be between 1 and n=3, inclusive
 135
 136     """
 137     if p < 1 or p > n:
 138         raise ValueError('order p=%d should be between 1 and n=%d, inclusive'
 139                          %
 140                          (p,n))
 141
 142     def d(j):
 143         v = [1]*n    # Create the list of all ones...
 144         v[j] = 1 - p # Now "fix" the ``j``th entry.
 145         return v
 146
 147     G = identity_matrix(ZZ,n).rows() + [ d(j) for j in xrange(n) ]
 148     return Cone(G)