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(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     """
  99
 100     def d(j):
 101         v = [1]*n    # Create the list of all ones...
 102         v[j] = 1 - p # Now "fix" the ``j``th entry.
 103         return v
 104
 105     V = VectorSpace(QQ, n)
 106     G = V.basis() + [ d(j) for j in xrange(n) ]
 107     return Cone(G)
 108
 109
 110 def has_rearrangement_property(v, p):
 111     r"""
 112     Test if the vector ``v`` has the "rearrangement property."
 113
 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.
 118
 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.
 124
 125     To become more sure of the result, generate a bunch of vectors with
 126     ``random_element()`` and test them with this function.
 127
 128     INPUT:
 129
 130     - ``v`` -- An element of a cone suspected of being the rearrangement
 131                cone of order ``p``.
 132
 133     - ``p`` -- The suspected order of the rearrangement cone.
 134
 135     OUTPUT:
 136
 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.
 140
 141     SETUP::
 142
 143         sage: from mjo.cone.rearrangement import (has_rearrangement_property,
 144         ....:                                     rearrangement_cone)
 145
 146     EXAMPLES:
 147
 148     Every element of a rearrangement cone should have the property::
 149
 150         sage: set_random_seed()
 151         sage: all( has_rearrangement_property(
 152         ....:        rearrangement_cone(p,n).random_element(),
 153         ....:        p
 154         ....:      )
 155         ....:      for n in xrange(2, 10)
 156         ....:      for p in xrange(1, n-1)
 157         ....: )
 158         True
 159
 160     """
 161     components = sorted(v)[0:p]
 162     return sum(components) >= 0