Change of Basis and the Change-of-Basis Matrix

Change-of-basis machinery is the quiet workhorse behind an enormous range of applied and pure mathematics. In numerical linear algebra, converting a vector or matrix into a basis of eigenvectors (when one exists) via a change-of-basis matrix is the entire point of diagonalization, which drastically simplifies computing matrix powers, solving linear recurrences, and analyzing stability of dynamical systems. In computer graphics, every object rendered on screen is repeatedly changed from "model coordinates" to "world coordinates" to "camera coordinates" to "screen coordinates," each conversion literally a change-of-basis (together with translation) matrix multiplication applied per vertex, many times per second. In physics, changing between coordinate frames — from a lab frame to a rotating frame, or between bases adapted to different symmetries of a crystal lattice — is expressed exactly through change-of-basis matrices acting on vectors of physical quantities. In signal processing and statistics, transforming data into a new basis (such as principal components in PCA, or a Fourier/wavelet basis) is precisely a change of basis: the change-of-basis matrix packages the old features into the new coordinates that better expose structure such as variance or frequency content. In cryptography, particularly lattice-based schemes, the "goodness" or "badness" of a basis for a lattice is central, and converting between different bases of the same lattice via unimodular change-of-basis matrices underlies both the design and the cryptanalysis of these systems. Across all these settings, the underlying fact is always the same theorem proved here: coordinates transform via a fixed invertible matrix that depends only on the two bases, never on the vector in question.

:::quiz[If $P_{\mathcal C \to \mathcal B}$ has columns equal to $[c_j]_{\mathcal B}$, which equation is correct?]

• $[v]_{\mathcal C} = P_{\mathcal C\to\mathcal B}[v]_{\mathcal B}$
• $[v]_{\mathcal B} = P_{\mathcal C\to\mathcal B}[v]_{\mathcal C}$ ✓
• $[v]_{\mathcal B} = P_{\mathcal C\to\mathcal B}^2[v]_{\mathcal C}$
• $P_{\mathcal C\to\mathcal B}$ has no relation to $[v]_{\mathcal B}$ or $[v]_{\mathcal C}$

Ask the tutor: How exactly does the formula $A' = PAP^{-1}$ for similar matrices follow from the change-of-basis theorem proved here?

Think of a basis as a language for naming vectors with tuples of numbers. The vector itself never moves; only its name changes when you switch languages. The change-of-basis matrix $P_{\mathcal C \to \mathcal B}$ is a dictionary: feed it the $\mathcal{C}$-name of a vector, and multiplication by $P$ returns its $\mathcal{B}$-name. Concretely, in $\mathbb{R}^2$, let $\mathcal B$ be the standard basis and let $\mathcal C = (c_1, c_2)$ be a tilted basis. To translate a $\mathcal C$-coordinate pair into standard coordinates, you simply take that many copies of $c_1$ and $c_2$ and add them — which is exactly matrix-vector multiplication by the matrix whose columns are $c_1, c_2$ written in standard coordinates. The picture below shows a single vector $v$, expressed once in the standard grid and once in a skewed grid built from $c_1=(2,1)$ and $c_2=(1,3)$.

Here $v = 1\cdot c_1 + 2\cdot c_2 = (2,1) + (2,6) = (4,7)$; to match the figure's label of $(4,5)$ exactly one would choose $c_1=(2,1), c_2=(1,2)$ instead, giving $v = 1\cdot(2,1)+2\cdot(1,2) = (4,5)$ — the essential point standing regardless of the exact numbers is that both diagrams draw the same arrow $v$, merely gridded differently, and the change-of-basis matrix is precisely the machine converting the red/green grid-coordinates into the black grid-coordinates.

Example 1: Two non-orthogonal bases of $\mathbb{R}^2$, going both directions. Let $\mathcal B = (b_1, b_2)$ be the standard basis of $\mathbb{R}^2$: $b_1 = (1,0)$, $b_2 = (0,1)$. Let

First check $\mathcal C$ is a basis: the matrix $\begin{pmatrix}3 & 2\\ 1 & 5\end{pmatrix}$ has determinant $3\cdot5 - 2\cdot1 = 13 \neq 0$, so $c_1, c_2$ are linearly independent, and two independent vectors in a 2-dimensional space form a basis. Since $\mathcal B$ is standard, writing $c_j$ in terms of $b_1, b_2$ is trivial: $c_1 = 3b_1 + 1b_2$, $c_2 = 2b_1 + 5b_2$. So

Take the vector $v = (11, 8)$ (in standard coordinates, i.e. $[v]_{\mathcal B} = (11,8)^T$). We find $[v]_{\mathcal C}$ two ways. Direct way. Solve $x_1 c_1 + x_2 c_2 = v$:

From the second equation $x_1 = 8 - 5x_2$. Substituting: $3(8-5x_2) + 2x_2 = 11 \Rightarrow 24 - 15x_2 + 2x_2 = 11 \Rightarrow -13x_2 = -13 \Rightarrow x_2 = 1$. Then $x_1 = 8 - 5 = 3$. So $[v]_{\mathcal C} = (3,1)^T$. Matrix way. By the theorem, $[v]_{\mathcal B} = P_{\mathcal C\to\mathcal B}[v]_{\mathcal C}$, so $[v]_{\mathcal C} = P_{\mathcal C\to\mathcal B}^{-1}[v]_{\mathcal B}$. Compute the inverse using the $2\times 2$ formula:

Then

Both methods agree: $[v]_{\mathcal C} = (3,1)^T$, confirming $v = 3c_1 + c_2 = 3(3,1) + (2,5) = (9,3)+(2,5) = (11,8)$. ✓. This also verifies the corollary-flavored fact $P_{\mathcal B \to \mathcal C} = P_{\mathcal C \to \mathcal B}^{-1}$ from Part 2 of the theorem, computed explicitly above.

Example 2: Neither basis is standard — $\mathbb{R}^3$, with an explicit intermediate step through the standard basis. Let $V = \mathbb{R}^3$. Define two ordered bases, neither one standard:

We want $P_{\mathcal C\to \mathcal B}$, whose columns are $[c_1]_{\mathcal B}, [c_2]_{\mathcal B}, [c_3]_{\mathcal B}$. Step 1: check $\mathcal B$ is a basis. Determinant of $\begin{pmatrix}1&0&1\\1&1&0\\0&1&1\end{pmatrix}$ (columns $b_1,b_2,b_3$) expand along the first row: $1\cdot(1\cdot1 - 0\cdot1) - 0\cdot(\cdots) + 1\cdot(1\cdot1-1\cdot0) = 1 + 1 = 2 \neq 0$. So $\mathcal B$ is a basis. Similarly for $\mathcal C$: determinant of $\begin{pmatrix}2&1&0\\0&1&2\\1&1&1\end{pmatrix}$ expand along first row: $2(1\cdot1-2\cdot1) - 1(0\cdot1-2\cdot1) + 0 = 2(-1) -1(-2) = -2+2=0$? Let's recompute carefully: entries are columns $c_1=(2,0,1)^T, c_2=(1,1,1)^T, c_3=(0,2,1)^T$, so the matrix is

$\det M = 2(1\cdot1 - 2\cdot1) - 1(0\cdot1 - 2\cdot1) + 0(0\cdot1-1\cdot1) = 2(1-2) - 1(0-2) + 0 = 2(-1) - 1(-2) = -2+2 = 0.$ This determinant is zero — $\mathcal C$ as originally chosen is not independent, so it fails to be a basis; let's fix this by replacing $c_3$ with a vector that restores independence, e.g. $c_3 = (0,2,3)$ instead of $(0,2,1)$, and redo the check:

Good — with $c_3=(0,2,3)$, $\mathcal C=(c_1,c_2,c_3)$, $c_1=(2,0,1),\,c_2=(1,1,1),\,c_3=(0,2,3)$, is a genuine basis of $\mathbb R^3$. Step 2: find each $[c_j]_{\mathcal B}$ by solving linear systems in the standard basis, then converting. Since we know $c_j$ and $b_i$ in standard coordinates, we solve $c_j = x_1 b_1 + x_2 b_2 + x_3 b_3$ directly. Writing $B = [b_1\,b_2\,b_3] = \begin{pmatrix}1&0&1\\1&1&0\\0&1&1\end{pmatrix}$, we need $B^{-1}$. Compute $B^{-1}$: since $\det B = 2$ (found above), use the adjugate. Cofactors of $B$:

(Check: $B \cdot \tfrac12\begin{pmatrix}1&1&-1\\-1&1&1\\1&-1&1\end{pmatrix}$, first column of product: $\begin{pmatrix}1&0&1\\1&1&0\\0&1&1\end{pmatrix}\cdot\frac12(1,-1,1)^T = \frac12(1\cdot1+0\cdot(-1)+1\cdot1,\ 1\cdot1+1\cdot(-1)+0\cdot1,\ 0\cdot1+1\cdot(-1)+1\cdot1) = \frac12(2,0,0) = (1,0,0)^T$. ✓ matches identity's first column.) Now compute $[c_1]_{\mathcal B} = B^{-1}c_1 = \frac12\begin{pmatrix}1&1&-1\\-1&1&1\\1&-1&1\end{pmatrix}\begin{pmatrix}2\\0\\1\end{pmatrix} = \frac12\begin{pmatrix}2+0-1\\-2+0+1\\2-0+1\end{pmatrix} = \frac12\begin{pmatrix}1\\-1\\3\end{pmatrix} = \begin{pmatrix}1/2\\-1/2\\3/2\end{pmatrix}.$ Check: $\tfrac12 b_1 - \tfrac12 b_2 + \tfrac32 b_3 = \tfrac12(1,1,0) - \tfrac12(0,1,1) + \tfrac32(1,0,1) = (\tfrac12,\tfrac12,0)+(0,-\tfrac12,-\tfrac12)+(\tfrac32,0,\tfrac32) = (2,0,1) = c_1$. ✓ $[c_2]_{\mathcal B} = B^{-1}c_2 = \frac12\begin{pmatrix}1&1&-1\\-1&1&1\\1&-1&1\end{pmatrix}\begin{pmatrix}1\\1\\1\end{pmatrix} = \frac12\begin{pmatrix}1+1-1\\-1+1+1\\1-1+1\end{pmatrix}=\frac12\begin{pmatrix}1\\1\\1\end{pmatrix} = \begin{pmatrix}1/2\\1/2\\1/2\end{pmatrix}.$ Check: $\tfrac12(b_1+b_2+b_3) = \tfrac12((1,1,0)+(0,1,1)+(1,0,1)) = \tfrac12(2,2,2) = (1,1,1) = c_2$. ✓ $[c_3]_{\mathcal B} = B^{-1}c_3 = \frac12\begin{pmatrix}1&1&-1\\-1&1&1\\1&-1&1\end{pmatrix}\begin{pmatrix}0\\2\\3\end{pmatrix} = \frac12\begin{pmatrix}0+2-3\\0+2+3\\0-2+3\end{pmatrix} = \frac12\begin{pmatrix}-1\\5\\1\end{pmatrix} = \begin{pmatrix}-1/2\\5/2\\1/2\end{pmatrix}.$ Check: $-\tfrac12 b_1 + \tfrac52 b_2 + \tfrac12 b_3 = -\tfrac12(1,1,0)+\tfrac52(0,1,1)+\tfrac12(1,0,1) = (-\tfrac12,-\tfrac12,0)+(0,\tfrac52,\tfrac52)+(\tfrac12,0,\tfrac12) = (0,2,3) = c_3$. ✓ Step 3: assemble $P_{\mathcal C \to \mathcal B}$.

Step 4: sanity-check invertibility and use it. Take $v$ with $\mathcal C$-coordinates $[v]_{\mathcal C} = (2, -1, 1)^T$, meaning $v = 2c_1 - c_2 + c_3 = 2(2,0,1) - (1,1,1) + (0,2,3) = (4,0,2)-(1,1,1)+(0,2,3) = (3,1,4)$. By the theorem, $[v]_{\mathcal B} = P_{\mathcal C\to\mathcal B}[v]_{\mathcal C}$:

Check directly: $0\cdot b_1 + 1\cdot b_2 + 3\cdot b_3 = (0,1,1) + 3(1,0,1) = (0,1,1)+(3,0,3) = (3,1,4) = v$. ✓ This matches the standard-coordinate computation of $v$ above, confirming the change-of-basis formula.