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