Definition D1
An f satisfying f(ax + by) = af(x) + bf(y) for all vectors x, y and all scalars a, b is called a linear map.
Proof.
The only maps treated in this walk are linear maps.A1
∎
Definition D2
Let e₁, …, eₙ be a basis of V and e′₁, …, e′ₘ a basis of W, and for f : V → W set f(eⱼ) = A₁ⱼe′₁ + ⋯ + Aₘⱼe′ₘ. The table collecting these Aᵢⱼ is called the matrix of f.
Proof.
(1)f(eⱼ) is a vector of W, so it is written uniquely in coordinates with respect to the basis e′.A2
(2)Aᵢⱼ is the i-th coordinate of the image of the j-th basis vector. A matrix is the map written down in a basis.(1), convention
∎
Definition D3
For f : V → W and g : W → U, set (g∘f)(x) = g(f(x)).
Proof.
Composition applies g to the value of f.convention
∎
Lemma L1
If n ≥ 2 and x = x₁e₁ + ⋯ + xₙeₙ, then f(x) = x₁f(e₁) + ⋯ + xₙf(eₙ)
Proof.
(1)The coordinates x₁, …, xₙ of x are uniquely determined.A2
(2)For n = 2, f(x₁e₁ + x₂e₂) = x₁f(e₁) + x₂f(e₂)A1
(3)Suppose it holds for n, and set u = x₁e₁ + ⋯ + xₙeₙ.assumption
(4)x₁e₁ + ⋯ + xₙ₊₁eₙ₊₁ = 1·u + xₙ₊₁eₙ₊₁(3), A9
(5)f(1·u + xₙ₊₁eₙ₊₁) = 1·f(u) + xₙ₊₁f(eₙ₊₁) = f(u) + xₙ₊₁f(eₙ₊₁)(4), A1, A9
(6)f(u) = x₁f(e₁) + ⋯ + xₙf(eₙ)(3)
(7)Therefore it holds for n + 1 as well.(5), (6)
(8)By induction it holds for every n ≥ 2.(2), (7), N
∎
Theorem T1
If f and g are linear maps, then g∘f is also a linear map.
Proof.
(1)(g∘f)(ax + by) = g(f(ax + by))D3
(2)f(ax + by) = af(x) + bf(y)D1
(3)(g∘f)(ax + by) = g(af(x) + bf(y))(1), (2)
(4)g(af(x) + bf(y)) = a g(f(x)) + b g(f(y))D1
(5)g(f(x)) = (g∘f)(x), g(f(y)) = (g∘f)(y)D3
(6)(g∘f)(ax + by) = a(g∘f)(x) + b(g∘f)(y)(3), (4), (5)
(7)Therefore g∘f satisfies D1.(6), D1
∎
Theorem T2
Let A be the matrix of f and B the matrix of g. Then the (i, j) entry of the matrix of g∘f is Bᵢ₁A₁ⱼ + ⋯ + BᵢₘAₘⱼ.
Proof.
(1)g∘f is a linear map, so its matrix is determined.T1, D2
(2)(g∘f)(eⱼ) = g(f(eⱼ))D3
(3)f(eⱼ) = A₁ⱼe′₁ + ⋯ + Aₘⱼe′ₘD2
(4)g(f(eⱼ)) = A₁ⱼ g(e′₁) + ⋯ + Aₘⱼ g(e′ₘ)(3), L1
(5)g(e′ₖ) = B₁ₖe″₁ + ⋯ + Bₗₖe″ₗD2
(6)Aₖⱼ g(e′ₖ) = (AₖⱼB₁ₖ)e″₁ + ⋯ + (AₖⱼBₗₖ)e″ₗ(5), A3, A5, A7, N
(7)Sum over k from 1 to m and collect the terms with the same e″ᵢ.(4), (6), A6, A7
(8)The coefficient of e″ᵢ is A₁ⱼBᵢ₁ + ⋯ + AₘⱼBᵢₘ(7), A4, N
(9)AₖⱼBᵢₖ = BᵢₖAₖⱼA8
(10)The e″ᵢ coordinate of (g∘f)(eⱼ) is Bᵢ₁A₁ⱼ + ⋯ + BᵢₘAₘⱼ.(8), (9)
(11)Coordinates are unique, so that is the (i, j) entry of the matrix of g∘f.(10), A2, D2
(12)Writing the matrix of g∘f as BA, we have (BA)ᵢⱼ = Bᵢ₁A₁ⱼ + ⋯ + BᵢₘAₘⱼ. This formula is not a definition of the product but a consequence of composition.(11), convention
∎
Corollary C
Let A, B, C be the matrices of linear maps h, g, f respectively. Then (AB)C = A(BC)
Proof.
(1)((h∘g)∘f)(x) = h(g(f(x))) = (h∘(g∘f))(x)D3
(2)Therefore (h∘g)∘f and h∘(g∘f) are the same map.(1)
(3)Both maps are linear, so each has a matrix.T1, D2
(4)Applying T2 twice, the matrix of (h∘g)∘f is (AB)C and the matrix of h∘(g∘f) is A(BC).T2
(5)The same map has the same images of the basis vectors, and coordinates are unique, so the two matrices are equal.(2), (3), A2, D2
(6)(AB)C = A(BC)(4), (5)
∎