So I just felt the need to refresh my concepts a bit, so I started reading about minimal polynomials. The minimal polynomial $p_A$ for a matrix ${\bf A}$, can be defined as the smallest degree monic polynomial (with coefficients in the field which it's elements belong to) such that $$p_A({\bf A}) = {\bf 0}$$ $\phantom{And is related to the concepts *algebraic* and *geometric* multiplicities of eigenvalues in the following sense:}$

Having learned about the Jordan Normal Form and the block diagonalization it gives, and definition of generalized eigenspaces $({\bf A}-\lambda{\bf I})^k = 0$, I have made the following guess :

The minimal polynomial will be $p_A(x) = \prod(x-\lambda_k)^{l_k}$, where $l_k$ is the largest sized jordan block associated with $\lambda_k$.

Does this make any sense or am I forgetting something important?

Also a related follow-up question, how fast is it to calculate the rank of a matrix nowadays, in comparison to other matrix operations?

I was thinking that if rank calculations are fast and we are unsure about the Jordan block sizes but just wanting to find the minimal polynomial, one could find out when (for which $l$) the rank of $({\bf A}-\lambda_k {\bf I})^l$ ceases to decrease.

Is this sensible?

  • 2
    $\begingroup$ The complexity of rank computing, for a matrix of size $n$ and classical row-reduction is $O(n^3)$. Your guess is perfectly right. $\endgroup$ – Bernard Oct 6 '15 at 14:03

It is true that the when a matrix has a Jordan normal form, the size of the largest block for an eigenvalue $\lambda$ equals the multiplicity of$~\lambda$ as root of the minimal polynomial. This is easy to see by computing powers of $J-\lambda I$ for a general Jordan normal form matrix$~J$ (in the $k$-th power the blocks for $\lambda$ with size at most$~k$ become zero, but other blocks do not).

However Jordan normal forms do not always exist over the field of definition of the matrix; you may need to extend the field in order to find the Jordan normal form. Computing a minimal polynomial with say rational coefficients in this way would be very cumbersome. And that while it is perfectly possible to compute the minimal polynomial directly; I would guess it requires about the same number of operations over the defining field as Gaussian elimination does, i.e., $O(n^3)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.