Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I'd start trying with k=2, and work from there. –  Thomas Andrews Apr 10 '11 at 18:12

1 Answer 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).

share|improve this answer
    
In principle. ${}$ –  Mariano Suárez-Alvarez Apr 11 '11 at 5:02
    
Oops. Corrected. Thanks! –  Alon Amit Apr 11 '11 at 5:15
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. –  Jack Schmidt Apr 11 '11 at 17:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.