3
$\begingroup$

Given $M \in GL(n,F_2)$ which is known to have a $k^{th}$ root. How can I find a root algorithmically? Can I find all roots?

Other than being invertible and having a $k^{th}$ root I know nothing of M.

If I'm lucky and it happens that $gcd(k, |GL(n,F_2)|)=1$ then I can find the root by raising $M$ to the appropriate power. I'm interested in solving it for the more general case.

(also, is there any software library that can do it for me?)

  • 0
    I'd start trying with k=2, and work from there.2011-04-10

1 Answers 1

1

For any $n$ you can, in principle, find the roots algorithmically by brute force enumeration. When $n$ is small, say $n=2$ or $n=3$, this is actually a very feasible approach - after all, there are just 6 invertible $2\times 2$ matrices over $F_2$, and 168 $3 \times 3$ ones. Raise each one to the $k$th power and see what you get.

For larger $n$, you can probably start by conjugating $M$ into a more convenient form such as the Frobenius Normal form. This may or may not help but if it does it can save a lot of computation.

Much of this can be easily programmed in GAP or SAGE (though I doubt there's a built-in function to do just that - you will need to do some coding).

  • 2
    The Frobenius Normal Form allows you to consider the question on conjugacy classes. Powers of a FNF have relatively easy to describe FNF. For small n you can just enumerate the conjugacy classes and compute the "power maps" between them.2011-04-11