Partition backtrack functions for matrices

EXAMPLES:

sage: 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()

Returns 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])
canonical_relabeling()

Returns 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]
display()

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
is_isomorphic(other)

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]
run(partition=None)

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

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