# Methods for finding the minimal polynomial of a matrix

The only methods I know for determining the minimal polynomial of a matrix involve first calculating its characteristic polynomial, then either testing all possible factors or looking at the generalised eigenspaces as you would for Jordan normal form.

Are there any other good algorithmic methods for calculating it? Ideally, I don't what anything involving row/column operations since I don't know my matrix explicitly, but can determine certain properties like its characteristic polynomial.

I would also be happy if you can give me any methods for calculating other properties of the minimal polynomial like its degree.

EDIT: For clarification, my matrix comes from a group action and is defined over a finite field, so I could also determine the order potentially, but this may be quite computationally intensive.

• "I don't what anything involving row/column operations since I don't know my matrix explicitly..." What properties do you know? – DisintegratingByParts Sep 16 '15 at 16:32
• One possibility is to start with a vector $v_1 \neq 0$. Then form $v_1, Av_1, A^2 v_1, \dots$ until you reach a linear dependency. This linear dependency has the form $p_1(A) v_1 = 0$ for some polynomial $p_1$. Now, choose a second vector $v_2$ with $p_1 (A) v_2 \neq 0$ (if there is no such vector, you are done). As above, obtain a polynomial $q_2$ with $q_2 (A) v_2 = 0$. Let $p_2$ be the least common multiple of $p_1, q_2$ and continue. Finally, you will reach $p_n (A) = 0$. Then $p_n$ will be the minimal polynomial. I don't know however, if you can do this with your available information. – PhoemueX Sep 16 '15 at 16:36
• @TrialAndError Currently, just the characteristic polynomial (so trace and determinant etc) but I am looking for a method that works intrinsically so without caring about the actual numbers itself hence any and all methods like that will do. – Matt B Sep 16 '15 at 16:40
• @PhoemueX: One may as well look for linear dependence among powers $I,A,A^2,\ldots$ of the matrix. – hardmath Sep 16 '15 at 16:43
• Hmm. The Schoof-Elkies-Atkin algorithm used in calculating the order of an elliptic curve does something like this for the Frobenius (acting on $\ell$-torsion). It is not easy. IIRC the original Schoof version just bruteforced the characteristic polynomial, Atkin added an attempt to find eigenvalues, and Elkies added modular curves. And it is the state of the art. I don't know to what extent stuff like it generalizes to abelian varieties (and automorphisms other than Frobenius). But this comparison may indicate that you are asking quite a lot! – Jyrki Lahtonen Oct 9 '15 at 18:23