[GAP Forum] Conjugacy in GLn(Z)

Mathieu Dutour mathieu.dutour at gmail.com
Fri May 10 07:38:36 BST 2013


I have a set of matrices in GLn(Z) and I want to reduce them
by conjugacy. The problem is that the existing tools in GAP
seem too slow.

Two matrices (but there are many others) that pose me problem
now are:
g1:=
[ [  -1,   0,   0,   0,   0,   0,   0,   0 ],
  [   0,  -1,   0,   0,   0,   0,   0,   0 ],
  [   0,   0,   0,   0,   0,   0,   1,   0 ],
  [   0,   0,   0,   0,   1,   0,  -1,   0 ],
  [   0,   0,   0,   1,   0,   0,   0,   0 ],
  [   0,   0,   0,   0,   1,   0,   0,   1 ],
  [   0,   0,  -1,   0,   0,   0,   1,   0 ],
  [   0,   0,   0,  -1,   0,   1,  -1,   0 ] ] ;
g2:=
[ [   1,   0,   0,   0,   0,   0,   0,   0 ],
  [   1,  -1,   0,   0,   0,   0,   0,   0 ],
  [   0,   0,   1,   0,   0,   0,   0,   0 ],
  [   0,   0,   1,  -1,   0,   0,   0,   0 ],
  [   0,   0,   0,   0,  -1,   0,   0,   0 ],
  [   0,   0,   0,   0,   0,  -1,   0,   0 ],
  [   0,   0,   0,   0,   1,   1,   1,   1 ],
  [   0,   0,   0,   0,  -1,   0,  -1,   0 ] ];

Two general strategy are available in GAP
1> Use
   RepresentativeAction(GL(8, Integers), g1, g2)
2> Use carat by computing the Bravais groups
   of Gi = BravaisGroup( Group( [gi] ) ), testing
   for conjugacy, computing the normalizer and then
   concluding.

Both approaches fail for g1 and g2, i.e. take too
much time. Of course it is possible to use the
eigenvalue -1 of multiplicity 4 to do a reduction, but
I have been designing a lot of such special cases
algorithm and now I am wondering if there is possibility
of improving the general algorithm.

In Newman, "Integral matrices" it is mentioned for
example that there is a one-to-one correspondence
between the conjugacy classes of matrices A in M_n(Z)
such that f(A)=0 with f irreducible over Q and the ideal
classes of the ring Z[theta] with theta a root of f. Are
such methods used in GAP ?

But this is of course only one aspect of the problem.
For example the matrices [ [0, 1], [1, 0] ] and [ [1, 0], [0,-1]]
are not conjugate because the sum of integral eigenspaces
form a basis of determinant 2 in the first case and 1 in the
second. The enumeration of all sum V1 + V2 of integral
spaces with determinant k is equivalent to the enumeration
of all double cosets H A K with H = GL(n1,Z) x GL(n2,Z),
K = GL(n,Z) and det A = k. Is there a way for achieving this
in GAP ?

Thanks in advance for any help.

  Mathieu


More information about the Forum mailing list