Change of Basis

Given vector spaces $V$ and $W$ of dimension $n$ and $m$ respectively, and bases $a_1,\ldots, a_n$ and $b_1,\ldots, b_m$ for $V$ and $W$, a linear map $L:V\to W$ has an $m\times n$ matrix representation

\[[L]_{A}^{B}=\left[\begin{matrix} c_{11} & c_{12} &\cdots & c_{1n}\\\vdots & \vdots &\vdots &\vdots\\ c_{m1} & c_{m2} & \cdots & c_{mn}\end{matrix}\right]\]

where the $c_{ij}$ are defined by

\[L(a_{i}) = \sum_{j=1}^{m} c_{ji}b_{j}.\]

If $v=\sum x_{i}a_{i}\in V$, define an $n\times 1$ matrix

\[[v]_{A}=\left[\begin{matrix} x_{1}\\ \vdots \\x_{n}\end{matrix}\right]\]

We can view this as an isomorphism from $V$ to $F^{n}$ if we write our elements of $F^{n}$ as column vectors. We can do the same construction for $W$ and $F^{m}$, yielding $[w]_{B}$.

Then

\[[Lv]_{B}=[L]_{A}^{B}[v]_{A}\]

meaning that the matrix representation turns the map into matrix multiplication.

More generally if $L:V\to W$ and $H:W\to K$ are linear maps, and $A,B,C$ are bases for $V,W,K$ then

\[[H\circ L]_{A}^{C} = [H]_{B}^{C}[L]_{A}^{B}.\]

Now suppose we choose different bases $A’$ and $B’$ for $V$ and $W$.

There is a unique invertible linear map $G:V\to V$ which satisfies $G(a_i’)=a_i$ for $i=1,\ldots, n$. This means that if

\[v=\sum x_{i}a_{i}'\]

then

\[G(v)=\sum x_{i}a_{i}.\]

Important: In this convention, the inverse of the linear map $G$ carries $a_{i}$ to $a_{i}’$, so if you look at its matrix $[G^{-1}]_{A}^{A}$ in the basis $A$, its columns give the coordinates of the new basis in terms of the old. This is in some ways the more natural thing to consider.

Now

\[[Gv]_{A} = [v]_{A'}.\]

Since \([Gv]_{A}=[G]_{A}^{A}[v]_{A}\) we see that

\[[v]_{A'} = [G]_{A}^{A}[v]_{A}.\]

Now given a linear map $L:V\to W$ and basis $A’$ and $B’$ for $V$ and $W$, with:

• $G$ the map carrying $a_i’$ to $a_i$, (note the convention here. The columns of $G^{-1}$ express the new basis in terms of the old one.)
• $H$ the map carrying $b_i’$ to $b_i$.

If $L(v)=w$ we know that the matrix for $L$ is characterized by

\[[L]_{A'}^{B'}[v]_{A'}=[w]_{B'}.\]

Then

\[[L]_{A'}^{B'}[G]_{A}^{A}[v]_{A}=[H]_{B}^{B}[w]_{B}\]

so

\[[L]_{A'}^{B'}=(H_{B}^{B})^{-1}[L]_{A}^{B}G_{A}^{A}.\]

So a change of basis on the source and target modifies the matrix of the linear map by left- and right- multiplication by invertible matrices.

Example: Lagrange interpolation

Given $n+1$ points $x_0,\ldots, x_n$ in $\R$, there is a polynomial of degree $n$ with prescribed values $f(x_i)=a_i$

Let

\[f_{i}(x) = \frac{(x-x_0)(x-x_1)\cdots \widehat{(x-x_i)}\cdots (x-x_n)}{(x_i-x_0)\cdots (x_i-x_n)}\]

This polynomial vanishes on all the $x$’s except $x_i$, where it takes value $1$. These are linearly independent and \(f=\sum a_i f_{i}\) is the desired expression.

Now $x^{k}$ takes the value $x_i^k$ at $x_i$, so

\[x^k = \sum x_i^k f_{i}\]

So the basis consisting of the powers of $x$, expressed in terms of the $x_i$, is the matrix whose $k^{th}$ column, $i^{th}$ row is $x_i^{k}$. Call this matrix $G$.

Let $D$ be the matrix giving the derivative operator on polynomials of degree $n$ in the standard basis $1,x,\ldots, x^n$.

Then $G^{-1}DG$ expresses the derivative operator in terms of the basis $f_{i}$. In practice this tells you have who to compute derivatives from values of polynomials at chosen points.

See Inverses of Vandermonde Matrices, by N. Macon and A. Spitzbart, American Math Monthly 1958 vol 65 number 2.

---