# Change of basis of a linear map defined by non-square matrix

The given:

Let a linear map $$L : V → U$$ be given in the basis $$(e_1, e_2, e_3)$$ of $$V$$ and in the basis $$(f_1, f_2)$$ of $$U$$ by $$\begin{pmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \end{pmatrix}$$. Find the matrix of $$L$$ with respect to the bases $$(e_1, e_1 + e_2, e_1 + e_2 + e_3)$$ and $$(f_1, f_1 + f_2)$$.

Now I know I am being stupid in some way, but I can't make this work. I want to say: we have new bases $$(e_1,e_1+e_2,e_1+e_2+e_3)$$ and $$(f_1,f_1+f_2)$$ which correspond to $$C = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}$$ and $$D = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$$ respectively. And Using our change of bases formula, one version of $$L_1' = C^TAC$$ and the other is $$L_2' = D^TAD$$. But here I run into a problem of dimension, the matrix multiplication does not work. I had thought perhaps to try $$L'=DAC$$, since this expression has workable dimension, but that's my only reason for trying it. The basis change examples I've seen before involve expressions with one matrix and either its transpose or inverse.

Apologies again for my stupidity here, and thanks very much in advance for any assistance.

Edit: Initial problem had typo on $$D$$, one-zero were swapped incorrectly.

I hate the change of basis formula. I think it confuses way too many people, and obscures the simple intuition going on behind the scenes.

Recall the definition of matrices for a linear map $$T : V \to W$$. If $$B_1 = (v_1, \ldots, v_m)$$ is a basis for $$V$$ and $$B_2$$ is a basis for $$W$$ (also ordered and finite), then we define $$[T]_{B_2 \leftarrow B_1} = \left([Tv_1]_{B_2} \mid [Tv_2]_{B_2} | \ldots | \, [Tv_n]_{B_2} \right),$$ where $$[w]_{B_2}$$ refers to the coordinate column vector of $$w \in W$$ with respect to the basis $$B_2$$. Essentially, it's the matrix you get by transforming the basis $$B_1$$, writing the resulting vectors in terms of $$B_2$$, and writing the resulting coordinate vectors as columns.

Such a matrix has the following lovely property (and is completely defined by this property):

$$[T]_{B_2 \leftarrow B_1} [v]_{B_1} = [Tv]_{B_2}.$$

This is what makes the matrix useful. When we compute with finite-dimensional vector spaces, we tend to store vectors in terms of their coordinate vector with respect to a basis. So, this matrix allows us to directly apply $$T$$ to such a coordinate vector to return a coordinate vector in terms of the basis on the codomain.

This also means that, if we also have $$S : W \to U$$, and $$U$$ has a (finite, ordered) basis $$B_3$$, then we have

$$[S]_{B_3 \leftarrow B_2}[T]_{B_2 \leftarrow B_1}[v]_{B_1} = [S]_{B_3 \leftarrow B_2}[Tv]_{B_2} = [STv]_{B_3},$$

and so

$$[ST]_{B_3 \leftarrow B_1} = [S]_{B_3 \leftarrow B_2}[T]_{B_2 \leftarrow B_1}.$$

Note also that, if $$\mathrm{id} : V \to V$$ is the identity operator, then

$$[\mathrm{id}]_{B_1 \leftarrow B_1}[v]_{B_1} = [v]_{B_1},$$

which implies $$[\mathrm{id}]_{B_1 \leftarrow B_1}$$ is the $$n \times n$$ identity matrix $$I_n$$. Moreover, if $$T$$ is invertible, then $$\operatorname{dim} W = n$$ and then

$$I_n = [\mathrm{id}]_{B_1 \leftarrow B_1} = [T^{-1}T]_{B_1 \leftarrow B_1} = [T^{-1}]_{B_1 \leftarrow B_2}[T]_{B_2 \leftarrow B_1}.$$

Similarly,

$$I_n = [\mathrm{id}]_{B_2 \leftarrow B_2} = [TT^{-1}]_{B_1 \leftarrow B_1} = [T]_{B_2 \leftarrow B_1}[T^{-1}]_{B_1 \leftarrow B_2}.$$

What this means is

$$[T]_{B_2 \leftarrow B_1}^{-1} = [T^{-1}]_{B_1 \leftarrow B_2}$$

From this, we can derive the change of basis formula. If we have a linear operator $$T : V \to V$$ and two bases $$B_1$$ and $$B_2$$ on $$V$$, then

\begin{align*} [T]_{B_2 \leftarrow B_2} &= [\mathrm{id} \circ T \circ \mathrm{id}]_{B_2 \leftarrow B_2} \\ &= [\mathrm{id}]_{B_2 \leftarrow B_1} [T]_{B_1 \leftarrow B_1} [\mathrm{id}]_{B_1 \leftarrow B_2} \\ &= [\mathrm{id}^{-1}]_{B_2 \leftarrow B_1} [T]_{B_1 \leftarrow B_1} [\mathrm{id}]_{B_1 \leftarrow B_2} \\ &= [\mathrm{id}]^{-1}_{B_1 \leftarrow B_2} [T]_{B_1 \leftarrow B_1} [\mathrm{id}]_{B_1 \leftarrow B_2} \\ \end{align*}

It's easy to see that, if $$B_1$$ is the standard basis for $$V = \mathbb{F}^n$$, then $$[\mathrm{id}]_{B_1 \leftarrow B_2}$$ is the result of putting the basis vectors in $$B_2$$ into columns of a matrix, and this particular case is the change of basis formula.

Now, this works for an operator on $$\mathbb{F}^n$$. You've got a linear map between two unspecified spaces, so this formula will not apply. But, we can definitely use the same tools. Let \begin{align*} B_1 &= (e_1, e_2, e_3) \\ B_1' &= (e_1, e_1 + e_2, e_1 + e_2 + e_3) \\ B_2 &= (f_1, f_2) \\ B_2' &= (f_1, f_1 + f_2). \end{align*} We want $$[L]_{B_2' \leftarrow B_1'}$$, and we know $$[L]_{B_2 \leftarrow B_1}$$. We compute

\begin{align*} [L]_{B_2' \leftarrow B_1'} &= [\mathrm{id} \circ L \circ \mathrm{id}]_{B_2' \leftarrow B_1'} \\ &= [\mathrm{id}]_{B_2' \leftarrow B_2} [L]_{B_2 \leftarrow B_1} [\mathrm{id}]_{B_1 \leftarrow B_1'}. \end{align*}

We know $$[L]_{B_2 \leftarrow B_1}$$, so we must compute the other two matrices. We have

$$[\mathrm{id}]_{B_1 \leftarrow B_1'} = \left([e_1]_{B_1} \mid [e_1 + e_2]_{B_1} | \, [e_1 + e_2 + e_3]_{B_1} \right) = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}.$$

Similarly,

$$[\mathrm{id}]_{B_2 \leftarrow B_2'} = \left([f_1]_{B_2} \mid \, [f_1 + f_2]_{B_2}\right) = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix},$$

and so

$$[\mathrm{id}]_{B_2' \leftarrow B_2} = [\mathrm{id}]^{-1}_{B_2 \leftarrow B_2'} = \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix}.$$

Finally, this gives us,

$$[L]_{B_2' \leftarrow B_1'} = \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \end{pmatrix} \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} -3 & -6 & -9 \\ 3 & 7 & 12 \end{pmatrix}.$$

• My thanks to you as well for the extremely in-depth answer, it's more than I can hope for. I think it will be especially helpful to see multiple deep perspectives on this. – Raj Sep 24 '18 at 1:14

TL;DR: The correct formula is $$D^{-1}AC$$.

Change of basis is not as hard as it looks and you don't need to memorize any formulas.

First, if $$e$$ is a basis for $$V$$ and $$f$$ is a basis for $$U$$, I will denote by $${[L]^e_f}$$ the matrix of $$L\colon V\to U$$ written in a pair of bases $$(e,f)$$. This works as follows: $$[L]^e_f$$ knows how to deal with vectors written in basis $$e$$ and spits out a vector written in basis $$f$$, i.e. $$[L]^e_f[v]_e = [Lv]_f$$.

Now, we want to change bases, i.e. we want $$[L]^{e'}_{f'}$$. Of course, that matrix can only deal with vectors written in basis $$e'$$ and will spit out a vector in basis $$f'$$. Unfortunately, we have no idea how $$[L]^{e'}_{f'}$$ is supposed to look like, but fortunately, there is an easy trick which comes from a simple observation: $$L = I_ULI_V,$$ where $$I$$'s are appropriate identity operators.

So, how does this help us? Well, we want to turn the last expression in a convenient matrix form, LHS should be $$[L]^{e'}_{f'}$$ and the $$L$$ on RHS should be $$[L]^{e}_{f}$$. That is, we want something like $$[L]^{e'}_{f'} = [I_U]^{?}_{?} [L]^{e}_{f} [I_V]^{?}_{?}$$.

On LHS, we want to feed the matrix a vector written in basis $$e'$$, so $$[I_V]^?_?$$ should recognize it as well. Also, $$[I_V]^?_?$$ should give us a vector written in basis $$e$$, so $$[L]^{e}_{f}$$ could recognize it. That is, we should have $$[I_V]^{e'}_{e}.$$

Since $$[L]^{e}_{f}$$ returns a vector written in basis $$f$$, $$[I_U]^?_?$$ should recognize it, and since $$[L]^{e'}_{f'}$$ should return a vector written in basis $$f'$$, the same applies to $$[I_U]^?_?$$. That is, we need $$[I_U]^{f}_{f'}.$$

The whole formula now looks like $$[L]^{e'}_{f'} = [I_U]^{f}_{f'} [L]^{e}_{f} [I_V]^{e'}_{e}$$. We can quickly check it:

$$[I_U]^{f}_{f'} [L]^{e}_{f} [I_V]^{e'}_{e}[v]_{e'} = [I_U]^{f}_{f'} [L]^{e}_{f} [I_Vv]_{e} = [I_U]^{f}_{f'} [LI_Vv]_{f} = [I_ULI_Vv]_{f'} = [Lv]_{f'} = [L]^{e'}_{f'}[v]_{e'}.$$

Now, that we have a formula (that we, hopefully, now understand how it works), all it remains is to see how to get $$[I_V]^{e'}_{e}$$ and $$[I_U]^{f}_{f'}$$.

To get $$i$$-th column of $$[I_V]^{e'}_{e}$$, we need to multiply $$[I_V]^{e'}_{e}$$ by column vector $$[0\, 0\, \ldots\, 0\, 1\, 0\, \ldots\, 0]^t$$ with $$1$$ on the $$i$$-th place. But since $$[I_V]^{e'}_{e}$$ only accepts vectors written in basis $$e'$$, that column vector is $$e'_i$$ written in basis $$e'$$. All in all, the $$i$$-th column is $$[I_V]^{e'}_{e}[e'_i]_{e'} = [I_Ve'_i]_{e} = [e'_i]_e,$$ i.e., $$e'_i$$ written in basis $$e$$.

In your example, this is precisely your matrix $$C$$.

To get $$[I_U]^{f}_{f'}$$, you would do precisely the same, write basis vectors $$f_i$$ in basis $$f'$$. Easy, right? Ok, ok, it's not as easy since in your example we know how to write $$f'_i$$ in basis $$f$$, but how to do the opposite is not obvious.

But there's a trick. Actually, $$[I_U]^{f'}_{f}$$ is quite easy, that's your matrix $$D$$. So, how do we get $$[I_U]^{f}_{f'}$$?

I claim that $$[I_U]^{f}_{f'} = ([I_U]^{f'}_{f})^{-1}.$$ We can see this since

$$[I_U]^{f}_{f'}[I_U]^{f'}_{f}[u]_{f'} = [I_U]^{f}_{f'}[u]_f = [u]_{f'}$$ and thus, $$[I_U]^{f}_{f'}[I_U]^{f'}_{f}$$ is the identity matrix.

Hence, in your example, $$[I_U]^{f}_{f'} = D^{-1}$$ and the correct formula is $$D^{-1}AC$$.

• Thank you very much for that exceptionally detailed explanation, I'm going to digest it for a while, but I greatly appreciate the efforts. – Raj Sep 24 '18 at 1:13
• @Raj, you are welcome. Definitely also check the answer by Theo Bendit, it's very similar but I think perhaps has some details better explained. – Ennar Sep 24 '18 at 1:15
• Oh wow, I didn't notice your answer. Whoops. +1 – Theo Bendit Sep 24 '18 at 1:15
• @Theo, +1 to you as well. The time difference for such a lenghty answers is too small, so it's understandable. And I like your answer, also. – Ennar Sep 24 '18 at 1:18

You should have gotten $$D = \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array} \right)$$ Then $$D^{-1}A C = \left( \begin{array}{ccc} -3 & -6 & -9\\ 3 & 7 & 12 \end{array} \right)$$