On similar matrices and polynomial matrices I'm teaching linear algebra and I'm encountering this theorem:
two matrices $A$ and B are similar iff $tI - A$ and $tI - B$ are equivalent (as polynomial matrices), where $I$ is the unit matrix.
The proof that I learned and found on all available textbooks is very tricky (to me). So I try to get a more intuitive proof, but end up with the following:
if $tI - A$ and $tI - B$ are equivalent, then $A$ and $B$ have same eigenvalues, and the corresponding eigenvector subspaces are of same dimensions etc.
So, can we move forward in this direction? e.g., if $k$ is an eigenvalue for both $A$ and $B$ and $(kI - A)^n x = 0$ then $(kI - B)^n x = 0$ ...
 A: The beautiful module-theoretic proof given by @user20948 in his comment can be translated into a (long but reasonably nice) elementary proof using right evaluations of (noncommutative) polynomials. I have now expanded this proof at
Darij Grinberg, Similar matrices and equivalent polynomial matrices.
(Mostly written up to have a readable reference around next time I need the result in a class.)
A: This proof is different from the one in Denis Serre's book.
As usual, take $M^A$ and $M^B$ to be the $k[t]$-modules with underlying space $k^n$, where $t$ acts by $A$ and $B$ respectively. Then $A$ is similar to $B$ if and only if $M^A$ and $M^B$ are isomorphic as $k[t]$-modules. As $k[t]$ modules $M^A$ and $M^B$ are both generated by the coordinate vectors $e_1,\dotsc,e_n$, and given by relations (in matrix form)
$\begin{pmatrix} e_1 & e_2 & \cdots & e_n \end{pmatrix}(A-It)=0$
and
$\begin{pmatrix} e_1 & e_2 & \cdots & e_n \end{pmatrix}(B-It)=0$
In general, modules given by matrices of relations are isomorphic if and only if the relation matrices are equivalent.
Thus $A$ and $B$ are similar if and only if $A-tI$ and $B-tI$ are equivalent.
A: Suppose there are matrices P and Q such that P(tI-A)Q=tI-B for all t. Then we conclude that PQ=I, PAQ=B. Or am I missing something?
If P and Q are allowed to depend on t, then all we can conclude is that tI-A and tI-B have the same rank for every t. This is not enough to make A and B similar.
