[proofplan]
We encode each ordered basis by its coordinate isomorphism between $R^n$ and $M$. The change-of-basis matrix is the matrix of the automorphism of $R^n$ obtained by passing from $\mathcal{B}$-coordinates to $\mathcal{C}$-coordinates, so changing back gives the inverse matrix. Conversely, an invertible matrix defines an automorphism of $R^n$; transporting the standard basis through this automorphism and then through the coordinate isomorphism for $\mathcal{B}$ gives a new basis of $M$.
[/proofplan]
[step:Define the coordinate maps attached to the two ordered bases]
Let $R^n$ denote the free left $R$-module of coordinate columns $x = (x_1,\dots,x_n)^\top$, with the convention that $R^0$ is the zero module. Define the coordinate realization maps
\begin{align*}
\Phi_{\mathcal{B}}: R^n \to M
\end{align*}
and
\begin{align*}
\Phi_{\mathcal{C}}: R^n \to M
\end{align*}
by
\begin{align*}
\Phi_{\mathcal{B}}(x) = \sum_{j=1}^{n} x_j b_j
\end{align*}
and
\begin{align*}
\Phi_{\mathcal{C}}(x) = \sum_{j=1}^{n} x_j c_j.
\end{align*}
Because $\mathcal{B}$ and $\mathcal{C}$ are bases, every element of $M$ has a unique coordinate column in each basis. Hence $\Phi_{\mathcal{B}}$ and $\Phi_{\mathcal{C}}$ are $R$-module isomorphisms. Their inverse maps are the coordinate maps
\begin{align*}
\Phi_{\mathcal{B}}^{-1}: M \to R^n
\end{align*}
and
\begin{align*}
\Phi_{\mathcal{C}}^{-1}: M \to R^n,
\end{align*}
where $\Phi_{\mathcal{B}}^{-1}(m) = [m]_{\mathcal{B}}$ and $\Phi_{\mathcal{C}}^{-1}(m) = [m]_{\mathcal{C}}$ for every $m \in M$.
[guided]
The point of introducing $\Phi_{\mathcal{B}}$ and $\Phi_{\mathcal{C}}$ is to replace the basis question in $M$ by a matrix question in $R^n$. A basis of $M$ means exactly that each element of $M$ is written uniquely as a finite coordinate combination of the basis elements. Since the bases here have length $n$, define
\begin{align*}
\Phi_{\mathcal{B}}: R^n \to M
\end{align*}
by
\begin{align*}
\Phi_{\mathcal{B}}(x) = \sum_{j=1}^{n} x_j b_j
\end{align*}
for a coordinate column $x = (x_1,\dots,x_n)^\top$. This map is $R$-linear because addition and scalar multiplication in $M$ distribute over finite sums. The basis property of $\mathcal{B}$ says precisely that $\Phi_{\mathcal{B}}$ is surjective and injective: surjectivity is spanning, and injectivity is uniqueness of coordinates. Therefore $\Phi_{\mathcal{B}}$ is an $R$-module isomorphism.
The same construction for $\mathcal{C}$ gives an $R$-module isomorphism
\begin{align*}
\Phi_{\mathcal{C}}: R^n \to M
\end{align*}
defined by
\begin{align*}
\Phi_{\mathcal{C}}(x) = \sum_{j=1}^{n} x_j c_j.
\end{align*}
The inverse maps are exactly the coordinate maps: $\Phi_{\mathcal{B}}^{-1}(m) = [m]_{\mathcal{B}}$ and $\Phi_{\mathcal{C}}^{-1}(m) = [m]_{\mathcal{C}}$. Thus changing coordinates is the same as composing these isomorphisms in the correct order.
[/guided]
[/step]
[step:Identify the change-of-basis matrix as an automorphism of $R^n$]
Define the $R$-[module homomorphism](/page/Module%20Homomorphism)
\begin{align*}
T_{\mathcal{C} \leftarrow \mathcal{B}}: R^n \to R^n
\end{align*}
by
\begin{align*}
T_{\mathcal{C} \leftarrow \mathcal{B}} = \Phi_{\mathcal{C}}^{-1} \circ \Phi_{\mathcal{B}}.
\end{align*}
For $x = [m]_{\mathcal{B}}$, we have $\Phi_{\mathcal{B}}(x) = m$, and therefore
\begin{align*}
T_{\mathcal{C} \leftarrow \mathcal{B}}(x) = \Phi_{\mathcal{C}}^{-1}(m) = [m]_{\mathcal{C}}.
\end{align*}
Thus the matrix of $T_{\mathcal{C} \leftarrow \mathcal{B}}$ in the standard basis of $R^n$ is exactly $P_{\mathcal{C} \leftarrow \mathcal{B}}$. Its $j$-th column is $[b_j]_{\mathcal{C}}$, because the $j$-th standard basis vector of $R^n$ is sent by $\Phi_{\mathcal{B}}$ to $b_j$.
[/step]
[step:Compose the two coordinate changes to obtain inverse matrices]
Similarly define
\begin{align*}
T_{\mathcal{B} \leftarrow \mathcal{C}}: R^n \to R^n
\end{align*}
by
\begin{align*}
T_{\mathcal{B} \leftarrow \mathcal{C}} = \Phi_{\mathcal{B}}^{-1} \circ \Phi_{\mathcal{C}}.
\end{align*}
Then
\begin{align*}
T_{\mathcal{B} \leftarrow \mathcal{C}} \circ T_{\mathcal{C} \leftarrow \mathcal{B}} = \Phi_{\mathcal{B}}^{-1} \circ \Phi_{\mathcal{C}} \circ \Phi_{\mathcal{C}}^{-1} \circ \Phi_{\mathcal{B}} = \operatorname{id}_{R^n}.
\end{align*}
Also,
\begin{align*}
T_{\mathcal{C} \leftarrow \mathcal{B}} \circ T_{\mathcal{B} \leftarrow \mathcal{C}} = \Phi_{\mathcal{C}}^{-1} \circ \Phi_{\mathcal{B}} \circ \Phi_{\mathcal{B}}^{-1} \circ \Phi_{\mathcal{C}} = \operatorname{id}_{R^n}.
\end{align*}
The matrix of the identity map on $R^n$ is the identity matrix $I_n$, and composition of $R$-linear maps corresponds to multiplication of their standard matrices. Hence
\begin{align*}
P_{\mathcal{B} \leftarrow \mathcal{C}} P_{\mathcal{C} \leftarrow \mathcal{B}} = I_n.
\end{align*}
Likewise,
\begin{align*}
P_{\mathcal{C} \leftarrow \mathcal{B}} P_{\mathcal{B} \leftarrow \mathcal{C}} = I_n.
\end{align*}
Therefore $P_{\mathcal{C} \leftarrow \mathcal{B}}$ is invertible in $R^{n \times n}$, with inverse $P_{\mathcal{B} \leftarrow \mathcal{C}}$.
[/step]
[step:Use an invertible matrix to construct a new ordered basis]
Now let $\mathcal{B} = (b_1,\dots,b_n)$ be an ordered basis of $M$, and let $A = (a_{ij}) \in R^{n \times n}$ be invertible. Let $A^{-1} = (d_{ij}) \in R^{n \times n}$ denote its inverse, so
\begin{align*}
A^{-1}A = I_n
\end{align*}
and
\begin{align*}
AA^{-1} = I_n.
\end{align*}
Define an ordered family $\mathcal{C} = (c_1,\dots,c_n)$ in $M$ by
\begin{align*}
c_j = \sum_{i=1}^{n} a_{ij} b_i
\end{align*}
for each $j \in \{1,\dots,n\}$.
Let
\begin{align*}
L_A: R^n \to R^n
\end{align*}
be the $R$-module homomorphism defined by ordinary matrix multiplication,
\begin{align*}
L_A(x) = Ax.
\end{align*}
Since $A^{-1}$ exists, $L_A$ is an $R$-module automorphism with inverse $L_{A^{-1}}$. The $j$-th standard basis vector of $R^n$ is sent by $L_A$ to the $j$-th column of $A$. Therefore
\begin{align*}
(\Phi_{\mathcal{B}} \circ L_A)(e_j) = \sum_{i=1}^{n} a_{ij} b_i = c_j.
\end{align*}
The map $\Phi_{\mathcal{B}} \circ L_A: R^n \to M$ is a composition of $R$-module isomorphisms, hence is an $R$-module isomorphism. Since it sends the standard ordered basis $(e_1,\dots,e_n)$ of $R^n$ to $(c_1,\dots,c_n)$, the ordered family $\mathcal{C}$ is a basis of $M$.
[guided]
We now prove the converse using the same coordinate-map idea. Fix the ordered basis $\mathcal{B} = (b_1,\dots,b_n)$ of $M$, and let $A = (a_{ij}) \in R^{n \times n}$ be invertible. Invertible means that there is a matrix $A^{-1} = (d_{ij}) \in R^{n \times n}$ satisfying
\begin{align*}
A^{-1}A = I_n
\end{align*}
and
\begin{align*}
AA^{-1} = I_n.
\end{align*}
We use the columns of $A$ as the $\mathcal{B}$-coordinates of the proposed new basis vectors. Thus, for each $j \in \{1,\dots,n\}$, define
\begin{align*}
c_j = \sum_{i=1}^{n} a_{ij} b_i.
\end{align*}
This is exactly the column-vector convention: the $j$-th new basis vector has coordinate column $(a_{1j},\dots,a_{nj})^\top$ relative to $\mathcal{B}$.
Define
\begin{align*}
L_A: R^n \to R^n
\end{align*}
by
\begin{align*}
L_A(x) = Ax.
\end{align*}
This map is $R$-linear because matrix multiplication is built from finite sums and scalar multiplication in the commutative ring $R$. Since $A^{-1}$ is both a left and right inverse for $A$, the corresponding map $L_{A^{-1}}$ satisfies
\begin{align*}
L_{A^{-1}} \circ L_A = \operatorname{id}_{R^n}
\end{align*}
and
\begin{align*}
L_A \circ L_{A^{-1}} = \operatorname{id}_{R^n}.
\end{align*}
Hence $L_A$ is an $R$-module automorphism of $R^n$.
Now compose this automorphism with the coordinate realization map for $\mathcal{B}$:
\begin{align*}
\Phi_{\mathcal{B}} \circ L_A: R^n \to M.
\end{align*}
Both factors are $R$-module isomorphisms, so the composition is an $R$-module isomorphism. If $e_j$ denotes the $j$-th standard basis vector of $R^n$, then $L_A(e_j)$ is the $j$-th column of $A$, and therefore
\begin{align*}
(\Phi_{\mathcal{B}} \circ L_A)(e_j) = \sum_{i=1}^{n} a_{ij} b_i = c_j.
\end{align*}
An ordered family in $M$ is a basis exactly when the map from $R^n$ sending the standard basis to that family is an isomorphism. Since $\Phi_{\mathcal{B}} \circ L_A$ is such an isomorphism and sends $e_j$ to $c_j$ for every $j$, the family $\mathcal{C} = (c_1,\dots,c_n)$ is an ordered basis of $M$.
[/guided]
[/step]
[step:Conclude both directions of the theorem]
The first part shows that the change-of-basis matrix between any two ordered bases is invertible, with inverse given by the change-of-basis matrix in the opposite direction. The second part shows that every invertible matrix $A \in R^{n \times n}$ acts on a fixed ordered basis by its columns and produces another ordered basis. This proves the theorem.
[/step]
