A matrix has a minpoly even if factoring is uncomputable

[darijgr]

Problem Description

If A is an n*n-matrix over a field F, then we can compute the minimal polynomial of A by finding the dimension -- say k -- of the span of the powers A^0, A^1, ..., A^{n-1} and writing A^k as a linear combination of A^0, A^1, ..., A^{k-1}. This does not require any factoring oracles, just usual linear algebra. As it stands, the minpoly method errors out when it does not know how to factor.

Proposed Solution

Quick and dirty:

n = A.nrows()
pow = A**0
pows = []
for k in range(n+1):
     pows.append(vector(pow.list()))
     pow *= A
     Mpows = Matrix(pows)
     try:
         cs = Mpows.solve_left(vector(pow.list()))
     except ValueError:
         continue
     P = PolynomialRing(A.base_ring(), "x")
     x = P.gen()
     return x**(k+1) - P.sum(cs[i] * x**i for i in range(k+1))

Alternatives Considered

...

Additional Information

...

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.