How should we understand change of the basis matrix? I'm rather new to linear algebra and my professor isn't very clear, so although this question may seem "too easy" for MSE it would be of great help to me!
I'm trying to understand the concept behind a change of basis matrix.


*

*Let's say we have some $m \times n$ matrix $A$, formed by a basis $\alpha$. This means that all the columns of $A$ are a linear combination of elements of $\alpha$, right?

*And if we want a change of basis to $\beta$, we're essentially finding $[A]_\beta$, right? 

*And, the thought behind this is "reforming" the columns of $A$ with respect to the basis $\beta$? 

*And, to do this, we take the elements of $\beta$ as columns of a new matrix $C$, then multiply it by the coordinates of $A$ w.r.t. $\beta$?
Am I on the right track to understanding this, or am I mistaken? 
 A: Here's the thing: vector spaces don't come with a basis "pre-loaded", it's an additional layer of structure we put on a vector space in order to describe them more easily.
It turns out the things of actual interest (for the most part) in linear algebra are "vector-space homomorphisms" (functions that preserve "vector-space-ness"), or as your professor and text more likely call them, linear mappings.
Now, normally, vector spaces are "pretty big" (as in infinite, because typically the field of scalars is infinite), and we can't just list all the vectors, and give them names like Fred and Charlie. However, in some cases (these cases are called "finite-dimensional") we have a finite generating set, which we can list.
If this generating set is the smallest one we can make, we call it a basis. Now bases, in general, aren't unique. They're a way to describe vectors explicitly (instead of, say, saying: "vectors are anything that obey the vector space axioms"). This process is called "co-ordinatizing", because given a basis, we can refer to specific vectors by their coordinates (an array of scalars), that is, the coefficients of the basis vectors in the (unique!) linear combination a vector is, in that basis.
It's easier to see what's going on with a two-dimensional example, and the grand-daddy of all such examples is the real cartesian plane, or what most texts refer to as $\Bbb R^2$. One possible basis is formed by the unit axis vectors, often denoted $\mathbf{e}_1$ and $\mathbf{e}_2$, or $\mathbf{i}$ and $\mathbf{j}$. In "standard coordinates" (that is, in this basis), these have the form $(1,0)$ and $(0,1)$, since:
$\mathbf{e}_1 = 1\cdot\mathbf{e}_1 + 0\cdot\mathbf{e}_2\\\mathbf{e}_2 = 0\cdot\mathbf{e}_1 + 1\cdot\mathbf{e}_2.$
Note well that the statement: "the vector that has coordinates $(a,b)$" has no meaning unless a basis is specified. For example, this is also a basis of $\Bbb R^2$: $\beta = \{\mathbf{e}_1 + \mathbf{e}_2, \mathbf{e}_2\}$, and in this basis, the vector that has coordinates $(3,4)$ in the basis $\{\mathbf{e}_1,\mathbf{e}_2\}$ has "different coordinates", namely $[3,1]$.
Now, since vectors are completely determined by their coordinates in a basis, to completely determine the action of a linear map, it suffices to determine its action on said basis (since linear maps preserve linear combinations, the image of a linear combination of basis elements is the same linear combination of the images of the basis elements, for example:
$T(c_1\mathbf{e}+c_2\mathbf{e}) = c_1T(\mathbf{e}_1) + c_2T(\mathbf{e}_2)$).
Note that such a determination represents a "co-ordinatization" of the linear transformation, and is not "intrinsic" but highly-dependent on the basis being used. We call this "array of coordinate arrays" a matrix. In is important to realize that the columns of such a matrix represent the image of the basis vectors "in their own basis", so the first column is the image of $(1,0,\dots,0)$ (which vector this array of coordinates is, depends on the basis; for example, in the basis $\beta$ I gave above this represents what we "usually call" $(1,1)$, in the standard basis).
A change-of basis is a certain kind of linear transformation, namely, one is that is bijective. When the "source" and "target" vector spaces are the same one, but represented by different coordinate systems, we can compute a matrix that lets us convert from one coordinate system, to another. Since this matrix is like a "translation system" between two languages of vector description, it's not in either basis.
The "standard basis" for a vector space can pose a stumbling block, here, because it's so "natural" that we often omit it, and just refer to a vector by coordinates. Put another way, the real cartesian plane doesn't come equipped with coordinate axes, just an origin. We choose coordinate axes, and this choice then determines the actual numbers we put in our scalar array to describe a point in the plane.
Here is an actual example: let's say student $A$ uses the traditional $x$ and $y$ axes, and thus means:
$(x,y) = x\mathbf{e}_1 + y\mathbf{e}_2$.
She is studying a linear transformation $T$ that maps the $x$-unit vector to $(2,2)$ in her coordinates, and the $y$-unit vector to $(3,4)$ in her coordinates. She writes this as:
$[T] = \begin{bmatrix}2&3\\2&4\end{bmatrix}$.
Student $B$ prefers to use the lines $y = x$ and $y = -x$ as his coordinates axes, which is the same as using the basis $\gamma = \{\frac{1}{\sqrt{2}}(\mathbf{e}_1+\mathbf{e}_2),\frac{1}{\sqrt{2}}(\mathbf{e}_2-\mathbf{e}_1)\}$ (for some odd reason, student $B$ prefers a coordinate system rotated at $45^{\circ}$ counter-clockwise to that of student $A$).
So student $A$ recognizes that student $B$'s $[1,0]$ is her $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$ and his $[0,1]$ is her $(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$.
Thus the $B$ to $A$ "translation"(change-of-basis matrix) is afforded by:
$P = \begin{bmatrix}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix}$.
(perhaps you recognize this as a rotation matrix).
Since bijective mappings are invertible, the $A$ to $B$ change will be:
$P^{-1} = \begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix}$.
Student $A$ reasons (correctly) that if she takes a coordinate vector in $B$'s coordinate system, "translates" it to her coordinate system, applies her matrix for $T$, and then translates it back, what she gets should be what $[T]_{\gamma}$ does, in $B$'s coordinate system; that is:
$[T]_{\gamma} = P^{-1}[T]P$
If we compute this, we get:
$[T]_{\gamma} = \begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix} \begin{bmatrix}2&3\\2&4\end{bmatrix} \begin{bmatrix}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{bmatrix}$
$= \begin{bmatrix}\frac{11}{2}&\frac{3}{2}\\ \frac{1}{2}&\frac{1}{2}\end{bmatrix}$.
