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 lyapunov_rank
  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([ lyapunov_rank(rearrangement_cone(p,n)) == n
  68         ....:               for n in range(2, 10)
  69         ....:               for p in [1, n-1] ])
  70         True
  71         sage: all([ lyapunov_rank(rearrangement_cone(p,n)) == 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)