Rigorously proving that a change-of-basis matrix is always invertible How can we prove that all change-of-basis matrices are invertible? The trivial case when it's a change of basis for $\mathbb{R^{n}}$ is easily demonstratable using, for example, determinants. But I am struggling to rigorously show this for all bases, for example for a two-dimensional subspace of $\mathbb{R^{4}}$. I am sure that there are many ways to go about this proof, and I would be very appreciative for as many ways of demonstration as possible, to back up my intuition!
 A: You can prove this by linking Change of Basis matrices to linear transformations. See Kuldeep Singh's Linear Algebra: Step by Step
(2013) p 414.

Let know me if you want me post Exercise 5.6 solution.
A: Let $M=[I]_{B_1}^{B_2}$ be the change of basis matrix the identity operator $I:V \rightarrow V$ with $B_1,B_2$ being basis for the vector space $V$.
We will show that the equation $Mx=0$ has $x=0$ as the only solution, where $x \in V$.
As mentioned in the above answer as well, the columns of the matrix $M$ are the representation for the vector in $B_2$ obtained by action of $I$ on the vectors in the basis $B_1$.
In mathematical terms:
Let $B_1=\{u^1,u^2,\ldots,u^n \}$ and $B_2=\{v^1,v^2,\ldots,v^n \}$
for $u^1,\ldots,u^n,v^1,\ldots,v^n \in V$.
$[I(u^j)]_{B_2} = [u^j]_{B_2} = a_{1j} v^1 + a_{2j} v^2+\ldots+a_{nj}v^n$ for some constants $a_{1j},a_{2j},\ldots,a_{nj}$.
Let's denote the $jth$ column of matrix $M=\begin{pmatrix} a_{1j} \\ a_{2j} \\ \vdots \\ a_{nj} \end{pmatrix}$ as $c_j$.
Claim: The columns of matrix $M$ are linearly independent.
Consider, $\alpha_1 c_1 + \alpha_2 c_2 + \ldots \alpha_n c_n = \alpha_1 [u^1]_{B_2} + \alpha_2 [u^2]_{B_2} + \ldots + \alpha_n [u^n]_{B_2}=0$
$\implies [\alpha_1 u_1 + \alpha_2 u_2 + \ldots \alpha_n u_n]_{B_2} = 0$
$\implies \alpha_1 u_1 + \alpha_2 u_2 + \ldots \alpha_n u_n = 0$
$ \implies \alpha_1 = \alpha_2 = \ldots = \alpha_n = 0$(as $u^j$'s form a basis in $B_1$).
Hence, we have for $x = \begin{pmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{pmatrix} \in V$ we have:
$Mx=0 \implies x_1c_1+x_2c_2+\ldots+x_nc_n=0 \implies x_1=x_2=\ldots=x_n=0$(from above claim).
$i.e. x=0$ is the only solution for $Mx=0$ and hence $M$, the change of basis matrix is invertible.
Note: We could have also completed the proof by concluding that $M$ is of full rank and hence invertible instead of considering $Mx=0$ as well.
