mjo/cone/rearrangement.py

   1 from sage.all import *
   2
   3 def rearrangement_cone(p,n,lattice=None):
   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       - ``lattice`` -- (default: ``None``) an ambient lattice of rank ``n``
  27                        to be passed to the :func:`Cone` constructor.
  28
  29     OUTPUT:
  30
  31     A polyhedral closed convex cone object representing a rearrangement
  32     cone of order ``p`` in ``n`` dimensions. Each generating ray will
  33     have the integer ring as its base ring.
  34
  35     If a ``lattice`` was specified, then the resulting cone will live in
  36     that lattice unless its rank is incompatible with the dimension
  37     ``n`` (in which case a ``ValueError`` is raised).
  38
  39     REFERENCES:
  40
  41     .. [HenrionSeeger] Rene Henrion and Alberto Seeger.
  42        Inradius and Circumradius of Various Convex Cones Arising in
  43        Applications. Set-Valued and Variational Analysis, 18(3-4),
  44        483-511, 2010. doi:10.1007/s11228-010-0150-z
  45
  46     .. [GowdaJeong] Muddappa Seetharama Gowda and Juyoung Jeong.
  47        Spectral cones in Euclidean Jordan algebras.
  48        Linear Algebra and its Applications, 509, 286-305.
  49        doi:10.1016/j.laa.2016.08.004
  50
  51     .. [Jeong] Juyoung Jeong.
  52        Spectral sets and functions on Euclidean Jordan algebras.
  53
  54     SETUP::
  55
  56         sage: from mjo.cone.rearrangement import rearrangement_cone
  57
  58     EXAMPLES:
  59
  60     The rearrangement cones of order one are nonnegative orthants::
  61
  62         sage: rearrangement_cone(1,1) == Cone([(1,)])
  63         True
  64         sage: rearrangement_cone(1,2) == Cone([(0,1),(1,0)])
  65         True
  66         sage: rearrangement_cone(1,3) == Cone([(0,0,1),(0,1,0),(1,0,0)])
  67         True
  68
  69     When ``p == n``, the resulting cone will be a half-space, so we
  70     expect its lineality to be one less than ``n`` because it will
  71     contain a hyperplane but is not the entire space::
  72
  73         sage: rearrangement_cone(5,5).lineality()
  74         4
  75
  76     All rearrangement cones are proper::
  77
  78         sage: all( rearrangement_cone(p,n).is_proper()
  79         ....:              for n in xrange(10)
  80         ....:              for p in xrange(1, n) )
  81         True
  82
  83     The Lyapunov rank of the rearrangement cone of order ``p`` in ``n``
  84     dimensions is ``n`` for ``p == 1`` or ``p == n`` and one otherwise::
  85
  86         sage: all( rearrangement_cone(p,n).lyapunov_rank() == n
  87         ....:              for n in xrange(2, 10)
  88         ....:              for p in [1, n-1] )
  89         True
  90         sage: all( rearrangement_cone(p,n).lyapunov_rank() == 1
  91         ....:              for n in xrange(3, 10)
  92         ....:              for p in xrange(2, n-1) )
  93         True
  94
  95     TESTS:
  96
  97     The rearrangement cone is permutation-invariant::
  98
  99         sage: n = ZZ.random_element(2,10).abs()
 100         sage: p = ZZ.random_element(1,n)
 101         sage: K = rearrangement_cone(p,n)
 102         sage: P = SymmetricGroup(n).random_element().matrix()
 103         sage: all( K.contains(P*r) for r in K )
 104         True
 105
 106     The smallest ``p`` components of every element of the rearrangement
 107     cone should sum to a nonnegative number (this tests that the
 108     generators really are what we think they are)::
 109
 110         sage: set_random_seed()
 111         sage: def _has_rearrangement_property(v,p):
 112         ....:     return sum( sorted(v)[0:p] ) >= 0
 113         sage: all( _has_rearrangement_property(
 114         ....:      rearrangement_cone(p,n).random_element(),
 115         ....:      p
 116         ....:    )
 117         ....:    for n in xrange(2, 10)
 118         ....:    for p in xrange(1, n-1)
 119         ....: )
 120         True
 121
 122     The rearrangenent cone of order ``p`` is contained in the
 123     rearrangement cone of order ``p + 1``::
 124
 125         sage: set_random_seed()
 126         sage: n = ZZ.random_element(2,10)
 127         sage: p = ZZ.random_element(1,n)
 128         sage: K1 = rearrangement_cone(p,n)
 129         sage: K2 = rearrangement_cone(p+1,n)
 130         sage: all( x in K2 for x in K1 )
 131         True
 132
 133     The order ``p`` should be between ``1`` and ``n``, inclusive::
 134
 135         sage: rearrangement_cone(0,3)
 136         Traceback (most recent call last):
 137         ...
 138         ValueError: order p=0 should be between 1 and n=3, inclusive
 139         sage: rearrangement_cone(5,3)
 140         Traceback (most recent call last):
 141         ...
 142         ValueError: order p=5 should be between 1 and n=3, inclusive
 143
 144     If a ``lattice`` was given, it is actually used::
 145
 146         sage: L = ToricLattice(3, 'M')
 147         sage: rearrangement_cone(2, 3, lattice=L)
 148         3-d cone in 3-d lattice M
 149
 150     Unless the rank of the lattice disagrees with ``n``::
 151
 152         sage: L = ToricLattice(1, 'M')
 153         sage: rearrangement_cone(2, 3, lattice=L)
 154         Traceback (most recent call last):
 155         ...
 156         ValueError: lattice rank=1 and dimension n=3 are incompatible
 157
 158     """
 159     if p < 1 or p > n:
 160         raise ValueError('order p=%d should be between 1 and n=%d, inclusive'
 161                          %
 162                          (p,n))
 163
 164     if lattice is None:
 165         lattice = ToricLattice(n)
 166
 167     if lattice.rank() != n:
 168         raise ValueError('lattice rank=%d and dimension n=%d are incompatible'
 169                          %
 170                          (lattice.rank(), n))
 171
 172     def d(j):
 173         v = [1]*n    # Create the list of all ones...
 174         v[j] = 1 - p # Now "fix" the ``j``th entry.
 175         return v
 176
 177     G = identity_matrix(ZZ,n).rows() + [ d(j) for j in xrange(n) ]
 178     return Cone(G, lattice=lattice)