Engineering / Mathematics — Modules, Vector Spaces and Matrices
Matrices and Linear Maps
The correspondence between matrices and linear maps, change of basis, and why the correspondence depends on a choice.
Executive summary
Choosing bases for the source and target turns a linear map into a matrix, and composition into matrix multiplication. The correspondence is an isomorphism of algebraic structures.
It depends on the chosen bases, and changing them conjugates the matrix — which is why invariants such as rank and determinant matter more than the entries.
Learning objectives
- Construct the matrix of a linear map relative to bases.
- Apply the change of basis formula.
- Distinguish basis-dependent from basis-independent quantities.
01The correspondence
Fix a basis e₁, ..., eₖ of V and f₁, ..., fₘ of W. The matrix of a linear map T: V → W has as its j-th column the coordinates of T(eⱼ) in the basis of W.
Structure preservation
The correspondence is an isomorphism of vector spaces from Hom(V, W) to m × n matrices, and it carries composition of maps to matrix multiplication.
This is why matrix multiplication is defined as it is. The formula is not an arbitrary convention but the unique definition making the correspondence respect composition.
02Change of basis
Change of basis
If P and Q are the change of basis matrices for the source and target, the matrix A of a map becomes Q⁻¹AP.
For an endomorphism with a single basis, this is conjugation: A ↦ P⁻¹AP.
| Quantity | Basis dependent? |
|---|---|
| Individual entries | Yes |
| Rank | No |
| Determinant | No, for endomorphisms |
| Trace | No, for endomorphisms |
| Characteristic polynomial | No, for endomorphisms |
| Minimal polynomial | No, for endomorphisms |
The invariant quantities are the ones carrying real information about the map. Everything basis-dependent is an artefact of a choice, which is why theory is stated in terms of invariants and computation in terms of matrices.
03Choosing a good basis
Much of computational linear algebra is the search for a basis making the matrix simple.
- Row echelon form
Gaussian eliminationReveals rank, kernel and image - Diagonal form
Eigenbasis, when one existsPowers and exponentials become trivial - Triangular form
Always available over an algebraically closed fieldEigenvalues on the diagonal - Rational canonical form
Available over any fieldInvariant factors; no field extension needed
For finite fields the rational canonical form is the relevant one, since it requires no extension of the base field. Its invariant factors are computed from the minimal polynomials of the module structure, which is where the linearly generated sequence machinery connects.
04Frequently asked questions
Why does the matrix depend on the basis at all?
Because a matrix is a coordinate representation, and coordinates require a reference frame. The map itself is basis-free; the matrix is what one writes down after choosing how to name the elements.
Is the correspondence valid for modules over a ring?
For free modules with chosen bases, yes. It fails for modules without bases, which is why matrix methods do not extend directly to general modules.
What makes the characteristic polynomial invariant?
It is defined by a determinant, and determinants are unchanged by conjugation since det(P⁻¹AP) = det(A). The same argument covers the trace and determinant individually.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 320-323.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.