Prove that $A$ and $B$ are not similar I have a question and a possible solution. Please let me know if I'm wrong:

Let $A,B$ be a complex matrices $n \times n$. Prove that if there is some polynomial $q(t)$ such that $q(A)=0$ and $q(B)\ne0$, than $A$ and $B$ are not similar matrices.

Possible Solution
From the Cayley Hamilton theorem we know that the minimal polynomial of a matrix divides every polynomial in which $q(A)=0$. 
From the above we know that $A$'s minimal polynomial divides $q(A)$, and $B$'s minimal polynomial does not divide $q(B)$. 
Therefore, $A,B$ do not have the same minimal polynomial and they are not similar.
Am I correct? If I'm not, please do not hesitate to give an alternative solution.
Alan
 A: That's because if $A$ and $B$ are similar then $B = P^{-1}AP$ which means that $B^n = P^{-1}A^nP$ for natural numbers $n$ (even if $n=0$) this in turn means that $q(B) = P^{-1}q(A)P$. So if $q(A)=0$ then so is $q(B)$.
A: Let the polynomial such that $q(A) = 0$ and $q(B) = \lambda \neq 0$ be represented by
$q(t) = \sum_{k = 0}^n a_k t^k$
Now since $A$ and $B$ are similar there exists a matrix $P$ such that $A = P^{-1}BP$.
Now take 
$0 = q(A) = q(P^{-1}BP) = \sum_{k = 0}^n a_k (P^{-1}BP)^k = P^{-1}\left ( \sum_{k = 0}^n a_k B^k\right ) P^{-1} = P^{-1}q(B)P$
Which means $q(B)$ is also 0. Somewhere in the middle there we used the crucial property that $(P^{-1}BP)^k = P^{-1} B^k P$ which works because all the factors $P^{-1}P$ which occur in between the $B$s cancel to $I$s. This is something we end up using often and which is the reason matrices and polynomials mix so well as concepts. 
A: The fundamental definition of a minimal polynomial (in the context of linear algebra) is for a linear operator on a finite dimensional vector space, not for a matrix. In other words it does not require any basis to be chosen (in order to describe the operator$~\phi$ by a matrix), it is just the minimal degree monic polynomial$~P$ such that $P[\phi]=0$, which statement does not involve any basis. Having a matrix for$~\phi$ is merely convenient for checking whether or not $P[\phi]=0$, but in no way necessary for the definition.
That being said, it is clear that of $\def\B{\mathcal B}A=\operatorname{Mat}_\B(\phi)$ for any basis$~\B$ of the vector space that $\phi$ acts on, then $P[\phi]$ is the zero operator if and only if $P[A]$ is the zero matrix. Therefore the minimal polynomial of$~\phi$ equals the minimal polynomial of$~A$. In particular it follows that if $A,A'$ are both  matrices for the same operator$~\phi$, but with respect to different bases (or what amounts to the same, if $A'$ is obtained from $A$ by some change of basis $A'=C^{-1}AC$), then $A$ and $A'$ have the same minimal polynomial (namely that of$~\phi$). In other words: similar matrices have the same minimal polynomial, which is what you asked for.

Of course you can check by a computation that $P[A]=0$ implies $P[A']=0$ and vice versa, but such a check is not really necessary, as the whole set-up implies that this must be the case. By contrast, such a check would probably be necessary in case of the characteristic polynomial instead of the minimal polynomial, since the characteristic polynomial is usually defined in terms of a matrix, rather than directly in terms of the linear operator represented by it. (It is probably possible to give an definition of the characteristic polynomial that avoids using any matrix, but this would require some abstract theory of determinants going beyond the case of linear operators on a vector space; this is not usual approach.)
