Skip to content

Maps that keep the laws

Level: 201 · for anyone who has met the definition of a linear map

One line: A linear map satisfies T(u + v) = Tu + Tv and T(av) = aTv; len(s + t) = len(s) + len(t), det(AB) = det(A) det(B) and 2^(a + b) = 2ᵃ · 2ᵇ have the same shape, one proof about that shape gives 2⁰ = 1, log 1 = 0, T(0) = 0 and det I = 1 all at once, and a map of this kind that can be undone shows two sets are one structure in two notations.

Laws between two sets

The first three lessons were about laws inside one set. Chapter 3 of Axler's Linear Algebra Done Right begins with a law between two sets. A linear map T from V to W has to satisfy:

additivity T(u + v) = Tu + Tv for all u, v ∈ V.

homogeneity T(λv) = λ(Tv) for all λ ∈ F and all v ∈ V.

Read additivity as a promise about order: adding and then mapping gives the same answer as mapping and then adding. The map carries the operations of V over to W without disturbing them. The program checks five maps against the two conditions, then finds the same shape in places that have nothing to do with vectors.

What the program prints

Verified output of maps_that_keep_the_laws.py — regenerated by tools/run_examples.py, never hand-typed.

1. WHAT A LINEAR MAP KEEPS
   additivity    T(u + v) = Tu + Tv     adding then mapping = mapping then adding
   homogeneity   T(av) = aTv            scaling then mapping = mapping then scaling

2. FIVE MAPS, TWO CHECKS
   multiply by i:  (x, y) -> (-y, x)    linear
   flatten:        (x, y) -> (x, 0)     linear
   log2: positive numbers -> R          linear
   x -> x + 1                           not linear
       additivity:   T(1 + 1) = 3,  but T(1) + T(1) = 4
       homogeneity:  T(-2 * 1) = -1,  but -2 * T(1) = -4
   x -> x * x                           not linear
       additivity:   T(1 + 1) = 4,  but T(1) + T(1) = 2
       homogeneity:  T(-2 * 1) = 4,  but -2 * T(1) = -2
   log2 is linear from lesson 2's positive numbers, where '+' is * and 'av'
   is v**a, to the ordinary numbers:
     log2(8 * 1/4) = 1 = log2 8 + log2 1/4 = 3 + (-2)
     log2(8**3) = 9 = 3 log2 8 = 3 * 3

3. THE SAME SHAPE, WITH OTHER OPERATIONS
   the law                        from                 to                on every sample pair
   len(s + t) = len(s) + len(t)   strings, +        -> whole numbers, +  holds
   2**(a + b) = 2**a * 2**b       integers, +       -> fractions, *      holds
   det(AB) = det(A) det(B)        2x2 matrices, *   -> numbers, *        holds
   |zw|^2 = |z|^2 |w|^2           complex pairs, *  -> numbers, *        holds
   M(zw) = M(z) M(w)              complex pairs, *  -> 2x2 matrices, *   holds
   |z + w|^2 = |z|^2 + |w|^2      complex pairs, +  -> numbers, +        FAILS
       at (1, 2) and (1, 2):  20 on the left, 10 on the right
   M sends (x, y) to [[x, -y], [y, x]]. Squared length keeps multiplication
   but not addition: a map keeps a particular operation, not every one.

4. A MAP THAT CAN BE UNDONE: ONE STRUCTURE, TWO NOTATIONS
   log2 and 2**n undo each other:
     log2 2 = 1,   2**1 = 2
     log2 8 = 3,   2**3 = 8
     log2 1/4 = -2,   2**-2 = 1/4
   Multiply in one world, or add in the other:
     8 * 1/4 = 2
     log2: 3 + (-2) = 1,  and 2**1 = 2
   The positive numbers under * are the numbers under + with every member
   renamed. That is why they passed lesson 2's test: they are R in disguise.

5. PRODUCTS OF LINEAR MAPS: WHICH LAWS, AND WHY
   Here ST means S after T, and S + T means v -> Sv + Tv.
   S, T, U are turn, flatten and shear, checked on the sample vectors:
     associative   (ST)U = S(TU)        True   any functions: both sides send v to S(T(U(v)))
     identity      TI = IT = T          True   any functions
     distributive  (S + T)U = SU + TU   True   any functions: both sides are S(U(v)) + T(U(v))
     distributive  S(T + U) = ST + SU   True   needs S to be additive
     commutative   ST = TS              False
   With S = (x, y) -> (x + 1, y), which is not additive, the second distributive
   law fails: at v = (1, 2), S(T + U) gives (5, 2) and ST + SU gives (6, 2).
   And order matters: turn after flatten sends (1, 2) to (0, 1),
   flatten after turn sends it to (-2, 0).
   Associative with an identity is lesson 1's monoid; with + and distributivity
   it is a ring: the linear maps from a space to itself are one, and not a
   commutative one.

Five maps

Section 2 has three maps that pass and two that fail:

  • Multiply by i, (x, y) ↦ (−y, x), is linear. It is the quarter turn from multiplication rotates.
  • Flatten, (x, y) ↦ (x, 0), is linear too, even though it throws the second coordinate away. Linear does not mean invertible.
  • log₂ is linear, from lesson 2's positive numbers (where "u + v" is u·v and "a times v" is vᵃ) to the ordinary numbers. Its two conditions are the laws of logarithms: log(uv) = log u + log v is additivity, and log(vᵃ) = a log v is homogeneity. The logarithm laws say exactly that the logarithm is a linear map.
  • x ↦ x + 1 is not linear, although its graph is a straight line. In linear algebra, a linear map always sends 0 to 0, because T(0) = T(0 + 0) = T(0) + T(0), and subtracting T(0) from both sides leaves T(0) = 0. This map sends 0 to 1. A straight line that misses the origin has its own name, affine.
  • x ↦ x² fails both conditions, as the witnesses show.

The same shape everywhere

Section 3 finds the same equation, f(a · b) = f(a) ∗ f(b), with other operations on each side. A map of this shape is a homomorphism, from Greek for "same shape", and a linear map is the vector-space kind.

  • len, from strings under concatenation to whole numbers under +. It also explains lesson 1's finding that strings have no inverses. If s + t is the empty string, then len(s) + len(t) = 0, so both were empty to begin with.
  • n ↦ 2ⁿ, from integers under + to fractions under ×. The exponent law 2^(a + b) = 2ᵃ · 2ᵇ is the statement that this map is a homomorphism.
  • det, from 2 × 2 matrices under × to numbers under ×.
  • Squared length, from complex numbers under × to numbers under ×: |zw|² = |z|²|w|². This is the "multiply the lengths" half of multiplication rotates. Written out in coordinates, it is the sums-of-two-squares identity in multiplication as pairs.
  • M, (x, y) ↦ [[x, −y], [y, x]], from complex numbers to 2 × 2 matrices. It keeps both multiplication and addition.

The last row fails, and that is the point of it. Squared length keeps multiplication but not addition: |z + w|² is not |z|² + |w|². A homomorphism always keeps some particular operation, and a map can keep one operation and not another.

One proof, four books

Here is a theorem about every homomorphism between groups. Write e for the identity. Then f(e) = f(e · e) = f(e) ∗ f(e), and cancelling one f(e) leaves f(e) is the identity. Apply the same move to a · a⁻¹ = e, and it gives f(a⁻¹) = f(a)⁻¹. That is one proof, a line long, and here is what it says in four different courses:

Homomorphism From → to Identity goes to identity Inverse goes to inverse
n ↦ 2ⁿ integers, + → nonzero fractions, × 2⁰ = 1 2⁻ⁿ = 1/2ⁿ
log positive numbers, × → numbers, + log 1 = 0 log(1/v) = −log v
linear map T V, + → W, + T(0) = 0 T(−v) = −Tv
det invertible matrices, × → nonzero numbers, × det I = 1 det(A⁻¹) = 1/det A

A school book states 2⁰ = 1, a precalculus book proves log 1 = 0, a linear-algebra book proves T(0) = 0, and a later chapter proves det I = 1. Each is the same line with different names. This is the most direct answer to the question the chapter opened with. The repetition is real, and it goes away as soon as the shared shape has a name.

A map that can be undone

Section 4 runs log₂ and n ↦ 2ⁿ back to back, and each undoes the other. A homomorphism with an inverse is an isomorphism, and it says two structures are the same one with the members renamed. Multiplying 8 by 1/4 among the positive numbers is the same calculation as adding 3 and −2 among the ordinary numbers, translated there and back.

That is why lesson 2's strange space passed the vector-space test: it is ℝ in disguise. It is also how a slide rule works. Its scales are marked at distances proportional to logarithms, so sliding one against the other adds lengths and reads off a product. A slide rule is an isomorphism made of wood.

Isomorphism is the second way mathematics avoids repeating itself. A theorem proved in one notation holds in every isomorphic one. Axler proves that two finite-dimensional vector spaces over the same field are isomorphic exactly when they have the same dimension. So in a sense there is only one vector space of each dimension, however many ways books find to write it. The same goes for the complex numbers. M is an isomorphism from the pairs of 03_Complex_Numbers onto the matrices [[x, −y], [y, x]]. The textbook that builds ℂ from pairs and the one that builds it from matrices built the same thing, and neither is the real one.

Products of linear maps

Axler goes on to list the algebraic properties of products of linear maps, where ST means "S after T": associativity, identity, and two distributive properties. Section 5 checks them on a quarter turn, a flattening and a shear, and sorts them by where they come from:

  • Associativity and identity are true for any functions at all. (ST)U and S(TU) both send v to S(T(U(v))), so there is nothing linear about the reason. Matrix multiplication is associative because a matrix is a linear map and matrix multiplication is composition. A book that proves associativity for matrices by expanding the triple sum is doing work that composition already did.
  • (S + T)U = SU + TU is also true for any functions. Both sides are S(U(v)) + T(U(v)).
  • S(T + U) = ST + SU needs S to be additive. With S = (x, y) ↦ (x + 1, y) the program finds it failing.
  • Commutativity is missing. Turning after flattening is not flattening after turning.

With addition, those are the laws of a ring, so the linear maps from a space to itself form a ring, and not a commutative one. That is the 2 × 2 matrix row of lesson 1, seen from the other side.

The general topic: categories

Look at the first two laws of section 5 again: composition is associative, and there are identity maps. Those two laws, and nothing else, are the definition of a category: a collection of objects, arrows between them, and a way to compose arrows that is associative and has identities. Samuel Eilenberg and Saunders Mac Lane gave the definition in 1945.

Sets with functions form a category. So do groups with homomorphisms, vector spaces with linear maps, and ordered sets with order-preserving maps. A theorem proved about categories holds in all of them, and category theory is the subject that studies the pattern this chapter keeps finding: structures, and the maps that keep them.

Run it yourself

From the root of your clone of this repository:

python3 06_Algebraic_Structures/maps_that_keep_the_laws/examples/maps_that_keep_the_laws.py

Po polsku, w skrócie

Odwzorowanie liniowe spełnia T(u + v) = Tu + Tv i T(av) = aTv: najpierw dodać, a potem odwzorować, daje to samo co odwrotnie. Ten sam kształt mają prawa logarytmów, prawo potęg 2^(a + b) = 2ᵃ · 2ᵇ, długość sklejonych napisów i wyznacznik iloczynu macierzy. Odwzorowanie tego rodzaju nazywa się homomorfizmem, a jeden krótki dowód o tym kształcie daje naraz 2⁰ = 1, log 1 = 0, T(0) = 0 i det I = 1. Pułapka: x ↦ x + 1 ma za wykres prostą, a liniowe nie jest, bo nie przenosi 0 na 0.

Homomorfizm, który da się odwrócić, to izomorfizm: logarytm i potęga zamieniają mnożenie w dodawanie i z powrotem, i na tym działa suwak logarytmiczny. Funkcja wykładnicza wraca w rozdziale o analizie jako ruch, którego prędkość równa się położeniu, i tam to samo prawo potęg wynika z samego ruchu.

Auf Deutsch: Stichwörter

Lineare Abbildungen, Logarithmen und Determinanten haben eine Gestalt: Abbildungen, die die Verknüpfung bewahren, f(a ∘ b) = f(a) ∗ f(b).

Stichwörter: Homomorphismus, strukturerhaltende Abbildung, lineare Abbildung, Logarithmus (Multiplikation wird Addition), Determinante, Isomorphismus, Rechenschieber.

See also