Partition backtrack functions for matrices#

EXAMPLES:

sage: import sage.groups.perm_gps.partn_ref.refinement_matrices

>>> from sage.all import *
>>> import sage.groups.perm_gps.partn_ref.refinement_matrices

REFERENCE:

  • [1] McKay, Brendan D. Practical Graph Isomorphism. Congressus Numerantium, Vol. 30 (1981), pp. 45-87.

  • [2] Leon, Jeffrey. Permutation Group Algorithms Based on Partitions, I: Theory and Algorithms. J. Symbolic Computation, Vol. 12 (1991), pp. 533-583.

class sage.groups.perm_gps.partn_ref.refinement_matrices.MatrixStruct#

Bases: object

automorphism_group()[source]#

Return a list of generators of the automorphism group, along with its order and a base for which the list of generators is a strong generating set.

For more examples, see self.run().

EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct

sage: M = MatrixStruct(matrix(GF(3),[[0,1,2],[0,2,1]]))
sage: M.automorphism_group()
([[0, 2, 1]], 2, [1])

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct

>>> M = MatrixStruct(matrix(GF(Integer(3)),[[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(2),Integer(1)]]))
>>> M.automorphism_group()
([[0, 2, 1]], 2, [1])
canonical_relabeling()[source]#

Return a canonical relabeling (in list permutation format).

For more examples, see self.run().

EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct

sage: M = MatrixStruct(matrix(GF(3),[[0,1,2],[0,2,1]]))
sage: M.canonical_relabeling()
[0, 1, 2]

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct

>>> M = MatrixStruct(matrix(GF(Integer(3)),[[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(2),Integer(1)]]))
>>> M.canonical_relabeling()
[0, 1, 2]
display()[source]#

Display the matrix, and associated data.

EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct
sage: M = MatrixStruct(Matrix(GF(5), [[0,1,1,4,4],[0,4,4,1,1]]))
sage: M.display()
[0 1 1 4 4]
[0 4 4 1 1]

01100
00011
1

00011
01100
4

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct
>>> M = MatrixStruct(Matrix(GF(Integer(5)), [[Integer(0),Integer(1),Integer(1),Integer(4),Integer(4)],[Integer(0),Integer(4),Integer(4),Integer(1),Integer(1)]]))
>>> M.display()
[0 1 1 4 4]
[0 4 4 1 1]
<BLANKLINE>
01100
00011
1
<BLANKLINE>
00011
01100
4
is_isomorphic(other)[source]#

Calculate whether self is isomorphic to other.

EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct
sage: M = MatrixStruct(Matrix(GF(11), [[1,2,3,0,0,0],[0,0,0,1,2,3]]))
sage: N = MatrixStruct(Matrix(GF(11), [[0,1,0,2,0,3],[1,0,2,0,3,0]]))
sage: M.is_isomorphic(N)
[0, 2, 4, 1, 3, 5]

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct
>>> M = MatrixStruct(Matrix(GF(Integer(11)), [[Integer(1),Integer(2),Integer(3),Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(0),Integer(0),Integer(1),Integer(2),Integer(3)]]))
>>> N = MatrixStruct(Matrix(GF(Integer(11)), [[Integer(0),Integer(1),Integer(0),Integer(2),Integer(0),Integer(3)],[Integer(1),Integer(0),Integer(2),Integer(0),Integer(3),Integer(0)]]))
>>> M.is_isomorphic(N)
[0, 2, 4, 1, 3, 5]
run(partition=None)[source]#

Perform the canonical labeling and automorphism group computation, storing results to self.

INPUT:

  • partition – an optional list of lists partition of the columns; default is the unit partition.

EXAMPLES:

sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct

sage: M = MatrixStruct(matrix(GF(3),[[0,1,2],[0,2,1]]))
sage: M.run()
sage: M.automorphism_group()
([[0, 2, 1]], 2, [1])
sage: M.canonical_relabeling()
[0, 1, 2]

sage: M = MatrixStruct(matrix(GF(3),[[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]))
sage: M.automorphism_group()[1] == 6
True

sage: M = MatrixStruct(matrix(GF(3),[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2]]))
sage: M.automorphism_group()[1] == factorial(14)
True

>>> from sage.all import *
>>> from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct

>>> M = MatrixStruct(matrix(GF(Integer(3)),[[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(2),Integer(1)]]))
>>> M.run()
>>> M.automorphism_group()
([[0, 2, 1]], 2, [1])
>>> M.canonical_relabeling()
[0, 1, 2]

>>> M = MatrixStruct(matrix(GF(Integer(3)),[[Integer(0),Integer(1),Integer(2)],[Integer(0),Integer(2),Integer(1)],[Integer(1),Integer(0),Integer(2)],[Integer(1),Integer(2),Integer(0)],[Integer(2),Integer(0),Integer(1)],[Integer(2),Integer(1),Integer(0)]]))
>>> M.automorphism_group()[Integer(1)] == Integer(6)
True

>>> M = MatrixStruct(matrix(GF(Integer(3)),[[Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(2)]]))
>>> M.automorphism_group()[Integer(1)] == factorial(Integer(14))
True
sage.groups.perm_gps.partn_ref.refinement_matrices.random_tests(n=10, nrows_max=50, ncols_max=50, nsymbols_max=10, perms_per_matrix=5, density_range=(0.1, 0.9))[source]#

Test to make sure that C(gamma(M)) == C(M) for random permutations gamma and random matrices M, and that M.is_isomorphic(gamma(M)) returns an isomorphism.

INPUT:

  • n – run tests on this many matrices

  • nrows_max – test matrices with at most this many rows

  • ncols_max – test matrices with at most this many columns

  • perms_per_matrix – test each matrix with this many random permutations

  • nsymbols_max – maximum number of distinct symbols in the matrix

This code generates n random matrices M on at most ncols_max columns and at most nrows_max rows. The density of entries in the basis is chosen randomly between 0 and 1.

For each matrix M generated, we uniformly generate perms_per_matrix random permutations and verify that the canonical labels of M and the image of M under the generated permutation are equal, and that the isomorphism is discovered by the double coset function.