CommeUnJeu · L1 PCSI

Change of basis, equivalence, similarity

⌚ ~19 min ▢ 2 blocks ✓ 11 exercises ➣ Prerequisites : Matrix representation of linear maps, Finite-dimensional vector spaces

The chapter Matrix representation of linear maps set up the dictionary $u \leftrightarrow \mathrm{Mat}_{\mathcal{B}, \mathcal{B}'}(u)$ between a linear map and its matrix once a basis is fixed. Two natural questions remained open: how does the matrix transform when the basis is changed, and what is the right way to say that two matrices encode « the same » endomorphism up to a change of viewpoint? This chapter answers both.
The plan has two sections. Change of basis introduces the passage matrix $P_{\mathcal{B}}^{\mathcal{B}'}$, proves the two key formulas $X = P X'$ (for a vector) and $A' = Q^{-1} A P$ (for a linear map), and specialises the second formula to endomorphisms ($A' = P^{-1} A P$). Similar matrices introduces the relation « matrices semblables » on square matrices: two matrices are similar when they represent the same endomorphism in two bases; the rank is a similarity invariant, but it does not classify similarity classes.
Throughout the chapter, $\mathbb{K} \in \{\mathbb{R}, \mathbb{C}\}$, and all vector spaces $E, F, G$ are $\mathbb{K}$-vector spaces of finite dimension, equipped with bases denoted by $\mathcal{B}, \mathcal{B}', \mathcal{B}''$ etc. For a linear map $u \in \mathcal{L}(E, F)$ with $\dim E = p$ and $\dim F = n$, the matrix $\mathrm{Mat}_{\mathcal{B}, \mathcal{B}'}(u) \in M_{n, p}(\mathbb{K})$ is read in the source basis $\mathcal{B}$ and the target basis $\mathcal{B}'$; for an endomorphism $u \in \mathcal{L}(E)$, $\mathrm{Mat}_{\mathcal{B}}(u) \in M_n(\mathbb{K})$ uses the same basis on both sides. The notations $\mathrm{rg}, \mathrm{Ker}, \mathrm{Im}$ keep their usual meaning. $\mathrm{GL}_n(\mathbb{K})$ is the group of invertible $n \times n$ matrices and $\mathrm{GL}(E)$ the group of automorphisms of $E$.

I Change of basis

The change-of-basis story rests on a single object: the passage matrix $P_{\mathcal{B}}^{\mathcal{B}'}$, whose columns store the new basis vectors expressed in the old basis. Two formulas then follow mechanically. A vector has two coordinate columns $X$ (old basis) and $X'$ (new basis); they are related by $X = P X'$. A linear map has two matrix representations $A$ (old basis pair) and $A'$ (new basis pair); they are related by $A' = Q^{-1} A P$, where $P$ is the source change and $Q$ is the target change. For an endomorphism, source and target collapse: $A' = P^{-1} A P$.

Definition — Passage matrix

Let $E$ be a $\mathbb{K}$-vector space of finite dimension and let $\mathcal{B}, \mathcal{B}'$ be two bases of $E$. The passage matrix from $\mathcal{B}$ to $\mathcal{B}'$ is $$ P_{\mathcal{B}}^{\mathcal{B}'} = \mathrm{Mat}_{\mathcal{B}', \mathcal{B}}(\mathrm{Id}_E). $$ More explicitly, write $\mathcal{B} = (e_1, \dots, e_n)$, $\mathcal{B}' = (e'_1, \dots, e'_n)$, and $P_{\mathcal{B}}^{\mathcal{B}'} = (a_{ij})_{1 \le i \le n,\, 1 \le j \le n}$. Then $$ \forall j \in \{1, \dots, n\}: \quad e'_j = \sum_{i=1}^{n} a_{ij}\, e_i. $$ Equivalently, the $j$-th column of $P_{\mathcal{B}}^{\mathcal{B}'}$ contains the coordinates of $e'_j$ in the basis $\mathcal{B}$:

Proposition — Properties of the passage matrix

Let $\mathcal{B}, \mathcal{B}', \mathcal{B}''$ be three bases of the same $\mathbb{K}$-vector space $E$ of finite dimension. Then:

Invertibility: $P_{\mathcal{B}}^{\mathcal{B}'} \in \mathrm{GL}_n(\mathbb{K})$ where $n = \dim E$, with inverse $\bigl(P_{\mathcal{B}}^{\mathcal{B}'}\bigr)^{-1} = P_{\mathcal{B}'}^{\mathcal{B}}$.
Composition: $P_{\mathcal{B}}^{\mathcal{B}'} \cdot P_{\mathcal{B}'}^{\mathcal{B}''} = P_{\mathcal{B}}^{\mathcal{B}''}$.

Proof

Both properties follow from the dictionary isomorphism of chapter Matrix representation of linear maps.

Invertibility. The identity $\mathrm{Id}_E$ is an automorphism of $E$, so by the « iso $\Leftrightarrow$ invertible matrix » theorem, $\mathrm{Mat}_{\mathcal{B}', \mathcal{B}}(\mathrm{Id}_E)$ is invertible and its inverse is $\mathrm{Mat}_{\mathcal{B}, \mathcal{B}'}(\mathrm{Id}_E^{-1}) = \mathrm{Mat}_{\mathcal{B}, \mathcal{B}'}(\mathrm{Id}_E) = P_{\mathcal{B}'}^{\mathcal{B}}$.
Composition. Apply the « composition becomes matrix product » theorem to $\mathrm{Id}_E \circ \mathrm{Id}_E = \mathrm{Id}_E$ read in the three bases $\mathcal{B}'', \mathcal{B}', \mathcal{B}$: $$ \mathrm{Mat}_{\mathcal{B}'', \mathcal{B}}(\mathrm{Id}_E) = \mathrm{Mat}_{\mathcal{B}', \mathcal{B}}(\mathrm{Id}_E) \cdot \mathrm{Mat}_{\mathcal{B}'', \mathcal{B}'}(\mathrm{Id}_E), $$ which reads $P_{\mathcal{B}}^{\mathcal{B}''} = P_{\mathcal{B}}^{\mathcal{B}'} \cdot P_{\mathcal{B}'}^{\mathcal{B}''}$.

Example

In $\mathbb{R}^2$, take the canonical basis $\mathcal{B} = ((1, 0), (0, 1))$ and the basis $\mathcal{B}' = ((1, 1), (1, -1))$. The columns of $P_{\mathcal{B}}^{\mathcal{B}'}$ are the coordinates of $(1, 1)$ and $(1, -1)$ in $\mathcal{B}$, read directly: $$ P_{\mathcal{B}}^{\mathcal{B}'} = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}. $$ The inverse $P_{\mathcal{B}'}^{\mathcal{B}}$ is obtained by Gauss-Jordan or by direct $2 \times 2$ inversion: $P_{\mathcal{B}'}^{\mathcal{B}} = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$.

Example

In $\mathbb{R}_2[X]$, take the canonical basis $\mathcal{B} = (1, X, X^2)$ and the Taylor basis at $a \in \mathbb{R}$: $\mathcal{B}' = (1, X - a, (X - a)^2)$. Expanding gives $(X - a)^2 = X^2 - 2 a X + a^2$, so the columns of $P_{\mathcal{B}}^{\mathcal{B}'}$ are $$ P_{\mathcal{B}}^{\mathcal{B}'} = \begin{pmatrix} 1 & -a & a^2 \\ 0 & 1 & -2 a \\ 0 & 0 & 1 \end{pmatrix}. $$ The matrix is upper triangular with $1$s on the diagonal, hence invertible --- confirming that $\mathcal{B}'$ is indeed a basis.

Method — Compute the passage matrix

To compute $P_{\mathcal{B}}^{\mathcal{B}'}$:

Read off each vector $e'_j$ of $\mathcal{B}'$.
Decompose $e'_j$ in $\mathcal{B}$: $e'_j = a_{1j} e_1 + \dots + a_{nj} e_n$.
The $j$-th column of $P_{\mathcal{B}}^{\mathcal{B}'}$ is $(a_{1j}, \dots, a_{nj})^\top$.

Columns of $P_{\mathcal{B}}^{\mathcal{B}'}$ are vectors of $\mathcal{B}'$ expressed in $\mathcal{B}$. Reverse the roles to obtain $P_{\mathcal{B}'}^{\mathcal{B}}$ --- or invert the matrix.

Theorem — Change of basis for a vector

Let $\mathcal{B}, \mathcal{B}'$ be two bases of a finite-dimensional $\mathbb{K}$-vector space $E$. For every $x \in E$, with $X = \mathrm{Mat}_{\mathcal{B}}(x)$ and $X' = \mathrm{Mat}_{\mathcal{B}'}(x)$: $$ X = P_{\mathcal{B}}^{\mathcal{B}'} \, X'. $$

Proof

Apply the matrix-vector formula from chapter Matrix representation of linear maps to the identity $\mathrm{Id}_E$ and the vector $x$, read in source basis $\mathcal{B}'$ and target basis $\mathcal{B}$: $$ \mathrm{Mat}_{\mathcal{B}}(\mathrm{Id}_E(x)) = \mathrm{Mat}_{\mathcal{B}', \mathcal{B}}(\mathrm{Id}_E) \cdot \mathrm{Mat}_{\mathcal{B}'}(x). $$ Since $\mathrm{Id}_E(x) = x$, the left-hand side is $X$; the right-hand side is $P_{\mathcal{B}}^{\mathcal{B}'} \cdot X'$, giving $X = P_{\mathcal{B}}^{\mathcal{B}'} X'$.

Convention warning

The passage matrix converts NEW coordinates to OLD coordinates, not the other way around: $$ X = P_{\mathcal{B}}^{\mathcal{B}'} \, X' \qquad \text{(new $X'$ on the right, old $X$ on the left).} $$ To go from old to new, invert: $X' = \bigl(P_{\mathcal{B}}^{\mathcal{B}'}\bigr)^{-1} X = P_{\mathcal{B}'}^{\mathcal{B}} X$.
This is the main trap of the chapter --- students often expect the opposite direction. The convention is forced by the definition $P_{\mathcal{B}}^{\mathcal{B}'} = \mathrm{Mat}_{\mathcal{B}', \mathcal{B}}(\mathrm{Id}_E)$: the columns are vectors of $\mathcal{B}'$ in $\mathcal{B}$, so multiplying by $P_{\mathcal{B}}^{\mathcal{B}'}$ « converts $\mathcal{B}'$-coordinates back to $\mathcal{B}$-coordinates ».

Example

With the bases $\mathcal{B} = ((1, 0), (0, 1))$ and $\mathcal{B}' = ((1, 1), (1, -1))$ of $\mathbb{R}^2$ as before, take $x = (3, 5)$. In the canonical basis, $X = (3, 5)^\top$ directly. The coordinates $X' = (a, b)^\top$ in $\mathcal{B}'$ satisfy $X = P_{\mathcal{B}}^{\mathcal{B}'} X'$, that is $a + b = 3$ and $a - b = 5$. Adding gives $a = 4$, then $b = -1$. So $X' = (4, -1)^\top$.

Method — Switch between coordinates in two bases

Given $P = P_{\mathcal{B}}^{\mathcal{B}'}$ and a vector $x$ with known coordinates in one basis:

New $\to$ old: if $X'$ is known, then $X = P X'$ directly.
Old $\to$ new: if $X$ is known, then $X' = P^{-1} X$. Either invert $P$, or solve the linear system $P X' = X$ for $X'$.

Theorem — Change of basis for a linear map

Let $u \in \mathcal{L}(E, F)$ with $E$ and $F$ finite-dimensional. Let $\mathcal{B}, \mathcal{B}'$ be two bases of $E$ and $\mathcal{C}, \mathcal{C}'$ two bases of $F$. Set $P = P_{\mathcal{B}}^{\mathcal{B}'}$, $Q = P_{\mathcal{C}}^{\mathcal{C}'}$, $A = \mathrm{Mat}_{\mathcal{B}, \mathcal{C}}(u)$, $A' = \mathrm{Mat}_{\mathcal{B}', \mathcal{C}'}(u)$. Then $$ A' = Q^{-1} \, A \, P. $$

Proof

Apply the « composition becomes matrix product » theorem to $u \circ \mathrm{Id}_E = \mathrm{Id}_F \circ u$, read in source basis $\mathcal{B}'$ and target basis $\mathcal{C}$: $$ \mathrm{Mat}_{\mathcal{B}', \mathcal{C}}(u \circ \mathrm{Id}_E) = \mathrm{Mat}_{\mathcal{B}', \mathcal{C}}(\mathrm{Id}_F \circ u). $$ The left-hand side factors as $\mathrm{Mat}_{\mathcal{B}, \mathcal{C}}(u) \cdot \mathrm{Mat}_{\mathcal{B}', \mathcal{B}}(\mathrm{Id}_E) = A \cdot P$. The right-hand side factors as $\mathrm{Mat}_{\mathcal{C}', \mathcal{C}}(\mathrm{Id}_F) \cdot \mathrm{Mat}_{\mathcal{B}', \mathcal{C}'}(u) = Q \cdot A'$. Hence $A P = Q A'$, and since $Q$ is invertible, $A' = Q^{-1} A P$.

The commutative diagram below visualises the formula. Each vertex is a coordinate space, each horizontal arrow encodes $u$ in the corresponding basis pair, and each vertical arrow encodes the change of basis (new $\to$ old). Commutativity of the square reads $A P = Q A'$, equivalently $A' = Q^{-1} A P$.

Corollary — Endomorphism case

Let $u \in \mathcal{L}(E)$ with $E$ finite-dimensional. Let $\mathcal{B}, \mathcal{B}'$ be two bases of $E$. Set $P = P_{\mathcal{B}}^{\mathcal{B}'}$, $A = \mathrm{Mat}_{\mathcal{B}}(u)$, $A' = \mathrm{Mat}_{\mathcal{B}'}(u)$. Then $$ A' = P^{-1} \, A \, P. $$

Proof

Special case of the previous theorem with $E = F$, $\mathcal{C} = \mathcal{B}$, $\mathcal{C}' = \mathcal{B}'$, hence $Q = P_{\mathcal{B}}^{\mathcal{B}'} = P$.

Example

Take the endomorphism $u \colon \mathbb{R}^2 \to \mathbb{R}^2$, $u(x, y) = (x + y, y)$ (a shear). In the canonical basis $\mathcal{B} = ((1, 0), (0, 1))$, $u(1, 0) = (1, 0)$ and $u(0, 1) = (1, 1)$, so $$ A = \mathrm{Mat}_{\mathcal{B}}(u) = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}. $$ Switch to the basis $\mathcal{B}' = ((1, 1), (0, 1))$. Read the columns of $P_{\mathcal{B}}^{\mathcal{B}'}$ as the new basis vectors expressed in the canonical basis: $P = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$, and $P^{-1} = \begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix}$. Compute step by step: $$ A P = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}, \qquad A' = P^{-1} (A P) = \begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ -1 & 0 \end{pmatrix}. $$ The new matrix $A'$ is genuinely different from $A$ --- entries have moved --- yet, by construction through the formula $A' = P^{-1} A P$, both matrices represent the same shear endomorphism $u$, simply read in two different bases.

Method — Apply the change-of-basis formula

To compute $A' = \mathrm{Mat}_{\mathcal{B}', \mathcal{C}'}(u)$ from $A = \mathrm{Mat}_{\mathcal{B}, \mathcal{C}}(u)$:

Identify the source passage matrix $P = P_{\mathcal{B}}^{\mathcal{B}'}$.
Identify the target passage matrix $Q = P_{\mathcal{C}}^{\mathcal{C}'}$.
Compute $A' = Q^{-1} A P$ (matrix product).

For an endomorphism with single basis change, $P = Q$ and the formula collapses to $A' = P^{-1} A P$.

Skills to practice

Change of basis

II Similar matrices

For an endomorphism, the source space and the target space are one and the same space $E$, so a single change of basis acts on both sides at once. Specialising the change-of-basis formula $A' = Q^{-1} A P$ to this situation forces $Q = P$, and the two matrices of the endomorphism in the old and new bases are related by $A' = P^{-1} A P$. Reading this backwards, we declare two square matrices to encode « the same endomorphism up to a choice of basis » whenever they are related by such a formula. This gives the relation similarity, which we now study.

Definition — Similar matrices

Two square matrices $A, B \in M_n(\mathbb{K})$ are similar if there exists $P \in \mathrm{GL}_n(\mathbb{K})$ such that $$ B = P^{-1} \, A \, P. $$ We denote this $A \sim_{\mathrm{sim}} B$. Similarity is defined only between square matrices of the same size.

Proposition — Fundamental example of similarity

For $u \in \mathcal{L}(E)$ with $E$ finite-dimensional, the matrices $\mathrm{Mat}_{\mathcal{B}}(u)$ and $\mathrm{Mat}_{\mathcal{B}'}(u)$ in two bases of $E$ are similar.

Proof

Direct from the endomorphism corollary of Change of basis: $\mathrm{Mat}_{\mathcal{B}'}(u) = P^{-1} \mathrm{Mat}_{\mathcal{B}}(u) P$ where $P = P_{\mathcal{B}}^{\mathcal{B}'}$.

Theorem — Properties of similarity

The relation $\sim_{\mathrm{sim}}$ on $M_n(\mathbb{K})$ satisfies:

Equivalence relation: $\sim_{\mathrm{sim}}$ is reflexive, symmetric, transitive.
Rank invariance: two similar matrices have the same rank.

Proof

Equivalence relation.
- Reflexivity: $A = I_n^{-1} A I_n$, so $A \sim_{\mathrm{sim}} A$.
- Symmetry: if $B = P^{-1} A P$, then $A = P B P^{-1} = (P^{-1})^{-1} B (P^{-1})$, so $B \sim_{\mathrm{sim}} A$.
- Transitivity: if $B = P^{-1} A P$ and $C = R^{-1} B R$, then $C = (P R)^{-1} A (P R)$, so $A \sim_{\mathrm{sim}} C$.
Rank invariance. Let $B = P^{-1} A P$ with $P \in \mathrm{GL}_n(\mathbb{K})$. Multiplying a matrix on the left or on the right by an invertible matrix preserves its rank (chapter Matrix representation of linear maps, Proposition « Invertible multiplication preserves rank »). Applying this twice --- once for the left factor $P^{-1}$, once for the right factor $P$ --- gives $\mathrm{rg}(B) = \mathrm{rg}(A)$.

Example

Same rank, but not similar. Take $A = I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ and $B = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ (a shear). Both have rank 2, so the rank invariant does not separate them.
Suppose for contradiction $B = P^{-1} I_2 P$ for some $P \in \mathrm{GL}_2(\mathbb{R})$. Then $B = P^{-1} P = I_2$. But $B \ne I_2$: contradiction. So $A \not\sim_{\mathrm{sim}} B$, even though they share the same rank. This shows the rank alone does not classify similarity classes.

Example

Two matrices of the same rank that are similar (explicit $P$). Take $A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ (swap) and $B = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ (diagonal). Both have rank 2. Set $$ P = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad P^{-1} = \frac{1}{2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}. $$ Compute $P^{-1} A P = \frac{1}{2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 2 & 0 \\ 0 & -2 \end{pmatrix} = B$. So $A \sim_{\mathrm{sim}} B$.

Method — Show two square matrices are NOT similar

For $A, B \in M_n(\mathbb{K})$, exhibit any invariant that differs:

Rank: if $\mathrm{rg}(A) \ne \mathrm{rg}(B)$, not similar.
Preserved algebraic identities: if one of $A, B$ satisfies a polynomial identity that the other does not (idempotency $X^2 = X$, involution $X^2 = I_n$, nilpotency $X^k = 0$, etc.), then not similar. Reason: similarity preserves all such identities, since $P^{-1} X^k P = (P^{-1} X P)^k$ and $P^{-1} I_n P = I_n$.

This closes the linear-algebra block at this level. Similarity captures « the same endomorphism read in two bases »: the rank is a similarity invariant, useful for proving that two matrices are not similar, but it does not classify similarity classes --- two matrices may share the same rank without being similar. Refining similarity further --- finding, for a given matrix, a simple similar matrix --- is the subject of eigenvalue theory, taken up in a later course. The next chapter moves on to determinants.

Skills to practice

Similar matrices