Maps Between Spaces

Jim Hefferon · GFDL + CC BY-SA 2.5 · Linear Algebra

A linear map (homomorphism) preserves addition and scalar multiplication. Every linear map from R^n to R^m is multiplication by an m-by-n matrix. The rank-nullity theorem says: dimension of domain = dimension of image + dimension of kernel. Always.

Linear maps

A function h: V to W is linear if h(v + w) = h(v) + h(w) and h(c*v) = c*h(v) for all vectors v, w and scalars c. Linearity means the map respects the vector space structure. It never bends straight lines or shifts the origin.

Scheme

; A linear map from R^2 to R^2: rotation by 90 degrees.
; h((x,y)) = (-y, x)

(define (h v)
  (list (- (cadr v)) (car v)))

; Check linearity:
; h(v + w) should equal h(v) + h(w)
(define (vec-add a b) (map + a b))
(define (scalar-mult c v) (map (lambda (x) (* c x)) v))

(define v '(3 1))
(define w '(2 4))

(display "h(v+w) = ")
(display (h (vec-add v w)))
(newline)

(display "h(v)+h(w) = ")
(display (vec-add (h v) (h w)))
(newline)

; h(c*v) should equal c*h(v)
(display "h(3*v) = ")
(display (h (scalar-mult 3 v)))
(newline)

(display "3*h(v) = ")
(display (scalar-mult 3 (h v)))

Matrix representation

Every linear map h: R^n to R^m can be represented as multiplication by an m-by-n matrix A. The j-th column of A is h(ej), the image of the j-th standard basis vector. Conversely, every m-by-n matrix defines a linear map. Maps and matrices are two views of the same thing.

Scheme

; Matrix-vector multiplication: A * v.
; A is a list of rows; v is a column vector.

(define (dot u v) (apply + (map * u v)))

(define (mat-vec-mult A v)
  (map (lambda (row) (dot row v)) A))

; The rotation map h((x,y)) = (-y, x) has matrix:
;   A = ((0 -1)
;        (1  0))
(define A '((0 -1)
            (1  0)))

(define v '(3 1))
(display "A * (3,1) = ")
(display (mat-vec-mult A v))
(newline)
; Should be (-1, 3) — same as rotating (3,1) by 90 degrees.

; Matrix of a scaling map: h((x,y)) = (2x, 3y)
(define B '((2 0)
            (0 3)))
(display "B * (4,5) = ")
(display (mat-vec-mult B '(4 5)))

Kernel and image

The kernel (null space) of a linear map h is the set of all vectors that map to zero: ker(h) = all v where h(v) = 0. The image (range) is the set of all outputs: im(h) = all h(v). Both are subspaces.

Scheme

; Projection onto the x-axis: h((x,y)) = (x, 0)
; Kernel: all (0, y) — the y-axis
; Image: all (x, 0) — the x-axis

(define (proj v)
  (list (car v) 0))

(display "h((3,7)) = ") (display (proj '(3 7))) (newline)
(display "h((0,5)) = ") (display (proj '(0 5))) (newline)
(display "h((0,0)) = ") (display (proj '(0 0))) (newline)

; (0,5) is in the kernel: it maps to (0,0)
(display "Kernel: the y-axis (all (0,y))")
(newline)
(display "Image: the x-axis (all (x,0))")
(newline)

; dim(kernel) = 1, dim(image) = 1
; dim(domain) = 2 = 1 + 1. That's rank-nullity.
(display "dim(ker) + dim(im) = 1 + 1 = 2 = dim(R^2)")

Rank-nullity theorem

For any linear map h: V to W, dim(V) = dim(ker h) + dim(im h). The dimension of the kernel is the nullity, and the dimension of the image is the rank. Rank-nullity is a conservation law: dimensions in minus dimensions lost equals dimensions out.

Scheme

; Example: h: R^3 -> R^2 defined by h(x,y,z) = (x+y, y+z).
; Matrix: ((1 1 0) (0 1 1))

(define (dot u v) (apply + (map * u v)))
(define (mat-vec-mult A v)
  (map (lambda (row) (dot row v)) A))

(define A '((1 1 0)
            (0 1 1)))

; Find kernel: solve Av = 0
; Row reduce: already in echelon form.
; z is free. y = -z, x = -y = z.
; Kernel = span of (1, -1, 1).
(display "Kernel basis: (1, -1, 1)")
(newline)

; Verify: A * (1,-1,1) = ?
(display "A * (1,-1,1) = ")
(display (mat-vec-mult A '(1 -1 1)))
(newline)

; Image = column space of A = span of (1,0) and (1,1).
; These are independent, so dim(image) = 2.
(display "Image basis: (1,0) and (1,1)")
(newline)

; Rank-nullity: 3 = 1 + 2
(display "dim(R^3) = dim(ker) + dim(im) = 1 + 2 = 3")

Notation reference

Symbol	Scheme	Python	Meaning
h: V to W	(define (h v) ...)	def h(v): ...	Linear map
A * v	(mat-vec-mult A v)	A @ v	Matrix-vector product
ker(h)	solve A*v = 0	null space	Vectors mapping to zero
im(h)	column space of A	column space	All possible outputs
rank + nullity = n	dim(im) + dim(ker)	rank + nullity	Rank-nullity theorem

Neighbors

Adjacent chapters

Ch.2 Vector Spaces — the spaces these maps act on
Ch.4 Determinants — a scalar invariant of square maps
🐱 Category Theory Ch.7 — functors are structure-preserving maps, just as linear maps preserve vector space structure
🔗 Abstract Algebra Ch.3 — homomorphisms are the same idea for groups
🤖 ML Ch.3 — neural network layers are linear maps followed by nonlinearities

Cross-references

Milewski Ch.1 — linear maps are arrows in the category of vector spaces
🍞 Milewski Ch.7 Functors — linear maps between vector spaces are functors preserving the additive structure
∫ Calculus Ch.11 Partial Derivatives — the derivative of a multivariable function is a linear map (the Jacobian)

Foundations (Wikipedia)

Translation notes

Hefferon builds up to the rank-nullity theorem through homomorphisms, isomorphisms, and the first isomorphism theorem (V/ker h is isomorphic to im h). This page focuses on the computational core. The chapter also covers composition of maps (matrix multiplication) and invertibility.

Full chapter: Hefferon, Chapter Three — Maps Between Spaces.

← Vector Spaces by june.kim Determinants →