The number of solutions of a matrix equation

Question

Let $P(X) = a_nX^n + \cdots + a_1X + a_0$ be a polynomial, $a_i \in \mathbb{R}$ for all $i$. Set $$S = \lbrace A \in \mathbb{M}_n: P(A) = 0 \rbrace.$$ We consider the following relation $\sim$ on $S$: $A \sim B$ iff there exists an invertible matrix $C$ such that $B = C^{-1}AC$. It is easy to see that $\sim$ is an equivalence relation on $S$. My question relates to the number of the equivalence classes of $\sim$.

Questions:

(1) Is $S/\sim$ a finite set.

(2) If (1) has an affirmative answer. Find an upper bound formula for $| S/ \sim|$ in term $n$.

Answer 1

The minimal polynomial $\mu_A$ of each matrix $A\in M_n(\mathbb R)$ with $P(A)=0$ divides $P$. Clearly, due to Jordan normal form, there are only finitely many conjugacy classes of such matrices. If you decompose $P$ into irreducible factors: $$ P = P_1^{k_1}\cdots P_r^{k_r} $$ then representatives for each equivalence classes of solutions are given by diagonal joins Jordan blocks with minimal polynomial dividing one of the factors $P_i^{k_i}$. Assume for simplicity that the $P_i$ all have degree $1$, then the number of equivalence classes is given by $$ \sum_{\lambda \textrm{ partiton of $n$ with $r$ parts}} \prod_{i=1}^r \textrm{(Number partitions of $\lambda_i$ with parts $\leq k_i$)} $$ If $P$ doesn't split into linear factors you can modify the formula accordingly. Or, you could just work over $\mathbb C$, since the exact number of eq. classes of solutions over $\mathbb C$ will still be an upper bound for the number of solutions over $\mathbb R$.

Answer 2

You can use Jordan normal form, as Florian does, but you can also use rational canonical form, which gives a uniform theory over any field, and degenerates to Jordan normal form over an algebraically closed field. It is also a nice demonstration of the theory of modules over a PID at work. So, given a field $F$, and a non-zero monic polynomial $p(x) \in F[x],$ we want to classify $n \times n$ matrices $A$ such that $p(A) = 0,$ up to the usual similarity, ie up to conjugacy via an element of ${\rm GL}(n,F).$ These are (up to similarity), the matrices $A$ whose minimum polynomials $m_{A}(x)$ divide $p(x)$ in $F[x].$ There are clearly only finitely many possibilities for such minimum polynomials by uniqueness of factorization in $F[x],$ as minimum polynomials are monic. Hence it suffices to show that there are only finitely many similarity classes of matrices $A$ with a given minimum polynomial $m(x)$. We write the underlying space $V$ of (say) $n$-long column vectors as a direct sum of $A$-invariant subspaces $V = V_{1} \oplus V_{2} \oplus \ldots \oplus V_{k},$ where $k$ is the number of distinct irrducible factors of $m(x)$, and the minimum polynomial of $A$ on each $V_{i}$ is a power of the $i$-th irreducible factor. This reduces us to considering the case that $m(x)$ is a power of a single irreducible polynomial, say $m(x) = q(x)^{t}$ with $q(x)$ monic irreducible, and now $V = V_{1}.$ We may choose a vector $v \in V$ such that $q(A)^{t-1}v \neq 0,$ and then (with a little more theoretical justification , which I omit) ` $\{ v, Av,\ldots A^{dt-1}v \}$ is a basis for a direct summand $W$ of $V$ with respect to which the matrix of $A$ on $W$ is the uniquely determined so-called companion matrix of $m(x)$ (here, $d = {\rm deg}q(x) ).$ By the general theory again, there is an $A$-invariant complement $U$ of $W$ in $V$, and the minimum polynomial of $A$ on $U$ has the form $q(x)^{s}$ for some $s \leq t$. We continue inductively.