4601.sagews

Example when base field is prime.

p = 13
k = GF(p)
m = matrix(k, 3, [0,11,1, 0,5,8, 0,7,7])
f = m.charpoly().factor(); f

x * (x^2 + x + 5)

P = f[1][0]; P

x^2 + x + 5

S = k.extension(P); S

Univariate Quotient Polynomial Ring in x over Finite Field of size 13 with modulus x^2 + x + 5

S = GF(p^P.degree(), modulus=P, names='a')

S.0.multiplicative_order()

56

m = random_matrix(k, 20)
for P, _ in m.charpoly().factor():
    S = GF(p^P.degree(), modulus=P, names='a')
    print S.0.multiplicative_order(), '\t\t', P

244 x^3 + x^2 + 9*x + 8 185646 x^5 + 12*x^3 + 9*x^2 + 11*x + 3 11649042561240 x^12 + 9*x^11 + 2*x^10 + 3*x^9 + 9*x^8 + 9*x^7 + 12*x^6 + 6*x^5 + 12*x^4 + 10*x^3 + 3*x^2 + 10*x + 10

Example when base field is not prime.

p = 13
k.<a> = GF(p^2)
m = matrix(k, 3, [0,11*a,1, 0,5*a,8, 0,7*a+1,7])
f = m.charpoly().factor(); f

x * (x^2 + (8*a + 6)*x + 5*a + 5)

This is a bit ugly.  

1. Make finite field that contains roots of a factor of f.
2. map base field into that field (by finding a root)
3. map poly into poly over that field
4. find root of that poly
5. compute its order.

P = f[1][0]
S.<b> = GF(p^(P.degree()*k.degree()))
T.<X> = S[]
z = k.modulus()
phi = k.hom([z.roots(S)[0][0]])
T([phi(alpha) for alpha in list(P)]).roots()[0][0].multiplicative_order()

7140

Here's an alternative that uses some of the above, and is surely just worse.

p = 13
k.<a> = GF(p^2)
m = matrix(k, 3, [0,11*a,1, 0,5*a,8, 0,7*a+1,7])
f = m.charpoly().factor()
d = max([e for _, e in f])
m2 = matrix(S, m.nrows(), [phi(alpha) for alpha in m.list()])
[lam.multiplicative_order() for lam in m2.eigenvalues() if lam]

[7140, 7140]