Opened 2 years ago

Closed 2 years ago

#25426 closed defect (fixed)

automorphisms_of_rows_and_columns fails on certain 5x5 matrix if bliss is installed

Reported by: dimpase Owned by:
Priority: blocker Milestone: sage-8.3
Component: graph theory Keywords:
Cc: stumpc5 Merged in:
Authors: Travis Scrimshaw Reviewers: Christian Stump
Report Upstream: N/A Work issues:
Branch: db37923 (Commits) Commit: db3792314ac93f966d099c99affb25aac487588c
Dependencies: Stopgaps:

Description

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...

Change History (16)

comment:1 Changed 2 years ago by gh-dimpase

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...).

comment:2 Changed 2 years ago by tscrim

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.

comment:3 Changed 2 years ago by dimpase

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...

comment:4 Changed 2 years ago by tscrim

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.

comment:5 Changed 2 years ago by tscrim

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.

comment:6 Changed 2 years ago by dimpase

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

comment:7 follow-up: Changed 2 years ago by 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]]
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?

comment:8 in reply to: ↑ 7 ; follow-up: Changed 2 years ago by dimpase

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.

comment:9 in reply to: ↑ 8 Changed 2 years ago by tscrim

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.

comment:10 Changed 2 years ago by stumpc5

  • Branch set to u/stumpc5/fix_25426

comment:11 Changed 2 years ago by stumpc5

  • Commit set to db3792314ac93f966d099c99affb25aac487588c

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


New commits:

db37923fix #25426

comment:12 Changed 2 years ago by stumpc5

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

comment:13 Changed 2 years ago by tscrim

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

comment:14 Changed 2 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Reviewers set to Christian Stump
  • Status changed from new to needs_review

comment:15 Changed 2 years ago by stumpc5

  • Status changed from needs_review to positive_review

comment:16 Changed 2 years ago by vbraun

  • Branch changed from u/stumpc5/fix_25426 to db3792314ac93f966d099c99affb25aac487588c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.