Why does counting companion matrices count conjugacy classes?

Question

A method of counting conjugacy classes of say $GL(n,\mathbb{F}_q)$ is to count the possible companion matrix blocks in the rational canonical form by counting the possible monic irreducible polynomials that satisfy the rational canonical form properties.

Summing up all possible ways to write rational canonical forms by companion matrices gives the number of conjugacy classes. Why do they count the same thing?

Answer 1

This is because the rational canonical form (block diagonal with companion matrices for the invariant factors, ordered by divisibility) is, um..., canonical. Two matrices are in the same conjugacy class of $GL(n,\mathbb{F}_q)$ if and only if they have the same rational canonical form. In other words every matrix is similar to its rational canonical form, and no two rational canonical forms are similar (which is by the uniqueness of the list of invariant factors, thanks to the divisibility requirement).

Answer 2

There is a canonical bijection between the set of similarity classes in $M(n,K)$ and the set of isomorphism classes $K[X]$-module structures on $K^n$.

Here $K$ is a field, $n$ a positive integer, and $X$ an indeterminate.

The $K[X]$-module structure on $K^n$ attached to a matrix in $M(n,K)$ is the obvious one.