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