← MA0 2 · Introduction to Algorithms and Numerical Analysis

Lesson 1

Vectors and Groups

Taught 24 Aug 2026

Vectors

Algebra deals with variables and equations, geometry with points, lines, planes and solids, and the two are tied together closely enough that a statement about one is usually a statement about the other. Take the equation $y = ax + b$ . On its own it is an algebraic object, a relation between two unknowns; but the collection of points whose coordinates satisfy it traces out a straight line, and the two constants appearing in it read off two features of that line. The number $a$ is the slope, the change in $y$ against the change in $x$ , and $b$ is the height at which the line meets the vertical axis.

Figure 1.1. The line

y = ax + b

, meeting the vertical axis at height

b

and rising by

a

over every unit travelled to the right.

So the constants in the equation of a line, which are algebraic data, correspond to the slope and the intercept, which are geometric data. What makes the correspondence possible is a dictionary between the points of the plane and pairs of numbers, and the pair is an object MA01 has already built.

Coordinates

An ordered pair $(a, b)$ is a pair in which one element is marked as coming first, so that

(a, b) = (a', b') \quad \text{if and only if} \quad a = a' \text{ and } b = b'.

Given two sets $A$ and $B$ , the Cartesian product $A \times B$ is the set of all ordered pairs whose first entry comes from $A$ and whose second comes from $B$ ,

A \times B = \{(a, b) \mid a \in A, \; b \in B\},

and when $A = B$ we write $A^2$ for it. More generally, for $n \in \mathbb{N}$ the $n$ -fold product of sets $A_1, \ldots, A_n$ consists of the $n$ -tuples with one entry drawn from each,

A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \ldots, a_n) \mid a_1 \in A_1, \; a_2 \in A_2, \; \ldots, \; a_n \in A_n\},

written $A^n$ as a Cartesian power when all the factors agree. Throughout this course $\mathbb{N} = \{1, 2, 3, \ldots\}$ .

The example we care about is $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$ , whose elements are the pairs of real numbers. Fixing an origin and two perpendicular axes in the plane identifies each point with exactly one such pair.

Remark (Descartes).

The identification of the points of the plane with $\mathbb{R}^2$ is due to René Descartes, and the product carries his name because of it. The geometry uses the whole of the ordered pair: $(a, b)$ and $(b, a)$ are different points unless $a = b$ , which is exactly the property that a two-element set could not supply. Given a point $P$ of the plane matched with the pair $(a, b)$ , we call $a$ the $x$ -coordinate and $b$ the $y$ -coordinate of $P$ .

Once points are pairs, two different kinds of quantity are in play. A scalar is a quantity settled by a single number, and for us that number will be real. Temperature, mass and altitude are scalars. Force and velocity are not: a force has a direction as well as a size, and both are needed to name it.

Remark (Magnitude and direction).

A vector is often introduced as a quantity carrying both a magnitude and a direction. That description says what vectors are for, but neither magnitude nor direction has been given a meaning yet, so it cannot be calculated with.

Take a pair $(a, b) \in \mathbb{R}^2$ and the origin $O = (0, 0)$ . Instead of drawing the single point $P = (a, b)$ we may draw the arrow that runs from $O$ to $P$ , reached by travelling $a$ units along the horizontal axis and $b$ units along the vertical one. The arrow carries the same information as the point, so nothing is lost.

Figure 1.2. The point

P = (a, b)

and the arrow from the origin that represents it.

Because the arrow and the point determine one another, we treat them as the same object and use the words interchangeably.

Definition 1.1 (Vector).

Let $n \in \mathbb{N}$ . An $n$ -dimensional vector, or $n$ -vector, is an element $\mathbf{x}$ of $\mathbb{R}^n$ . It may be written as a column vector

\mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}

or as a row vector $\mathbf{x} = (x_1, x_2, \ldots, x_n)$ . For $1 \leqslant i \leqslant n$ the real number $x_i$ is the $i$ th component of $\mathbf{x}$ . The set $\mathbb{R}^n$ of all such vectors is called $n$ -dimensional space.

Since points and vectors are the same objects here, the words component and coordinate are used interchangeably as well. For $n = 2$ we usually name the components $x$ and $y$ , so that

\mathbb{R}^2 = \{(x, y) \mid x, y \in \mathbb{R}\}

is the $xy$ -plane; for $n = 3$ we name them $x$ , $y$ and $z$ , and call $\mathbb{R}^3$ the $xyz$ -space.

Remark (Notation for vectors).

We write vectors in bold, $\mathbf{u}$ and $\mathbf{v}$ , and write $\overrightarrow{OA}$ for the vector running from $O$ to $A$ . Other texts write $\vec{u}$ or $\underline{u}$ for the same thing, and a vector of length one often gets a hat, as in $\hat{x}$ or $\hat{e}_1$ . The multiplicity of conventions does not matter; what matters is that a scalar and a vector are never written the same way, since almost every claim below depends on knowing which of the two a symbol names.

Example 1.2 (Vectors in $\mathbb{R}^2$ and $\mathbb{R}^3$ ).

\begin{pmatrix} 2 \\ 3 \end{pmatrix} \in \mathbb{R}^2, \qquad \begin{pmatrix} 7 \\ -10 \\ 1 \end{pmatrix} \in \mathbb{R}^3, \qquad \begin{pmatrix} 2.5 \\ 3/10 \\ 4.001 \end{pmatrix} \in \mathbb{R}^3.

Remark (Rows against columns).

A row vector and a column vector with the same entries are the same element of $\mathbb{R}^n$ , and for everything in this chapter the shape is only a matter of how the thing is printed. It stops being a matter of printing as soon as vectors are multiplied by matrices, since the rules for that multiplication treat a row of $n$ entries and a column of $n$ entries as objects of different shapes, and the two cannot then be swapped. We will keep to columns whenever the shape could matter.

Definition 1.3 (Zero vector).

The zero vector of $\mathbb{R}^n$ is the vector all of whose components are $0$ ,

\mathbf{0} = (0, 0, \ldots, 0),

also called the null vector. It is the vector $\overrightarrow{OO}$ representing the origin.

The vectors of the form $(0, \ldots, 0, x_i, 0, \ldots, 0)$ , with every component but the $i$ th equal to zero, are exactly the points of the $x_i$ -axis, so the $n$ axes meeting at $\mathbf{0}$ are already visible in the notation.

Vector Algebra

Definition 1.4 (Addition and subtraction).

Let $\mathbf{u} = (u_1, u_2, \ldots, u_n)$ and $\mathbf{v} = (v_1, v_2, \ldots, v_n)$ be vectors in $\mathbb{R}^n$ . Their sum and difference are formed component by component:

\begin{aligned} \mathbf{u} + \mathbf{v} &= (u_1 + v_1, \; u_2 + v_2, \; \ldots, \; u_n + v_n), \\ \mathbf{u} - \mathbf{v} &= (u_1 - v_1, \; u_2 - v_2, \; \ldots, \; u_n - v_n). \end{aligned}

Two vectors can be added only when they have the same number of components, since otherwise some component of the answer has nothing to be built from. A vector in $\mathbb{R}^3$ and a vector in $\mathbb{R}^2$ have no sum.

Example 1.5 (A sum in $\mathbb{R}^3$ ).

\begin{pmatrix} 3 \\ 6 \\ 5 \end{pmatrix} + \begin{pmatrix} 7 \\ 8 \\ 1 \end{pmatrix} = \begin{pmatrix} 10 \\ 14 \\ 6 \end{pmatrix}.

Read as arrows, $\mathbf{u} + \mathbf{v}$ is what we reach by travelling along $\mathbf{u}$ and then travelling along $\mathbf{v}$ from wherever that leaves us. Travelling along $\mathbf{v}$ first and $\mathbf{u}$ second lands in the same place, which is the picture behind $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ : the two routes are the two ways round a parallelogram.

Figure 1.3. The sum of two vectors is the diagonal of the parallelogram they span; the difference

\mathbf{v} - \mathbf{u}

is the arrow carrying the tip of

\mathbf{u}

to the tip of

\mathbf{v}

The right-hand panel records the other useful reading of the definition. The vector $\mathbf{v} - \mathbf{u}$ is the one that translates the point with position vector $\mathbf{u}$ to the point with position vector $\mathbf{v}$ , since adding it to $\mathbf{u}$ returns $\mathbf{v}$ . For two points $P$ and $Q$ this is written

\overrightarrow{PQ} = \overrightarrow{OQ} - \overrightarrow{OP}.

Definition 1.6 (Scalar multiplication).

Let $\mathbf{u} = (u_1, u_2, \ldots, u_n) \in \mathbb{R}^n$ and let $\lambda \in \mathbb{R}$ . The scalar multiple $\lambda\mathbf{u}$ is

\lambda\mathbf{u} = (\lambda u_1, \; \lambda u_2, \; \ldots, \; \lambda u_n).

We write $-\mathbf{u}$ for $(-1)\mathbf{u} = (-u_1, -u_2, \ldots, -u_n)$ .

When $\lambda$ is a positive integer, $\lambda\mathbf{u}$ is the translation obtained by translating $\lambda$ times by $\mathbf{u}$ . Letting $\lambda$ range over all of $\mathbb{R}$ , the points $\lambda\mathbf{u}$ trace out the straight line through the origin and the point $\mathbf{u}$ . Translating by $-\mathbf{u}$ undoes a translation by $\mathbf{u}$ .

Figure 1.4. The scalar multiples of a vector

\mathbf{u} \neq \mathbf{0}

fill the line through the origin and

\mathbf{u}

Example 1.7 (A scalar multiple).

4 \cdot \begin{pmatrix} 2 \\ 7 \\ 9 \end{pmatrix} = \begin{pmatrix} 8 \\ 28 \\ 36 \end{pmatrix}.

The product $\lambda \cdot \mathbf{u}$ is written $\lambda\mathbf{u}$ from here on, the dot being dropped as it is for the product of two reals.

With both operations available we can build one vector out of several others.

Definition 1.8 (Linear combination).

Let $\mathbf{v}_1, \ldots, \mathbf{v}_k \in \mathbb{R}^n$ and $\lambda_1, \ldots, \lambda_k \in \mathbb{R}$ . The vector

\lambda_1\mathbf{v}_1 + \lambda_2\mathbf{v}_2 + \cdots + \lambda_k\mathbf{v}_k

is a linear combination of $\mathbf{v}_1, \ldots, \mathbf{v}_k$ with coefficients $\lambda_1, \ldots, \lambda_k$ . A sum of this shape is abbreviated

\sum_{i=1}^{k} \lambda_i \mathbf{v}_i ,

the symbol $\textstyle\sum$ instructing us to add the terms obtained as the index $i$ runs through the integers from the value below the symbol to the value above it.

Definition 1.9 (Standard basis).

Let $n \in \mathbb{N}$ . For $1 \leqslant i \leqslant n$ let $\hat{e}_i \in \mathbb{R}^n$ be the vector whose $i$ th component is $1$ and whose other components are $0$ , so that

\hat{e}_1 = (1, 0, \ldots, 0, 0), \quad \hat{e}_2 = (0, 1, \ldots, 0, 0), \quad \ldots, \quad \hat{e}_n = (0, 0, \ldots, 0, 1).

These $n$ vectors form the standard basis, or canonical basis, of $\mathbb{R}^n$ .

Proposition 1.10 (Expansion in the standard basis).

Let $n \in \mathbb{N}$ and let $\mathbf{x} \in \mathbb{R}^n$ . There is exactly one $n$ -tuple $(\lambda_1, \ldots, \lambda_n)$ of real numbers with

\mathbf{x} = \sum_{i=1}^{n} \lambda_i \hat{e}_i,

namely the tuple of components of $\mathbf{x}$ itself.

Discussion.

The statement is an existence and uniqueness claim about the tuple of coefficients, so the proof has two halves. Both are settled by looking at one component at a time, because addition and scalar multiplication were defined component by component: the $j$ th component of $\sum_i \lambda_i \hat{e}_i$ is $\sum_i \lambda_i (\hat{e}_i)_j$ , and by the definition of the standard basis every term of that sum vanishes except the one with $i = j$ . So the $j$ th component of the combination is $\lambda_j$ , whatever the coefficients were. Existence then follows by taking $\lambda_j = x_j$ , and uniqueness follows because any tuple that works must have $\lambda_j$ equal to the $j$ th component of $\mathbf{x}$ , which leaves no freedom.

Proof.

Let $\lambda_1, \ldots, \lambda_n$ be any real numbers and fix $j$ with $1 \leqslant j \leqslant n$ . By the definition of scalar multiplication the $j$ th component of $\lambda_i \hat{e}_i$ is $\lambda_i (\hat{e}_i)_j$ , which is $\lambda_i$ when $i = j$ and $0$ otherwise; and by the definition of addition the $j$ th component of a sum is the sum of the $j$ th components. Hence

\Bigl( \sum_{i=1}^{n} \lambda_i \hat{e}_i \Bigr)_j = \sum_{i=1}^{n} \lambda_i (\hat{e}_i)_j = \lambda_j.

Now write $\mathbf{x} = (x_1, \ldots, x_n)$ . Taking $\lambda_i = x_i$ for each $i$ , the displayed identity says that $\sum_i x_i \hat{e}_i$ has $j$ th component $x_j$ for every $j$ , so it equals $\mathbf{x}$ ; this proves existence. If $(\lambda_1, \ldots, \lambda_n)$ is any tuple with $\mathbf{x} = \sum_i \lambda_i \hat{e}_i$ , then comparing $j$ th components in that equation and using the identity again gives $x_j = \lambda_j$ for every $j$ ; this proves uniqueness.

Remark (The basis in two and three dimensions).

For $n = 2$ the standard basis is $(1, 0)$ and $(0, 1)$ , commonly written $\hat{i}$ and $\hat{j}$ , and the proposition says that every $\mathbf{u} = (x, y)$ is $x\hat{i} + y\hat{j}$ and is so in only one way. For $n = 3$ the basis is written $\hat{i}$ , $\hat{j}$ , $\hat{k}$ .

Definition 1.11 (Norm of a vector).

Let $\mathbf{u} = (u_1, u_2, \ldots, u_n) \in \mathbb{R}^n$ . The norm, or magnitude, or length, of $\mathbf{u}$ is the real number

\lVert \mathbf{u} \rVert = \sqrt{u_1^2 + u_2^2 + \cdots + u_n^2} = \sqrt{\sum_{i=1}^{n} u_i^2}.

This is also called the Euclidean norm. A vector with $\lVert \mathbf{u} \rVert = 1$ is a unit vector.

Remark (Bars and double bars).

Many texts write $|\mathbf{u}|$ for the norm. We keep the single bars for the absolute value of a real number, which appears in the last chapter of this lesson and again throughout the course, and reserve the double bars for vectors. Nothing but legibility turns on the choice, but a formula such as $\lVert \lambda \mathbf{u} \rVert = |\lambda| \, \lVert \mathbf{u} \rVert$ is a good deal easier to read when the two are told apart.

Example 1.12 (A norm in $\mathbb{R}^3$ ).

Let $A = (3, 4, 0)$ and let $\mathbf{a} = \overrightarrow{OA}$ . Then

\lVert \mathbf{a} \rVert = \sqrt{3^2 + 4^2 + 0^2} = \sqrt{25} = 5.

Proposition 1.13 (Properties of the norm).

Let $\mathbf{x} \in \mathbb{R}^n$ and $\lambda \in \mathbb{R}$ . Then

$\lVert \mathbf{x} \rVert \geqslant 0$ ;
$\lVert \mathbf{x} \rVert = 0$ if and only if $\mathbf{x} = \mathbf{0}$ ;
$\lVert \lambda\mathbf{x} \rVert = |\lambda| \, \lVert \mathbf{x} \rVert$ .

Discussion.

All three parts are about the number under the square root, which is a sum of squares of real numbers, so each is settled by a fact about real squares rather than by anything about vectors. For the first, every square is non-negative and so is the sum, and the square root of a non-negative number is non-negative by definition. The second is a biconditional; the reverse direction is a computation, and the forward one uses that a sum of non-negative terms vanishes only if every term does, so each $x_i^2$ is $0$ and hence each $x_i$ is. The third pulls the constant out of the sum and out of the root, where the identity $\sqrt{\lambda^2} = |\lambda|$ supplies the absolute value; it is the reason the absolute value appears at all, since the root is the non-negative one and $\lambda$ need not be.

Proof.

Write $\mathbf{x} = (x_1, \ldots, x_n)$ and $S = \sum_{i=1}^{n} x_i^2$ .

For the first part, each $x_i^2 \geqslant 0$ , so $S \geqslant 0$ , and $\lVert \mathbf{x} \rVert = \sqrt{S} \geqslant 0$ since the square root of a non-negative real is taken to be non-negative.

For the second, if $\mathbf{x} = \mathbf{0}$ then every $x_i = 0$ , so $S = 0$ and $\lVert \mathbf{x} \rVert = 0$ . Conversely, suppose $\lVert \mathbf{x} \rVert = 0$ . Squaring gives $S = 0$ ; since $S$ is a sum of terms each of which is at least $0$ , no term can be strictly positive, so $x_i^2 = 0$ and hence $x_i = 0$ for every $i$ . Thus $\mathbf{x} = \mathbf{0}$ .

For the third, the definition of scalar multiplication makes the components of $\lambda\mathbf{x}$ the numbers $\lambda x_i$ , so

\lVert \lambda\mathbf{x} \rVert = \sqrt{\sum_{i=1}^{n} \lambda^2 x_i^2} = \sqrt{\lambda^2 \, S} = \sqrt{\lambda^2} \, \sqrt{S} = |\lambda| \, \lVert \mathbf{x} \rVert.

Definition 1.14 (Euclidean distance).

Let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ . The Euclidean distance between $\mathbf{u}$ and $\mathbf{v}$ , taken as position vectors, is $\lVert \mathbf{v} - \mathbf{u} \rVert$ ; in components,

\lVert \mathbf{v} - \mathbf{u} \rVert = \sqrt{\sum_{i=1}^{n} (v_i - u_i)^2}.

The distance is symmetric in its two arguments, since $\mathbf{u} - \mathbf{v} = -(\mathbf{v} - \mathbf{u})$ and the third part of the last proposition, with $\lambda = -1$ , gives the two vectors the same norm.

Figure 1.5. The norms of two vectors and the distance between the points they represent.

Problem 1.1.

Let $\mathbf{u}, \mathbf{v}, \mathbf{w} \in \mathbb{R}^n$ and $\lambda, \mu \in \mathbb{R}$ . Prove that $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ , that $(\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})$ , that $\mathbf{u} + \mathbf{0} = \mathbf{u}$ and $\mathbf{u} + (-\mathbf{u}) = \mathbf{0}$ , and that

\lambda(\mathbf{u} + \mathbf{v}) = \lambda\mathbf{u} + \lambda\mathbf{v}, \qquad (\lambda + \mu)\mathbf{u} = \lambda\mathbf{u} + \mu\mathbf{u}, \qquad \lambda(\mu\mathbf{u}) = (\lambda\mu)\mathbf{u}.

Problem 1.2.

Let $\mathbf{u} \in \mathbb{R}^n$ with $\mathbf{u} \neq \mathbf{0}$ . Show that $\mathbf{u} / \lVert \mathbf{u} \rVert$ is a unit vector, and that it is the only unit vector of the form $\lambda\mathbf{u}$ with $\lambda > 0$ .

The Scalar Product

Definition 1.15 (Scalar product).

Let $\mathbf{u} = (u_1, \ldots, u_n)$ and $\mathbf{v} = (v_1, \ldots, v_n)$ be vectors in $\mathbb{R}^n$ . Their scalar product, also called the dot product or the Euclidean inner product, is the real number

\mathbf{u} \cdot \mathbf{v} = \sum_{i=1}^{n} u_i v_i.

It is also written $\langle \mathbf{u}, \mathbf{v} \rangle$ .

The scalar product of two vectors is a scalar, not a vector. Comparing the definition with that of the norm gives

\mathbf{u} \cdot \mathbf{u} = \sum_{i=1}^{n} u_i^2 = \lVert \mathbf{u} \rVert^2, \qquad \text{so} \qquad \lVert \mathbf{u} \rVert = \sqrt{\mathbf{u} \cdot \mathbf{u}}.

Example 1.16 (A scalar product in $\mathbb{R}^3$ ).

\begin{pmatrix} 2 \\ 5 \\ 3 \end{pmatrix} \cdot \begin{pmatrix} 7 \\ 1 \\ 9 \end{pmatrix} = 2 \cdot 7 + 5 \cdot 1 + 3 \cdot 9 = 46.

Remark (A glance ahead at the transpose).

A matrix has a transpose, obtained by exchanging its rows and its columns. A column vector is a matrix of one column, so its transpose $\mathbf{u}^{\mathsf{T}}$ is a row, and once matrices are multiplied the product $\mathbf{u}^{\mathsf{T}} \mathbf{v}$ is a matrix with one row and one column whose single entry is

u_1 v_1 + \cdots + u_n v_n = \mathbf{u} \cdot \mathbf{v}.

So the dot product is a matrix product in disguise, which is why the row and column shapes of the earlier remark are kept apart.

Remark (Inner products in general).

Later modules replace $\mathbb{R}^n$ by a vector space $V$ over a field $F$ and keep the product as a map

\langle \cdot, \cdot \rangle : V \times V \to F, \qquad (\mathbf{u}, \mathbf{v}) \mapsto \langle \mathbf{u}, \mathbf{v} \rangle,

subject to the properties proved in the next proposition, which are there taken as axioms. Fields and vector spaces are defined in the last chapter of this lesson. The proofs that follow use only those properties, so they hold for any inner product.

Proposition 1.17 (The scalar product is a symmetric bilinear form).

Let $\mathbf{u}, \mathbf{v}, \mathbf{w} \in \mathbb{R}^n$ and $\lambda, \mu \in \mathbb{R}$ . Then

$\mathbf{u} \cdot \mathbf{v} = \mathbf{v} \cdot \mathbf{u}$ ;
$(\lambda\mathbf{u} + \mu\mathbf{w}) \cdot \mathbf{v} = \lambda (\mathbf{u} \cdot \mathbf{v}) + \mu (\mathbf{w} \cdot \mathbf{v})$ ;
$\mathbf{u} \cdot (\lambda\mathbf{v} + \mu\mathbf{w}) = \lambda (\mathbf{u} \cdot \mathbf{v}) + \mu (\mathbf{u} \cdot \mathbf{w})$ ;
$\mathbf{u} \cdot \mathbf{u} = \lVert \mathbf{u} \rVert^2 \geqslant 0$ , with $\mathbf{u} \cdot \mathbf{u} = 0$ if and only if $\mathbf{u} = \mathbf{0}$ .

Discussion.

Parts 1 to 3 are identities between two real numbers, each of which is a sum over the components, so each is proved by writing both sides as such a sum and reconciling them term by term with the arithmetic of $\mathbb{R}$ . Symmetry needs only that $u_i v_i = v_i u_i$ . Linearity in the first argument needs the definitions of the sum and the scalar multiple to compute the $i$ th component of $\lambda\mathbf{u} + \mu\mathbf{w}$ , and then the distributive law to split the sum in two. Part 3 does not need a separate argument: once symmetry is available, the two arguments may be exchanged, part 2 applied, and the arguments exchanged back. Part 4 is not new either, since $\mathbf{u} \cdot \mathbf{u} = \lVert \mathbf{u} \rVert^2$ was read off the two definitions above, and the remaining claims are the first two parts of the proposition on the norm.

Proof.

Write $\mathbf{u} = (u_1, \ldots, u_n)$ , $\mathbf{v} = (v_1, \ldots, v_n)$ and $\mathbf{w} = (w_1, \ldots, w_n)$ .

Multiplication of reals is commutative, so

\mathbf{u} \cdot \mathbf{v} = \sum_{i=1}^{n} u_i v_i = \sum_{i=1}^{n} v_i u_i = \mathbf{v} \cdot \mathbf{u},

which is the first part. For the second, the $i$ th component of $\lambda\mathbf{u} + \mu\mathbf{w}$ is $\lambda u_i + \mu w_i$ , so

\begin{aligned} (\lambda\mathbf{u} + \mu\mathbf{w}) \cdot \mathbf{v} &= \sum_{i=1}^{n} (\lambda u_i + \mu w_i) v_i = \sum_{i=1}^{n} \bigl( \lambda u_i v_i + \mu w_i v_i \bigr) \\ &= \lambda \sum_{i=1}^{n} u_i v_i + \mu \sum_{i=1}^{n} w_i v_i = \lambda (\mathbf{u} \cdot \mathbf{v}) + \mu (\mathbf{w} \cdot \mathbf{v}). \end{aligned}

For the third, we use the symmetry just proved twice, with the second part in between:

\mathbf{u} \cdot (\lambda\mathbf{v} + \mu\mathbf{w}) = (\lambda\mathbf{v} + \mu\mathbf{w}) \cdot \mathbf{u} = \lambda (\mathbf{v} \cdot \mathbf{u}) + \mu (\mathbf{w} \cdot \mathbf{u}) = \lambda (\mathbf{u} \cdot \mathbf{v}) + \mu (\mathbf{u} \cdot \mathbf{w}).

For the fourth, the identity $\mathbf{u} \cdot \mathbf{u} = \lVert \mathbf{u} \rVert^2$ holds because both sides are $\sum_{i=1}^{n} u_i^2$ . That quantity is non-negative and vanishes exactly when $\mathbf{u} = \mathbf{0}$ , by the first two parts of the proposition on the norm.

Proposition 1.18 (Cauchy–Schwarz inequality).

Let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ . Then

|\mathbf{u} \cdot \mathbf{v}| \leqslant \lVert \mathbf{u} \rVert \, \lVert \mathbf{v} \rVert,

with equality if and only if one of $\mathbf{u}$ and $\mathbf{v}$ is a scalar multiple of the other. Two vectors standing in that relation are called linearly dependent.

Discussion.

The inequality compares a quantity that may be negative with one that is not, and the way to reach it is to produce a real number that is non-negative for a reason we already have, then read the inequality off it. The reason available is part 4 of the last proposition: $\lVert \mathbf{u} + t\mathbf{v} \rVert^2 \geqslant 0$ for every real $t$ . Expanding that norm with bilinearity turns it into

\lVert \mathbf{u} \rVert^2 + 2t \, (\mathbf{u} \cdot \mathbf{v}) + t^2 \lVert \mathbf{v} \rVert^2,

a quadratic in $t$ whose coefficients are the three quantities the statement mentions. A quadratic with positive leading coefficient that is never negative has at most one real root, so its discriminant is at most $0$ , and that discriminant is exactly $4(\mathbf{u} \cdot \mathbf{v})^2 - 4\lVert \mathbf{u} \rVert^2 \lVert \mathbf{v} \rVert^2$ . The case $\mathbf{v} = \mathbf{0}$ has to be handled on its own, since then the leading coefficient vanishes and the expression is not a quadratic; both sides of the inequality are $0$ there. For the equality case, note that the discriminant is $0$ exactly when the quadratic has a root $t_0$ , and by part 4 again a root means $\mathbf{u} + t_0\mathbf{v} = \mathbf{0}$ .

Problem 1.3.

Prove the Cauchy–Schwarz inequality, including the description of the case of equality.

Remark (Where the inequality lives).

The proof asked for above uses only the four properties of the previous proposition, so the inequality holds for every inner product, not only for the dot product on $\mathbb{R}^n$ .

Proposition 1.19 (Triangle inequality).

Let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ . Then

\lVert \mathbf{u} + \mathbf{v} \rVert \leqslant \lVert \mathbf{u} \rVert + \lVert \mathbf{v} \rVert.

Discussion.

Both sides are non-negative, so it is enough to compare their squares, and squaring is what makes the statement tractable: the left-hand square is $(\mathbf{u} + \mathbf{v}) \cdot (\mathbf{u} + \mathbf{v})$ , which bilinearity expands into $\lVert \mathbf{u} \rVert^2 + 2(\mathbf{u} \cdot \mathbf{v}) + \lVert \mathbf{v} \rVert^2$ , while the right-hand square is $\lVert \mathbf{u} \rVert^2 + 2\lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert + \lVert \mathbf{v} \rVert^2$ . The two differ only in the middle term, so the whole claim reduces to $\mathbf{u} \cdot \mathbf{v} \leqslant \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert$ , which is Cauchy–Schwarz together with the fact that a real number is at most its own absolute value.

Proof.

By the identity $\lVert \mathbf{x} \rVert^2 = \mathbf{x} \cdot \mathbf{x}$ and bilinearity,

\lVert \mathbf{u} + \mathbf{v} \rVert^2 = (\mathbf{u} + \mathbf{v}) \cdot (\mathbf{u} + \mathbf{v}) = \lVert \mathbf{u} \rVert^2 + 2 (\mathbf{u} \cdot \mathbf{v}) + \lVert \mathbf{v} \rVert^2.

Every real number is at most its absolute value, so $\mathbf{u} \cdot \mathbf{v} \leqslant |\mathbf{u} \cdot \mathbf{v}|$ , and the Cauchy–Schwarz inequality bounds the latter by $\lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert$ . Hence

\lVert \mathbf{u} + \mathbf{v} \rVert^2 \leqslant \lVert \mathbf{u} \rVert^2 + 2 \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert + \lVert \mathbf{v} \rVert^2 = \bigl( \lVert \mathbf{u} \rVert + \lVert \mathbf{v} \rVert \bigr)^2.

Both $\lVert \mathbf{u} + \mathbf{v} \rVert$ and $\lVert \mathbf{u} \rVert + \lVert \mathbf{v} \rVert$ are non-negative, and for non-negative reals $a$ and $b$ the inequality $a^2 \leqslant b^2$ gives $a \leqslant b$ . Therefore $\lVert \mathbf{u} + \mathbf{v} \rVert \leqslant \lVert \mathbf{u} \rVert + \lVert \mathbf{v} \rVert$ .

Figure 1.6. The triangle with vertices

\mathbf{0}

\mathbf{u}

and

\mathbf{u} + \mathbf{v}

. Its sides have lengths

\lVert \mathbf{u} \rVert

\lVert \mathbf{v} \rVert

and

\lVert \mathbf{u} + \mathbf{v} \rVert

The name comes from that picture. The side from $\mathbf{0}$ to $\mathbf{u} + \mathbf{v}$ has length $\lVert \mathbf{u} + \mathbf{v} \rVert$ , and the other two sides have lengths $\lVert \mathbf{u} \rVert$ and $\lVert \mathbf{v} \rVert$ , the second because $(\mathbf{u} + \mathbf{v}) - \mathbf{u} = \mathbf{v}$ . Going from $\mathbf{0}$ to $\mathbf{u} + \mathbf{v}$ by way of $\mathbf{u}$ cannot be shorter than going straight there, and it is exactly as long only when $\mathbf{u}$ lies on the straight segment between the two.

Problem 1.4.

Let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ . Prove the parallelogram law

\lVert \mathbf{u} + \mathbf{v} \rVert^2 + \lVert \mathbf{u} - \mathbf{v} \rVert^2 = 2\lVert \mathbf{u} \rVert^2 + 2\lVert \mathbf{v} \rVert^2,

and interpret it as a statement about the two diagonals of the parallelogram spanned by $\mathbf{u}$ and $\mathbf{v}$ .

Problem 1.5.

Let $\mathbf{u}_1, \ldots, \mathbf{u}_k \in \mathbb{R}^n$ . Prove that

\lVert \mathbf{u}_1 + \mathbf{u}_2 + \cdots + \mathbf{u}_k \rVert \leqslant \lVert \mathbf{u}_1 \rVert + \lVert \mathbf{u}_2 \rVert + \cdots + \lVert \mathbf{u}_k \rVert .

Problem 1.6.

Write $d(\mathbf{u}, \mathbf{v}) = \lVert \mathbf{v} - \mathbf{u} \rVert$ for the Euclidean distance. Show that $d(\mathbf{u}, \mathbf{v}) \geqslant 0$ with equality exactly when $\mathbf{u} = \mathbf{v}$ , that $d(\mathbf{u}, \mathbf{v}) = d(\mathbf{v}, \mathbf{u})$ , and that

d(\mathbf{u}, \mathbf{w}) \leqslant d(\mathbf{u}, \mathbf{v}) + d(\mathbf{v}, \mathbf{w})

for all $\mathbf{u}, \mathbf{v}, \mathbf{w} \in \mathbb{R}^n$ .

Symmetries

A symmetry of a geometrical figure is a way of moving the figure so that it ends up occupying exactly the position it started in. Draw an equilateral triangle on a transparent sheet, then pick the sheet up, turn it or flip it over without tearing or stretching it, and put it back down. If the triangle lands exactly on top of where it was, the movement we performed is a symmetry of the triangle.

To watch what a movement does we number the corners, $1$ at the top, $2$ at the bottom left and $3$ at the bottom right. The numbers travel with the paper; the three corner positions stay where they are. Reading off which number sits in which position after the movement tells us which movement it was.

Figure 1.7. The six symmetries of an equilateral triangle. Each mirror line runs through one corner and the midpoint of the opposite side.

The first of the six, the movement which does nothing, is the identity symmetry, written $e$ .

Six is the whole list, because a symmetry has to send corners to corners, and once we know where two of the corners go the third has nowhere left to be.

What makes the six worth studying is that they combine. Performing one symmetry and then another leaves the triangle in its original position, so the result is again a symmetry.

Figure 1.8. A turn followed by a flip. The arrangement at the end is the one a single flip in the left axis would have produced from the start.

Combining also shows up the feature that makes this subject interesting: the order in which two symmetries are performed matters.

Figure 1.9. The same two symmetries, performed in the two possible orders. The flip is in the top axis in both rows, and the two results differ.

So three things are true of the symmetries of a figure, and one thing is not. There is an identity; every symmetry can be undone, so it has an inverse; combining is associative, since bracketing a list of movements only says where to pause and not what order to perform them in. But combining does not commute.

Maps

Making that precise takes a little vocabulary about functions and three facts about them. The same ground is covered at length in MA01.

Definition 1.20 (Injections, surjections, bijections).

Let $f : A \to B$ be a function. It is injective if $f(a) = f(a')$ implies $a = a'$ ; surjective if for every $b \in B$ there is an $a \in A$ with $f(a) = b$ ; and bijective, or a bijection, if it is both.

For $f : A \to B$ and $g : B \to C$ the composite $g \circ f : A \to C$ is the function with $(g \circ f)(a) = g(f(a))$ . The identity map $\mathrm{id}_A : A \to A$ is the function with $\mathrm{id}_A(a) = a$ .

Proposition 1.21 (Composition and inverses).

Let $f : A \to B$ , $g : B \to C$ and $h : C \to D$ be functions.

$(h \circ g) \circ f = h \circ (g \circ f)$ ;
if $f$ and $g$ are bijections, then so is $g \circ f$ ;
if $f$ is a bijection, there is exactly one function $f^{-1} : B \to A$ with $f^{-1} \circ f = \mathrm{id}_A$ and $f \circ f^{-1} = \mathrm{id}_B$ , and $f^{-1}$ is itself a bijection.

Discussion.

The first part is an equality of two functions with the same domain and codomain, so it is proved by evaluating both at an arbitrary point and unfolding the definition of a composite twice on each side; the two unfoldings meet at $h(g(f(a)))$ , and nothing about $f$ , $g$ or $h$ beyond their being functions is used. The second splits along the definition of bijection: injectivity is proved by peeling the two functions off an equation of images in the order they were applied, surjectivity by producing a preimage in two steps, first under $g$ and then under $f$ . The third is a construction rather than a deduction: surjectivity of $f$ says each $b \in B$ has at least one preimage and injectivity says it has at most one, so “the” preimage is a well-defined function of $b$ , and the two composites collapse to the identity by construction. That $f^{-1}$ is again a bijection follows because $f$ does for $f^{-1}$ exactly what $f^{-1}$ does for $f$ .

Proof.

For the first part, let $a \in A$ . Then

\bigl((h \circ g) \circ f\bigr)(a) = (h \circ g)\bigl(f(a)\bigr) = h\Bigl(g\bigl(f(a)\bigr)\Bigr) = h\bigl((g \circ f)(a)\bigr) = \bigl(h \circ (g \circ f)\bigr)(a),

and as $a$ was arbitrary the two functions are equal.

For the second, suppose $f$ and $g$ are bijections. If $g(f(a)) = g(f(a'))$ then $f(a) = f(a')$ because $g$ is injective, and then $a = a'$ because $f$ is injective; so $g \circ f$ is injective. Given $c \in C$ , surjectivity of $g$ supplies $b \in B$ with $g(b) = c$ , and surjectivity of $f$ supplies $a \in A$ with $f(a) = b$ , whence $(g \circ f)(a) = c$ ; so $g \circ f$ is surjective.

For the third, let $f$ be a bijection and let $b \in B$ . Surjectivity gives at least one $a \in A$ with $f(a) = b$ , and injectivity gives at most one, so there is exactly one; define $f^{-1}(b)$ to be it. Then $f(f^{-1}(b)) = b$ for every $b$ , and for $a \in A$ the element $f^{-1}(f(a))$ is the unique preimage of $f(a)$ , which is $a$ . So the two composites are the identities. If $k : B \to A$ also satisfies them, then $k = k \circ \mathrm{id}_B = k \circ (f \circ f^{-1}) = (k \circ f) \circ f^{-1} = \mathrm{id}_A \circ f^{-1} = f^{-1}$ by the first part, which is uniqueness. Finally, the same two equations read with the roles of $f$ and $f^{-1}$ exchanged say that $f^{-1}$ has an inverse, namely $f$ ; so $f^{-1}$ is injective, since $f^{-1}(b) = f^{-1}(b')$ gives $b = f(f^{-1}(b)) = f(f^{-1}(b')) = b'$ , and surjective, since $a = f^{-1}(f(a))$ for every $a \in A$ .

Symmetries of the Square

The informal account leaves “moving without tearing or stretching” undefined. What such a movement does not change is the distance between any two points of the figure, and that is enough to pin the notion down.

Definition 1.22 (Symmetry).

Let $P \subset \mathbb{R}^2$ be a non-empty subset. A symmetry of $P$ is a bijection $f : P \to P$ that preserves distances, meaning

\lVert f(x) - f(y) \rVert = \lVert x - y \rVert \qquad \text{for all } x, y \in P.

The distance-preserving condition is what “not tearing or stretching” amounts to, and the norm it is stated with is the one from the first chapter of this lesson. Nothing in the definition mentions turns or flips; those are conclusions, not assumptions.

We work with one figure throughout, the unit square centred at the origin with its edges parallel to the axes.

Definition 1.23 (The square $S$ ).

S = \Bigl\{ (x, y) \in \mathbb{R}^2 \;\Bigm|\; -\tfrac{1}{2} \leqslant x \leqslant \tfrac{1}{2}, \; -\tfrac{1}{2} \leqslant y \leqslant \tfrac{1}{2} \Bigr\}.

Its four corners, numbered anticlockwise from the top right, are

c_1 = \bigl(\tfrac{1}{2}, \tfrac{1}{2}\bigr), \quad c_2 = \bigl(-\tfrac{1}{2}, \tfrac{1}{2}\bigr), \quad c_3 = \bigl(-\tfrac{1}{2}, -\tfrac{1}{2}\bigr), \quad c_4 = \bigl(\tfrac{1}{2}, -\tfrac{1}{2}\bigr),

and we call them the vertices of $S$ .

Figure 1.10. The square

S

and its vertices.

Eight symmetries of $S$ can be written down by inspection: the movement which does nothing; the clockwise rotations through $90^\circ$ , $180^\circ$ and $270^\circ$ ; the reflections in the vertical and the horizontal axis; and the reflections in the two diagonals.

Problem 1.7.

For each of the eight symmetries just listed, determine which vertex it sends $c_1$ to.

Whether that list is complete is not obvious. A symmetry is heavily constrained by what it does to the four vertices, so the vertices must first be made recognisable from the distance structure alone.

Proposition 1.24 (Symmetries send vertices to vertices).

Let $f$ be a symmetry of $S$ . Then $f(c)$ is a vertex of $S$ whenever $c$ is.

Discussion.

A symmetry knows nothing about corners; all it preserves is distance. So the proof has to characterise the four vertices by a distance condition, and the natural candidate is that they are the points lying furthest apart. We therefore first show that $\lVert x - y \rVert \leqslant \sqrt{2}$ for all $x, y \in S$ , with equality exactly when $x$ and $y$ are diagonally opposite vertices; this is a computation on coordinates, since each coordinate of $x - y$ has absolute value at most $1$ and equality in the sum of squares forces equality in each term. That done, a point of $S$ is a vertex if and only if some point of $S$ is at distance $\sqrt{2}$ from it, a condition stated purely in distances. Applying $f$ to such a pair preserves the distance, so the image of a vertex again has a partner at distance $\sqrt{2}$ and is therefore a vertex.

Proof.

Let $x = (x_1, x_2)$ and $y = (y_1, y_2)$ lie in $S$ . Each of $x_1, y_1$ lies between $-\tfrac{1}{2}$ and $\tfrac{1}{2}$ , so $|x_1 - y_1| \leqslant 1$ , and likewise $|x_2 - y_2| \leqslant 1$ . Hence

\lVert x - y \rVert^2 = (x_1 - y_1)^2 + (x_2 - y_2)^2 \leqslant 1 + 1 = 2,

so $\lVert x - y \rVert \leqslant \sqrt{2}$ . Equality forces $(x_1 - y_1)^2 = (x_2 - y_2)^2 = 1$ , hence $|x_i - y_i| = 1$ for $i = 1, 2$ ; and since both coordinates are confined to an interval of length $1$ , this happens only when one of them is $-\tfrac{1}{2}$ and the other $\tfrac{1}{2}$ . So equality holds exactly when $x$ and $y$ are vertices with both coordinates opposite, that is, when they are diagonally opposite vertices.

Consequently a point $x \in S$ is a vertex if and only if there is some $x' \in S$ with $\lVert x - x' \rVert = \sqrt{2}$ : if $x$ is a vertex, take $x'$ diagonally opposite; and conversely the equality case just described makes $x$ a vertex.

Now let $f$ be a symmetry and $c$ a vertex, and choose $c'$ with $\lVert c - c' \rVert = \sqrt{2}$ . Then

\lVert f(c) - f(c') \rVert = \lVert c - c' \rVert = \sqrt{2},

and $f(c')$ lies in $S$ , so $f(c)$ is a vertex by the criterion.

Example 1.25 (A quarter-turn on the vertices).

The anticlockwise rotation through $90^\circ$ sends $(x, y)$ to $(-y, x)$ . On the vertices it acts by

c_1 \mapsto c_2, \qquad c_2 \mapsto c_3, \qquad c_3 \mapsto c_4, \qquad c_4 \mapsto c_1,

which is the numbering running one step anticlockwise, as it should be.

The second constraint is that the vertices pin down every other point of the square.

Proposition 1.26 (Two adjacent vertices locate a point).

Let $d$ and $d'$ be vertices of $S$ with $\lVert d - d' \rVert = 1$ , and let $p, q \in S$ satisfy

\lVert p - d \rVert = \lVert q - d \rVert \qquad \text{and} \qquad \lVert p - d' \rVert = \lVert q - d' \rVert.

Then $p = q$ .

Discussion.

The claim is that two distances determine a point, so what we want is to recover each coordinate of $p$ from the two given numbers. Adjacent vertices agree in one coordinate and differ by $1$ in the other, which is what makes the recovery possible: subtracting the two squared distances cancels the coordinate they agree in, and what survives is a multiple of the coordinate they differ in. That coordinate is therefore determined outright. Feeding it back into either squared distance determines the square of the remaining coordinate’s offset from the shared value, and a square leaves two candidates; the ambiguity is killed by the fact that $p$ lies in $S$ , which forces the offset to have a known sign. Since every step determines a quantity from the two given distances alone, $q$ must produce the same values, and the two points agree.

Proof.

Write $d = (d_1, d_2)$ and $d' = (d'_1, d'_2)$ . Since $d$ and $d'$ are vertices at distance $1$ , they agree in one coordinate and differ in the other. Say they agree in coordinate $l$ and differ in coordinate $k$ , where $\{k, l\} = \{1, 2\}$ , and write

d_k = \tfrac{\varepsilon}{2}, \qquad d'_k = -\tfrac{\varepsilon}{2}, \qquad d_l = d'_l = \tfrac{\delta}{2},

with $\varepsilon, \delta \in \{1, -1\}$ .

Let $p = (p_1, p_2) \in S$ . Expanding and cancelling the terms in coordinate $l$ ,

\lVert p - d' \rVert^2 - \lVert p - d \rVert^2 = \bigl(p_k + \tfrac{\varepsilon}{2}\bigr)^2 - \bigl(p_k - \tfrac{\varepsilon}{2}\bigr)^2 = 2\varepsilon p_k,

so $p_k$ is determined by the two distances. Then

\bigl(p_l - \tfrac{\delta}{2}\bigr)^2 = \lVert p - d \rVert^2 - \bigl(p_k - \tfrac{\varepsilon}{2}\bigr)^2

is determined as well. Since $p \in S$ we have $|p_l| \leqslant \tfrac{1}{2}$ , so $\delta\bigl(p_l - \tfrac{\delta}{2}\bigr) = \delta p_l - \tfrac{1}{2} \leqslant 0$ ; that is, $p_l - \tfrac{\delta}{2}$ is $-\delta$ times a non-negative number, and it is therefore the one square root of the displayed quantity carrying that sign. Hence $p_l$ is determined too.

Every quantity in this computation depends only on $\lVert p - d \rVert$ and $\lVert p - d' \rVert$ . The point $q$ has the same two distances, so the same computation returns the same coordinates, and $p = q$ .

Remark (The same fact drawn).

Geometrically the proposition says that two circles centred at adjacent vertices meet in at most one point of $S$ . Two distinct circles meet in at most two points, and those two are mirror images of one another in the line through the centres. Here that line is an edge of the square, so one of the two intersections lies on the square’s side of the edge and the other lies outside $S$ altogether.

Figure 1.11. Circles centred at two adjacent vertices. Of their two intersections only

p

lies in

S

; the other,

p'

, is its mirror image in the edge and lies outside.

Proposition 1.27 (A symmetry is determined by the vertices).

Let $f$ and $g$ be symmetries of $S$ with $f(c_i) = g(c_i)$ for $i = 1, 2, 3, 4$ . Then $f = g$ .

Discussion.

This is a uniqueness claim about functions, so we fix an arbitrary $x \in S$ and prove $f(x) = g(x)$ . The tool is the proposition above, which needs two things: a pair of adjacent vertices, and the two points $f(x)$ and $g(x)$ standing at equal distances from each of them. The pair to use is $f(c_1)$ and $f(c_2)$ , adjacent because $f$ preserves the distance $\lVert c_1 - c_2 \rVert = 1$ and by the previous proposition sends both to vertices. The equal distances come from distance preservation applied to each of $f$ and $g$ in turn: both $\lVert f(x) - f(c_i) \rVert$ and $\lVert g(x) - g(c_i) \rVert$ equal $\lVert x - c_i \rVert$ , and the hypothesis makes $f(c_i)$ and $g(c_i)$ the same point, so the two distances are measured from the same place. That proposition then closes the argument.

Proof.

The vertices $c_1$ and $c_2$ satisfy $\lVert c_1 - c_2 \rVert = 1$ . By the previous proposition $f(c_1)$ and $f(c_2)$ are vertices, and

\lVert f(c_1) - f(c_2) \rVert = \lVert c_1 - c_2 \rVert = 1,

so they are adjacent. Let $x \in S$ and let $i \in \{1, 2\}$ . Since $f$ preserves distances,

\lVert f(x) - f(c_i) \rVert = \lVert x - c_i \rVert,

and since $g$ does too, together with $g(c_i) = f(c_i)$ ,

\lVert g(x) - f(c_i) \rVert = \lVert g(x) - g(c_i) \rVert = \lVert x - c_i \rVert.

So $f(x)$ and $g(x)$ are points of $S$ at equal distances from each of the adjacent vertices $f(c_1)$ and $f(c_2)$ . The proposition above gives $f(x) = g(x)$ , and as $x$ was arbitrary, $f = g$ .

Remark (Not every shuffle of the corners is a symmetry).

The proposition says a symmetry is determined by its effect on the vertices, not that every map of the vertices to themselves comes from one. Consider the assignment

c_1 \mapsto c_2, \qquad c_2 \mapsto c_3, \qquad c_3 \mapsto c_1, \qquad c_4 \mapsto c_4.

Here $\lVert c_1 - c_4 \rVert = 1$ while the images satisfy $\lVert c_2 - c_4 \rVert = \sqrt{2}$ , so the assignment changes a distance and cannot be the restriction of a symmetry.

Proposition 1.28 (The square has exactly eight symmetries).

There are exactly eight symmetries of $S$ , namely the eight listed above.

Discussion.

The eight are known to exist, so the work is the upper bound: no ninth symmetry can hide anywhere. By the last proposition a symmetry is settled once its values on the four vertices are known, so it is enough to count the possible sets of values, and that count is made one vertex at a time. There are four choices for $f(c_1)$ . Given it, $f(c_2)$ must be a vertex at distance $1$ from $f(c_1)$ , and each vertex has exactly two neighbours, so two choices. The remaining two values are then forced rather than chosen, because $c_3$ is diagonally opposite $c_1$ and $c_4$ diagonally opposite $c_2$ , and a symmetry preserves the distance $\sqrt{2}$ that says so. Four times two is eight, and since the eight listed symmetries are distinct, every count is attained.

Proof.

Let $f$ be a symmetry of $S$ . By the proposition on vertices, $f$ carries each $c_i$ to a vertex, so there are at most four possibilities for $f(c_1)$ .

Suppose $f(c_1)$ is fixed. Since $\lVert c_1 - c_2 \rVert = 1$ , the vertex $f(c_2)$ satisfies $\lVert f(c_1) - f(c_2) \rVert = 1$ , so it is one of the two vertices adjacent to $f(c_1)$ : two possibilities.

Now $\lVert c_1 - c_3 \rVert = \sqrt{2}$ , so $\lVert f(c_1) - f(c_3) \rVert = \sqrt{2}$ , and by the equality case established earlier $f(c_3)$ is the vertex diagonally opposite $f(c_1)$ . It is therefore determined by $f(c_1)$ . The same argument determines $f(c_4)$ as the vertex diagonally opposite $f(c_2)$ .

So the values of $f$ on the four vertices are settled by at most $4 \cdot 2 = 8$ combinations, and by the previous proposition $f$ is settled by those values. Hence there are at most eight symmetries. The eight movements listed act differently on the vertices, so they are eight distinct symmetries, and the count is exact.

Combining Symmetries

Proposition 1.29 (Symmetries compose and invert).

Let $P \subset \mathbb{R}^2$ be non-empty and let $f, g$ be symmetries of $P$ . Then $f \circ g$ is a symmetry of $P$ , the identity map on $P$ is a symmetry of $P$ , and $f^{-1}$ is a symmetry of $P$ .

Discussion.

Each of the three claims asks for two things, that a certain map is a bijection $P \to P$ and that it preserves distances, and the proposition on composition and inverses supplies the first half in every case. What is left is distance, and each case is one line. For the composite, apply the hypothesis on $g$ and then the hypothesis on $f$ to the pair it produced. For the identity, there is nothing to check. For the inverse, note that an arbitrary pair of points of $P$ can be written as $f(x), f(y)$ , because $f$ is onto, and then the condition on $f$ read backwards is the condition on $f^{-1}$ .

Proof.

Let $x, y \in P$ . Since $g$ and then $f$ preserve distances,

\lVert f(g(x)) - f(g(y)) \rVert = \lVert g(x) - g(y) \rVert = \lVert x - y \rVert,

and $f \circ g$ is a bijection $P \to P$ by the second part of the proposition on composition and inverses, so it is a symmetry. The identity map is a bijection and leaves both sides of the condition untouched.

For the inverse, $f^{-1}$ is a bijection $P \to P$ by the third part of that proposition. Let $u, v \in P$ ; since $f$ is surjective there are $x, y \in P$ with $u = f(x)$ and $v = f(y)$ , and then $f^{-1}(u) = x$ , $f^{-1}(v) = y$ . Hence

\lVert f^{-1}(u) - f^{-1}(v) \rVert = \lVert x - y \rVert = \lVert f(x) - f(y) \rVert = \lVert u - v \rVert.

Definition 1.30 (Product of symmetries).

For symmetries $f$ and $g$ of a set $P$ we write $fg$ for the composite $f \circ g$ , so that

(fg)(x) = f\bigl(g(x)\bigr) \qquad \text{for every } x \in P.

The symmetry $g$ is performed first and $f$ second.

Composition of maps is associative, so a product of several symmetries may be written without brackets. From here on $r$ denotes the anticlockwise quarter-turn of $S$ and $s$ the reflection in the horizontal axis, that is

r(x, y) = (-y, x), \qquad s(x, y) = (x, -y).

Example 1.31 (Powers of the quarter-turn).

Repeating $r$ gives the other rotations:

r^2 = \text{rotation through } 180^\circ, \qquad r^3 = \text{rotation through } 270^\circ, \qquad r^4 = e.

Since $r^4 = e$ , the inverse of $r$ is $r^3$ .

Example 1.32 ( $rs \neq sr$ ).

Read off the action on $c_1$ . We have $s(c_1) = c_4$ and $r(c_4) = c_1$ , so

(rs)(c_1) = r\bigl(s(c_1)\bigr) = r(c_4) = c_1.

On the other hand $r(c_1) = c_2$ and $s(c_2) = c_3$ , so $(sr)(c_1) = c_3$ . The two symmetries disagree at $c_1$ , hence $rs \neq sr$ .

That is the first operation we have met which is not commutative: the order of the two movements is part of the data, not a convention about how the formula is written.

Problem 1.8.

Identify $rs$ and $sr$ among the eight symmetries listed earlier, describing each as a rotation or as a reflection in a named axis.

The two generators are not independent. Computing both sides on a general point,

(sr)(x, y) = s(-y, x) = (-y, -x), \qquad (r^{-1}s)(x, y) = r^{-1}(x, -y) = (-y, -x),

so $sr = r^{-1}s$ ; multiplying on the right by $s$ and using $s^2 = e$ gives the equivalent form $srs = r^{-1}$ . The relation lets any product of $r$ ‘s and $s$ ‘s be rewritten with all the $r$ ‘s on the left, and the resulting shapes are

e, \quad r, \quad r^2, \quad r^3, \quad s, \quad rs, \quad r^2 s, \quad r^3 s.

These are eight symmetries and they are distinct, so by the counting proposition they are exactly the eight symmetries of the square. The first four are the rotations and the last four the reflections.

Groups

The symmetries of the square use four facts and nothing else: combining two of them gives a third; there is an identity; every one of them can be undone; and combining is associative. The axioms of a group are exactly those four.

Definition 1.33 (Binary operation).

A binary operation on a set $G$ is a function $\star : G \times G \to G$ . We write $a \star b$ for the value of $\star$ at the ordered pair $(a, b)$ .

Definition 1.34 (Group).

A group is a pair $(G, \star)$ consisting of a set $G$ and a binary operation $\star$ on $G$ satisfying:

(G1) Associativity. $(f \star g) \star h = f \star (g \star h)$ for all $f, g, h \in G$ ;
(G2) Identity. there is an $e \in G$ with $e \star g = g \star e = g$ for every $g \in G$ ;
(G3) Inverses. for every $g \in G$ there is an $h \in G$ with $g \star h = h \star g = e$ .

The element $e$ of (G2) is the identity, or neutral element, and the element $h$ of (G3) is an inverse of $g$ . Both turn out to be unique, and the inverse of $g$ is then written $g^{-1}$ .

The first of the four facts about symmetries, that combining two gives a third, does not appear as an axiom because it is already in the definition of a binary operation: the codomain of $\star$ is $G$ , so a product of two elements of $G$ is an element of $G$ and there is nothing further to require.

Remark (The closure axiom).

Some texts add a fourth axiom, closure: if $g, k \in G$ then $g \star k \in G$ . Under our definition that is automatic, for the reason just given. It has to be stated when the operation is introduced as something defined on a larger set and then restricted, since one must then check that the restriction lands back inside $G$ .

Remark (Writing the operation).

The symbol $\star$ is usually replaced by a dot, and the dot is usually dropped: we write $gh$ for $g \star h$ and call it the product of $g$ and $h$ , exactly as for a product of numbers. This is a convention about notation, not a claim that the operation resembles multiplication, and in particular it does not license writing $gh = hg$ .

Associativity means that a product of three elements may be written $ghk$ with no bracket, since the two possible bracketings agree. The same then holds for longer products: an expression such as $((a_1a_2)(a_3a_4))a_5$ has the same value as every other bracketing of $a_1, \ldots, a_5$ in that order, and we write it $a_1a_2a_3a_4a_5$ . From here on products of any length are written without brackets.

Problem 1.9.

Let $(G, \star)$ be a group and let $a_1, \ldots, a_n \in G$ . Prove that every way of bracketing the product $a_1 \star a_2 \star \cdots \star a_n$ , keeping the terms in that order, gives the same element of $G$ .

Problem 1.10.

Let $c_n$ be the number of ways of bracketing a product $a_1 \star a_2 \star \cdots \star a_n$ , keeping the terms in that order, so that $c_2 = 1$ , $c_3 = 2$ and $c_4 = 5$ , and set $c_1 = 1$ .

Explain why $c_n = c_1 c_{n-1} + c_2 c_{n-2} + \cdots + c_{n-1} c_1$ .
Use the recurrence to compute $c_5$ and $c_6$ .

Definition 1.35 (Abelian group).

A group $(G, \star)$ is commutative, or abelian, if it satisfies the further condition

gh = hg \qquad \text{for all } g, h \in G.

Example 1.36 (Two groups).

The integers under addition, $(\mathbb{Z}, +)$ , form an infinite abelian group: addition is associative, $0$ is the identity, and the inverse of $n$ is $-n$ . The symmetries of the square under composition form a finite group which is not abelian, since $rs \neq sr$ .

Remark (Associativity is not commutativity).

Associativity says $(fg)h = f(gh)$ and commutativity says $fg = gf$ ; the two are easy to confuse and are not related. Associativity holds in every group by definition, while commutativity is an extra condition that a group may or may not satisfy.

For symmetries, associativity is free. Both $(fg)h$ and $f(gh)$ mean: perform $h$ , then $g$ , then $f$ . The brackets only divide the calculation into stages and do not touch the order in which the movements happen. Operations that are not associative do exist, subtraction on $\mathbb{R}$ being one, since $(a - b) - c$ and $a - (b - c)$ usually differ; but they cannot arise from composing functions, which is associative always.

Proposition 1.37 (The identity is unique).

Let $(G, \star)$ be a group. If $e$ and $e'$ both satisfy the condition (G2), then $e = e'$ .

Discussion.

The statement is an equality of two elements, and the only material available is that each of them is neutral. The move is to form the one product in which both hypotheses can be used, namely $e \star e'$ , and evaluate it twice: treating $e$ as an identity leaves $e'$ , and treating $e'$ as an identity leaves $e$ . No contradiction and no case split is needed, and neither associativity nor inverses enter.

Proof.

Since $e'$ satisfies (G2), we have $e \star e' = e$ . Since $e$ satisfies (G2), we have $e \star e' = e'$ . Hence $e = e \star e' = e'$ .

Proposition 1.38 (Inverses are unique).

Let $(G, \star)$ be a group with identity $e$ , and let $g, g', g'' \in G$ satisfy

g g' = e = g' g \qquad \text{and} \qquad g g'' = e = g'' g.

Then $g' = g''$ .

Discussion.

Again the goal is an equality of two elements and the hypotheses are two equations, so we build one expression that both can act on: the triple product $g' g g''$ . Read with the brackets to the left it uses $g'g = e$ and collapses to $g''$ ; read with the brackets to the right it uses $gg'' = e$ and collapses to $g'$ . Associativity is what says the two readings are the same element, and it is the whole content of the proof.

Proof.

Using associativity in the middle step,

g'' = e g'' = (g' g) g'' = g' (g g'') = g' e = g'.

Because of this proposition the inverse of $g$ may be named, and we write it $g^{-1}$ .

Problem 1.11.

The following is offered as a proof of the last proposition: “from the hypotheses, $g' = g^{-1}$ and $g'' = g^{-1}$ , so $g' = g''$ .” Explain why it is not one.

Proposition 1.39 (Solving an equation in a group).

Let $(G, \cdot)$ be a group and let $g, h \in G$ .

For $x \in G$ we have $gx = h$ if and only if $x = g^{-1}h$ ;
for $y \in G$ we have $yg = h$ if and only if $y = hg^{-1}$ .

Discussion.

Each part is a biconditional between two equations, so each direction is proved by multiplying the given equation by $g^{-1}$ on the appropriate side and simplifying with the axioms. Which side matters: the first part multiplies on the left throughout, because the unknown sits to the right of $g$ , and the second multiplies on the right for the mirror-image reason. There is no step where the two factors are exchanged, which is what makes the two parts genuinely different statements in a group that is not abelian.

Proof.

For the first part, suppose $gx = h$ . Multiplying on the left by $g^{-1}$ gives $g^{-1}(gx) = g^{-1}h$ , and associativity turns the left side into $(g^{-1}g)x = ex = x$ , so $x = g^{-1}h$ . Conversely, suppose $x = g^{-1}h$ . Multiplying on the left by $g$ gives $gx = g(g^{-1}h) = (gg^{-1})h = eh = h$ .

Problem 1.12.

Prove the second part of the last proposition.

Proposition 1.40 (Inverse of a product).

Let $(G, \cdot)$ be a group and let $g, h \in G$ . Then $(gh)^{-1} = h^{-1}g^{-1}$ .

Discussion.

By the uniqueness of inverses it is enough to check that the proposed element does what an inverse of $gh$ has to do, so the proof is a computation rather than a search: multiply $h^{-1}g^{-1}$ by $gh$ on one side and cancel from the middle outwards, then do the same on the other side. The order in which the two factors are reversed is forced by exactly this cancellation, since it is $g^{-1}$ that has to meet $g$ first.

Proof.

Using associativity to bracket at will,

(h^{-1}g^{-1})(gh) = h^{-1}(g^{-1}g)h = h^{-1} e h = h^{-1}h = e,

and symmetrically $(gh)(h^{-1}g^{-1}) = g(hh^{-1})g^{-1} = gg^{-1} = e$ . So $h^{-1}g^{-1}$ is an inverse of $gh$ , and by uniqueness it is $(gh)^{-1}$ .

Problem 1.13.

Let $(G, \cdot)$ be a group and let $g_1, \ldots, g_n \in G$ . Prove that

(g_1 g_2 \cdots g_n)^{-1} = g_n^{-1} \cdots g_2^{-1} g_1^{-1}.

Groups of Small Order

Definition 1.41 (Order of a group).

A group $(G, \cdot)$ is a finite group if the set $G$ is finite. The order of a finite group is the cardinality $\#(G)$ , the number of its elements. Every group has an identity, so $G$ is never empty and its order is at least $1$ .

Remark (Infinite groups).

Not every group is finite. The unit circle in $\mathbb{R}^2$ has infinitely many symmetries, one rotation for each angle, and $(\mathbb{Z}, +)$ is infinite as well.

To speak of an element repeating itself we need powers, and the definition is the one arithmetic suggests.

Definition 1.42 (Powers).

Let $(G, \cdot)$ be a group and $g \in G$ . Define $g^0 = e$ and $g^{n+1} = g^n g$ for $n \geqslant 0$ , and set $g^{-n} = (g^{-1})^n$ for $n \geqslant 1$ .

Proposition 1.43 (Laws of exponents).

Let $(G, \cdot)$ be a group, let $g \in G$ and let $m, n$ be integers. Then

g^{m+n} = g^m g^n \qquad \text{and} \qquad (g^m)^n = g^{mn}.

Discussion.

Both identities are statements about all integers, but the definition of a power is a recursion on the non-negative ones, so the natural route is induction for $m, n \geqslant 0$ followed by a reduction of the remaining sign cases to that one. The induction for the first identity runs on $n$ : the base case is the definition of $g^0$ , and the step is the recursion clause together with associativity. The second identity then follows from the first by a second induction on $n$ . For negative exponents the key observation is that $g^{-1}$ has the same structure, and that $g^n$ and $g^{-n}$ are inverse to one another, which converts a negative exponent into a positive one on the inverse element.

Proof.

Take first $m \geqslant 0$ and induct on $n \geqslant 0$ . For $n = 0$ both sides are $g^m$ , since $g^0 = e$ . If $g^{m+n} = g^m g^n$ , then

g^{m + (n+1)} = g^{(m+n)+1} = g^{m+n} g = (g^m g^n) g = g^m (g^n g) = g^m g^{n+1},

which is the claim at $n + 1$ . A second induction on $n \geqslant 0$ gives $(g^m)^n = g^{mn}$ : the case $n = 0$ reads $e = g^0$ , and the step is $(g^m)^{n+1} = (g^m)^n g^m = g^{mn} g^m = g^{mn + m} = g^{m(n+1)}$ , using the first identity.

For the sign cases, note that $g^n g^{-n} = e$ for $n \geqslant 0$ , by induction on $n$ using the first identity for the inverse element; so $g^{-n} = (g^n)^{-1}$ . Any instance of the two identities with negative exponents now follows by rewriting each negative power as the inverse of a positive one and applying the proposition on the inverse of a product.

Definition 1.44 (Order of an element).

Let $(G, \cdot)$ be a group and $g \in G$ . The order of $g$ is the smallest $n \in \mathbb{N}$ with $g^n = e$ , and is $\infty$ if there is no such $n$ .

Example 1.45 (Orders in the group of the square).

In the group of symmetries of the square the identity has order $1$ ; the quarter-turns $r$ and $r^3$ have order $4$ ; and the remaining five elements, the half-turn $r^2$ and the four reflections $s$ , $rs$ , $r^2s$ , $r^3s$ , all have order $2$ .

Proposition 1.46 (Orders are bounded by the order of the group).

Let $G$ be a finite group of order $n$ . Then every element of $G$ has order at most $n$ .

Discussion.

The claim is that some power of $g$ within reach is the identity, and the only resource is that $G$ has just $n$ elements. Listing $n + 1$ powers of $g$ therefore forces a repetition, and a repetition $g^a = g^b$ with $a < b$ is exactly what we want: cancelling $g^a$ from both sides, which the group allows, leaves $g^{b-a} = e$ with the exponent between $1$ and $n$ . The definition of order then bounds it by that exponent.

Proof.

Let $g \in G$ and consider the $n + 1$ elements $g^0, g^1, \ldots, g^n$ of $G$ . Since $G$ has only $n$ elements they cannot all be distinct, so there are $a, b$ with $0 \leqslant a < b \leqslant n$ and $g^a = g^b$ . Multiplying by $(g^a)^{-1} = g^{-a}$ and using the laws of exponents gives

e = g^{b} g^{-a} = g^{b-a},

with $1 \leqslant b - a \leqslant n$ . So the set of positive exponents killing $g$ is non-empty, and the least of them, which is the order of $g$ , is at most $n$ .

Remark (Lagrange).

More is true: in a finite group the order of every element divides the order of the group. That is Lagrange’s theorem, and it belongs to a course on abstract algebra rather than here. The finiteness of $G$ is what the argument above uses, not merely that orders are finite; there are infinite groups in which every element has finite order.

Proposition 1.47 (Rows and columns of the table).

Let $(G, \cdot)$ be a group and let $x \in G$ . Then the maps $y \mapsto xy$ and $y \mapsto yx$ are bijections from $G$ to $G$ . In a finite group, therefore, each element appears exactly once in every row and exactly once in every column of the multiplication table.

Discussion.

Each map is a bijection because an explicit inverse is available: multiplying by $x^{-1}$ on the same side undoes it, which is the content of the proposition on solving $gx = h$ . The statement about the table is a translation, since the row labelled $x$ lists the values of $y \mapsto xy$ as $y$ runs over $G$ ; a bijection from a finite set to itself hits each element exactly once, so no entry is missing and none is repeated.

Proof.

Let $L(y) = xy$ and $M(y) = x^{-1}y$ . Then $M(L(y)) = x^{-1}(xy) = (x^{-1}x)y = y$ and likewise $L(M(y)) = y$ , so $L$ is a bijection with inverse $M$ . The argument for $y \mapsto yx$ is the same with the multiplications on the other side.

The row of the multiplication table labelled $x$ has the entry $xy$ in the column labelled $y$ , so its entries are the values of $L$ . As $L$ is a bijection of the finite set $G$ onto itself, every element of $G$ occurs among them exactly once. Columns are handled by the other map.

Definition 1.48 (Isomorphism).

Let $(G, \cdot)$ and $(G', \cdot)$ be groups. An isomorphism from $G$ to $G'$ is a bijection $\varphi : G \to G'$ with

\varphi(ab) = \varphi(a)\,\varphi(b) \qquad \text{for all } a, b \in G.

If one exists, $G$ and $G'$ are isomorphic, written $G \cong G'$ .

Two isomorphic groups may be built from entirely different material, one from movements of a figure and one from numbers, and still be the same group as far as the operation is concerned: the isomorphism is a dictionary translating products into products.

Proposition 1.49 (What an isomorphism preserves).

Let $\varphi : G \to G'$ be an isomorphism, with identities $e$ and $e'$ . Then $\varphi(e) = e'$ , and for every $a \in G$ and every integer $n$ ,

\varphi(a^{-1}) = \varphi(a)^{-1}, \qquad \varphi(a^n) = \varphi(a)^n .

Moreover $a$ and $\varphi(a)$ have the same order.

Discussion.

The hypothesis is a single equation, $\varphi(ab) = \varphi(a)\varphi(b)$ , so each claim has to be manufactured from it by a well-chosen substitution. Taking $a = b = e$ makes the equation say $\varphi(e) = \varphi(e)\varphi(e)$ , which cancels to the first claim. Taking $b = a^{-1}$ then says $e' = \varphi(a)\varphi(a^{-1})$ , which identifies the second. The power law follows by induction on $n \geqslant 0$ , the negative case by combining the two claims already made. The statement about orders uses bijectivity: injectivity turns $\varphi(a^n) = \varphi(e)$ back into $a^n = e$ , so the positive exponents killing $a$ are exactly those killing $\varphi(a)$ , and two sets of positive integers that coincide have the same least element.

Proof.

Putting $a = b = e$ gives $\varphi(e) = \varphi(e)\varphi(e)$ , and multiplying by $\varphi(e)^{-1}$ gives $e' = \varphi(e)$ . Putting $b = a^{-1}$ gives $\varphi(a)\varphi(a^{-1}) = \varphi(aa^{-1}) = \varphi(e) = e'$ , and symmetrically on the other side, so $\varphi(a^{-1}) = \varphi(a)^{-1}$ .

For $n \geqslant 0$ induct: $\varphi(a^0) = \varphi(e) = e' = \varphi(a)^0$ , and if $\varphi(a^n) = \varphi(a)^n$ then $\varphi(a^{n+1}) = \varphi(a^n a) = \varphi(a^n)\varphi(a) = \varphi(a)^{n+1}$ . For $n < 0$ write $a^n = (a^{-1})^{-n}$ and apply the case just proved to $a^{-1}$ , using $\varphi(a^{-1}) = \varphi(a)^{-1}$ .

Finally, for $n \in \mathbb{N}$ we have $a^n = e$ if and only if $\varphi(a^n) = \varphi(e)$ , since $\varphi$ is injective, and $\varphi(a^n) = \varphi(a)^n$ while $\varphi(e) = e'$ . So $a^n = e$ if and only if $\varphi(a)^n = e'$ . The two elements are killed by the same positive exponents, hence have the same order.

Proposition 1.50 (Cyclic groups).

Let $G$ be a group of order $n$ containing an element $g$ of order $n$ . Then

G = \{e, g, g^2, \ldots, g^{n-1}\},

and $g^a g^b = g^c$ , where $c$ is the remainder of $a + b$ on division by $n$ . Any two such groups are isomorphic.

Discussion.

Two things need proving: that the listed powers exhaust $G$ , and that the operation is forced. For the first, the $n$ listed powers are distinct, since an equality between two of them would produce a positive exponent smaller than $n$ killing $g$ and so contradict the order of $g$ ; being $n$ distinct elements of a set with $n$ elements they are all of it. For the second, write $a + b = qn + c$ by division with remainder and use the laws of exponents, where $g^n = e$ makes the multiple of $n$ disappear. The last sentence is then immediate: the map $g^a \mapsto (g')^a$ between two such groups is a bijection by the first part and respects products by the second.

Proof.

Suppose $g^i = g^j$ with $0 \leqslant i < j \leqslant n - 1$ . Then $g^{j-i} = e$ with $1 \leqslant j - i < n$ , contradicting the order of $g$ being $n$ . So the $n$ elements $e, g, \ldots, g^{n-1}$ are distinct, and as $\#(G) = n$ they are all of $G$ .

Let $a, b \geqslant 0$ and write $a + b = qn + c$ with $0 \leqslant c < n$ . By the laws of exponents,

g^a g^b = g^{a+b} = g^{qn + c} = (g^n)^q g^c = e^q g^c = g^c .

Finally, let $G'$ be another group of order $n$ with an element $g'$ of order $n$ . Both groups are listed by their powers as above, so $\varphi(g^a) = (g')^a$ for $0 \leqslant a < n$ is a well-defined bijection $G \to G'$ , and the displayed rule computes the product on both sides by the same remainder, so $\varphi(g^ag^b) = \varphi(g^a)\varphi(g^b)$ .

Definition 1.51 (Cyclic group).

The group described by the last proposition is the cyclic group of order $n$ , written $C_n$ . It is abelian, since $g^ag^b$ and $g^bg^a$ are both computed from the remainder of $a + b$ .

We can now work through the small orders. Throughout, the multiplication table of a finite group has a row and a column for each element, and the entry in row $x$ and column $y$ is $x \star y$ .

Order 1. The identity is the only element and the operation is $e \star e = e$ . This is the trivial group. The letter “P”, read as a subset of $\mathbb{R}^2$ , has trivial symmetry group.

Problem 1.14.

Assuming a reasonably symmetrical font, so that “Y” has a reflection symmetry in a vertical axis and “B” one in a horizontal axis, determine which capital letters have trivial symmetry group.

Order 2. Let $G = \{e, f\}$ . The identity axiom fills in every entry but one:

\begin{array}{c|cc} \star & e & f \\ \hline e & e & f \\ f & f & ? \end{array}

If $f \star f = f$ then multiplying by $f^{-1}$ gives $f = e$ , which is false. So $f \star f = e$ , the table is forced, and $f$ has order $2$ . Hence $G \cong C_2$ , and $C_2$ is the only group of order $2$ .

Remark (One group, two pictures).

This group is the symmetry group of the letter “Z”, whose non-trivial element is the half-turn that carries the letter onto itself, and also of the letter “Y”, whose non-trivial element is a reflection. The two figures have nothing geometric in common; as groups they are isomorphic, and that is all the group axioms can see.

Order 3. Let $G = \{e, f, g\}$ with $f, g \neq e$ . Row $f$ of the table consists of $f \star e = f$ together with $f \star f$ and $f \star g$ , and by the proposition on rows and columns those three entries are $e$ , $f$ and $g$ in some order. So $\{f \star f, f \star g\} = \{e, g\}$ . Were $f \star f = e$ we should have $f \star g = g$ , and multiplying by $g^{-1}$ would give $f = e$ . Hence $f \star f = g$ and $f \star g = e$ , which fills the table:

\begin{array}{c|ccc} \star & e & f & g \\ \hline e & e & f & g \\ f & f & g & e \\ g & g & e & f \end{array}

Here $g = f^2$ and $f^3 = f \star g = e$ , so $f$ has order $3$ and $G \cong C_3$ .

Order 4. Two structures occur, and we separate them by the largest order of an element. By the proposition bounding orders that largest order is $1$ , $2$ , $3$ or $4$ , and it is not $1$ , since then every element would be $e$ .

If some element has order $4$ , the cyclic proposition gives $G \cong C_4$ .

Suppose some $g$ has order $3$ , and put $K = \{e, g, g^2\}$ . Pick $h \in G \setminus K$ , which exists since $\#(G) = 4$ . If $hg^i = g^j$ for some $i, j$ then $h = g^{j-i} \in K$ , contrary to the choice of $h$ ; so the three elements $h$ , $hg$ , $hg^2$ all lie outside $K$ , and they are distinct because $y \mapsto hy$ is injective. That gives at least $3 + 3 = 6$ elements of $G$ , which is impossible. So no element has order $3$ .

The remaining case is that every element other than $e$ has order $2$ . Write $G = \{e, f, g, h\}$ . Then $fg \neq e$ , since $fg = e$ would make $g = f^{-1} = f$ ; and $fg \neq f$ and $fg \neq g$ , since either would force one of $f, g$ to be $e$ . Hence $fg = h$ , and the same argument applied to each pair fills the table:

\begin{array}{c|cccc} \star & e & f & g & h \\ \hline e & e & f & g & h \\ f & f & e & h & g \\ g & g & h & e & f \\ h & h & g & f & e \end{array}

This really is a group, because it occurs inside one we have already built: taking $f = r^2$ , $g = s$ and $h = r^2s$ inside the symmetries of the square gives a set of four symmetries closed under composition, each equal to its own inverse, with exactly this table. It is the Klein four-group, written $V_4$ , and it is the symmetry group of the letter “H”.

So there are exactly two groups of order $4$ up to isomorphism, $C_4$ and $V_4$ . They are not isomorphic: one has an element of order $4$ and the other does not, and an isomorphism preserves the order of an element.

Remark (How the list grows).

All the groups above are abelian, and so is every group of order $5$ , though we do not prove it. The smallest non-abelian group has order $6$ . Tabulating the groups of order $n$ becomes hard quickly, especially when $n$ is a large power of a small prime: there are $267$ groups of order $64$ .

Symmetry Groups of Regular Polygons

The symmetries of the square, with composition, satisfy the group axioms by the proposition on composing and inverting symmetries. That group has eight elements and is called the dihedral group of degree four, written $D_4$ .

Remark ($D_4$ or $D_8$).

The subscript here counts the sides of the square, so $D_4$ has eight elements. Some texts write $D_8$ for the same group, counting its elements instead. Check which convention a source is using before comparing statements.

In terms of the quarter-turn $r$ and the reflection $s$ , the group is described by the relations

r^4 = e, \qquad s^2 = e, \qquad srs = r^{-1}.

These carry a surprising amount of information, because the third one lets every $s$ be pushed past every $r$ . Rewriting $sr$ as $r^{-1}s$ moves the $r$ ‘s to the left, and any product of $r$ ‘s and $s$ ‘s collapses to one of $e, r, r^2, r^3, s, rs, r^2s, r^3s$ . For instance

sr^2 = (sr)r = (r^{-1}s)r = r^{-1}(sr) = r^{-1}(r^{-1}s) = r^{-2}s = r^2 s,

using $r^4 = e$ at the last step, so the half-turn commutes with $s$ even though the quarter-turn does not. Similarly

(rs)^2 = rsrs = r(srs) = r r^{-1} = e,

so $rs$ is one of the reflections: doing it twice returns the square to where it started.

An equilateral triangle has six symmetries, three rotations and three reflections. The rotations are $e$ , $r$ and $r^2$ , where $r$ is the rotation through $120^\circ$ , and they satisfy $r^3 = e$ . Each reflection fixes one vertex and exchanges the other two; if $s$ is one of them, the other two are $rs$ and $r^2s$ . The group they form is $D_3$ , with

r^3 = e, \qquad s^2 = e, \qquad srs = r^{-1}, \qquad D_3 = \{e, r, r^2, s, rs, r^2s\}.

These are the relations of the square with the order of the basic rotation changed from $4$ to $3$ . The group $D_3$ has order $6$ and is not abelian, so it is the smallest non-abelian group.

The same account fits every regular polygon. A regular $n$ -gon with $n \geqslant 3$ has $n$ rotational and $n$ reflectional symmetries, so its symmetry group $D_n$ has $2n$ elements. Writing $r$ for the rotation through $360^\circ / n$ and $s$ for any one of the reflections,

r^n = e, \qquad s^2 = e, \qquad srs = r^{-1},

and the elements are $e, r, r^2, \ldots, r^{n-1}$ , which are the rotations, together with $s, rs, r^2s, \ldots, r^{n-1}s$ , which are the reflections.

Remark (Small $n$).

For $n < 3$ there is no regular polygon to act on, but the three relations still make sense and still define a group of order $2n$ . Neither is new: $D_1$ is $C_2$ under another name, and $D_2$ is the Klein four-group.

Symmetries as Permutations

A symmetry of the square is determined by where it sends the four vertices, and a symmetry of the triangle by where it sends the three. That suggests dropping the geometry and studying the rearrangements themselves.

Definition 1.52 (Permutation).

Let $X$ be a non-empty set. A permutation of $X$ is a bijection $\alpha : X \to X$ . The set of all permutations of $X$ is written $\operatorname{Sym}(X)$ , and for $X = \{1, 2, \ldots, n\}$ we write $\operatorname{Sym}(n)$ or $S_n$ .

A permutation of a finite set is recorded by a table of two rows, the points along the top and their images beneath. For $X = \{1, 2, 3, 4\}$ ,

\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}

means $\alpha(1) = 2$ , $\alpha(2) = 4$ , and so on. The bottom row is a rearrangement of the top one, which is exactly the condition that $\alpha$ is a bijection.

There is a shorter notation. Take $p \in S_5$ sending $(1, 2, 3, 4, 5)$ to $(3, 5, 4, 1, 2)$ . Following one point at a time, $1$ goes to $3$ , which goes to $4$ , which goes back to $1$ ; that is a cycle of length three. Separately $2$ and $5$ exchange, a cycle of length two. Writing each cycle in brackets gives the cycle notation

p = (1\,3\,4)(2\,5).

Cycle notation is not unique, since $(1\,3\,4)$ and $(3\,4\,1)$ name the same cycle, and by convention we leave out the points a permutation fixes: an index that does not appear is understood to stay where it is.

Example 1.53 (Multiplying in cycle notation).

Let $p = (1\,3\,4)(2\,5)$ as above and let $q = (1\,2)(3\,4)$ in $S_5$ . Recall that $pq$ means $q$ first, then $p$ . Following each point through both,

1 \xrightarrow{\;q\;} 2 \xrightarrow{\;p\;} 5, \qquad 5 \xrightarrow{\;q\;} 5 \xrightarrow{\;p\;} 2, \qquad 2 \xrightarrow{\;q\;} 1 \xrightarrow{\;p\;} 3, \qquad 3 \xrightarrow{\;q\;} 4 \xrightarrow{\;p\;} 1,

and $4 \mapsto 3 \mapsto 4$ . Collecting the cycles,

pq = (1\,5\,2\,3).

Example 1.54 (Inverses and conjugates).

Let $r = (1\,2\,3\,4\,5)$ and let $p$ be as above. Then

rp = (1\,4\,2)(3\,5), \qquad r^{-1} = (1\,5\,4\,3\,2), \qquad rpr^{-1} = (1\,3)(2\,4\,5).

The inverse of a cycle is the same cycle traversed backwards, which is where the second of these comes from. The third combination, $rpr^{-1}$ , is called a conjugate of $p$ .

Example 1.55 (Composing in two-row notation).

Let

\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}, \qquad \beta = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}.

Then

\alpha \circ \beta = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1 \end{pmatrix}, \qquad \beta \circ \alpha = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{pmatrix},

which disagree at $1$ , so composition of permutations is not commutative either.

Theorem 1.56 (The symmetric group).

Let $X$ be a non-empty set. Then $\operatorname{Sym}(X)$ with composition is a group, called the symmetric group on $X$ .

Discussion.

There are four things to check and the proposition on composition and inverses has done most of them. First that composition is a binary operation on $\operatorname{Sym}(X)$ , which is the statement that a composite of bijections $X \to X$ is again one. Then the three axioms: associativity is associativity of composition of maps, which holds for all functions and not merely for bijections; the identity map is a bijection and satisfies the identity axiom by definition; and the inverse required by (G3) is the inverse function, which exists because $\alpha$ is a bijection and is itself a bijection.

Proof.

If $\alpha, \beta \in \operatorname{Sym}(X)$ then $\alpha \circ \beta$ is a bijection $X \to X$ by the second part of the proposition on composition and inverses, so composition is a binary operation on $\operatorname{Sym}(X)$ .

(G1) Composition of maps is associative by the first part of that proposition, so $\alpha \circ (\beta \circ \gamma) = (\alpha \circ \beta) \circ \gamma$ for all $\alpha, \beta, \gamma \in \operatorname{Sym}(X)$ ; both send $x$ to $\alpha(\beta(\gamma(x)))$ .

(G2) The identity map $\iota : X \to X$ with $\iota(x) = x$ is a bijection, so lies in $\operatorname{Sym}(X)$ , and $\iota \circ \alpha = \alpha \circ \iota = \alpha$ for every $\alpha$ .

(G3) If $\alpha \in \operatorname{Sym}(X)$ then $\alpha$ is a bijection, so by the third part of that proposition it has an inverse function $\alpha^{-1}$ , itself a bijection, and $\alpha \circ \alpha^{-1} = \alpha^{-1} \circ \alpha = \iota$ .

As with symmetries we write $\alpha\beta$ for $\alpha \circ \beta$ , so that $\beta$ acts first. Some texts write the argument on the left, $(x)\alpha$ rather than $\alpha(x)$ , and then read products in the opposite order; work one product out by hand before trusting a source’s convention.

Theorem 1.57 (The size of $S_n$ ).

For $n \in \mathbb{N}$ we have $\#(S_n) = n!$ .

Discussion.

An element of $S_n$ is settled by its bottom row, a list $a_1, \ldots, a_n$ in which each of $1, \ldots, n$ appears once, so the count is a count of such lists. Building one from left to right, each entry may be any value not already used, so the number of choices falls by one at each step: $n$ for the first, $n - 1$ for the second, and so on down to $1$ . Multiplying the numbers of choices gives the total, and that product is the factorial.

Proof.

A permutation $\alpha \in S_n$ is determined by the list $a_1 = \alpha(1), \ldots, a_n = \alpha(n)$ , and a list arises from a permutation exactly when the $a_i$ are $1, \ldots, n$ in some order.

Choose the entries left to right. There are $n$ possibilities for $a_1$ . Once $a_1$ is chosen, injectivity excludes it from the rest, leaving $n - 1$ possibilities for $a_2$ ; after $a_1$ and $a_2$ , there are $n - 2$ possibilities for $a_3$ ; and so on, with one possibility left for $a_n$ . Each choice is free of the others in the sense that the number available at each step does not depend on which values were taken earlier, so the number of lists is

n (n-1)(n-2) \cdots 2 \cdot 1 = n!\,.

For the triangle there is no constraint at all on how the vertices may be moved: every rearrangement of the three of them is produced by exactly one symmetry. There are $3! = 6$ rearrangements and six symmetries, so the symmetry group of the equilateral triangle is the group of all permutations of three objects,

D_3 \cong S_3 .

The two sides describe different things, movements of a figure on one and rearrangements of three labels on the other, and the isomorphism is the dictionary between them.

The square is different. It has eight symmetries while $S_4$ has $4! = 24$ elements, and the remark above on shuffles of the corners exhibits a rearrangement that no symmetry produces.

Remark (Where $S_4$ does live).

No figure in the plane has symmetry group $S_4$ . In three dimensions it appears at once: $S_4$ is the group of symmetries of a regular tetrahedron, whose four vertices may be permuted in any way at all.

Problem 1.15.

Let $X$ be a finite set and let $\alpha : X \to X$ be a function. Show that $\alpha$ is injective if and only if it is surjective, and give an example of an infinite $X$ for which this fails.

Problem 1.16.

In $S_6$ , let

\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 4 & 5 & 6 & 1 \end{pmatrix}, \qquad \beta = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 6 & 5 & 4 & 3 & 2 \end{pmatrix}.

Compute $\alpha\beta$ , $\beta\alpha$ , $\alpha^{-1}$ , $\beta^{-1}$ and $\alpha\beta\alpha^{-1}$ , and write each in cycle notation. Then label the vertices of a regular hexagon $1$ to $6$ clockwise and identify each of these permutations with a symmetry of the hexagon.

Problem 1.17.

Write out the eight symmetries of the square as permutations of $\{c_1, c_2, c_3, c_4\}$ in cycle notation, and use the result to exhibit an injective map $D_4 \to S_4$ carrying products to products.

Fields

A group carries one binary operation. The number systems we actually compute in carry two, addition and multiplication, and the two cooperate: multiplication distributes over addition, so an expression built from both can be rearranged. A set with two operations cooperating in that way is a field.

Definition 1.58 (Field).

Let $F$ be a set with two binary operations $+ : F \times F \to F$ and $\cdot : F \times F \to F$ . The triple $(F, +, \cdot)$ is a field if

(F1) $(F, +)$ is an abelian group, with neutral element written $0_F$ ;
(F2) $(F \setminus \{0_F\}, \cdot)$ is an abelian group, with neutral element written $1_F$ ;
(F3) multiplication distributes over addition: $a \cdot (b + c) = a \cdot b + a \cdot c$ for all $a, b, c \in F$ .

Condition (F2) says two things at once: every element other than $0_F$ has a multiplicative inverse, and $F \setminus \{0_F\}$ is closed under multiplication, so a product of two non-zero elements is never $0_F$ .

Since $1_F$ lies in $F \setminus \{0_F\}$ we have $1_F \neq 0_F$ , so a field has at least two elements. Two is achievable: the set $\{0, 1\}$ with $1 + 1 = 0$ and the obvious multiplication is a field.

Example 1.59 (Fields and near misses).

The rationals $\mathbb{Q}$ and the reals $\mathbb{R}$ are fields, and so are the complex numbers.

The naturals $\mathbb{N}$ are not: (F1) already fails, since $1$ has no additive inverse. The integers $\mathbb{Z}$ are not either, though they come closer. They satisfy (F1) and (F3), and multiplication on them is associative and commutative with neutral element $1$ ; what fails is (F2), because no integer other than $1$ and $-1$ has a multiplicative inverse in $\mathbb{Z}$ .

Remark (The complex numbers).

MA01 does not build $\mathbb{C}$ , so here is what we take it to be. Its elements are the expressions $x + yi$ with $x, y \in \mathbb{R}$ , where $i$ is a formal symbol, added and multiplied by

\begin{aligned} (x + yi) + (z + wi) &= (x + z) + (y + w)i, \\ (x + yi)(z + wi) &= (xz - yw) + (xw + yz)i, \end{aligned}

the second rule being what expanding the brackets gives once $i^2$ is replaced by $-1$ . The conjugate of $z = x + yi$ is $\bar{z} = x - yi$ and its modulus is $|z| = \sqrt{x^2 + y^2}$ , so that $z\bar{z} = x^2 + y^2 = |z|^2$ . Every $z \neq 0$ therefore has the multiplicative inverse $\bar{z}/|z|^2$ , and $\mathbb{C}$ is a field.

Problem 1.18.

Let $z, w \in \mathbb{C}$ . Prove that

\overline{z + w} = \bar{z} + \bar{w}, \qquad \overline{zw} = \bar{z}\,\bar{w}, \qquad \overline{\bar{z}} = z, \qquad z\bar{z} = |z|^2,

and deduce that $|zw| = |z|\,|w|$ and that $z\neq 0$ has inverse $\bar{z}/|z|^2$ .

Problem 1.19.

Show that $z = \bar{z}$ if and only if $z \in \mathbb{R}$ . Then show that conjugation is an isomorphism of $(\mathbb{C}, +)$ onto itself, and also of $(\mathbb{C} \setminus \{0\}, \cdot)$ onto itself, and that it is its own inverse in both cases.

A subtler near miss drops commutativity of multiplication rather than invertibility.

Example 1.60 (The quaternions).

Let $\mathbb{H}$ be the set of expressions

a + bi + cj + dk, \qquad a, b, c, d \in \mathbb{R},

where $i$ , $j$ , $k$ are formal symbols. Addition is componentwise, and multiplication is determined by requiring it to be associative and to distribute over addition, together with the rules

i^2 = j^2 = k^2 = ijk = -1 .

From these one finds $ij = k$ and $ji = -k$ , and similar relations among the other pairs. So multiplication on $\mathbb{H}$ is not commutative, and $\mathbb{H}$ satisfies every field axiom except that one. A structure of this kind, where the non-zero elements form a group under multiplication which need not be abelian, is a skew field or division ring.

Problem 1.20.

Show that $ij = k$ and $ji = -k$ in $\mathbb{H}$ . Suggestion: first check that $i^{-1} = -i$ , $j^{-1} = -j$ and $k^{-1} = -k$ , then read $ijk = -1$ as an equation to be solved for $ij$ , and use the rule for the inverse of a product to get at $ji$ .

A field is what a set of scalars has to be before vectors can be built over it, and the first chapter of this lesson is the case $F = \mathbb{R}$ of the following.

Definition 1.61 (Vector space).

Let $(F, +, \cdot)$ be a field. An $F$ -vector space is a set $V$ with an addition $V \times V \to V$ and a scalar multiplication $F \times V \to V$ such that

$(V, +)$ is an abelian group, with neutral element $\mathbf{0}$ ;
$\lambda(\mu v) = (\lambda\mu)v$ for all $\lambda, \mu \in F$ and $v \in V$ ;
$(\lambda + \mu)v = \lambda v + \mu v$ and $\lambda(v + w) = \lambda v + \lambda w$ for all $\lambda, \mu \in F$ and $v, w \in V$ ;
$1_F \, v = v$ for every $v \in V$ .

Elements of $V$ are vectors and elements of $F$ are scalars.

The last condition cannot be dropped: without it the rule sending every $(\lambda, v)$ to $\mathbf{0}$ would satisfy the other three. With the four in place, any calculation in $V$ reduces to a linear combination

\lambda_1 v_1 + \lambda_2 v_2 + \cdots + \lambda_n v_n, \qquad \lambda_i \in F, \; v_i \in V,

which is the shape every computation in the first chapter took. That $\mathbb{R}^n$ satisfies these axioms is what the first problem of that chapter asked you to check.

The Real Numbers

We take the reals as known from school: a field carrying an order relation $\leqslant$ compatible with the two operations, so that $a \leqslant b$ implies $a + c \leqslant b + c$ , and $a \leqslant b$ with $0 \leqslant c$ implies $ac \leqslant bc$ .

The rationals are a field with an order as well, so the order alone does not separate the two. What separates them is a property of how the order behaves.

For $a, b, c \in \mathbb{R}$ we write $a < b < c$ as shorthand for ” $a < b$ and $b < c$ ”. Between any two distinct reals there is a third, namely their average, so a chain like this never closes up.

Definition 1.62 (Intervals).

Let $a, b \in \mathbb{R}$ with $a \leqslant b$ . The closed interval and the open interval are

[a, b] = \{x \in \mathbb{R} \mid a \leqslant x \leqslant b\}, \qquad (a, b) = \{x \in \mathbb{R} \mid a < x < b\},

the first a single point when $a = b$ and the second empty then. The half-open intervals are

(a, b] = \{x \in \mathbb{R} \mid a < x \leqslant b\}, \qquad [a, b) = \{x \in \mathbb{R} \mid a \leqslant x < b\},

again empty when $a = b$ . The half-infinite intervals are

(-\infty, a) = \{x \in \mathbb{R} \mid x < a\}, \quad (a, \infty) = \{x \in \mathbb{R} \mid x > a\},

together with $(-\infty, a]$ and $[a, \infty)$ , defined with $\leqslant$ and $\geqslant$ in place of $<$ and $>$ .

Remark (Reading the notation).

Three things about these symbols.

The $\infty$ and $-\infty$ are notation and nothing else. They do not name elements of $\mathbb{R}$ , and there is no such set as $[a, \infty]$ .

The notation $(a, b)$ for an open interval collides with the notation for an ordered pair. Some authors avoid this by writing the open ends with reversed square brackets, $]a, b[$ and $[a, \infty[$ . We tolerate the ambiguity, since context always says whether a subset of $\mathbb{R}$ or an element of $\mathbb{R} \times \mathbb{R}$ is meant.

If $a < b$ then $(a, b)$ contains infinitely many reals, since the averaging remark above produces a new one from any two. The same is true of the other bounded intervals, which contain $(a, b)$ .

Finally, the notation works over any ordered number system, not only $\mathbb{R}$ . Where it is not clear from context we write $[0, 1]_{\mathbb{R}}$ or $[0, 1]_{\mathbb{Q}}$ .

What does it mean for a subset of $\mathbb{R}$ to have a largest element? We want an $m \in \mathbb{R}$ with

$m \in S$ , and
$x \leqslant m$ for every $x \in S$ .

An $m$ satisfying the second condition alone is called an upper bound for $S$ , and $S$ is bounded above if it has one. Lower bounds and bounded below are defined the same way with the inequality reversed, and $S$ is bounded if it is both.

Proposition 1.63 (A largest element is unique).

Let $S \subset \mathbb{R}$ . If $m$ and $m'$ both satisfy conditions 1 and 2, then $m = m'$ .

Discussion.

The conditions come in a pair, one saying the candidate belongs to $S$ and one saying it dominates $S$ , and the proof works by crossing them over: membership of $m$ feeds into the domination property of $m'$ , and membership of $m'$ feeds into that of $m$ . Each crossing yields one of the two inequalities $m \leqslant m'$ and $m' \leqslant m$ , and antisymmetry of the order turns the pair into an equality. Nothing about $\mathbb{R}$ beyond the order is used, so the same argument works in any ordered set.

Proof.

Since $m \in S$ and $m'$ is an upper bound for $S$ , we have $m \leqslant m'$ . Since $m' \in S$ and $m$ is an upper bound for $S$ , we have $m' \leqslant m$ . Hence $m = m'$ .

We may therefore speak of the largest element of $S$ and write it $\max(S)$ . What we may not do is write $\max(S)$ into an argument before knowing it exists, because many sets have no largest element. This can fail for three separate reasons.

A set may be empty, so that no $m$ can satisfy the first condition. A set may be unbounded above, so that no $m$ satisfies the second; $\mathbb{R}$ itself is one, and so is

S = [0, 1) \cup (2, 3] \cup [4, 5) \cup (6, 7] \cup \cdots .

And a set may be non-empty and bounded above and still have no element meeting both conditions at once.

Example 1.64 (A bounded set with no largest element).

Let $S = (-\infty, 1)$ and let $m \in S$ , so $m < 1$ . Put $m' = \tfrac{m + 1}{2}$ . Then $m < m' < 1$ , so $m' \in S$ and $m' > m$ ; hence $m$ is not an upper bound for $S$ . As $m$ was arbitrary, $S$ has no largest element, even though $1$ is an upper bound for it.

Everything said about largest elements applies to smallest ones with the inequalities reversed: a smallest element is unique when it exists, is written $\min(S)$ , and need not exist. For a finite non-empty set there is no difficulty at all, which is why $\max(x, y)$ , meaning the larger of $x$ and $y$ , may be written down freely.

Problem 1.21.

Show that every non-empty subset of $\mathbb{N}$ has a smallest element. (Harder.)

Remark (Least upper bounds).

In the example above, $1$ clearly acts as an upper limit of $S = (-\infty, 1)$ , and the reason $S$ has no largest element is that $1$ was left out. Making that precise is what the following construction does. For $S \subset \mathbb{R}$ let

\operatorname{UB}(S) = \{m \in \mathbb{R} \mid x \leqslant m \text{ for every } x \in S\}

be the set of upper bounds of $S$ . If $S$ has a largest element then $\operatorname{UB}(S)$ has a smallest one and $\min(\operatorname{UB}(S)) = \max(S)$ . But $\min(\operatorname{UB}(S))$ can exist when $\max(S)$ does not: for $S = (-\infty, 1)$ we get $\operatorname{UB}(S) = [1, \infty)$ , whose smallest element is $1$ . That number is the least upper bound, or supremum, of $S$ .

The property that separates $\mathbb{R}$ from $\mathbb{Q}$ is that in $\mathbb{R}$ this never fails: every non-empty subset bounded above has a least upper bound. In $\mathbb{Q}$ it does fail, as the set of rationals with square less than $2$ shows. Making that statement into a construction of $\mathbb{R}$ is a course in itself.

Problem 1.22.

Let $S \subset \mathbb{R}$ be non-empty. Show that if $\max(S)$ exists then $\min(\operatorname{UB}(S))$ exists and the two are equal.

Absolute Value

Definition 1.65 (Absolute value).

The absolute value is the function $|\cdot| : \mathbb{R} \to \mathbb{R}$ given by

|x| = \begin{cases} x & \text{if } x \geqslant 0, \\ -x & \text{if } x < 0, \end{cases}

equivalently $|x| = \max(x, -x)$ .

Theorem 1.66 (Properties of the absolute value).

For all $x, y \in \mathbb{R}$ :

$|x| \geqslant 0$ , and $|x| = 0$ if and only if $x = 0$ (positive definiteness);
$|xy| = |x| \, |y|$ (homogeneity);
$|x + y| \leqslant |x| + |y|$ (triangle inequality).

Discussion.

The first part is read straight off the definition, one case at a time. The second could also be done by cases, four of them, but there is a shorter route: both sides are non-negative by the first part, and two non-negative reals with equal squares are equal, so it is enough to check that the squares agree, which they do because $|t|^2 = t^2$ for every $t$ . The third rests on the two inequalities $-|t| \leqslant t \leqslant |t|$ , which hold by inspection of the definition; adding the versions for $x$ and for $y$ traps $x + y$ between $-(|x|+|y|)$ and $|x|+|y|$ , and being trapped that way is exactly what $|x+y| \leqslant |x|+|y|$ says.

Proof.

For the first part, if $x \geqslant 0$ then $|x| = x \geqslant 0$ , and if $x < 0$ then $|x| = -x > 0$ ; so $|x| \geqslant 0$ always, and $|x| = 0$ forces the first case with $x = 0$ . Conversely $|0| = 0$ .

For the second, note that $|t|^2 = t^2$ for every real $t$ , since $|t|$ is $t$ or $-t$ . Hence

|xy|^2 = (xy)^2 = x^2 y^2 = |x|^2 \, |y|^2 = \bigl(|x| \, |y|\bigr)^2 .

Both $|xy|$ and $|x||y|$ are non-negative by the first part, and for non-negative reals equal squares give equal values, so $|xy| = |x||y|$ .

For the third, $-|t| \leqslant t \leqslant |t|$ holds for every $t$ : if $t \geqslant 0$ the right-hand inequality is an equality and the left is clear, and if $t < 0$ the two swap roles. Adding the inequalities for $x$ and for $y$ ,

-\bigl(|x| + |y|\bigr) \leqslant x + y \leqslant |x| + |y| .

Now $|x+y|$ is either $x + y$ or $-(x+y)$ , and both are bounded above by $|x| + |y|$ by the two halves of the display. Hence $|x+y| \leqslant |x| + |y|$ .

Remark (Distance on the line).

Setting $d(x, y) = |x - y|$ turns the absolute value into a measure of distance between points of $\mathbb{R}$ , and the three properties above become exactly the three properties of the Euclidean distance proved in the first chapter. A function $d : X \times X \to \mathbb{R}$ with those properties is called a metric, and $|\cdot|$ on $\mathbb{R}$ is the case $n = 1$ of the norm on $\mathbb{R}^n$ .

Problem 1.23.

Show that $E \subset \mathbb{R}$ is bounded if and only if there is an $M > 0$ with $|x| < M$ for every $x \in E$ . Then give examples of subsets of $\mathbb{R}$ that are bounded above only, bounded below only, and unbounded, with bounds where they exist.

Problem 1.24.

Sketch the set $E = \{x \in \mathbb{R} \mid |x - 3| \leqslant 6\}$ and write it as an interval.

Problem 1.25.

Let $x, y \in \mathbb{R}$ with $y \neq 0$ . Show that $\left| \dfrac{x}{y} \right| = \dfrac{|x|}{|y|}$ , and that $|x - y| + |x + y| = 2\max(|x|, |y|)$ .

Useful Inequalities

Theorem 1.67 (Reverse triangle inequality).

For all $x, y \in \mathbb{R}$ ,

|x - y| \geqslant |x| - |y| \qquad \text{and} \qquad |x + y| \geqslant |x| - |y| .

Discussion.

Each claim bounds a quantity from below, and the triangle inequality bounds things from above, so the two are made to meet by writing $x$ as a sum of the pieces the statement mentions. Taking $x = (x - y) + y$ and applying the triangle inequality to that sum gives $|x| \leqslant |x-y| + |y|$ , which rearranges into the first claim. The second is the same trick with $y$ replaced by $-y$ , using $|-y| = |y|$ , which is the homogeneity part of the previous theorem with the factor $-1$ .

Proof.

Write $x = (x - y) + y$ and apply the triangle inequality:

|x| \leqslant |x - y| + |y|,

so $|x - y| \geqslant |x| - |y|$ . Replacing $y$ by $-y$ throughout and using $|-y| = |y|$ gives $|x| \leqslant |x + y| + |y|$ , hence $|x + y| \geqslant |x| - |y|$ .

Theorem 1.68 (Bernoulli's inequality).

Let $x \in \mathbb{R}$ with $x \geqslant -1$ . Then $(1 + x)^n \geqslant 1 + nx$ for every $n \in \mathbb{N}$ .

Discussion.

The exponent ranges over $\mathbb{N}$ and appears on both sides, so the proof is an induction on $n$ . The base case is an equality. In the step we multiply the inductive hypothesis by $1 + x$ , which is legitimate precisely because $x \geqslant -1$ makes that factor non-negative and so preserves the inequality; this is the only place the hypothesis on $x$ is used, and the inequality is false without it. Expanding the product leaves an extra term $nx^2$ , which is non-negative and may simply be dropped to reach the claim at $n + 1$ .

Proof.

For $n = 1$ both sides equal $1 + x$ . Suppose $(1 + x)^n \geqslant 1 + nx$ . Since $x \geqslant -1$ we have $1 + x \geqslant 0$ , so multiplying the inductive hypothesis by $1 + x$ preserves the inequality:

(1 + x)^{n+1} \geqslant (1 + nx)(1 + x) = 1 + (n+1)x + nx^2 \geqslant 1 + (n+1)x,

the last step because $nx^2 \geqslant 0$ . This is the claim at $n + 1$ .

Theorem 1.69 (Young's inequality).

Let $a, b \in \mathbb{R}$ and $\varepsilon > 0$ . Then

ab \leqslant \tfrac{1}{2}\bigl(a^2 + b^2\bigr), \qquad ab \leqslant \tfrac{1}{2}\Bigl(\tfrac{a^2}{\varepsilon} + \varepsilon b^2\Bigr), \qquad |ab| \leqslant \tfrac{1}{2}\bigl(a^2 + b^2\bigr).

Discussion.

All three come from the same source, that a square is never negative, applied to a well-chosen difference. Expanding $(a - b)^2 \geqslant 0$ produces the first. For the second, the weights $\varepsilon$ and $1/\varepsilon$ have to appear, so the square to expand is that of $a/\sqrt{\varepsilon} - \sqrt{\varepsilon}\,b$ , whose cross term is again $-2ab$ while the outer terms carry the weights. The third is the first applied twice: expanding $(a + b)^2 \geqslant 0$ instead bounds $-ab$ by the same quantity, and a number bounded above together with its negative is exactly a number whose absolute value is bounded.

Proof.

From $0 \leqslant (a - b)^2 = a^2 - 2ab + b^2$ we get $2ab \leqslant a^2 + b^2$ , which is the first inequality. Since $\varepsilon > 0$ ,

0 \leqslant \Bigl(\tfrac{a}{\sqrt{\varepsilon}} - \sqrt{\varepsilon}\,b\Bigr)^2 = \tfrac{a^2}{\varepsilon} - 2ab + \varepsilon b^2,

which is the second. From $0 \leqslant (a + b)^2 = a^2 + 2ab + b^2$ we get $-ab \leqslant \tfrac{1}{2}(a^2 + b^2)$ ; combined with the first inequality, both $ab$ and $-ab$ are at most $\tfrac{1}{2}(a^2+b^2)$ , and $|ab|$ is one of them.

Theorem 1.70 (Arithmetic and geometric mean).

Let $a, b \in \mathbb{R}$ with $a, b \geqslant 0$ . Then $\sqrt{ab} \leqslant \tfrac{1}{2}(a + b)$ .

Discussion.

The statement is Young’s first inequality in disguise: since $a$ and $b$ are non-negative they have square roots, and substituting $\sqrt{a}$ and $\sqrt{b}$ for the two variables there turns the product into $\sqrt{ab}$ and the squares into $a$ and $b$ . Equivalently one may expand $(\sqrt{a} - \sqrt{b})^2 \geqslant 0$ directly, which is the same computation written out.

Proof.

Both $a$ and $b$ are non-negative, so $\sqrt{a}$ and $\sqrt{b}$ exist. Then

0 \leqslant \bigl(\sqrt{a} - \sqrt{b}\bigr)^2 = a - 2\sqrt{ab} + b,

which rearranges to $\sqrt{ab} \leqslant \tfrac{1}{2}(a + b)$ .

Standard Functions

The simplest real-valued functions are built from the field operations alone. A polynomial function is one of the form $x \mapsto c_n x^n + \cdots + c_1 x + c_0$ , such as $x^3 - 17x + 5$ ; later in the course we approximate arbitrary functions by these. A rational function is a quotient of two polynomials, such as

\frac{x}{x^2 + 3} \qquad \text{and} \qquad \frac{x^3 + 7}{x + 2}.

The second is not a function on $\mathbb{R}$ , since division by zero is undefined and the denominator vanishes at $x = -2$ ; it is a function on the subset $\{x \in \mathbb{R} \mid x \neq -2\}$ .

Definition 1.71 (Exponential function).

The exponential function is the unique differentiable $\exp : \mathbb{R} \to \mathbb{R}$ with

\exp(0) = 1 \qquad \text{and} \qquad \exp'(x) = \exp(x) \text{ for every } x \in \mathbb{R}.

We write $e = \exp(1) = 2.71828\ldots$ , and $e^x$ for $\exp(x)$ .

That such a function exists and is unique is proved in analysis; we take it, and the addition law

\exp(a + b) = \exp(a) \exp(b) \qquad \text{for all } a, b \in \mathbb{R},

as given.

Figure 1.12. The natural exponential function. It is positive everywhere, strictly increasing, and takes the value

1

0

Proposition 1.72 (Rules for the exponential).

For $a, b \in \mathbb{R}$ and $n \in \mathbb{N}$ ,

\exp(-a) = \frac{1}{\exp a}, \qquad \exp(a - b) = \frac{\exp a}{\exp b}, \qquad \exp(na) = (\exp a)^n,

and $\exp(x) > 0$ for every $x$ . The function $\exp$ is strictly increasing, and is a bijection from $\mathbb{R}$ onto $(0, \infty)$ .

Discussion.

Every rule here is the addition law used once or repeatedly. Setting $b = -a$ in it makes the left side $\exp(0) = 1$ , which identifies $\exp(-a)$ as a reciprocal and in passing shows $\exp$ never vanishes; the quotient rule is then the addition law applied to $a + (-b)$ . The rule for $\exp(na)$ is an induction whose step is one more application. Positivity needs a separate observation: $\exp(x)$ is the square of $\exp(x/2)$ , hence non-negative, and it is not zero by what has just been shown. Strict increase then comes from the derivative, which equals the function and is therefore positive; and a strictly increasing function is injective, which leaves only surjectivity onto $(0, \infty)$ , and that is the part we take from analysis along with existence.

Proof.

Putting $b = -a$ in the addition law gives $\exp(a)\exp(-a) = \exp(0) = 1$ , so neither factor is zero and $\exp(-a) = 1/\exp(a)$ . Hence

\exp(a - b) = \exp(a)\exp(-b) = \frac{\exp a}{\exp b}.

For $\exp(na) = (\exp a)^n$ , induct on $n$ : the case $n = 1$ is trivial, and $\exp((n+1)a) = \exp(na)\exp(a) = (\exp a)^n \exp(a) = (\exp a)^{n+1}$ .

For positivity, $\exp(x) = \exp\bigl(\tfrac{x}{2} + \tfrac{x}{2}\bigr) = \exp\bigl(\tfrac{x}{2}\bigr)^2 \geqslant 0$ , and $\exp(x) \neq 0$ by the first paragraph, so $\exp(x) > 0$ . Consequently $\exp' = \exp > 0$ everywhere, so $\exp$ is strictly increasing and therefore injective. Its range is $(0, \infty)$ .

Being a bijection onto $(0, \infty)$ , the exponential has an inverse.

Definition 1.73 (Natural logarithm).

The natural logarithm is the inverse of $\exp : \mathbb{R} \to (0, \infty)$ , written

\log : (0, \infty) \to \mathbb{R},

so that $\log(\exp x) = x$ for every $x \in \mathbb{R}$ and $\exp(\log y) = y$ for every $y > 0$ .

Figure 1.13. The natural logarithm, the inverse of the exponential. It is defined only for

x > 0

, is strictly increasing, and vanishes at

1

Proposition 1.74 (Rules for the logarithm).

For $a, b > 0$ and $n \in \mathbb{N}$ ,

\log(ab) = \log a + \log b, \qquad \log\!\left(\frac{a}{b}\right) = \log a - \log b, \qquad \log\!\left(\frac{1}{a}\right) = -\log a,

together with $\log(a^n) = n \log a$ and $\log 1 = 0$ . Moreover $\log$ is differentiable with $\log'(x) = 1/x$ .

Discussion.

An identity about $\log$ becomes an identity about $\exp$ the moment both sides are fed to $\exp$ , because $\exp$ is injective and undoes $\log$ . So each rule is proved by applying $\exp$ to the proposed right-hand side and watching the addition law turn a sum into the product on the left. The value $\log 1 = 0$ is $\exp(0) = 1$ read backwards. The derivative is different in kind: differentiating the identity $\exp(\log x) = x$ by the chain rule produces $\exp(\log x)\log'(x) = 1$ , and the left factor is $x$ , which solves for $\log'(x)$ .

Proof.

For $a, b > 0$ ,

\exp(\log a + \log b) = \exp(\log a)\exp(\log b) = ab,

and applying $\log$ to both sides gives $\log a + \log b = \log(ab)$ . Replacing $b$ by $1/b$ and using the same computation gives the quotient rule, and taking $a = 1$ in it gives $\log(1/b) = -\log b$ since $\log 1 = 0$ ; and $\log 1 = 0$ holds because $\exp(0) = 1$ . The rule $\log(a^n) = n\log a$ follows by induction from the product rule.

Differentiating $\exp(\log x) = x$ by the chain rule gives $\exp(\log x)\log'(x) = 1$ , and $\exp(\log x) = x$ , so $\log'(x) = 1/x$ for $x > 0$ .

Remark (Which logarithm is $\log$?).

In mathematics an unadorned $\log$ always means the natural logarithm, to base $e$ . Some software takes the opposite convention, using $\log$ for the base- $10$ logarithm and $\ln$ for the natural one; check before trusting a numerical result.

Remark (Why there is no logarithm of a negative number).

We have not defined $\log x$ for $x \leqslant 0$ , and no definition is possible. The identity $\exp(\log x) = x$ is what makes the logarithm useful, and $\exp$ takes only positive values, so no value of $\log x$ could satisfy it for $x \leqslant 0$ . The same restriction is inherited by the power functions below.

Definition 1.75 (Powers and logarithms to a general base).

For $a > 0$ define $a^{\,\cdot} : \mathbb{R} \to (0, \infty)$ by

a^x = \exp(x \log a).

It is a bijection, and its inverse is the logarithm to base $a$ , written $\log_a : (0, \infty) \to \mathbb{R}$ .

This agrees with the elementary meaning of a power whenever that meaning is available: for $y \in \mathbb{Z}$ the definition returns $x$ multiplied by itself $y$ times when $y > 0$ , returns $1$ when $y = 0$ , and returns $1/x^{-y}$ when $y < 0$ . Its advantage is that it makes sense for every real exponent.

Figure 1.14. The functions

x \mapsto a^x

for

a = 1.5

2

and

2.5

. Each takes the value

1

0

, and each is

\exp(x \log a)

Figure 1.15. Logarithms to base

10

, base

2

and base

e

. All three vanish at

1

, and each is a fixed multiple of the others.

Proposition 1.76 (Changing the base).

For $a, b, x > 0$ with $a \neq 1$ and $b \neq 1$ ,

\log_a x = \frac{\log x}{\log a} \qquad \text{and} \qquad \log_a x = \log_a b \cdot \log_b x .

Discussion.

The base- $a$ logarithm was defined as an inverse, so the way to compute it is to apply the function it inverts and read off what the exponent must have been. Writing $y = \log_a x$ means $a^y = x$ , which by the definition of a power is $\exp(y \log a) = x$ ; taking $\log$ of both sides turns it into $y \log a = \log x$ , and dividing gives the first identity. The second is then arithmetic: substituting the first identity three times, once for each of the three logarithms appearing, reduces the claim to cancelling a common factor.

Proof.

Let $y = \log_a x$ , so $a^y = x$ , that is $\exp(y \log a) = x$ . Applying $\log$ gives $y \log a = \log x$ , and $\log a \neq 0$ since $a \neq 1$ , so $y = \log x / \log a$ .

For the second identity, substituting the first three times,

\log_a b \cdot \log_b x = \frac{\log b}{\log a} \cdot \frac{\log x}{\log b} = \frac{\log x}{\log a} = \log_a x .

Example 1.77 (Halving a fish population).

Suppose a lake holds $C$ fish and that fishing reduces the population according to $f(t) = Ce^{-\lambda t}$ with $\lambda > 0$ . The time $T$ at which half the fish are gone satisfies

Ce^{-\lambda T} = \frac{C}{2} \iff e^{-\lambda T} = \frac{1}{2} \iff -\lambda T = \log \tfrac{1}{2} = -\log 2 \iff T = \frac{\log 2}{\lambda},

which does not depend on $C$ .

Trigonometric Functions

Definition 1.78 (Periodic function).

A function $f : X \to Y$ with $X \subset \mathbb{R}$ is $T$ -periodic for $T \in \mathbb{R}$ if $f(x + T) = f(x)$ for every $x \in X$ with $x + T \in X$ .

The trigonometric functions are read off the unit circle, the circle of radius $1$ centred at the origin $O = (0, 0)$ . Angles are measured in radians and counted anticlockwise from the positive $x$ -axis, so that a full circuit is $2\pi$ .

Figure 1.16. The unit circle. The point

M_\alpha

has coordinates

(\cos\alpha, \sin\alpha)

, and the outer arrow shows the direction in which angles are counted.

\begin{array}{c|cccccc} \text{radians} & 2\pi & \pi & \tfrac{\pi}{2} & \tfrac{\pi}{3} & \tfrac{\pi}{4} & \tfrac{\pi}{6} \\ \hline \text{degrees} & 360 & 180 & 90 & 60 & 45 & 30 \end{array}

The angle $\alpha$ may be any real number, and $M_\alpha$ denotes the point of the unit circle for which the angle from the positive $x$ -axis to $OM_\alpha$ is $\alpha$ . A full circuit is $2\pi$ , so $M_\alpha$ , $M_{\alpha + 2\pi}$ and $M_{\alpha + 4\pi}$ are the same point; it is often convenient to restrict $\alpha$ to $(-\pi, \pi]$ or to $[0, 2\pi)$ . We say in this situation that $\alpha$ is defined modulo $2\pi$ .

Definition 1.79 (Congruence modulo a real number).

Let $a, b, c \in \mathbb{R}$ . We say $a$ is equal to $b$ modulo $c$ , written $a = b \bmod c$ , if

a \in \{b + ck \mid k \in \mathbb{Z}\},

a set also written $b + c\mathbb{Z}$ .

Example 1.80 (An angle modulo $2\pi$ ).

The equation $\alpha = \tfrac{\pi}{3} \bmod 2\pi$ says that

\alpha \in \Bigl\{\tfrac{\pi}{3} + 2k\pi \;\Bigm|\; k \in \mathbb{Z}\Bigr\} = \Bigl\{\ldots, -\tfrac{5\pi}{3}, \; \tfrac{\pi}{3}, \; \tfrac{7\pi}{3}, \ldots\Bigr\}.

Definition 1.81 (Sine, cosine and tangent).

Let $\alpha \in \mathbb{R}$ and let $M_\alpha$ be as above. The cosine $\cos\alpha$ is the $x$ -coordinate of $M_\alpha$ and the sine $\sin\alpha$ is its $y$ -coordinate. Where $\cos\alpha \neq 0$ , that is where $\alpha \neq \tfrac{\pi}{2} \bmod \pi$ , the tangent is

\tan\alpha = \frac{\sin\alpha}{\cos\alpha}.

Thus $\cos, \sin : \mathbb{R} \to [-1, 1]$ and $\tan : \mathbb{R} \setminus \bigl\{\tfrac{\pi}{2} + k\pi \mid k \in \mathbb{Z}\bigr\} \to \mathbb{R}$ .

Since a full circuit returns $M_\alpha$ to itself, $\sin$ and $\cos$ are $2\pi$ -periodic; $\tan$ turns out to be $\pi$ -periodic, which the shift formulas below explain.

Figure 1.17. Sine (solid) and cosine (dashed) over two periods. Both take values in

[-1, 1]

and repeat every

2\pi

Figure 1.18. The tangent. It repeats every

\pi

and is undefined at the dashed lines

x = \tfrac{\pi}{2} + k\pi

We take the addition formulas as known,

\begin{aligned} \sin(x + y) &= \sin x \cos y + \cos x \sin y, \\ \cos(x + y) &= \cos x \cos y - \sin x \sin y, \end{aligned}

and derive the rest from them together with the definition.

Proposition 1.82 (Trigonometric identities).

For all real $x$ and $y$ at which the expressions are defined:

$\cos^2 x + \sin^2 x = 1$ , and $1 + \tan^2 x = \dfrac{1}{\cos^2 x}$ ;
$\sin(-x) = -\sin x$ , $\cos(-x) = \cos x$ , $\tan(-x) = -\tan x$ ;
$\sin(x - y) = \sin x \cos y - \cos x \sin y$ and $\cos(x - y) = \cos x \cos y + \sin x \sin y$ ;
$\sin(x + \pi) = -\sin x$ , $\cos(x + \pi) = -\cos x$ , and $\tan(x + \pi) = \tan x$ ;
$\sin(\pi - x) = \sin x$ and $\cos(\pi - x) = -\cos x$ ;
$\sin\bigl(x + \tfrac{\pi}{2}\bigr) = \cos x$ and $\cos\bigl(x + \tfrac{\pi}{2}\bigr) = -\sin x$ ;
$\sin\bigl(x - \tfrac{\pi}{2}\bigr) = -\cos x$ and $\cos\bigl(x - \tfrac{\pi}{2}\bigr) = \sin x$ ;
$\sin 2x = 2\sin x \cos x$ and $\cos 2x = \cos^2 x - \sin^2 x$ ;
$\tan(x + y) = \dfrac{\tan x + \tan y}{1 - \tan x \tan y}$ .

Discussion.

Only the first two parts need anything beyond the addition formulas. The Pythagorean identity is the statement that $M_x$ lies on the unit circle, since its coordinates are $\cos x$ and $\sin x$ and the circle has radius $1$ ; dividing it by $\cos^2 x$ , where that is non-zero, gives the companion identity for the tangent. The parity statements are read off the circle as well: reflecting in the $x$ -axis carries $M_x$ to $M_{-x}$ , which negates the second coordinate and fixes the first. Everything after that is substitution. Part 3 is the addition formulas with $-y$ in place of $y$ , using part 2. Parts 4 to 7 are the addition formulas evaluated at the special angles $\pi$ and $\tfrac{\pi}{2}$ , whose sines and cosines are $0$ and $\pm 1$ , so most terms vanish; part 5 combines part 4 with part 2, and part 7 combines part 6 with part 2. Part 8 is the addition formulas with $y = x$ , and part 9 is part 8’s method applied to the quotient defining the tangent, dividing numerator and denominator by $\cos x \cos y$ .

Proof.

The point $M_x = (\cos x, \sin x)$ lies on the circle of radius $1$ about the origin, so $\cos^2 x + \sin^2 x = 1$ by the formula for the Euclidean norm. Where $\cos x \neq 0$ , dividing by $\cos^2 x$ gives $1 + \tan^2 x = 1/\cos^2 x$ . Reflecting the circle in the $x$ -axis sends $M_x$ to $M_{-x}$ and negates the second coordinate, so $\cos(-x) = \cos x$ and $\sin(-x) = -\sin x$ ; the statement for $\tan$ follows by dividing.

Substituting $-y$ for $y$ in the addition formulas and using the parity just proved gives part 3. Taking $y = \pi$ , where $\cos\pi = -1$ and $\sin\pi = 0$ , gives part 4, and the statement for $\tan$ follows by dividing the two; part 5 is part 3 with $x = \pi$ together with parity. Taking $y = \tfrac{\pi}{2}$ , where $\cos\tfrac{\pi}{2} = 0$ and $\sin\tfrac{\pi}{2} = 1$ , gives part 6, and part 3 with $y = \tfrac{\pi}{2}$ gives part 7.

Taking $y = x$ in the addition formulas gives part 8. For part 9, divide

\tan(x+y) = \frac{\sin x \cos y + \cos x \sin y}{\cos x \cos y - \sin x \sin y}

above and below by $\cos x \cos y$ , which is non-zero wherever both tangents are defined.

Figure 1.19. The five angles related to

\alpha

by the parity and shift identities, read off the same circle.

With the labelling of the figure below, where $\alpha$ , $\beta$ , $\gamma$ are the angles at the three vertices and $a$ , $b$ , $c$ are the sides opposite them,

\frac{\sin\alpha}{a} = \frac{\sin\beta}{b} = \frac{\sin\gamma}{c} \qquad \text{(law of sines)},

c^2 = a^2 + b^2 - 2ab\cos\gamma \qquad \text{(law of cosines)}.

Between them they recover the unknown sides and angles of a triangle from the known ones. The law of cosines is proved once the angle between two vectors has been defined.

Figure 1.20. A triangle labelled for the law of sines and the law of cosines: each side is named by the lower-case letter matching the angle opposite it.

Back to Vectors

The angle can now be brought back to $\mathbb{R}^n$ , and with it the case of equality in the triangle inequality.

Proposition 1.83 (Equality in the triangle inequality).

Let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ with $\mathbf{v} \neq \mathbf{0}$ . Then

\lVert \mathbf{u} + \mathbf{v} \rVert = \lVert \mathbf{u} \rVert + \lVert \mathbf{v} \rVert

if and only if $\mathbf{u} = \lambda\mathbf{v}$ for some real $\lambda \geqslant 0$ .

Discussion.

The proof of the triangle inequality passed through two steps where something was given away, first replacing $\mathbf{u}\cdot\mathbf{v}$ by $|\mathbf{u}\cdot\mathbf{v}|$ and then bounding that by $\lVert\mathbf{u}\rVert\lVert\mathbf{v}\rVert$ . Equality at the end forces equality at both, so the condition is that $\mathbf{u}\cdot\mathbf{v}$ is non-negative and that Cauchy–Schwarz is tight. The Cauchy–Schwarz proposition already says when the second happens, namely when one vector is a multiple of the other, and $\mathbf{v} \neq \mathbf{0}$ lets us take the multiple in the direction $\mathbf{u} = \lambda\mathbf{v}$ . The sign condition then decides $\lambda$ , because $\mathbf{u}\cdot\mathbf{v} = \lambda\lVert\mathbf{v}\rVert^2$ has the sign of $\lambda$ . The converse is a direct computation with $\lambda \geqslant 0$ , where the homogeneity of the norm produces the factor $\lambda$ without an absolute value.

Proof.

Suppose first that $\mathbf{u} = \lambda\mathbf{v}$ with $\lambda \geqslant 0$ . Then

\lVert \mathbf{u} + \mathbf{v} \rVert = \lVert (\lambda + 1)\mathbf{v} \rVert = (\lambda + 1)\lVert \mathbf{v} \rVert = \lambda\lVert \mathbf{v} \rVert + \lVert \mathbf{v} \rVert = \lVert \mathbf{u} \rVert + \lVert \mathbf{v} \rVert,

using $|\lambda + 1| = \lambda + 1$ and $|\lambda| = \lambda$ .

Conversely, suppose the norms are equal. Squaring and expanding as in the proof of the triangle inequality,

\lVert \mathbf{u} \rVert^2 + 2(\mathbf{u} \cdot \mathbf{v}) + \lVert \mathbf{v} \rVert^2 = \lVert \mathbf{u} \rVert^2 + 2\lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert + \lVert \mathbf{v} \rVert^2,

so $\mathbf{u} \cdot \mathbf{v} = \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert$ . In particular $|\mathbf{u} \cdot \mathbf{v}| = \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert$ , which is the case of equality in the Cauchy–Schwarz inequality, so one of $\mathbf{u}$ , $\mathbf{v}$ is a multiple of the other; as $\mathbf{v} \neq \mathbf{0}$ we may write $\mathbf{u} = \lambda\mathbf{v}$ . Then $\mathbf{u} \cdot \mathbf{v} = \lambda\lVert \mathbf{v} \rVert^2$ is non-negative and $\lVert \mathbf{v} \rVert^2 > 0$ , so $\lambda \geqslant 0$ .

Restricted to $[0, \pi]$ the cosine is a bijection onto $[-1, 1]$ , so it has an inverse $\cos^{-1} : [-1, 1] \to [0, \pi]$ , and the Cauchy–Schwarz inequality says exactly that the quotient below is an admissible input to it.

Definition 1.84 (Angle between vectors).

Let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ be non-zero. The angle between them is

\theta = \cos^{-1}\!\left( \frac{\mathbf{u} \cdot \mathbf{v}}{\lVert \mathbf{u} \rVert \, \lVert \mathbf{v} \rVert} \right) \in [0, \pi].

The vectors are orthogonal, or perpendicular, if $\mathbf{u} \cdot \mathbf{v} = 0$ , that is if $\theta = \tfrac{\pi}{2}$ .

The definition is legitimate because Cauchy–Schwarz gives $|\mathbf{u} \cdot \mathbf{v}| \leqslant \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert$ , so the quotient lies in $[-1, 1]$ . Taking the value of $\cos^{-1}$ in $[0, \pi]$ measures the smaller of the two angles between the vectors. For $n = 2$ this agrees with the angle read off the unit circle.

Corollary 1.85 (Law of cosines).

Let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ be non-zero, with angle $\theta$ between them. Then

\lVert \mathbf{u} - \mathbf{v} \rVert^2 = \lVert \mathbf{u} \rVert^2 + \lVert \mathbf{v} \rVert^2 - 2 \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert \cos\theta .

Taking $\mathbf{u}$ and $\mathbf{v}$ to be two sides of a triangle issuing from the vertex where the angle is $\gamma$ , this is the law of cosines $c^2 = a^2 + b^2 - 2ab\cos\gamma$ .

Proof.

By bilinearity of the scalar product,

\lVert \mathbf{u} - \mathbf{v} \rVert^2 = (\mathbf{u} - \mathbf{v}) \cdot (\mathbf{u} - \mathbf{v}) = \lVert \mathbf{u} \rVert^2 - 2(\mathbf{u} \cdot \mathbf{v}) + \lVert \mathbf{v} \rVert^2,

and the definition of the angle gives $\mathbf{u} \cdot \mathbf{v} = \lVert \mathbf{u} \rVert \lVert \mathbf{v} \rVert \cos\theta$ . The third side of the triangle with sides $\mathbf{u}$ and $\mathbf{v}$ is $\mathbf{u} - \mathbf{v}$ , whose length is $c$ , while $\lVert \mathbf{u} \rVert$ and $\lVert \mathbf{v} \rVert$ are $b$ and $a$ .

Example 1.86 (An angle in $\mathbb{R}^4$ ).

Let $\mathbf{u} = (1, 2, 3, 1)$ and $\mathbf{v} = (-1, 0, 2, 3)$ . Their norms are

\lVert \mathbf{u} \rVert^2 = 1 + 4 + 9 + 1 = 15, \qquad \lVert \mathbf{v} \rVert^2 = 1 + 0 + 4 + 9 = 14,

so $\lVert \mathbf{u} \rVert = \sqrt{15}$ and $\lVert \mathbf{v} \rVert = \sqrt{14}$ . Their scalar product is

\mathbf{u} \cdot \mathbf{v} = 1 \cdot (-1) + 2 \cdot 0 + 3 \cdot 2 + 1 \cdot 3 = 8,

so the angle between them is

\theta = \cos^{-1}\!\left( \frac{8}{\sqrt{15}\sqrt{14}} \right) = \cos^{-1}\!\left( \frac{8}{\sqrt{210}} \right) \approx 0.986 \text{ radians}.

Proposition 1.87 (Orthogonal projection).

Let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$ with $\mathbf{v} \neq \mathbf{0}$ . There is exactly one real $\lambda$ for which $\mathbf{u} - \lambda\mathbf{v}$ is orthogonal to $\mathbf{v}$ , namely

\lambda = \frac{\mathbf{u} \cdot \mathbf{v}}{\lVert \mathbf{v} \rVert^2},

and the resulting decomposition is

\mathbf{u} = \lambda\mathbf{v} + (\mathbf{u} - \lambda\mathbf{v}).

Discussion.

The condition to be met is a single scalar equation, $(\mathbf{u} - \lambda\mathbf{v}) \cdot \mathbf{v} = 0$ , in the single unknown $\lambda$ . Bilinearity expands its left side into $\mathbf{u}\cdot\mathbf{v} - \lambda\lVert\mathbf{v}\rVert^2$ , which is a linear expression in $\lambda$ with coefficient $-\lVert\mathbf{v}\rVert^2$ ; that coefficient is non-zero exactly because $\mathbf{v} \neq \mathbf{0}$ , so the equation has exactly one solution and existence and uniqueness are settled together. The decomposition is then a matter of adding and subtracting the same vector.

Proof.

For $\lambda \in \mathbb{R}$ , bilinearity of the scalar product gives

(\mathbf{u} - \lambda\mathbf{v}) \cdot \mathbf{v} = \mathbf{u} \cdot \mathbf{v} - \lambda (\mathbf{v} \cdot \mathbf{v}) = \mathbf{u} \cdot \mathbf{v} - \lambda \lVert \mathbf{v} \rVert^2 .

Since $\mathbf{v} \neq \mathbf{0}$ we have $\lVert \mathbf{v} \rVert^2 > 0$ , so this vanishes for exactly one $\lambda$ , namely $\lambda = (\mathbf{u} \cdot \mathbf{v}) / \lVert \mathbf{v} \rVert^2$ . Writing $\mathbf{u} = \lambda\mathbf{v} + (\mathbf{u} - \lambda\mathbf{v})$ is then an identity.

Definition 1.88 (Vector projection).

With $\lambda$ as in the last proposition, the vector

\operatorname{proj}_{\mathbf{v}} \mathbf{u} = \lambda\mathbf{v} = \frac{\mathbf{u} \cdot \mathbf{v}}{\lVert \mathbf{v} \rVert^2}\,\mathbf{v}

is the component of $\mathbf{u}$ in the direction of $\mathbf{v}$ , or the vector projection of $\mathbf{u}$ onto $\mathbf{v}$ , and $\mathbf{u} - \lambda\mathbf{v}$ is the component of $\mathbf{u}$ perpendicular to $\mathbf{v}$ .

Figure 1.21. The components of

\mathbf{u}

relative to

\mathbf{v}

: the projection

\lambda\mathbf{v}

along

\mathbf{v}

, and

\mathbf{u} - \lambda\mathbf{v}

at right angles to it.

Problem 1.26.

Let $\mathbf{u} = (2, -1, 2)$ and $\mathbf{v} = (1, 2, 2)$ in $\mathbb{R}^3$ . Compute the angle between them, the projection of $\mathbf{u}$ onto $\mathbf{v}$ , and the component of $\mathbf{u}$ perpendicular to $\mathbf{v}$ , and verify that the two components are orthogonal.

Problem 1.27.

Let $\mathbf{v} \in \mathbb{R}^n$ be non-zero. Show that $\operatorname{proj}_{\mathbf{v}}$ is unchanged when $\mathbf{v}$ is replaced by $\mu\mathbf{v}$ for any real $\mu \neq 0$ .

Problem 1.28.

With $\lambda$ as in the last proposition, prove that

\lVert \mathbf{u} \rVert^2 = \lVert \lambda\mathbf{v} \rVert^2 + \lVert \mathbf{u} - \lambda\mathbf{v} \rVert^2,

and deduce that $\lVert \operatorname{proj}_{\mathbf{v}} \mathbf{u} \rVert \leqslant \lVert \mathbf{u} \rVert$ .

One more construction is available in three dimensions only.

Definition 1.89 (Vector product).

For $\mathbf{u} = (u_1, u_2, u_3)$ and $\mathbf{v} = (v_1, v_2, v_3)$ in $\mathbb{R}^3$ , the vector product, or cross product, is

\mathbf{u} \times \mathbf{v} = (u_2 v_3 - u_3 v_2, \; u_3 v_1 - u_1 v_3, \; u_1 v_2 - u_2 v_1) \in \mathbb{R}^3 .

Unlike the scalar product it returns a vector rather than a number, and it exists only for $n = 3$ .

Exercises on Vectors

Exercise 1.1.

Let $\mathbf{a} = (2, 1)$ and $\mathbf{b} = (8, 2)$ . Find $\mathbf{a} + \mathbf{b}$ twice, once by drawing and once by computing, and check that the two agree.

Exercise 1.2.

Let $\mathbf{a} = (1, 2, 4)$ , $\mathbf{b} = (2, 1, -1)$ and $c = 3$ . Compute

\mathbf{a} + \mathbf{b}, \quad \mathbf{a} - \mathbf{b}, \quad \mathbf{a} \cdot \mathbf{b}, \quad c\mathbf{a}, \quad \lVert \mathbf{a} \rVert, \quad \lVert c\mathbf{a} \rVert,

and normalise $\mathbf{a}$ and $\mathbf{b}$ .

Exercise 1.3.

Give the coordinates of the eight corners of a cube of edge length $1$ positioned so that three of its edges lie along the $x$ -, $y$ - and $z$ -axes.

Exercise 1.4.

Romeo is at $(3, 4, 0)$ and Juliet is at $(2, 1, 5)$ . How far apart are they?

Exercise 1.5.

Find a vector in $\mathbb{R}^3$ orthogonal to $(2, -3, 4)$ , and describe all of them.

Exercises on Symmetries and Groups

Exercise 1.6.

Let $S = \{a, b\}$ be a two-element set. Show that there are exactly $16$ binary operations on $S$ , and determine how many of them make $S$ a group. Then find a formula for the number of binary operations on a set of $n$ elements.

Exercise 1.7.

Prove that multiplication of complex numbers is associative.

Exercise 1.8.

Which of the following are groups? Justify each answer.

The complex numbers $z$ with $|z| = 1$ , under multiplication;
$\{x \in \mathbb{R} \mid x \geqslant 0\}$ under $x \star y = \max(x, y)$ ;
the rationals with odd denominator, under addition;
$\{a, b\}$ with $a \neq b$ and $a \star a = a$ , $b \star b = b$ , $a \star b = b$ , $b \star a = b$ ;
$\{a, b\}$ with $a \neq b$ and $a \star a = a$ , $b \star b = a$ , $a \star b = b$ , $b \star a = b$ ;
$\mathbb{R}^3$ under the vector product $\mathbf{v} \star \mathbf{w} = \mathbf{v} \times \mathbf{w}$ .

Exercise 1.9.

Let $S$ be the set of all real numbers except $-1$ , and for $a, b \in S$ define $a \star b = ab + a + b$ . Show that $(S, \star)$ is a group. Check in particular that $\star$ really is a binary operation on $S$ .

Exercise 1.10.

Let $G$ be a group and $a, b, c \in G$ . Prove that

if $ab = ac$ then $b = c$ ;
the equation $axb = c$ has exactly one solution $x \in G$ ;
$(a^{-1})^{-1} = a$ .

Exercise 1.11.

Let $G$ be a group with identity $e$ in which $x \star x = e$ for every $x \in G$ . Show that $G$ is abelian. Then produce infinitely many groups with this property.

Exercise 1.12.

Let $X$ be a non-empty set and let $\alpha, \beta$ be permutations of $X$ such that every element moved by $\alpha$ is fixed by $\beta$ and every element moved by $\beta$ is fixed by $\alpha$ . Prove that $\alpha \circ \beta = \beta \circ \alpha$ . (Harder.)

Exercise 1.13.

Let $(G, \cdot)$ be a group and let $g, h \in G$ with $gh = hg$ . Show that $(gh)^r = g^r h^r$ for every $r \in \mathbb{N}$ . Then exhibit $g, h \in S_3$ with $(gh)^2 \neq g^2 h^2$ .

Exercise 1.14.

Prove that $S_n$ is abelian only for $n < 3$ .

Exercises on Fields and Real Functions

Exercise 1.15.

Solve $\sin x = \cos x$ for $x \in \mathbb{R}$ .

Exercise 1.16.

Solve each of the following for $\theta \in [0, 2\pi)$ .

$\sin\theta = \sqrt{3}\cos\theta$ ;
$\sin\theta = \cos 2\theta$ ;
$\sin\theta\cos\theta = \tfrac{\sqrt{3}}{4}$ ;
$2\cos^2\theta - 3\cos\theta + 1 = 0$ ;
$3\sin\theta - \cos^2\theta + 3 = 0$ .

Exercise 1.17.

In a triangle labelled as in the figure of the last chapter, let $\alpha = \tfrac{\pi}{6}$ , $\beta = \tfrac{\pi}{3}$ and $a = 1$ . Compute $c$ .

Exercise 1.18.

Let $F$ be a field. Prove that $0_F \cdot a = 0_F$ and $(-1_F)\,a = -a$ for every $a \in F$ .

Exercise 1.19.

Show that $\{0, 1\}$ with $1 + 1 = 0$ and the usual multiplication is a field, and that no field has exactly three elements in which $1 + 1 = 0$ .

Check Yourself

Fresh questions on the whole lesson — none of them is worked out above. Do each on paper first; the box only tells you whether you got there.

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.