Matrices of linear maps and change of basis

Lesson 3 treated linear maps abstractly. To compute with them we need numbers, and numbers come from bases. Once you choose a basis for the domain and a basis for the codomain, every linear map becomes a matrix, every vector becomes a column, and applying the map becomes matrix multiplication. Choosing different bases gives a different matrix for the same map. This lesson builds the matrix of a linear map, shows how it changes when the bases change, and introduces similarity, the relation between two matrices that describe the same operator in different coordinates. The rest of the course, from diagonalization to the singular value decomposition, is a search for the basis in which a map's matrix is as simple as possible.

The matrix of a linear map

Let \(T : V \to W\) be linear, with ordered basis \(\mathcal{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)\) for \(V\) and \(\mathcal{C} = (\mathbf{c}_1, \dots, \mathbf{c}_m)\) for \(W\). Because \(T\) is determined by its values on a basis, record those values in coordinates. The matrix of \(T\) relative to \(\mathcal{B}\) and \(\mathcal{C}\) is the \(m \times n\) matrix whose \(j\)th column is the \(\mathcal{C}\)-coordinate vector of \(T(\mathbf{b}_j)\):

The defining property is that the matrix does in coordinates what \(T\) does to vectors:

Proof: write \(\mathbf{v} = x_1\mathbf{b}_1 + \dots + x_n\mathbf{b}_n\). Then \(T(\mathbf{v}) = x_1T(\mathbf{b}_1) + \dots + x_nT(\mathbf{b}_n)\), and taking coordinates (a linear operation) gives \(x_1\) times column 1 plus ... plus \(x_n\) times column \(n\), which is the matrix times the column \((x_1, \dots, x_n)\). The notation \(\mathcal{C} \gets \mathcal{B}\) reads right to left, like the multiplication: feed in \(\mathcal{B}\)-coordinates, get out \(\mathcal{C}\)-coordinates.

For an operator \(T : V \to V\) we usually use the same basis on both sides and write \([T]_{\mathcal{B}}\). When \(V = \mathbb{R}^n\) and \(\mathcal{B}\) is the standard basis, \([T]_{\mathcal{B}}\) is the standard matrix you met in MATH-125.

Observe that \([D]_{\mathcal{B}}\) is strictly upper triangular and \(D^4 = 0\): differentiating a cubic four times gives zero. Such operators are called nilpotent, and they reappear in lesson 8 as the building blocks of the Jordan form.

Composition is multiplication

If \(T : U \to V\) and \(S : V \to W\) with bases \(\mathcal{A}, \mathcal{B}, \mathcal{C}\), then

Proof: apply both sides to \([\mathbf{u}]_{\mathcal{A}}\) and use the defining property twice. The inner subscripts \(\mathcal{B}\) cancel, like a chain. This identity is the real reason matrix multiplication is defined row by column: it is the unique definition that makes composing maps correspond to multiplying matrices. Associativity of matrix multiplication follows for free from associativity of composition, with no index juggling.

Similarly, \([S + T] = [S] + [T]\) and \([cT] = c[T]\). Together these say that the map \(T \mapsto [T]_{\mathcal{C} \gets \mathcal{B}}\) is an isomorphism from \(L(V, W)\) to \(M_{m \times n}\), so \(\dim L(V, W) = \dim V \cdot \dim W\).

Change of basis for vectors

Suppose \(\mathcal{B}\) and \(\mathcal{B}'\) are two bases of the same space \(V\). The change-of-coordinates matrix from \(\mathcal{B}\) to \(\mathcal{B}'\) is the matrix of the identity map with \(\mathcal{B}\) on the input side and \(\mathcal{B}'\) on the output side:

Its columns are the old basis vectors written in the new basis. It is invertible, and its inverse goes the other way: \(P_{\mathcal{B} \gets \mathcal{B}'} = (P_{\mathcal{B}' \gets \mathcal{B}})^{-1}\). In \(\mathbb{R}^n\), if \(\mathcal{E}\) is the standard basis, then \(P_{\mathcal{E} \gets \mathcal{B}}\) is simply the matrix whose columns are the vectors of \(\mathcal{B}\), and \(P_{\mathcal{B} \gets \mathcal{E}}\) is its inverse. To go between two non-standard bases, route through the standard one: \(P_{\mathcal{B}' \gets \mathcal{B}} = P_{\mathcal{B}' \gets \mathcal{E}} P_{\mathcal{E} \gets \mathcal{B}}\).

A common confusion is direction. The matrix whose columns are the new basis vectors converts new coordinates into standard coordinates, not the other way round. When in doubt, test it on one basis vector: the first new basis vector has new coordinates \((1, 0, \dots, 0)\), and the matrix should turn that into its standard coordinates.

Change of basis for operators and similarity

Now let \(T : V \to V\) be an operator with matrices \(A = [T]_{\mathcal{B}}\) and \(A' = [T]_{\mathcal{B}'}\). To compute \(A'\) applied to new coordinates, convert to old coordinates, apply \(A\), then convert back:

Two square matrices \(A\) and \(A'\) are similar if \(A' = P^{-1}AP\) for some invertible \(P\). Similar matrices are the same linear operator seen in two coordinate systems. Anything that describes the operator rather than the coordinates must therefore be the same for similar matrices. Such quantities are called similarity invariants:

These invariants let you tell quickly when two matrices cannot be similar: different traces or determinants settle it. The converse is harder. Two matrices can share trace, determinant and characteristic polynomial without being similar; \(I\) and \(\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\) are the standard example. Lesson 8 shows that the Jordan form is a complete invariant: two matrices are similar exactly when they have the same Jordan form.

A worked change of basis

Take the operator on \(\mathbb{R}^2\) with standard matrix \(A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}\) and the basis \(\mathcal{B}' = (\mathbf{b}_1, \mathbf{b}_2)\) with \(\mathbf{b}_1 = (1, 1)\), \(\mathbf{b}_2 = (1, -1)\). Here \(P = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\), whose columns are the new basis vectors. The code computes \(P^{-1}AP\) exactly and also converts a vector's coordinates both ways.

from fractions import Fraction as F

def mul(X, Y):
    return [[sum(X[i][k] * Y[k][j] for k in range(len(Y))) for j in range(len(Y[0]))] for i in range(len(X))]

def inv2(M):
    (a, b), (c, d) = M
    det = F(a * d - b * c)
    return [[d / det, -b / det], [-c / det, a / det]]

A = [[2, 1], [1, 2]]
P = [[1, 1], [1, -1]]           # columns are b1 = (1, 1) and b2 = (1, -1)
Pinv = inv2(P)
Anew = mul(mul(Pinv, A), P)
print("matrix of T in the new basis:", [[str(x) for x in row] for row in Anew])

v_std = [[3], [1]]              # standard coordinates of v
v_new = mul(Pinv, v_std)
print("new coordinates of (3, 1):", [str(r[0]) for r in v_new])
back = mul(P, v_new)
print("converted back to standard:", [str(r[0]) for r in back])
print("trace and determinant unchanged:",
      A[0][0] + A[1][1], Anew[0][0] + Anew[1][1], "|",
      A[0][0] * A[1][1] - A[0][1] * A[1][0], Anew[0][0] * Anew[1][1] - Anew[0][1] * Anew[1][0])

matrix of T in the new basis: [['3', '0'], ['0', '1']]
new coordinates of (3, 1): ['2', '1']
converted back to standard: ['3', '1']
trace and determinant unchanged: 4 4 | 3 3

In the new basis the matrix is diagonal, with entries 3 and 1. That is no accident: \(\mathbf{b}_1\) and \(\mathbf{b}_2\) are eigenvectors of \(A\), with eigenvalues 3 and 1. In the eigenvector basis the operator simply stretches each axis. Lesson 6 develops this into diagonalization; the point here is that the right basis can turn a full matrix into a diagonal one without changing the operator at all.

Changing bases in both spaces

For a map \(T : V \to W\) between different spaces, we may change the basis on each side independently. If \(P\) changes coordinates in \(V\) and \(Q\) changes coordinates in \(W\), then the new matrix is \(Q^{-1}AP\). Because the two changes are independent, we have far more freedom than for operators, and the simplest possible form is very simple indeed.

Theorem (rank normal form). If \(T : V \to W\) has rank \(r\), there are bases of \(V\) and \(W\) in which the matrix of \(T\) has the \(r \times r\) identity in its top-left corner and zeros everywhere else. Proof sketch: choose a basis of \(V\) whose last \(n - r\) vectors span the kernel (as in the proof of rank–nullity); the images of the first \(r\) vectors are independent, so extend them to a basis of \(W\). In these bases, the first \(r\) basis vectors go to the first \(r\) basis vectors and the rest go to zero.

So, up to a choice of bases on both sides, the only thing a linear map has is its rank. For operators, where we must use one basis on both sides, the story is much richer, and that richness, captured by eigenvalues and the Jordan form, occupies lessons 6 to 8. The singular value decomposition of lesson 12 is a version of rank normal form in which both bases are required to be orthonormal; then the identity block becomes a diagonal block of singular values.

Polynomial spaces and other bases

Change of basis is not only about \(\mathbb{R}^n\). In \(P_2\), the standard basis is \((1, t, t^2)\), but for interpolation the Lagrange basis built on nodes \(0, 1, 2\) is often better: its vectors are the quadratics that equal 1 at one node and 0 at the others. The coordinates of a polynomial in the Lagrange basis are simply its values at the nodes. The change-of-basis matrix from Lagrange coordinates to standard coordinates has as columns the coefficients of the Lagrange polynomials, and its inverse is the Vandermonde matrix of the nodes. Numerical analysts choose among the standard, Lagrange, Newton, Chebyshev and Bernstein bases according to which makes their computation stable; computer graphics uses the Bernstein basis because its coordinates are the control points of a Bézier curve.