[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$.[/step]

[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: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$.[/step]

[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: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]