Similar matrices and field extensions 
Given a field $F$ and a subfield $K$ of $F$. Let $A$, $B$ be $n\times n$ matrices such that all the entries of $A$ and $B$ are in $K$. Is it true that if $A$ is similar to $B$ in $F^{n\times n}$ then they are similar in $K^{n\times n}$?

Any help ... thanks!
 A: Just a remark which develops Pierre's and Soarer's answers toward abstract algebra.
Proposition. Let $A \subseteq B$ an extension of domains. Suppose that $A$ is a PID and $B$ is a Dedekind domain. Let $K$ be the field of quotients of $A$ and suppose that $B \cap K = A$. If $M$ and $N$ are finite $A$-modules such that $M \otimes_A B$ and $N \otimes_A B$ are isomorphic as $B$-modules, then $M$ and $N$ are isomorphic as $A$-modules.
The proposition implies the thesis on similar matrices if we consider the extension $F[t] \subseteq K[t]$. The proposition can be applied to every finite extension $A \subseteq B$, where $A$ is a PID and $B$ is a Dedekind domain.
Proof of the proposition. From the structure theorem of finite modules over PIDs, we have $M = A/I_1 \oplus \cdots \oplus A/I_r$ and $N = A / J_1 \oplus \cdots \oplus A / J_s$, where $I_1 \subseteq \cdots \subseteq I_r$ and $J_1 \subseteq \cdots \subseteq J_s$ are proper ideals of $A$. Then:
$$
(1) \qquad \qquad \qquad \qquad M \otimes_A B = B / I_1 B \oplus \cdots \oplus B / I_r B
$$
$$
(2) \qquad \qquad \qquad \qquad N \otimes_A B = B / J_1 B \oplus \cdots \oplus B / J_s B.
$$
The condition $B \cap K = A$ implies that if $I$ is a proper ideal of $A$ then $IB$ is a proper ideal of $B$. So all summands of (1) and (2) are not trivial.
Since $I_rB \subsetneqq B$, there exists a maximal ideal $\mathfrak{m}$ of $B$ such that $\mathfrak{m} \supseteq I_r B$. We have that $M \otimes_A B_\mathfrak{m}$ and $N \otimes_A B_\mathfrak{m}$ are isomorphic as $B_\mathfrak{m}$-modules. Since $B_\mathfrak{m}$ is a PID, from the uniqueness of the structure of direct sum of cyclic modules, we have $I_i B_\mathfrak{m} = J_i B_\mathfrak{m}$ for all $i = 1, \dots, r$; in particular we have $r \geq s$. Picking a maximal ideal containing $J_sB$ we prove that $r \leq s$. So $r = s$.
Repeating the same argument of uniqueness of the structure, we prove that for all $\mathfrak{q} \in \mathrm{Specm} \ B$, $I_i B_\mathfrak{q} = J_i B_\mathfrak{q}$ for all $i =1, \dots, r$. From the arbitrariness of $\mathfrak{q} \in \mathrm{Specm} \ B$, we have $I_i B = J_i B$ for all $i$. Since $I_i B, J_i B$ are principal ideals of $B$ and $B \cap K = A$, we deduce that $I_i = J_i$. QED
A: Let $E/F$ be an extension. We claim that two squares matrices with coefficients in $F$ are similar over $F$ if they are similar over $E$. 
Let $X$ be an indeterminate. For any field $K$ write $K'$ for the set of irreducible monic polynomials in $K[X]$. Let $V$ be a finite dimensional $F[X]$-module. It suffices to show that 

the isomorphism class of the $F[X]$-module $V$ can be recovered from the isomorphism class of the $E[X]$-module $V_E:=E\otimes_FV$. 

By the Chinese Remainder Theorem and (1) below, there are unique finitely supported maps 
$$
n:F'\times\mathbb N\to\mathbb N,\quad m:E'\times\mathbb N\to\mathbb N
$$ 
which are weakly decreasing in the second variable and satisfy 
$$
V\simeq\bigoplus_{f,i}\ F[X]/(f^{n(f,i)}),\quad 
V_E\simeq\bigoplus_{e,i}\ E[X]/(e^{m(e,i)}). 
$$
We musty prove that $n$ can be recovered from $m$. 
We have $$V_E\simeq\bigoplus_{f,i}\ E[X]/(f^{n(f,i)}).$$ 
There is a unique map $k:F'\times E'\to\mathbb N$ which is finitely supported in the second variable and satisfies 
$$
f=\prod_e\ e^{k(f,e)}  
$$ 
for all $f$. As, for each $e$ there is at most one $f$ such that $k(f,e)\not=0$, the claim follows from the isomorphism 
$$
V_E\simeq\bigoplus_{e,f,i}\ E[X]/(e^{k(f,e)n(f,i)}).
$$ 
QED 
(1) Let $A$ be the ring $F[X]/(f^n)$ where $f$ is irreducible and $n\ge1$. Let $V$ be a finite dimensional $A$-module. Then there are $v_1,\dots,v_k\in V$ such that $V=Av_1\oplus\cdots\oplus Av_k$. 
Proof. We can assume that there is a $v$ in $V$ with $f^{n-1}v\not=0$ (otherwise replace $n$ by $n-1$). Let $\mathcal W$ be the set of those sub-$A$-modules $W$ of $V$ whose intersection with $Av$ is zero, let $W$ be a maximal element of  $\mathcal W$, and assume by contradiction that there is an $x$ in $V$ which is not in $Av+W$. Let $i$ be the least positive integer such that $f^ix$ is in $Av$. On replacing $x$ by $f^{i-1}x$ if $i\ge2$, we may assume $i=1$. We have $fx=f^jav$ with $0\le j\le n$ and $a$ a unit of $A$. As $j=0$ would imply $f^nx\not=0$, we have $j\ge1$. But then $W+K(x-f^{j-1}av)$ is an element of $\mathcal W$ which contradicts the maximality of $W$. An obvious induction on $\dim V$ completes the proof. QED 
A: If the fields are infinite, there is an easy proof.
Let $F \subseteq K$ be a field extension with $F$ infinite. Let $A, B \in \mathcal{Mat}_n(F)$ be two square matrices that are similar over $K$. So there is a matrix $M \in \mathrm{GL}_n(K)$ such that $AM = MB$. We can write:
$$
M = M_1 e_1 + \dots + M_r e_r,
$$
with $M_i \in \mathcal{M}_n(F)$ and $\{ e_1, \dots, e_r \}$ is a $F$-linearly independent subset of $K$. So we have $A M_i = M_i B$ for every $i = 1,\dots, r$. Consider the polynomial
$$
P(t_1, \dots, t_r) = \det( t_1 M_1 + \dots + t_r M_r) \in F[t_1, \dots, t_r ].
$$
Since $\det M \neq 0$, $P(e_1, \dots, e_r) \neq 0$, hence $P$ is not the zero polynomial. Since $F$ is infinite, there exist $\lambda_1, \dots, \lambda_r \in F$ such that $P(\lambda_1, \dots, \lambda_r) \neq 0$. Picking $N = \lambda_1 M_1 + \dots + \lambda_r M_r$, we have $N \in \mathrm{GL}_n(F)$ and $A N = N B$.
A: 
THEOREM 1. Let $E$ be a field, let $F$ be a subfield, and let $A$ and $B$ be $n$ by $n$ matrices with coefficients in $F$. If $A$ and $B$ are similar over $E$, they are similar over $F$.

This is an immediate consequence of

THEOREM 2. In the above setting, let $X$ be an indeterminate, and let $g_k(A)\in F[X]$, $1\le k\le n$, be the monic gcd of the determinants of all the $k$ by $k$ submatrices of $X-A$. Then $A$ and $B$ are similar over $F$ if and only if $g_k(A)=g_k(B)$ for all $k$.

References:
Basic Algebra I: Second Edition, Jacobson, N., Section 3.10.
A Survey of Modern Algebra, Birkhoff, G. and Lane, S.M., 2008. In the 1999 edition it was in Section X1.8, titled
"The Calculation of Invariant Factors".
Algèbre: Chapitres  4 à 7, Nicolas Bourbaki. Translation: Algebra II.
(I haven't found online references.)
Here is the sketch of a proof of Theorem 2.
EDIT [This edit follows Soarer's interesting comment.] Each of the formulas $fv:=f(A)v$ and $fv:=f(B)v$ (for all $f\in F[X]$ and all $v\in F^n$) defines on $F^n$ a structure of finitely generated module over the principal ideal domain $F[X]$. Moreover, $A$ and $B$ are similar if and only if the corresponding modules are isomorphic. The good news is that a wonderful theory for the finitely generated modules over a principal ideal domain is freely available to us. TIDE

THEOREM 3. Let $A$ be a principal ideal domain and $M$ a finitely generated $A$-module. Then $M$ is isomorphic to $\oplus_{i=1}^nA/(a_i)$, where the $a_i$ are elements of $A$ satisfying $a_1\mid a_2\mid\cdots\mid a_n$. [As usual $(a)$ is the ideal generated by $a$ and $a\mid b$ means "$a$ divides $b$".] Moreover the ideals $(a_i)$ are uniquely determined by these conditions.

Let $K$ be the field of fractions of $A$, and $S$ a submodule of $A^n$. The maximum number of linearly independent elements of $S$ is also the dimension of the vector subspace of $K^n$ generated by $S$. Thus this integer, called the rank of $S$, only depends on the isomorphism class of $S$ and is additive with respect to finite direct sums.

THEOREM 4. In the above setting we have:
(a) $S$ is free of rank $r\le n$.
(b) There is a basis $u_1,\dots,u_n$ of $A^n$ and there are elements $a_1,\dots,a_r$ of $A$ such that $a_1u_1,\dots,a_ru_r$ is a basis of $S$, and $a_1\mid a_2\mid\cdots\mid a_r$.

Let $A$ be a commutative ring with one. Recall that $A$ is a principal ideal ring if all its ideals are principal, and that $A$ is a Bézout ring if all its finitely generated ideals are principal.

LEMMA. Let $A$ be a Bézout ring and let $c,d$ be in $A$. Let $\Phi$ be a set of ideals of $A$ such that: $(c)$ and $(d)$ are in $\Phi$; $(c)$ is maximal in $\Phi$; and $(ac+bd)\in\Phi$ for all $a,b\in A$. Then $c$ divides $d$ [equivalently $(c)$ contains $(d)$].

Proof. We have $(c,d)=(ac+bd)$ for some $a,b\in A$. This ideal belongs to $\Phi$, contains $(c)$ and is thus equal to $(c)$. Hence we get $(d)\subset(c,d)=(c)$. QED

PROPOSITION 1. Let $A$ be a principal ideal ring and $f$ an $A$-valued bilinear map defined on a product of two $A$-modules. Then the image of $f$ is an ideal.

Proof. Let $\Phi$ be the set of all ideals of the form $(f(x,y))$; pick $x,y$ such that $(f(x,y))$ is maximal in $\Phi$; and let $(f(u,v))$ be another element of $\Phi$. It suffices to show that $f(x,y)\mid f(u,v)$.
Claim: $f(x,y)\mid f(x,v)$ and $f(x,y)\mid f(u,y)$.
Since we have $af(x,y)+bf(x,v)=f(x,ay+bv)$ and $af(x,y)+bf(u,y)=f(ax+bu,y)$, the claim follows from the lemma.
By the claim we have $f(u,y)=af(x,y)$ and $f(x,v)=bf(x,y)$ for some $a,b\in A$. Setting $u'=u-av$, $v'=v-by$ we get $f(x,v')=0=f(u',y)$ and thus $af(x,y)+bf(u',v')=f(ax+bu',y+v')$. Now the lemma yields the conclusion. QED
We assume now that $A$ is a principal ideal domain.
Proof of Theorem 4. We assume (as we may) that $S$ is nonzero, we let $f:A^n\times A^n\to A$ be the dot product. By Proposition 1 the set $f(S\times A^n)$. Let $a_1=f(s_1,y_1)$ be a a generator of this ideal. [Naively: $a_1$ is a gcd of the coordinates of the elements of $S$.] Clearly, $u_1:=s_1/a_1$ is in $A^n$ and $f(u_1,y_1)=1$. Moreover we have
$$
A^n=Au_1\oplus (y_1)^\perp,\qquad S=As_1\oplus(S\cap(y_1)^\perp),
$$
where $(y_1)^\perp$ is the orthogonal of $y_1$. [The corresponding projection $A^n\twoheadrightarrow Au_1$ is given by $x\mapsto f(x,u_1)\,u_1$.] Then (a) follows by induction on $r$. Let us prove (b). By (a) we know that $(y_1)^\perp$ and $S\cap(y_1)^\perp$ are free of rank $n-1$ and $r-1$. By the induction hypothesis there is a basis $u_2,\dots,u_n$ of $(y_1)^\perp$ and there are elements $a_2,\dots,a_r$ of $A$ such that $a_2u_2,\dots,a_ru_r$ is a basis of $S\cap (y_1)^\perp$ and $a_1\mid a_2\mid\cdots\mid a_r$. It only remains to show $a_1\mid a_2$. We have $a_1\mid f(s,y)$ for all $(s,y)\in S\times A^n$. There is a $y$ in $A^n$ such that $f(u_2,y)=1$. Indeed, since the determinant of $(f(u_i,e_j))$ is $\pm1$, no prime of $A$ can divide $f(u_2,e_i)$ for all $i$, and we get $a_1\mid f(a_2u_2,y)=a_1$. QED
Proof of Theorem 3. First statement: Let $v_1,\dots,v_n$ be generators of the $A$-module $M$, let $(e_i)$ be the canonical basis of $A^n$, and let $\phi:A^n\twoheadrightarrow M$ be the $A$-linear surjection mapping $e_i$ to $v_i$. Applying Theorem 4 to the submodule $\operatorname{Ker}\phi$ of $A^n$, we get a basis $u_1,\dots,u_n$ of $A^n$ and elements $a_1,\dots,a_r$ of $A$ such that $a_1u_1,\dots,a_ru_r$ is a basis of $\operatorname{Ker}\phi$ and $a_1\mid a_2\mid\cdots\mid a_r$, and we set $a_{r+1}=\cdots=a_n=0$. Then $M$ is isomorphic to $\oplus_{i=1}^nA/(a_i)$, where the $a_i$ are as in Theorem 3.
Second statement: Assume that $M$ is also isomorphic to $\oplus_{i=1}^mA/(b_i)$, where the $b_i$ satisfy the same conditions as the $a_i$. We only need to prove $m=n$ and $(a_i)=(b_i)$ for all $i$. Let $p\in A$ be a prime. By the Chinese Remainder Theorem [see below] it suffices to prove the above equality in the case where $M$ is the direct sum of a finite family of modules of the form $M_i:=A/(p^{i+1})$ for $i\ge0$. For each $j\ge0$ the quotient $p^jM/p^{j+1}M$ is an $A/(p)$ vector space of finite dimension $n_j$. We claim that the multiplicity of $A/(p^{i+1})$ in $M$ is then $n_i-n_{i+1}$.
Here is a way to see this. Form the polynomial $M(X):=\sum n_jX^j$ (where $X$ is an indeterminate). We have
$$
M_i(X)=1+X+X^2+\cdots+X^i=\frac{X^{i+1}-1}{X-1}\ ,
$$
and we must solve $\sum\,m_i\,M_i(X)=\sum\,n_j\,X^j$ for the $m_i$, where the $n_j$ are considered as known quantities (almost all equal to zero). Multiplying through by $X-1$ we get
$$
\sum\,m_{i-1}\,X^i-\sum\,m_i=\sum\,(n_{i-1}-n_i)\,X^i,
$$
whence the formula. QED

PROPOSITION 2. Let $0\to A^r\overset f{\to}A^n\to M\to0$ be an exact sequence of $A$-modules. Then there are basis of $A^r$ and $A^n$ making the matrix of $f$ of the form
$$
\begin{bmatrix} 
a_1\\
&\ddots\\
&&a_r\\ 
{}\\ 
{}\\ 
{} 
\end{bmatrix}
$$
where only the nonzero entries are indicated. The ideals $(a_i)$ coincide with the ones given by Theorem 3. Moreover, if $\alpha$ is the matrix of $f$ relative to an arbitrary basis of $A^r$ and $A^n$, then the ideal of $A$ generated by the $k$-minors of $\alpha$ is $(a_1a_2\cdots a_k)$.

Proof. It suffices to prove the last sentence because the other statements follow immediately from Theorems 3 and 4. Let $\beta$ and $\gamma$ be rectangular matrices with entries in $A$ such that the product $\beta\gamma$ is defined. Clearly, if an element of $A$ divides each entry of $\alpha$, or if it divides each entry of $\gamma$, then it divides each entry of $\beta\gamma$. A similar statement holds if we replace $\beta$ and $\gamma$ with $\bigwedge^k\beta$ and $\bigwedge^k\gamma$. Thus, multiplying $\beta$ on the left or on the right by an invertible matrix does not change the ideal of $A$ generated by the $k$-minors. QED
Proof of Theorem 2. We will apply Proposition 2 to the principal ideal domain $F[X]$. It suffices to find an exact sequence of the form
$$
0\to F[X]^n\xrightarrow{X-A}F[X]^n\xrightarrow\phi F^n\to0.
$$
We do this in a slightly more general setting:
Let $K$ be a commutative ring, let $M$ be a $K$-module, let $f$ be an endomorphism of $M$, let $X$ be an indeterminate, and let $M[X]$ be the $K[X]$-module of polynomials in $X$ with coefficients in $M$. [In particular, any $K$-basis of $M$ is a $K[X]$-basis of $M[X]$.] Equip $M$ and $M[X]$ with the $K[X]$-module structures characterized by
$$ 
X^i\cdot x=f^ix,\qquad X^i\cdot X^jx=X^{i+j}x 
$$
for all $i,j$ in $\mathbb N$ and all $x$ in $M$. Let $\phi$ be the $K[X]$-linear map from $M[X]$ to $M$ satisfying $\phi(X^ix)=f^ix$ for all $i,x$, and write again $f:M[X]\to M[X]$ the $K[X]$-linear extension of $f:M\to M$. It is enough to check that the sequence
$$ 
0\to M[X]\xrightarrow{X-f}M[X]\xrightarrow{\phi}M\to0 
$$
is exact. The only nontrivial inclusion to verify is $\operatorname{Ker}\phi\subset\operatorname{Im}(X-f)$. For $x=\sum_{i\ge0}X^ix_i$ in $\operatorname{Ker}\phi$, we have
$$ 
x=\sum_{i\ge0}X^ix_i-\sum_{i\ge0}f^ix_i=\sum_{i\ge1}\,(X^i-f^i)\,x_i=(X-f)
\sum_{j+k=i-1}X^jf^kx_i. 
$$
[Non-rigorous wording of the argument: Since $f$ is a root of the polynomial $P(X)=\sum X^ix_i$, the linear polynomial $X-f$ divides $P(X)$.]
QED
Here is a proof of the Chinese Remainder Theorem.

CHINESE REMAINDER THEOREM. Let $A$ be a commutative ring and $\mathfrak a_1,\dots,\mathfrak a_n$ ideals such that $\mathfrak a_p+\mathfrak a_q=A$ for $p\not=q$. Then the natural morphism from $A$ to the product of the $A/\mathfrak a_p$ is surjective. Moreover the intersection of the $\mathfrak a_p$ coincides with their product.

Proof. Multiplying the equalities $A=\mathfrak a_1+\mathfrak a_p$ for $p=2,\dots,n$ we get
$$
A=\mathfrak a_1+\mathfrak a_2\cdots\mathfrak a_n.\qquad(*)
$$
In particular there is an $a_1$ in $A$ such that
$$ 
a_1\equiv1\bmod\mathfrak a_1,\quad a_1\equiv0\bmod\mathfrak a_p\ \forall\ p>1.
$$
Similarly we can find elements $a_p$ in $A$ such that $a_p\equiv\delta_{pq}\bmod\mathfrak a_q$ (Kronecker delta). This proves the first claim. Let $\mathfrak a$ be the intersection of the $\mathfrak a_p$. Multiplying $(*)$ by $\mathfrak a$ we get
$$
\mathfrak a=\mathfrak a_1\mathfrak a+\mathfrak a\mathfrak a_2\cdots\mathfrak a_n\subset\mathfrak a_1\,(\mathfrak a_2\cap\cdots\cap\mathfrak a_n)\subset\mathfrak a.
$$
This gives the second claim, directly for $n=2$, by induction for $n>2$. QED
A: This result is an immediate consequence of the existence of the rational canonical form of square matrices over a field (and the fact that it is rational, i.e., obtained without using any operations that change under field extensions, and canonical, i.e., uniquely determined by the matrix). Any square matrix over a field is similar to its rational canonical form, and two different rational canonical forms are never similar. Hence two matrices are similar if and only if they have the same rational canonical form.
Now the rational canonical form of a matrix$~A$ over the extension field $F$ is the same as over the base field $K$ (which is certainly a rational canonical form similar to$~A$ over$~F$, and there are no others similar to it over$~F$). So two matrices over$~K$ are similar over $K$ iff their rational canonical forms over$~K$ coincide, iff their rational canonical forms over$~F$ coincide, iff the matrices are similar over$~F$.
An interesting consequence of the above is that the field generated (over the prime field) by the entries of the rational canonical form of$~A$ (equivalently by the coefficients of the monic invariant factors of$~A$) is the smallest field$~k$ such that $A$ is similar to a matrix over$~k$.
A: While the structure theory for finitely generated modules over a PID provides the royal route to this result, it does so in a rather indirect way, and it is not easy to see for instance by which basis change two matrices that turn out to produce the same invariant factors under the Smith normal form algorithm are similar. I'll therefore try to formulate a second answer which, although inspired by this structure theory, proceeds in a more straightforward way.
First some terminology. Fixing a linear operator$~\phi$ of a finite dimensional vector space $V$ over$~F$, say that a vector $v\in V$ "generates" the subspace spanned by it and its repeated images by the operator, $\bigl<\phi^k(v)\mid k\in\mathbf N\,\bigr>_F\,$, and call such subspaces "cyclic" subspaces (the terminology mimicks that used in Abelian groups). The first linear dependence between the images $\phi^k(v)$ determines a monic polynomial $P$ such that $P[\phi](v)=0$, which I shall call the "order" of$~v$ (for$~\phi$). Since $P$ is the minimal polynomial of the restriction of$~\phi$ to that cyclic subspace, it does not depend on which generator was used (different vectors may generate the same subspace), and this polynomial can therefore be called the order of the cyclic subspace.
The construction is based on the following two facts.
Proposition 1. There exists a vector whose order equals the minimal polynomial of$~\phi$ (on$~V$).
Proposition 2. If $V$ admits two decompositions as direct sum of a sequence of cyclic subspaces of nonzero dimension such that the order of each subspace divides the order of any subspace before it, then the two decompositions have the same sequence of orders of their subspaces.
Admitting these for the moment, we can proceed as follows. First construct a decomposition into cyclic subspaces satisfying the divisibility condition of proposition 2, by induction on $\dim V$. For $\dim V=0$ the empty direct sum works. So assume $\dim V>0$, and use proposition 1 to find a vector $v$ whose order is the minimal polynomial$~\mu$ of$~\phi$. The dimension$~d$ of the subspace$~S$ generated by$~v$ is $\deg\mu>0$. In order to find a $\phi$-stable complementary subspace$~C$ to$~S$, choose a linear functional $\alpha$ on$~V$ that vanishes on $v=\phi^0(v),\phi(v),\ldots,\phi^{d-2}(v)$ but not on $\phi^{d-1}(v)$ (this can be done for instance by extending those vectors to a basis of $V$, and taking the coordinate function corresponding to the basis vector $\phi^{d-1}(v)$). Then $\alpha=\alpha\circ\phi^0,\alpha\circ\phi,\ldots,\alpha\circ\phi^{d-1}$ are linearly independent functionals: for $0\leq i<d$ the vector $\phi^{d-1-i}(v)$ is annihilated by all functionals in the list before $\alpha\circ\phi^i$, but not by $\alpha\circ\phi^i$ itself, which shows that the latter functional is independent of its predecessors. These $d$ linearly independent functionals span a $\phi$-stable subspace of $V^*$ (the stability follows from $\alpha\circ\mu[\phi]=0$), and the annihilator of this subspace (the space of vectors on which $\alpha,\ldots,\alpha\circ\phi^{d-1}$ all vanish) gives our $\phi$-stable complement$~C$ of$~S$ in$~V$, as is easily checked. The minimal polynomial of the restriction of$~\phi$ to$~C$ obviously divides the global minimal polynomial$~\mu$, so one can apply the induction hypothesis to decompose $C$ (whose dimension is $\dim V-d$) as a direct sum of cyclic subspaces, all of whose orders will divide$~\mu$.
If $A$ and $B$ are similar matrices over$~F$, then they can be seen as matrices of the same linear operator$~\phi$ expressed on different bases. Proposition$~$2 now says that the above procedure will always produce the same sequence of orders of the cyclic factors. Conversely if one finds the same sequence of orders of the cyclic factors using $A$ or $B$ to define$~\phi$, then choosing in each cyclic subspace the basis $v,\phi(v),\ldots,\phi^{d-1}(v)$ finds a pair of bases transformed to which $A$ and $B$ are given by the same matrix (the rational canonical form), showing that $A$ and $B$ are similar over$~F$.
And to answer the question, if $A$ and $B$ are not similar over$~F$, then one gets decompositions with different sequences of orders of the cyclic factors. These decompositions persist under extending the field to$~K$, with the same orders, and this shows that $A$ and $B$ cannot become similar over$~K$.
Now both propositions are easy to show using the canonical decomposition of $V$ into subspaces associated to the distinct irreducible factors of$~\mu$, according to the Chinese remainder theorem for the ring $F[X]/(\mu)$: 
