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     SETUP::
  32
  33         sage: from mjo.cone.rearrangement import rearrangement_cone
  34
  35     EXAMPLES:
  36
  37     The rearrangement cones of order one are nonnegative orthants::
  38
  39         sage: rearrangement_cone(1,1) == Cone([(1,)])
  40         True
  41         sage: rearrangement_cone(1,2) == Cone([(0,1),(1,0)])
  42         True
  43         sage: rearrangement_cone(1,3) == Cone([(0,0,1),(0,1,0),(1,0,0)])
  44         True
  45
  46     When ``p == n``, the resulting cone will be a half-space, so we
  47     expect its lineality to be one less than ``n`` because it will
  48     contain a hyperplane but is not the entire space::
  49
  50         sage: rearrangement_cone(5,5).lineality()
  51         4
  52
  53     All rearrangement cones are proper::
  54
  55         sage: all( rearrangement_cone(p,n).is_proper()
  56         ....:              for n in xrange(10)
  57         ....:              for p in xrange(n) )
  58         True
  59
  60     The Lyapunov rank of the rearrangement cone of order ``p`` in ``n``
  61     dimensions is ``n`` for ``p == 1`` or ``p == n`` and one otherwise::
  62
  63         sage: all( rearrangement_cone(p,n).lyapunov_rank() == n
  64         ....:              for n in xrange(2, 10)
  65         ....:              for p in [1, n-1] )
  66         True
  67         sage: all( rearrangement_cone(p,n).lyapunov_rank() == 1
  68         ....:              for n in xrange(3, 10)
  69         ....:              for p in xrange(2, n-1) )
  70         True
  71
  72     TESTS:
  73
  74     The rearrangement cone is permutation-invariant::
  75
  76         sage: n = ZZ.random_element(2,10).abs()
  77         sage: p = ZZ.random_element(1,n)
  78         sage: K = rearrangement_cone(p,n)
  79         sage: P = SymmetricGroup(n).random_element().matrix()
  80         sage: all( K.contains(P*r) for r in K )
  81         True
  82
  83     """
  84
  85     def d(j):
  86         v = [1]*n    # Create the list of all ones...
  87         v[j] = 1 - p # Now "fix" the ``j``th entry.
  88         return v
  89
  90     V = VectorSpace(QQ, n)
  91     G = V.basis() + [ d(j) for j in xrange(n) ]
  92     return Cone(G)
  93
  94
  95 def has_rearrangement_property(v, p):
  96     r"""
  97     Test if the vector ``v`` has the "rearrangement property."
  98
  99     The rearrangement cone of order ``p`` in `n` dimensions has its
 100     members vectors of length `n`. The "rearrangement property,"
 101     satisfied by its elements, is to have its smallest ``p`` components
 102     sum to a nonnegative number.
 103
 104     We believe that we have a description of the extreme vectors of the
 105     rearrangement cone: see ``rearrangement_cone()``. This function is
 106     used to test that conic combinations of those extreme vectors are in
 107     fact elements of the rearrangement cone. We can't test all conic
 108     combinations, obviously, but we can test a random one.
 109
 110     To become more sure of the result, generate a bunch of vectors with
 111     ``random_element()`` and test them with this function.
 112
 113     INPUT:
 114
 115     - ``v`` -- An element of a cone suspected of being the rearrangement
 116                cone of order ``p``.
 117
 118     - ``p`` -- The suspected order of the rearrangement cone.
 119
 120     OUTPUT:
 121
 122     If ``v`` has the rearrangement property (that is, if its smallest ``p``
 123     components sum to a nonnegative number), ``True`` is returned. Otherwise
 124     ``False`` is returned.
 125
 126     SETUP::
 127
 128         sage: from mjo.cone.rearrangement import (has_rearrangement_property,
 129         ....:                                     rearrangement_cone)
 130
 131     EXAMPLES:
 132
 133     Every element of a rearrangement cone should have the property::
 134
 135         sage: set_random_seed()
 136         sage: all( has_rearrangement_property(
 137         ....:        rearrangement_cone(p,n).random_element(),
 138         ....:        p
 139         ....:      )
 140         ....:      for n in xrange(2, 10)
 141         ....:      for p in xrange(1, n-1)
 142         ....: )
 143         True
 144
 145     """
 146     components = sorted(v)[0:p]
 147     return sum(components) >= 0