automorphisms_of_rows_and_columns fails on certain 5x5 matrix if bliss is installed

[dimpase]

In #24924 bliss was enabled for computing automorphisms of edge-coloured graphs. The latter is used for automorphisms_of_rows_and_columns() of matrices. For the following matrix j, with bliss installed, we have failure, found on #25399, see comment 10 there. Namely

sage: j = matrix([(3, 2, 1, 0, 0),
....:  (2, 2, 0, 1, 0),
....:  (1, 0, 3, 0, 2),
....:  (0, 1, 0, 2, 1),
....:  (0, 0, 2, 1, 2)])
sage: j.automorphisms_of_rows_and_columns()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...

This is probably due to wrong order of elements in generators produced by the bliss interface:

sage: gj=j.as_bipartite_graph()
sage: gj.automorphism_group(edge_labels=True,algorithm="bliss")
Permutation Group with generators [(10,2)(1,8)(3,6)(4,9)(5,7), (10,5)(1,6)(2,7)(3,8)(4,9)]
sage: gj.automorphism_group(edge_labels=True,algorithm="sage")
Permutation Group with generators [(1,3)(2,5)(6,8)(7,10), (1,6)(2,7)(3,8)(4,9)(5,10)]

That (10,2) and (10,5) cycles don't look good...

CC: @stumpc5

Component: graph theory

Author: Travis Scrimshaw

Branch/Commit: db37923

Reviewer: Christian Stump

Issue created by migration from https://trac.sagemath.org/ticket/25426

[dimpase]

comment:1

In particular, one can see that the order of elements in cycles is important:

age: aa=gj.automorphism_group(edge_labels=True,algorithm="bliss")
sage: aa.gens()
[(10,2)(1,8)(3,6)(4,9)(5,7), (10,5)(1,6)(2,7)(3,8)(4,9)]
sage: aa.order() # this is correct
4
sage: PermutationGroup(map(Permutation,aa.gens())).order() # nonsense!
960

whereas having "sage" instead of "bliss" above gives 4 in both outputs.
Indeed, it's Permutation() that does not like wrongly ordered cycles:

sage: Permutation(aa.gens()[0]) # 2->10, but 10->4, not 10->2 !!!
[2, 8, 10, 6, 9, 7, 3, 5, 1, 4]

Perhaps it should be fixed instead, I don't know (but it's a mess, I recall ncohen getting really upset about the quality of the code there...).

[tscrim]

comment:2

I have my suspicions that it is not in Permutation as elements of PermutationGroup are stored in GAP as lists and converted to cycles for their print representation. So my guess is the creation of the permutation group elements is going wrong somehow.

[dimpase]

comment:3

well, should Permutation throw an error if it encountered wrong order of elements in a cycle?

specifically, you see that the group is fine, while convering its elements into lists goes nuts...

[tscrim]

comment:4

I gave the wrong cycles to from_cycles() and I got the correct output. So I think there is an assumption made about the internal storage of the permutation group element, and these not-properly-ordered cycles are saying some (likely undocumenred) internal assumption is violated. I can look into this more tomorrow.

[tscrim]

comment:5

Okay, so the issue is roughly stemming from the domain being non-standard from the bliss group:

sage: cycles = [[(10,2), (1,8), (3,6), (4,9), (5,7)], [(10,5), (1,6), (2,7), (3,8), (4,9)]]
sage: PermutationGroup(cycles, domain=[10,1,2,3,4,5,6,7,8,9])
Permutation Group with generators [(10,2)(1,8)(3,6)(4,9)(5,7), (10,5)(1,6)(2,7)(3,8)(4,9)]
sage: PermutationGroup(cycles, domain=[1,2,3,4,5,6,7,8,9,10])
Permutation Group with generators [(1,6)(2,7)(3,8)(4,9)(5,10), (1,8)(2,10)(3,6)(4,9)(5,7)]

This generates the out-of-order cycles. However, things seem to be generally broken for these permutation group elements:

sage: G = gj.automorphism_group(edge_labels=True,algorithm="bliss")
sage: G.domain()
{10, 1, 2, 3, 4, 5, 6, 7, 8, 9}
sage: x = G.gens()[0]
sage: x
(10,2)(1,8)(3,6)(4,9)(5,7)
sage: x._gap_list()
[3, 9, 1, 7, 10, 8, 4, 6, 2, 5]
sage: x.domain()
[2, 8, 10, 6, 9, 7, 3, 5, 1, 4]

So I think there is an implicit assumption that when the domain in [n], it should be sorted.

[dimpase]

comment:6

it is a typical GAP thing, unsorted lists output as orbits.

[tscrim]

comment:7

So in my opinion, Permutation is doing the correct thing:

sage: G = gj.automorphism_group(edge_labels=True,algorithm="bliss")
sage: map(Permutation, G)
[[10, 1, 2, 3, 4, 5, 6, 7, 8, 9],
 [5, 6, 7, 8, 9, 10, 1, 2, 3, 4],
 [2, 8, 10, 6, 9, 7, 3, 5, 1, 4],
 [7, 3, 5, 1, 4, 2, 8, 10, 6, 9]]
sage: list(G)
[(),
 (10,5)(1,6)(2,7)(3,8)(4,9),
 (10,2)(1,8)(3,6)(4,9)(5,7),
 (10,7)(1,3)(2,5)(6,8)]

Permutation rightly has a domain of [1, ..., 10], but it is the return trip that is the problem. I think your test in comment:1 is a bit wrong because PermutationGroup (also rightly) assumes a domain of [1, ..., 10]. However, there is an issue:

sage: PermutationGroup(map(list, map(Permutation, G)), domain=G.domain()).order()
4
sage: PermutationGroup(map(Permutation, G), domain=G.domain()).order()
1920

in particular PermutationGroup is ignoring the domain input when given a list of Permutation's. I am somewhat hesitant to call this a bug given the natural domain of Permutation (this also is completely broken for non-standard permutations).

In many ways this is a red herring because automorphisms_of_rows_and_columns makes the assumption that the domain is [1, ..., nrows]. I am tempted to have the bliss automorphism_group method sort the vertices of G (if able to) before returning the PermutationGroup.

Thoughts?

[dimpase]

comment:8

Replying to @tscrim:

So in my opinion, Permutation is doing the correct thing:

sage: G = gj.automorphism_group(edge_labels=True,algorithm="bliss")
sage: map(Permutation, G)
[[10, 1, 2, 3, 4, 5, 6, 7, 8, 9],
 [5, 6, 7, 8, 9, 10, 1, 2, 3, 4],
 [2, 8, 10, 6, 9, 7, 3, 5, 1, 4],
 [7, 3, 5, 1, 4, 2, 8, 10, 6, 9]]

this makes no sense to me. How come there is no identify permutation in this list?! At best, what we see here is a coset of the Klein 4-group...

sage: list(G)
[(),
 (10,5)(1,6)(2,7)(3,8)(4,9),
 (10,2)(1,8)(3,6)(4,9)(5,7),
 (10,7)(1,3)(2,5)(6,8)]

Permutation rightly has a domain of [1, ..., 10], but it is the return trip that is the problem. I think your test in comment:1 is a bit wrong because PermutationGroup (also rightly) assumes a domain of [1, ..., 10]. However, there is an issue:

sage: PermutationGroup(map(list, map(Permutation, G)), domain=G.domain()).order()
4
sage: PermutationGroup(map(Permutation, G), domain=G.domain()).order()
1920

in particular PermutationGroup is ignoring the domain input

I don't understand. Domains are, mathematically, sets, not lists.

when given a list of Permutation's. I am somewhat hesitant to call this a bug given the natural domain of Permutation (this also is completely broken for non-standard permutations).

In many ways this is a red herring because automorphisms_of_rows_and_columns makes the assumption that the domain is [1, ..., nrows]. I am tempted to have the bliss automorphism_group method sort the vertices of G (if able to) before returning the PermutationGroup.

Thoughts?

the background is that to respect edge-labels, the implementation by Christian constucts an auxiliary graph, and then cuts out the relevant subdomain action.

[tscrim]

comment:9

Replying to @dimpase:

Replying to @tscrim:

So in my opinion, Permutation is doing the correct thing:

this makes no sense to me. How come there is no identify permutation in this list?! At best, what we see here is a coset of the Klein 4-group...

I don't understand. Domains are, mathematically, sets, not lists.

Perhaps in the strict sense, but here, we need to know what the identity permutation is. So an domain is an ordered set, i.e., a list, and that ordering defines the identity permutation. So in the example above, [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] is the identity.

when given a list of Permutation's. I am somewhat hesitant to call this a bug given the natural domain of Permutation (this also is completely broken for non-standard permutations).

In many ways this is a red herring because automorphisms_of_rows_and_columns makes the assumption that the domain is [1, ..., nrows]. I am tempted to have the bliss automorphism_group method sort the vertices of G (if able to) before returning the PermutationGroup.

Thoughts?

the background is that to respect edge-labels, the implementation by Christian constucts an auxiliary graph, and then cuts out the relevant subdomain action.

It is that cut out that assumes the domain/identity is [1, ..., nrows], which is the source of the problem.

[stumpc5]

Branch: u/stumpc5/fix_25426

[stumpc5]

Commit: db37923

[stumpc5]

comment:11

According to Travis, this fixes the bug (and it indeed does), I haven't really gotten into the hack, though...

---

New commits:

db37923

fix #25426

[stumpc5]

comment:12

sage: j.automorphisms_of_rows_and_columns()
[((), ()), ((1,3)(2,5), (1,3)(2,5))]

sage: gj=j.as_bipartite_graph()
sage: a = gj.automorphism_group(edge_labels=True,algorithm="bliss")
sage: b = gj.automorphism_group(edge_labels=True,algorithm="sage")
sage: a == b
True

[tscrim]

comment:13

This gets around the domain issue I noted above. Dima, is this change is okay with you?

[tscrim]

Reviewer: Christian Stump

[tscrim]

Author: Travis Scrimshaw

[vbraun]

Changed branch from u/stumpc5/fix_25426 to db37923