Automorphisms of Matrices Under Row/Column Permutations

[samgonshaw]

Hey all,

I'm trying to implement an algorithm of Alexander Kasprzyk improving the capabilities of PALP's normal form algorithm for lattice polytopes. The procedure uses ideas of finding permutations of rows and columns of matrices, and a few tools for looking at these for example: finding the automorphisms of a matrix under these transformations representing a matrix as a bipartite graph, ordering the rows and columns of a matrix in lex order. 

Firstly I feel these may warrant a module of their own, but any suggestions on where anyone feels they should live?

And secondly, representing a matrix row and column permutation is tricky. I've tried creating a new Matrix Permutation that wraps two elementary matrices, or extending Permutation_class to act on matrices (and iterables in general - PermutationGroupElement can be called on iterables, but not Permutation for some reason?), or returning tuples of the form (Permutation of  rows, Permutation of columns). These all end up being quite clunky. Opinions?

[David Joyner]

On Thu, Aug 16, 2012 at 6:17 AM, samgonshaw <samgo...@gmail.com> wrote:
> Hey all,
>
> I'm trying to implement an algorithm of Alexander Kasprzyk improving the
> capabilities of PALP's normal form algorithm for lattice polytopes. The
> procedure uses ideas of finding permutations of rows and columns of
> matrices, and a few tools for looking at these for example: finding the
> automorphisms of a matrix under these transformations representing a matrix
> as a bipartite graph, ordering the rows and columns of a matrix in lex
> order.
>

Robert Miller has done a lot of work on automorphisms of graphs.
Are you familiar with that code?

> Firstly I feel these may warrant a module of their own, but any suggestions
> on where anyone feels they should live?
>
> And secondly, representing a matrix row and column permutation is tricky.
> I've tried creating a new Matrix Permutation that wraps two elementary
> matrices, or extending Permutation_class to act on matrices (and iterables
> in general - PermutationGroupElement can be called on iterables, but not
> Permutation for some reason?), or returning tuples of the form (Permutation
> of rows, Permutation of columns). These all end up being quite clunky.
> Opinions?

You might also want to look at GAP's function MatrixAutomorphisms.
I
>
> --
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
>
>

[Volker Braun]

The PALP normal form is already unique, so internally it permutes vertices already. What exactly are you trying to implement? Is this just about permutation actions on matrices?

[samgonshaw]

David,

 

Robert Miller has done a lot of work on automorphisms of graphs. 
Are you familiar with that code? 

His code does the work of these functions: the functions convert the matrices to graphs, Miller's functions find the automorphisms of these, and then I return them in a format that will be useful to the other aims of this code: namely to represent permutations of matrices.

You might also want to look at GAP's function MatrixAutomorphisms. 

It doesn't quite achieve what I'm looking at. It checks permutations of columns that preserve rows, while I require also permutations of rows that preserve columns. Not too difficult to obtain from this, but a) I should make a function achieving the desired affect anyway and b) Is it better to have something that a package achieves added natively to SAGE if possible? Or is it better practice to rely more on the packages? 

 

Volker,

The PALP normal form is already unique, so internally it permutes vertices already. What exactly are you trying to implement? Is this just about permutation actions on matrices?

The project at the moment has a few aims, spurred on by talks between Kasprzyk and Kreuzer before he passed:

1) To reimplement the PALP algorithm natively in SAGE, so the code will be easier to understand and build on, as well as more robust avoiding the integer overflows that the PALP code is prone to.

2) To implement a second algorithm that is faster for polytopes whose facet vertex pairing matrix (as used in PALP) has many automorphisms in the sense being talked about here.

3) To then use these to compute a normal form for Laurent polynomials.

So these require these permutation actions on matrices. Just not sure what is the best object to use to represent these permutations. For example, the permutation taking a polytope P to its normal form can then be used to permute the terms of a Laurent polynomial. And the automorphisms of a facet vertex pairing matrix can be fed through to speed up finding the normal form. All these are permutations actions on matrices. How should these be represented? 

[Volker Braun]

I, for one, would love to see more of PALP's algorithms be implemented natively to work without compile-time limits. On http://trac.sagemath.org/12553 I've started working on a PPL-based LatticePolytope_PPL class with that in mind, though its clearly nowhere finished. It can compute  the automorphism group and fibrations of the lattice polytope, though.

You should represent the permutations as PermutationGroupElements:

sage: PermutationGroupElement([3,1,2])

(1,3,2)

Its slightly annoying that permutations are indexed 1,..,n but rows/columns 0,...,n-1 but you'll survive ;-)

There are already methods swap_rows() and swap_columns() for matrices, so you could add permute_rows() and permute_columns() in the same spirit. Right now you can do the following:

sage: g = PermutationGroupElement([3,1,2,4]); g

(1,3,2)

sage: m = random_matrix(ZZ,4); m

[  4   1  -1   1]

[ 27  -1 -17   0]

[  0   1  -1  -4]

[-11   0  -4   0]

sage: g.matrix() * m

[  0   1  -1  -4]

[  4   1  -1   1]

[ 27  -1 -17   0]

[-11   0  -4   0]

but g*m or m*g doesn't work. If you look at sage.groups.perm_gps.permgroup_element.PermutationGroupElement._act_on_() you see that permutations can only act on polynomials so far. It would be nice to extend this to do row/column permutations in O(n^2) instead of O(n^3).

One snag that I ran into when implementing Fan isomorphisms is that Robert Miller's code is great for finding a particular isomorphism of graphs, but if you want to iterate over all isomorphisms (i.e. compose with the automorphism group of the domain or codomain graph) then Sage uses GAP. And GAP is great for big groups, but the latency for calling GAP is pretty bad right now.

[samgonshaw]

I have now uploaded a patch that includes the native algorithm, an alternate algorithm and an implementation of the algorithm to calculate a normal form for Laurent polynomials. This patch out of necessity introduces automorphisms of lattice polytopes and as discussed above permutations acting on matrices. http://trac.sagemath.org/sage_trac/ticket/13525

Feel free to have a look and also consider giving my other recent, related patch (http://trac.sagemath.org/sage_trac/ticket/13282)

[Dima Pasechnik]

I am very curious (I happen to do some work right now on automorphisms of "general" polyhedral cones) 

to find out what this normal form is. It's not described in the PALP original paper, IMHO.

[Volker Braun]

See Section 3.4 of http://arxiv.org/pdf/hep-th/9805190.pdf for the definition of the PALP normal form.

[Volker Braun]

On Monday, September 24, 2012 5:07:09 PM UTC+1, Dima Pasechnik wrote:

I am very curious (I happen to do some work right now on automorphisms of "general" polyhedral cones) 

to find out what this normal form is. It's not described in the PALP original paper, IMHO.

PS: This might be of interest to you which we just recently finished:

sage: sage: from sage.geometry.fan_isomorphism import fan_isomorphism_generator

sage: cone = Cone([(0,0,1), (0,1,1), (1,1,1)])

sage: fan = Fan([cone])

sage: list( fan_isomorphism_generator(fan, fan) )

[

[1 0 0]  [-1  0  0]  [ 1  1  0]  [-1 -1  0]  [ 0  1  0]  [ 0 -1  0]

[0 1 0]  [ 1  1  0]  [ 0 -1  0]  [ 1  0  0]  [-1 -1  0]  [-1  0  0]

[0 0 1], [ 0  0  1], [ 0  1  1], [ 0  1  1], [ 1  1  1], [ 1  1  1]

]

[Dima Pasechnik]

wow, a lot of fan :)