Smith form of integer matrices

Here we give 3 applications of the Smith form algorithm.

(1) Set HS to be the Higman-Sims simple group:

> HS := PermutationGroup<100 |  
>    (2, 3)(6, 9)(8, 13)(10, 14)(11, 17)(12, 19)(15, 27)(16, 24)(18, 26)(20, 
>        32)(21, 28)(25, 35)(29, 40)(30, 37)(31, 39)(36, 41)(38, 44)(42, 47)(45, 
>        48)(46, 56)(49, 60)(50, 54)(51, 63)(53, 64)(55, 66)(57, 67)(58, 68)(59, 
>        70)(61, 73)(62, 72)(65, 76)(69, 81)(74, 83)(75, 79)(78, 80)(89, 92)(91, 
>        95)(94, 97)(96, 98)(99, 100),
>    (3, 4)(5, 6)(7, 10)(8, 11)(12, 18)(13, 21)(16, 24)(17, 28)(19, 31)(20, 
>        33)(22, 27)(23, 35)(26, 39)(29, 36)(30, 41)(37, 40)(38, 46)(42, 49)(43, 
>        51)(44, 53)(45, 55)(47, 58)(48, 59)(50, 61)(52, 57)(54, 62)(56, 64)(60, 
>        68)(66, 70)(69, 71)(72, 73)(75, 79)(76, 85)(77, 80)(83, 87)(86, 89)(88, 
>        91)(94, 96)(97, 99)(98, 100),
>    (4, 5)(6, 9)(10, 16)(11, 17)(12, 20)(14, 24)(15, 28)(18, 30)(19, 32)(21, 
>        27)(22, 34)(25, 38)(26, 37)(29, 40)(31, 42)(33, 43)(35, 44)(36, 45)(39, 
>        47)(41, 48)(46, 57)(50, 54)(51, 59)(53, 65)(55, 58)(56, 67)(61, 74)(63, 
>        70)(64, 76)(66, 68)(69, 79)(73, 83)(75, 81)(77, 86)(78, 80)(84, 88)(87, 
>        90)(91, 94)(95, 97)(99, 100),
>    (5, 8)(6, 11)(7, 12)(9, 15)(10, 18)(13, 22)(14, 25)(16, 29)(17, 28)(19, 
>        23)(21, 27)(24, 36)(26, 39)(30, 40)(31, 35)(37, 41)(38, 45)(42, 50)(43, 
>        52)(44, 54)(46, 55)(47, 48)(49, 61)(51, 57)(53, 62)(56, 60)(58, 59)(64, 
>        68)(66, 73)(69, 71)(70, 72)(76, 83)(77, 80)(78, 84)(81, 82)(85, 87)(86, 
>        88)(89, 91)(97, 98)(99, 100),
>    (1, 2)(6, 10)(9, 16)(11, 18)(13, 23)(14, 24)(15, 29)(17, 30)(19, 22)(21, 
>        27)(25, 36)(26, 37)(28, 40)(31, 35)(32, 34)(38, 45)(39, 41)(42, 44)(46, 
>        59)(47, 48)(50, 54)(51, 57)(55, 58)(56, 69)(60, 71)(63, 75)(64, 77)(66, 
>        78)(67, 79)(68, 80)(70, 81)(72, 82)(73, 84)(76, 86)(83, 88)(85, 89)(87, 
>        91)(90, 94)(93, 96)(99, 100)
> >;

Construct the orbital graph G with 100 vertices, and set A to be the 100 by 100 adjacency matrix of graph G:

> G := OrbitalGraph(HS, 1, {2});
> A := AdjacencyMatrix(G);
> Parent(A);
Full Matrix Algebra of degree 100 over Integer Ring

Note that A has 7700 1-entries (out of a total of 10000 entries):

> &+Eltseq(A);
7700

Print the elementary divisors of A using the Smith form algorithm:

> time ElementaryDivisors(A);
[ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 
21, 21, 21, 231 ]
Time: 0.200

Of course, one can calculate the determinant also using the Smith algorithm:

> time Determinant(A);       
-1648102502800662698588828758017385398170569532348877389799
Time: 0.200

(2) Compute the abelian-quotient invariants of a normal subgroup of G(7, 8) using the Smith algorithm.

> G := func< alpha, n |
>     Group<a, b, d, e | a^2 = b^n =
>     a * b^-1 * a * b * e^(alpha - 1) * a * b^2 * a * b^-2 = 1,
>     e = a * b * a * b^-1, d^b = e,
>     (e * b)^n = (d, e^(alpha - 1)) = 1, e^b = e^alpha * d> >;
> G7_8<a, b, d, e> := G(7, 8);
> R := ncl<G7_8 | e^3>;
> k := Rewrite(G7_8, R: Simplify := false);

Apply the Smith algorithm to the relevant matrix with 1081 rows and 2657 columns.

> time AbelianQuotientInvariants(k);
[ 2, 2, 2, 2, 102, 37842 ]
Time: 69.070

(3) Calculating the Smith form or determinant of arbitrary matrices is easy too:

> m := MatrixAlgebra(IntegerRing(), 50);    
> a := m ! [Random(0,1): i in [1..50^2]];
> a[1];  // the first row
(1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0
1 0 0 0 1 0 1 1 1 1)
> time ElementaryDivisors(a);
[ 2, 87285028673206080 ]
Time: 0.380

Previous Group: Solution of matrix equations