# 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!

• The answer is yes. This follows from the classification of finitely generated modules over a principal ideal domain. That's classical. Briefly, $A$ and $B$ are similar iff, for all $k \le n$, the gcd of the order $k$ minors of $A-X$ and $B-X$ coincide, and this doesn't depend on the field. (Here $X$ is an indeterminate.) I can look for references, if you want. – Pierre-Yves Gaillard Aug 13 '11 at 15:22
• I should have said that the gcd's are computed in $K[X]$ or in $F[X]$, and the point is you obviously get the same gcd's. Also, $A-X$ is the matrix whose determinant is the characteristic polynomial (in case you're used to other notation). - That's in all the standard algebra books. I can look for online references. – Pierre-Yves Gaillard Aug 13 '11 at 15:33
• Sorry, but I didn't get the idea! Could you please be more clear, or is there any other method? – Melesia Aug 13 '11 at 15:59
• You can use the rational canonical form, but one has to be a bit careful (because the uniqueness of the rational canonical form depends on the monic irreducible factors one chooses). – Arturo Magidin Aug 13 '11 at 18:27
• @ArturoMagidin: How so "the uniqueness of the rational canonical form depends on the monic irreducible factors one chooses"? Uniqueness is uniqueness; one can show explicitly that distinct rational canonical forms are not similar. Also the rational canonical form does not use or depend on any irreducible factors; this is why it is rational (independent of field extensions). – Marc van Leeuwen Dec 13 '13 at 15:10

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$.

• Dear Andrea, please take a look at this “answer”. (At the time of writing, it's just below.) – Pierre-Yves Gaillard Aug 13 '11 at 18:37
• You're welcome! Wonderful argument! Where did you find it? In your head? – Pierre-Yves Gaillard Aug 13 '11 at 19:23
• I remembered an exercise that I made when I was at my first year: it concerned only the extension $\mathbb{R} \subseteq \mathbb{C}$, but I could adapt the proof. I found the exercise in a wonderful Italian book that contains hard problems in linear algebra: "Broglia, Fortuna, Luminati - Problemi risolti di algebra lineare". – Andrea Aug 14 '11 at 8:00
• why there will exist λ1,…,λr∈F such that P(λ1,…,λr)≠0? – Sushil Jun 3 '16 at 9:24
• @Andrea This is my question as well, why are there such $\lambda_1, ..., \lambda_r$ in $F$...? – Majid May 21 '18 at 18:45

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.)

[I'm using the community wiki mode to encourage you to improve this answer.]

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 $V$ a finitely generated $A$-module. Then $V$ is isomorphic to $\oplus_{i=1}^nA/(a_i)$, where the $a_i$ are elements of $A$ satisfying $a_1 | a_2 | \cdots | a_n$. Here $a | b$ means "$a$ divides $b$". Moreover the ideals $Aa_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. (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 nonzero 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 | a_2 | \cdots | a_r$.

We'll need the

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

Proof of the Proposition. Let $T$ be the set of all ideals of the form $(f(x,y))$, let $(f(x,y))$ and $(f(u,v))$ be two elements of $T$, and suppose that $(f(x,y))$ is maximal in $T$. It suffices to show that $f(x,y) | f(u,v)$.

Claim: $f(x,y) | f(x,v)$ and $f(x,y) | f(u,y)$. Indeed, any generator of $(f(x,y),f(x,v))$ is of the form $$a f(x,y)+bf(x,v)=f(x,ay+bv),$$ and the maximality of $(f(x,y))$ implies $f(x,y) | f(x,v)$. The proof of $f(x,y) | f(u,y)$ is similar.

We can assume $f(x,v)=0=f(u,y)$. [Write $f(x,v)=a f(x,y)$ and replace $v$ by $v-ay$. Similarly for $u$.] Using the equality $$f(a x+b u,y+v)=a f(x,y)+b f(u,v)$$ for all $a$ and $b$ in $A$, and arguing as in the proof of the claim, we see that $f(x,y) | f(u,v)$. QED

Proof of Theorem 4. We assume (as we may) that $S$ is nonzero, we let $f$ be the bilinear form on $A^n$ whose matrix with respect to the canonical basis is the identity matrix, and we pick a generator $a_1=f(s_1,y_1)$ of $f(S\times A^n)$. [Naively: $a_1$ is the gcd of the coordinates of the elements of $S$.] Clearly, $u_1:=s_1/a_1$ is in $A^n$, and we have $$A^n=Au_1\oplus y_1^\perp,\quad S=As_1\oplus(S\cap y_1^\perp),$$ where $y_1^\perp$ is the orthogonal of $y_1$. Then (a) follows by induction on $r$. In particular $y_1^\perp$ and $S\cap y_1^\perp$ are free of rank $n-1$ and $r-1$, and (b) follows also by induction. [Note that if $x$ belongs to a basis of $A^n$, then $f(x,y)=1$ for some $y$ in $A^n$.] QED

Proof of Theorem 3. Let $v_1,\dots,v_n$ be generators of the $A$-module $V$, let $(e_i)$ be the canonical basis of $A^n$, and let $\varphi:A^n\to V$ be the $A$-linear epimorphism mapping $e_i$ to $v_i$. Theorem 4 shows that there is an $r\le n$ and an $A$-linear from $\psi:A^r\to A^n$ such that $\psi(A^r)=\ker\varphi$. This implies that $V$ is isomorphic to $\oplus_{i=1}^nA/(a_i)$, where the $a_i$ are as in Theorem 3. Assume that $V$ 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. It suffices to prove the above equality in the case where $V$ is the direct sum of a finite family of modules of the form $$V_i:=A/(p^{i+1}).$$ For each $j$ the quotient $p^jM/p^{j+1}M$ is an $A/(p)$ vector space of finite dimension $n_j$. The multiplicity of $A/(p^{i+1})$ is then $n_i-n_{i+1}$.

Here is a way to see this. Form the polynomial $V(X):=\sum\ n_j\ X^j$. We have $$V_i(X)=\frac{X^{i+1}-1}{X-1}=1+X+X^2+\cdots+X^i,$$ and we must solve $\sum\ m_i\ V_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

Proof of Theorem 2. Let the notation of Theorem 2 be in force. In particular $F$ is a field, and $A$ is now an $n$ by $n$ matrix with coefficients in $F$. The formula $fv:=f(A)v$, for $f\in F[X]$ and $v\in F^n$, defines an $F[X]$-module structure on $F^n$. Let $(b_i)\subset F[X]^n$ and $(e_i)\subset F^n$ be the canonical basis, let $\varphi:F[X]^n\to F^n$ be the $F[X]$-module epimorphism mapping $b_i$ to $e_i$, and let $\psi$ be the $F[X]$-module endomorphism of $F[X]^n$ whose matrix is $X-A$. It is not difficult to check that we have $\psi(A^r)=\ker\varphi$, as in the proof of Theorem 3. Now Theorem 2 follows from Theorem 3. QED

Here is a proof of the Chinese Remainder Theorem (which has been silently used).

CHINESE REMAINDER THEOREM. Let $A$ be a ring and $I_1,\dots,I_n$ ideals such that $I_p+I_q=A$ for $p\not=q$. Then the natural morphism from $A$ to the product of the $A/I_p$ is surjective. Moreover the intersection of the $I_p$ coincides with their product.

Proof. Multiplying the equalities $A=I_1+I_p$ for $p=2,\dots,n$ we get $$A=I_1+I_2\cdots I_n.\qquad(*)$$ In particular there is an $a_1$ in $A$ such that $$a_1\equiv1\bmod I_1,\quad a_1\equiv0\bmod I_p\ \forall\ p>1.$$ Similarly we can find elements $a_p$ in $A$ such that $a_p\equiv\delta_{p q}\bmod I_q$ (Kronecker delta). This proves the first claim. Let $I$ be the intersection of the $I_p$. Multiplying (*) by $I$ we get $$I=I_1I+II_2\cdots I_n\subset I_1\ (I_2\cap\cdots\cap I_n)\subset I.$$ This gives the second claim, directly for $n=2$, by induction for $n>2$. QED

EDIT. Here is a more intrinsic formulation (taken from Bourbaki) of the argument used to prove Theorem 2.

Let $K$ be a commutative ring, let $V$ be a $K$-module, let $f$ be an endomorphism of $V$, let $X$ and $Y$ be indeterminates, and let $V[X]$ be the $K[X]$-module of polynomials in $X$ with coefficients in $V$. [In particular, any $K$-basis of $V$ is a $K[X]$-basis of $V[X]$.] Equip $V$ and $V[X]$ with the $K[X,Y]$-module structures characterized by $$X^iY^j\cdot v=f^{i+j}v,\quad X^iY^j\cdot X^kv=X^{i+k}f^jv$$ for all $i,j,k$ in $\mathbb N$ and all $v$ in $V$. Let $\phi$ be the unique $K[X,Y]$-linear map from $V[X]$ to $V$ satisfying $\phi(v)=v$ for all $v$ in $V$.

Claim: the sequence $$0\to V[X]\xrightarrow{X-Y}V[X]\xrightarrow{\phi}V\to0$$ is exact.

The only nontrivial inclusion to verify is $\mathrm{Ker}\ \phi\subset\mathrm{Im}(X-Y)$. For $$v=\sum_{i\ge0}X^iv_i$$ in $\mathrm{Ker}\ \phi$, we have $$v=\sum_{i\ge0}X^iv_i-\sum_{i\ge0}Y^iv_i=\sum_{i\ge1}\ (X^i-Y^i)\ v_i=(X-Y) \sum_{j+k=i-1}X^jY^kv_i.$$

• While I like your answer, I think the way it was presented slightly obscures the point: which is two matrices $A,B \in M_n(F)$ are similar over $F$ iff the $F[A]$-module structure and the $F[B]$-module structure of $F^n$ are isomorphic. This is where classification of finitely generated modules over PID comes in because to classify a $F[T]$-module, we only need to know the invariant factors. – Soarer Aug 15 '11 at 5:41
• Dear @Soarer: Thanks! I completely agree with you. Would you consider editing the answer? – Pierre-Yves Gaillard Aug 15 '11 at 5:44
• Dear @Pierre, I only have that short comment to add, and it seems out of place wherever I put it, so maybe I'll just leave it as a comment, or you can add that wherever you like. – Soarer Aug 15 '11 at 5:50
• Though this answer certainly points to the right results that answer the question, I am somewhat shocked by the complication of the methods used to prove these results. I thought the classification of modules over PID was a simple corollary to the existence of the Smith normal form of matrices over a PID. – Marc van Leeuwen Dec 11 '13 at 9:39
• @MarcvanLeeuwen: Dear Marc, Thanks for your comment! I read and up-voted your nice answer. The point of my answer was to be as self-contained and simple as possible. It is certainly neither perfect nor original (I basically followed Samuel's Algebraic Theory of Numbers). – Pierre-Yves Gaillard Dec 11 '13 at 10:41

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$.

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

• Dear Andrea, Your post looks very interesting. I'm trying to understand it, but I'm very slow. Something looks superficially surprising to me: You conclude that $I_i B_\mathfrak{q} = J_i B_\mathfrak{q}$ for all $i$ before concluding that $r=s$. – Pierre-Yves Gaillard Aug 23 '11 at 13:08
• I modified some notations. I hope to be clearer. – Andrea Aug 23 '11 at 13:54
• Thanks! I'll look at the edited version. In the meantime, a detail: Is it on purpose that you write "The proposition can be applied to every finite extension ...", although there is no such assumption in the statement of the proposition? [I got the notification, but it'd be better, if you remember, to put an @Pierre.] – Pierre-Yves Gaillard Aug 23 '11 at 14:20
• @Pierre: Yes, because if $A$ is a PID and $B$ is finite over $A$, then $A$ is integrally closed in its quotients field $K$ and $B$ is integral over $A$, so $A = B \cap K$. So there is no need that $B$ is finite over $A$, it suffices that $B$ is integral over $A$. – Andrea Aug 23 '11 at 14:35
• I forgot the "$B\cap K=A$"... When you say that the extension $A\subset B$ is "finite", you mean "module-finite", right? ... An infinitesimal detail: Shouldn't the first word of the proof be "From" instead of "For"? --- Wonderful answer! +1. – Pierre-Yves Gaillard Aug 23 '11 at 15:04

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

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)$: