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.