mjo/cone/permutation_invariant.py

   1 from sage.all import *
   2
   3 def random_permutation_invariant_cone(lattice=None,
   4                                       min_ambient_dim=0,
   5                                       max_ambient_dim=None,
   6                                       min_rays=0,
   7                                       max_rays=None,
   8                                       strictly_convex=None,
   9                                       solid=None):
  10     r"""
  11     Return a random permutation-invariant cone.
  12
  13     A cone ``K`` is said to be permutation-invariant if ``P(K) == K``
  14     for all permutation matrices ``P``. To generate one, we can begin
  15     with any cone, and construct the set of all permutations of its
  16     generators. The resulting set will generate a permutation-invariant
  17     cone by construction.
  18
  19     All of this function's parameters are passed to ``random_cone()``
  20     function used to generate the initial cone whose generators we will
  21     permute.
  22     """
  23     K = random_cone(lattice=lattice,
  24                     min_ambient_dim=min_ambient_dim,
  25                     max_ambient_dim=max_ambient_dim,
  26                     min_rays=min_rays,
  27                     max_rays=max_rays,
  28                     strictly_convex=strictly_convex,
  29                     solid=solid)
  30
  31     # We'll need this to turn rays into vectors so that we can permute
  32     # them with permutation matrices.
  33     V = K.lattice().vector_space()
  34
  35     # The set of all permutatin matrices on ``V``.
  36     Sn = ( p.matrix() for p in SymmetricGroup(V.dimension()) )
  37
  38     # Set of permuted generators
  39     pgens = ( permutation*V(g) for permutation in Sn for g in K )
  40
  41     return Cone(pgens, K.lattice())
  42
  43
  44 def is_permutation_invariant(K):
  45     r"""
  46     Determine if ``K`` is permutation-invariant.
  47
  48     A cone is said to be permutation-invariant if ``P(K)`` is a subset
  49     of ``K`` for every permutation matrix ``P``.
  50
  51     SETUP::
  52
  53         sage: from mjo.cone.nonnegative_orthant import nonnegative_orthant
  54         sage: from mjo.cone.permutation_invariant import is_permutation_invariant
  55         sage: from mjo.cone.rearrangement import rearrangement_cone
  56
  57     EXAMPLES:
  58
  59     The rearrangement cone is permutation-invariant::
  60
  61         sage: all( is_permutation_invariant(rearrangement_cone(p,n))
  62         ....:               for n in range(3, 6)
  63         ....:               for p in range(1, n) )
  64         True
  65
  66     As is the nonnegative orthant::
  67
  68         sage: K = nonnegative_orthant(ZZ.random_element(5))
  69         sage: is_permutation_invariant(K)
  70         True
  71
  72     """
  73     # We'll need this to turn rays into vectors so that we can permute
  74     # them with permutation matrices.
  75     V = K.lattice().vector_space()
  76
  77     # The set of all permutation matrices on ``V``.
  78     Sn = ( p.matrix() for p in SymmetricGroup(V.dimension()) )
  79
  80     return all(K.contains(permutation*V(g))
  81                    for g in K
  82                    for permutation in Sn)