I have been stuck on this question for a while now. I can easily do the change of basis matrix if the entries in the basis are vectors as opposed to a matrix.
Let
$$B_1 = \{\begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}
,\begin{bmatrix}
0 & 1 \\
1 & 0
\end{bmatrix}
,\begin{bmatrix}
0 & -1 \\
1 & 0
\end{bmatrix}\}
\quad and \quad B_2 = \{\begin{bmatrix}
1 & 1 \\
0 & -1
\end{bmatrix}
,\begin{bmatrix}
1 & 0 \\
1 & -1
\end{bmatrix}
,\begin{bmatrix}
0 & 1 \\
0 & 0
\end{bmatrix}\}$$
be two bases for $span(B_1)$ in $M_{22}$, where the usual left to right ordering is assumed. Find the transition matrix (change of coordinate/change of basis matrix) $P_{B1\rightarrow B2}$
Best Answer
Our "playground" is a vector space $E$ with two basis $\{\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3\}$ and $\{\mathbf{f}_1,\mathbf{f}_2,\mathbf{f}_3\}$.
You have linear transformations. They can be defined without reference to any peculiar basis, it's sufficient to know their actions on vectors. For instance the identity transform is defined by $\forall v, v=Id_E(v)$.
Then you have matrices that are representations of the linear transformations given two basis (one for the domain space, the other one for the image space). With such representations you work with "arrays" of numbers that transform vector's components (makes sense only when the basis are clearly specified).
The transition matrix $P$ is nothing more than the representation of the identity transform $Id_E$ once that you have specified the domain and image spaces basis. You can use a matrix representation that transforms $v$ components expressed in the $\mathbf{e}_i$ basis to components of $v$ expressed in the $\mathbf{f}_j$ basis: $P_{B_1\to B_2}=\mathcal{M}_{B_1,B_2}(Id_E)$. You can also use the $P_{B_2\to B_1}=\mathcal{M}_{B_2,B_1}(Id_E)$ matrix that transforms the components of $v$ expressed in the $\mathbf{f}_i$ basis to components of $v$ expressed in the $\mathbf{e}_j$ basis (note that we have $P^{-1}_{B_2\to B_1}=P_{B_1\to B_2}$).
Let's compute $P_{B_1\to B_2}=\mathcal{M}_{B_1,B_2}(Id_E)$.
If we consider $v=\mathbf{e}_1$, its components in the $\mathbf{e}_i$ basis are $\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$ and you have: $$ \begin{bmatrix} P_{11} \\ P_{21} \\ P_{31} \end{bmatrix}=P_{B_1\to B_2}.\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} $$ This LHS term represents the components of $\mathbf{e}_1$ in the $\mathbf{f}_i$ basis. In other terms we have $$ P_{11}\mathbf{f}_1+P_{21}\mathbf{f}_2+P_{31}\mathbf{f}_3 = 1\mathbf{e}_1 $$ To find the $\{P_{11},P_{21},P_{31}\}$ you can use your representation: $$ \mathbf{e}_1= \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} ,\ \mathbf{e}_2=\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} ,\ \mathbf{e}_3=\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} $$ $$ \mathbf{f}_1=\begin{bmatrix} 1 & 1 \\ 0 & -1 \end{bmatrix} ,\ \mathbf{f}_2=\begin{bmatrix} 1 & 0 \\ 1 & -1 \end{bmatrix} ,\ \mathbf{f}_3=\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} $$ (but you could also have used something like $\mathbf{e}_1=(1,1,1,-1)$, $\mathbf{f}_1=(...)$ where numbers are stacked in 1D arrays, this is not relevant).
In all cases, you find (by identification): $$ \begin{bmatrix} P_{11} \\ P_{21} \\ P_{31} \end{bmatrix}=\begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} $$
You can do the same for the two other columns and finally get: $$ P_{B_1\to B_2}= \begin{bmatrix} 0 & -1 & -1 \\ 1 & 1 & 1 \\ 1 & 2 & 0 \\ \end{bmatrix} $$
To be more explicit:
if you have a vector $v$ of components $(\alpha,\beta,\gamma)$ in your initial basis $\mathbf{e}_i$ $$ v=\alpha \mathbf{e}_1 + \beta \mathbf{e}_2 + \gamma \mathbf{e}_3 $$
Then its components in the $\mathbf{f}_j$ basis can be computed by: $$ \begin{bmatrix} -\beta -\gamma \\ \alpha +\beta +\gamma \\ \alpha +2 \beta \\ \end{bmatrix} = P_{B_1\to B_2} \begin{bmatrix} \alpha \\ \beta \\ \gamma \end{bmatrix} $$
Another example:
If you have a matrix $T=\mathcal{M}_{B_1,B_1}(\mathcal{T})$ that represents a linear transform $\mathcal{T}$ in the basis $B_1$, you have a similar matrix $$ P_{B_1\to B_2}.T.P_{B_2\to B_1} = P^{-1}_{B_2\to B_1}.T.P_{B_2\to B_1}=\mathcal{M}_{B_2,B_2}(\mathcal{T}) $$
that represents $\mathcal{T}$ in the $B_2$ basis.
Note: you do not change the "meaning" of the initial $\mathcal{T}$ precisely because the $P$ matrices are nothing more than the representations of the identity transform (as explained at the beginning).