mjo/cone/rearrangement.py

   1 # Sage doesn't load ~/.sage/init.sage during testing (sage -t), so we
   2 # have to explicitly mangle our sitedir here so that "mjo.cone"
   3 # resolves.
   4 from os.path import abspath
   5 from site import addsitedir
   6 addsitedir(abspath('../../'))
   7
   8 from sage.all import *
   9 from mjo.cone.cone import random_element
  10
  11 def rearrangement_cone(p,n):
  12     r"""
  13     Return the rearrangement cone of order ``p`` in ``n`` dimensions.
  14
  15     The rearrangement cone in ``n`` dimensions has as its elements
  16     vectors of length ``n``. For inclusion in the cone, the smallest
  17     ``p`` components of a vector must sum to a nonnegative number.
  18
  19     For example, the rearrangement cone of order ``p == 1`` has its
  20     single smallest component nonnegative. This implies that all
  21     components are nonnegative, and that therefore the rearrangement
  22     cone of order one is the nonnegative orthant.
  23
  24     When ``p == n``, the sum of all components of a vector must be
  25     nonnegative for inclusion in the cone. That is, the cone is a
  26     half-space in ``n`` dimensions.
  27
  28     INPUT:
  29
  30     - ``p`` -- The number of components to "rearrange."
  31
  32     - ``n`` -- The dimension of the ambient space for the resulting cone.
  33
  34     OUTPUT:
  35
  36     A polyhedral closed convex cone object representing a rearrangement
  37     cone of order ``p`` in ``n`` dimensions.
  38
  39     EXAMPLES:
  40
  41     The rearrangement cones of order one are nonnegative orthants::
  42
  43         sage: rearrangement_cone(1,1) == Cone([(1,)])
  44         True
  45         sage: rearrangement_cone(1,2) == Cone([(0,1),(1,0)])
  46         True
  47         sage: rearrangement_cone(1,3) == Cone([(0,0,1),(0,1,0),(1,0,0)])
  48         True
  49
  50     When ``p == n``, the resulting cone will be a half-space, so we
  51     expect its lineality to be one less than ``n`` because it will
  52     contain a hyperplane but is not the entire space::
  53
  54         sage: rearrangement_cone(5,5).lineality()
  55         4
  56
  57     All rearrangement cones are proper::
  58
  59         sage: all([ rearrangement_cone(p,n).is_proper()
  60         ....:               for n in range(10)
  61         ....:               for p in range(n) ])
  62         True
  63
  64     The Lyapunov rank of the rearrangement cone of order ``p`` in ``n``
  65     dimensions is ``n`` for ``p == 1`` or ``p == n`` and one otherwise::
  66
  67         sage: all([ rearrangement_cone(p,n).lyapunov_rank() == n
  68         ....:               for n in range(2, 10)
  69         ....:               for p in [1, n-1] ])
  70         True
  71         sage: all([ rearrangement_cone(p,n).lyapunov_rank() == 1
  72         ....:               for n in range(3, 10)
  73         ....:               for p in range(2, n-1) ])
  74         True
  75
  76     TESTS:
  77
  78     The rearrangement cone is permutation-invariant::
  79
  80         sage: n = ZZ.random_element(2,10).abs()
  81         sage: p = ZZ.random_element(1,n)
  82         sage: K = rearrangement_cone(p,n)
  83         sage: P = SymmetricGroup(n).random_element().matrix()
  84         sage: all([ K.contains(P*r) for r in K.rays() ])
  85         True
  86
  87     """
  88
  89     def d(j):
  90         v = [1]*n    # Create the list of all ones...
  91         v[j] = 1 - p # Now "fix" the ``j``th entry.
  92         return v
  93
  94     V = VectorSpace(QQ, n)
  95     G = V.basis() + [ d(j) for j in range(n) ]
  96     return Cone(G)
  97
  98
  99 def has_rearrangement_property(v, p):
 100     r"""
 101     Test if the vector ``v`` has the "rearrangement property."
 102
 103     The rearrangement cone of order ``p`` in `n` dimensions has its
 104     members vectors of length `n`. The "rearrangement property,"
 105     satisfied by its elements, is to have its smallest ``p`` components
 106     sum to a nonnegative number.
 107
 108     We believe that we have a description of the extreme vectors of the
 109     rearrangement cone: see ``rearrangement_cone()``. This function is
 110     used to test that conic combinations of those extreme vectors are in
 111     fact elements of the rearrangement cone. We can't test all conic
 112     combinations, obviously, but we can test a random one.
 113
 114     To become more sure of the result, generate a bunch of vectors with
 115     ``random_element()`` and test them with this function.
 116
 117     INPUT:
 118
 119     - ``v`` -- An element of a cone suspected of being the rearrangement
 120                cone of order ``p``.
 121
 122     - ``p`` -- The suspected order of the rearrangement cone.
 123
 124     OUTPUT:
 125
 126     If ``v`` has the rearrangement property (that is, if its smallest ``p``
 127     components sum to a nonnegative number), ``True`` is returned. Otherwise
 128     ``False`` is returned.
 129
 130     EXAMPLES:
 131
 132     Every element of a rearrangement cone should have the property::
 133
 134         sage: for n in range(2,10):
 135         ....:     for p in range(1, n-1):
 136         ....:         K = rearrangement_cone(p,n)
 137         ....:         v = random_element(K)
 138         ....:         if not has_rearrangement_property(v,p): print v
 139
 140     """
 141     components = sorted(v)[0:p]
 142     return sum(components) >= 0