Linear Algebra

Numbering on this page runs in one sequence per chapter, so every definition, theorem, example and exercise here has a number. Where an item also appears in your lecture notes, its number there is given after the name. The two do not always agree, so when you cite something from the notes, quote the number the notes give it.

Course format

• Three lectures per week (2h, 2h, 1h)
• Tutorials every week
• Homework: written submission and online quiz, due 12 noon Wednesday
• Lecture notes and recordings on Blackboard

Dr Rachael Carey is the unit organiser for the first half of the course — watch her announcements on Blackboard.

Assessment

• 10% — quizzes, weeks 2–5 and 8–11. Highest 6 of 8 scores count.
• 90% — final exam, December, written.

Engage with the quizzes and tutorials and you will do well in the exam.

Course content: first six weeks

• $\mathbb{R}^n$
• Vectors and points in $\mathbb{R}^n$
• Matrices
• Finding solution(s) to linear equations
• Determinants
• Linear maps

Where we start

What we study

Flat objects, passing through the origin.

What we don't study

Curved objects. Beautiful, but not linear algebra.

Finding solution(s) to linear equations

Determinants

A determinant is a single number attached to a square matrix. Geometrically it measures signed volume — the volume of the solid whose edges are the columns of the matrix, together with a sign.

Linear algebra is wonderful!

1. You can visualise concepts most of the time

$x = \tfrac{5}{2}$ is an equation, so this is algebra. It is also a point on $\mathbb{R}^1$, so this is geometry.

Another example: $2x = 3$ and $y - x = 1$ are two lines in $\mathbb{R}^2$, meeting at one point, $\left(\tfrac{3}{2}, \tfrac{5}{2}\right)$.

2. It has applications throughout science

• Other parts of mathematics
• Physics
• Data science
• Computer graphics
• Artificial intelligence

Computer graphics

Computer graphics needs vast numbers of linear algebra calculations, all at once. Doing them in parallel is precisely what a GPU is built for.

Artificial intelligence

Nvidia: $+109\%$ by 24 May 2023, then $+24\%$ in one day, adding $\$184$ billion. It ended 2023 up $239\%$. Training an LLM needs vast numbers of matrix calculations.

Let's learn some maths

In maths texts we have: Definition, Theorem, Proposition, Lemma, Corollary, Example, Proof, Exercise, Remark.

Definitions

A definition in mathematics is far more precise than an everyday one: it means exactly what it says — no more and no less.

• Everything that satisfies the properties is an example of the concept.
• Every possible example satisfies all of the properties.
• There is no “sometimes” and no ambiguity — an object either satisfies the definition or it does not.

Theorems and proofs

Theorems, propositions, lemmas and corollaries are all true statements, proved in the notes or as an exercise.

• Theorems and propositions are usually main results: very important results are called theorems, and interesting but perhaps not quite as important ones are called propositions.
• Lemmas are usually more minor or technical results, used to prove later ones.
• Corollaries follow fairly immediately from a previous theorem.

Standard Euclidean $n$-space

We can call the elements of $\mathbb{R}^n$ either points or vectors. So $\mathbb{R}^2$ is the set of all ordered pairs $(x_1, x_2)$ with $x_1, x_2 \in \mathbb{R}$, and we call $\mathbb{R}^2$ the Euclidean plane.

Vector notation

We write an element of $\mathbb{R}^n$ as a row, $x = (x_1, x_2, \dots, x_n)$, or as a column vector. These mean the same thing.

We can encode information in vectors

$(\text{height in cm}, \; \text{left- or right-handed}, \; \text{eye colour as RGB})$, where left-handed $= 1$ and right-handed $= 0$. A right-handed person, $180$ cm tall, with blue eyes:

More examples

Space and time:

And we can keep adding whatever we want to record:

You can assign vectors to words too!

Adding vectors, and multiplying by a scalar

Both operations are component-wise. Note we are not defining the multiplication of two vectors here.

Linear combinations

For $v, w \in \mathbb{R}^n$ and $\lambda, \mu \in \mathbb{R}$, we call $\lambda v + \mu w$ a linear combination of $v$ and $w$. More generally, for $v_1, \dots, v_k \in \mathbb{R}^n$ and $\lambda_1, \dots, \lambda_k \in \mathbb{R}$,

The zero vector

For any $v \in \mathbb{R}^n$ we have $0v = (0,0,\dots,0)$. We write this vector as $\mathbf{0}$, so that $v + \mathbf{0} = \mathbf{0} + v = v$.

In $0v = \mathbf{0}$, the $0$ on the left is the scalar $0 \in \mathbb{R}$, and the $\mathbf{0}$ on the right is the vector $(0,0,\dots,0) \in \mathbb{R}^n$.

Negatives and subtraction

For any $v \in \mathbb{R}^n$, $\;v + (-1)v = \mathbf{0}$, so $(-1)v = -v$. We call $-v$ the negative of $v$, and we write $\;w - v := w + (-1)v$.

Addition and negatives, pictured in $\mathbb{R}^2$.

A useful piece of notation

Example 1.5. In $\mathbb{R}^2$, $e_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ and $e_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$.

Example 1.6. In $\mathbb{R}^3$, $e_1 = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}$, $e_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}$ and $e_3 = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}$.

The dot product

Input: two vectors. Output: a number.

The output can be negative.

Properties of the dot product

The norm

A vector of norm $1$ is a unit vector; $\hat{x} = \dfrac{1}{\|x\|} x$ is the unit vector in the direction of $x$. For $v, w \in \mathbb{R}^n$, $\|v - w\|$ is the distance between $v$ and $w$.

Orthogonal vectors

For example, if $x = (1,1)$ and $y = (1,-1)$ then $x \cdot y = 1 \cdot 1 + 1 \cdot (-1) = 0$, so $x$ and $y$ are orthogonal.

Pythagoras in $\mathbb{R}^n$

The proof is left as an exercise.

The Cauchy–Schwarz inequality

A fundamental property of the dot product is the Cauchy–Schwarz inequality, which relates the dot product of two vectors to their norms.

The two proofs are the same quadratic seen from two sides. The value $t = (x \cdot y)/\|y\|^2$ chosen in the first is exactly the vertex $t = -B/2A$ of the parabola in the second: one evaluates $q$ at its minimum, the other says the parabola never crosses the axis.

You can check this on the four number lines above: drag $x$ and $y$, and compare the value on the $x \cdot y$ line against the product of the $\|x\|$ and $\|y\|$ values. The dot product never escapes that bound.

The norm is the distance from the origin

So the definition has to agree with what "distance" already means on a line, in the plane and in space — and that is what forces the formula, rather than it being an arbitrary choice:

• In $\mathbb{R}^1$ the distance from $0$ to $x$ is $|x|$, so $\|x\| = |x|$.
• In $\mathbb{R}^2$, $x$ and $y$ are the two legs of a right-angled triangle whose hypotenuse runs from the origin to $(x,y)$. Pythagoras gives $\|(x,y)\|^2 = x^2 + y^2$.
• In $\mathbb{R}^3$ apply Pythagoras twice: first in the horizontal plane to the shadow of the vector, then in the vertical triangle standing on that shadow. This gives $\|(x,y,z)\|^2 = x^2 + y^2 + z^2$.

So $\|x\| = \sqrt{x \cdot x}$ is not a new idea — it is the only thing distance could mean, written in coordinates.

Properties of the norm

An application: distance as similarity

This section goes beyond the lecture notes and is not examinable. It is here because it is the shortest honest answer to the question of what a norm is for.

A distance tells you how far apart two things are. If the things are pictures, that is a statement about how alike they look, and almost everything a computer does with images rests on it. The step that makes it possible is turning a picture into a vector.

Suppose the picture is $150$ pixels square. Each pixel carries a red, a green and a blue value, so the whole picture is

numbers, which is to say a single point of $\mathbb{R}^{67500}$. Nothing has been thrown away and nothing has been invented: the picture is that vector, written differently. And once pictures are vectors, $\|x - y\|$ is a number measuring how unlike two pictures are, computed by Definition 1.9 exactly as in the plane.

This is what supervised learning starts from. You are given a pile of pictures already labelled, these are cats and those are dogs, which in vector terms is a pile of labelled points in $\mathbb{R}^{67500}$. A new picture arrives as a new point, and the simplest possible question you can ask is which labelled points it is nearest to.

The picture is drawn in two dimensions because that is what fits on a page, but nothing in the idea depends on that: the same distance, the same comparison, and the same conclusion work in $\mathbb{R}^{67500}$, where they cannot be drawn at all. That is the usual reason for setting a subject up in $\mathbb{R}^n$ rather than in the plane.

The angle between two vectors

The dot product also lets us define the angle between two vectors.

This definition makes sense precisely because of Cauchy–Schwarz. Theorem 1.13 gives $|x \cdot y| \leq \|x\| \, \|y\|$, that is

and every number in $[-1, 1]$ is $\cos \theta$ for exactly one $\theta \in [0, \pi]$. So the angle exists and is unique. If $x$ and $y$ are orthogonal in the sense of Definition 1.11 then $x \cdot y = 0$, so $\cos \theta = 0$ and $\theta = \pi/2$, as expected.

In $\mathbb{R}^2$ one can check that this definition agrees with the geometric way of measuring an angle. The notes leave that as an exercise.

Polar form in the Euclidean plane

A unit vector in the plane is determined by the angle $\theta$ it makes with the $x$-axis, and elementary geometry gives it as

Multiplying it by a positive scalar reaches any non-zero vector of the plane, and the scalar needed is exactly the norm.

In practice one computes $\theta$ from $\arctan(v_2/v_1)$, but the quadrant of $(v_1, v_2)$ decides which value in $[0, 2\pi)$ to take, since $\arctan$ only returns values in $(-\pi/2, \pi/2)$. The converse also holds: given $\theta \in [0, 2\pi)$ and $\lambda \geq 0$ there is a unique vector $v = \lambda \begin{pmatrix} \cos \theta \\ \sin \theta \end{pmatrix}$ of that direction and length.

Complex numbers

The equation \[ x^2 = -1 \] has no solution among the real numbers, because a real square is never negative. So we define a new number $i$ to be a solution of it, $i^2 = -1$, and then take everything we can build from $i$ and the reals.

We write $z = x + iy$ and call $x = \operatorname{Re} z$ the real part and $y = \operatorname{Im} z$ the imaginary part of $z$. What is remarkable is that having added this one new number, every polynomial equation with real or complex coefficients has a solution in $\mathbb{C}$. This is the Fundamental Theorem of Algebra, proved by the great German mathematician Carl Friedrich Gauss in his doctoral thesis of 1799, at the age of 22: every non-constant polynomial with complex coefficients has a root in $\mathbb{C}$. He returned to it throughout his life, giving four proofs in all.

Intuition: $i$ is a quarter turn

Only $-1$ itself. And look at what that does geometrically: it sends the point $1$ to the point $-1$, that is, it turns it through $180^\circ$ about the origin. Multiplying by $-1$ is a half turn.

A quarter turn: $90^\circ$ twice is $180^\circ$. But a quarter turn takes $1$ off the real line altogether. That is exactly what $i$ is. Multiplying by $i$ is a quarter turn, and doing it twice gives $i^2 = -1$, the half turn we started with. The number that had no place on the line is simply the number that lives a quarter turn away from it.

Operations on complex numbers

The multiplication rule is not an extra assumption: it is what you get by multiplying out as usual and then substituting $i^2 = -1$,

A complex number is a pair of real numbers, so we may associate with $z = x + iy$ the vector $v(z) = (x, y) \in \mathbb{R}^2$. This identifies $\mathbb{C}$ with the plane, which we then call the complex plane. Real numbers lie on the $x$-axis and purely imaginary numbers $z = iy$ on the $y$-axis, so these are called the real and imaginary axes.

Conjugation is reflection in the real axis. It turns a product into something real:

so the norm of the vector representing $z$ can be recovered from the conjugate. In the complex setting this is called the modulus of $z$,

This is what makes division work: for $z \neq 0$,

As well as treating complex numbers as vectors in $\mathbb{R}^2$, we can consider vectors whose components are themselves complex.

This is Definition 1.2 again, with $\mathbb{C}$ in place of $\mathbb{R}$. We return to complex vectors later in the course, where working in $\mathbb{C}^n$ turns out to have real advantages over $\mathbb{R}^n$.

The polar form of complex numbers and Euler's formula

To see what multiplication does geometrically it helps to switch to polar coordinates. Take $z = x + iy \neq 0$, with associated point $v(z) = (x,y)$. By Theorem 1.16 we can write $v(z) = \lambda \begin{pmatrix} \cos \theta \\ \sin \theta \end{pmatrix}$, where $\lambda = \sqrt{x^2 + y^2} = |z|$ and $\theta$ is the angle the line from the origin to $(x,y)$ makes with the $x$-axis. In complex notation,

We call $\theta$ the argument (or phase) of $z$. Note that $z = 0$ is special: its argument is not defined.

There is a second route to the same thing, through the exponential. For $z \in \mathbb{C}$ the exponential is defined by the series

which makes sense for complex $z$ because we can take powers and add. (Convergence is not discussed here; the series converges for every $z \in \mathbb{C}$.) We will use that for arbitrary complex $z_1, z_2$,

Putting $\theta = \pi$ into Euler's formula gives $e^{i\pi} = \cos\pi + i\sin\pi = -1$, that is

an identity relating $e$, $i$, $\pi$, $1$ and $0$ in a single line. The series of $(2.1)$ shows it happening: with $z = i\pi$ each term is a step in the complex plane, and the running totals spiral inwards onto $-1$.

In the notation of Theorem 1.16 this says $v(e^{i\theta}) = \begin{pmatrix} \cos \theta \\ \sin \theta \end{pmatrix}$. So every $z \neq 0$ can be written in polar form

where $\lambda = |z|$ is the modulus and $\theta$ the argument. Multiplication now becomes easy: if $z_1 = \lambda_1 e^{i\theta_1}$ and $z_2 = \lambda_2 e^{i\theta_2}$ then, by $(2.2)$,

So multiplying complex numbers multiplies the moduli and adds the arguments. In particular, if $\lambda = 1$ then multiplying by $e^{i\theta}$ is exactly rotation by $\theta$ in the complex plane.

Polar form also makes large powers easy. By $(2.2)$, $(e^{i\theta})^n = e^{in\theta}$ for $n \in \mathbb{N}$, and applying Euler's formula to both sides gives the following.

Trigonometric identities now come for free. Taking $n = 2$ and expanding, $\cos^2\theta + 2i\sin\theta\cos\theta - \sin^2\theta = \cos(2\theta) + i\sin(2\theta)$; real and imaginary parts give

Likewise $e^{i\theta} e^{-i\phi} = e^{i(\theta - \phi)}$, expanded by Euler on both sides, gives

Roots of unity

De Moivre answers a natural question at once: what are the solutions of

Taking moduli, $|z|^n = 1$, so $|z| = 1$ and every solution lies on the unit circle. Writing $z = e^{i\theta}$, the equation becomes $e^{in\theta} = 1$, which holds exactly when $n\theta$ is a whole multiple of $2\pi$. So $\theta = 2\pi k / n$, and there are precisely $n$ distinct solutions,

These are the $n$th roots of unity. They all have modulus $1$ and their arguments are equally spaced by $2\pi/n$, so they sit at the vertices of a regular $n$-gon inscribed in the unit circle, with one vertex at $z = 1$. Multiplying by $\omega_1$ rotates the whole picture by one step round the circle.

Two videos, if you have an evening

Neither is required and neither is examinable. They are here because complex numbers are one of the places where the history and the pictures are worth as much as the algebra.

Where complex numbers actually came from

Not, as it happens, from $x^2 + 1 = 0$. Mathematicians were content to say that equation has no solution and move on. They came instead from the cubic. In the 1500s del Ferro, Tartaglia and Cardano found a formula for solving $x^3 + px = q$, published in Cardano's Ars Magna of 1545, and it had an awkward feature: for some cubics whose roots are all perfectly ordinary real numbers, the formula insists on passing through square roots of negative quantities on the way. The answers are real, but the route is not. Bombelli, in 1572, took the view that one might simply carry those quantities along and let them cancel at the end, which they do. That is closer to how $i$ earned its place than any appeal to $x^2 = -1$: it was useful before it was respectable. The names came later, and the picture later still, the plane we have been drawing on being the work of Wessel, Argand and Gauss around 1800.

Complex transformations, and a hole in an Escher print

This one is harder, and worth it. Escher's lithograph Print Gallery of 1956 shows a man in a gallery looking at a print of a harbour town, which contains the gallery he is standing in. The spiral never quite closes: in the middle of the picture Escher left a blank disc and signed it. In 2003 Lenstra and de Smit, at Leiden, worked out what the missing piece must be, and the tool was complex analysis. The idea connects directly to what we have been doing. Multiplying by a complex number rotates and scales at once, so repeating a rotate-and-scale means multiplying over and over; and the complex logarithm turns multiplying into adding, which straightens Escher's spiral into a flat, repeating grid where the missing piece can simply be read off. The video builds that from the beginning.

Week 2

Linear equations

The simplest linear equation has a single unknown, \[ ax = b, \] where $x$ is the unknown and $a, b \in \mathbb{R}$ are given, with $a \neq 0$. For $2x = 7$ we find $x = 7/2$. Linear means that no powers of $x$, and no more complicated expressions in $x$, are allowed: the equations \[ 3x^5 - 2x = 3 \qquad\text{and}\qquad x + \cos(x) = 1 \] are not linear.

Far more interesting is what happens with more than one unknown. The picture below carries one equation through one, two and three unknowns. Step through the examples with the buttons, or set the coefficients yourself, and watch what the solution set becomes.

So one equation in one unknown has one solution, one equation in two unknowns has a whole line of them, and one equation in three unknowns has a whole plane. Having named the pattern, we can write the general object down.

One warning before we go on. An equation on its own does not determine a solution set: we must also say how many unknowns are in play. The same equation $x = 0$ means three different things in $\mathbb{R}$, in $\mathbb{R}^2$ and in $\mathbb{R}^3$.

Throughout this chapter the coefficients and the solutions are real numbers. Nothing forces that choice: replacing every $\mathbb{R}$ by $\mathbb{C}$ leaves the results of the chapter intact.

A single equation is rarely the whole story: usually several conditions have to hold at once. Asking for a solution then does not mean solving each equation on its own. It means finding one list of numbers $(x_1, x_2, \dots, x_n)$ that satisfies all of the equations at the same time.

In $\mathbb{R}^2$ each equation is a line, and a solution of the system is a point lying on every one of them. Drag the marked points below to move the lines about, and watch the verdict underneath change.

Three outcomes are possible, and the picture shows all three. The lines can meet in a single point, giving exactly one solution; they can fail to share any point at all, giving none; or they can lie on top of one another, in which case every point of that line is a solution and there are infinitely many. We will see later that for a linear system these are the only possibilities.

The same happens one dimension up. In $\mathbb{R}^3$ each equation is a plane, and a solution is a point lying on all of them. Three planes in general position meet in exactly one point.

Matrices

One often looks at the array of coefficients $a_{ij}$ defining a system as an object in its own right.

Matrices with elements in other sets are defined the same way: $M_{m,n}(\mathbb{C})$ is the set of matrices with complex elements. (The plural of matrix is matrices.)

An $m \times n$ matrix has $m$ rows and $n$ columns. Switch between them below.

The same shape of array can hold different kinds of number, and the notation records which:

The last one is square, so we use the shorthand $M_2(\mathbb{R})$ rather than $M_{2,2}(\mathbb{R})$.

Since $\mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$, the same holds for matrices of any fixed shape: an integer matrix is a rational one, a rational matrix is a real one, and so on. So

Writing a matrix by its rows or columns

Besides $A = (a_{ij})$, it is often useful to name the rows and columns and write $A$ in terms of them. If the rows of $A$ are $r_1, r_2, \dots, r_m$ we may write

and if the columns of $A$ are $c_1, c_2, \dots, c_n$ we may write

For the matrix of Example 3.5 this reads

Matrix operations

Addition and multiplication by a scalar are the easy ones: both are done componentwise, and both need the two matrices to have exactly the same shape.

A note on these two: they come much later in your lecture notes than they do here, which is why the numbers they carry there, 3.21 and 3.22, are so far ahead of the ones on this page. The statements are unchanged.

For example,

Addition has a neutral element, just as it does for numbers.

Directly from Definition 3.6, adding it changes nothing: for every $A \in M_{m,n}(\mathbb{R})$,

since $a_{ij} + 0 = 0 + a_{ij} = a_{ij}$ for every entry. The zero matrix plays the role that $0$ plays for numbers.

Multiplication

Multiplication is the interesting one. Two arbitrary matrices cannot be multiplied at all: the shapes have to agree. But when they do, there is a product, and it is the following.

Note the shapes. For $BA$ to be defined at all, the number of columns of $B$ must equal the number of rows of $A$; here both are $m$. The result is $l \times n$: it has as many rows as $B$ and as many columns as $A$.

Two examples. The first uses the matrix of Example 3.5 as its right-hand factor.

The entry in row $1$, column $2$, for instance, is the first row of the left matrix dotted with the second column of the right: $1 \cdot 4 + 0 \cdot 5 + 2 \cdot 6 = 16$. A $2 \times 3$ times a $3 \times 2$ gives a $2 \times 2$. Reversing the order is also allowed here, but gives something of a different shape, a $3 \times 3$. Order matters twice over: the answer changes, and even the shape of the answer changes.

Not every pair can be multiplied at all:

In the second product the left matrix has $2$ columns and the right has $1$ row, and $2 \neq 1$.

A row and a column of matching length can be multiplied in either order, and the two answers could hardly look less alike. One way round gives a single number:

A $1 \times 3$ times a $3 \times 1$ is $1 \times 1$, and a $1 \times 1$ matrix is naturally identified with the number in it. This is just the dot product of $(1,2,3)$ with $(4,5,6)$. Now try the other order.

The identity matrix

Among the diagonal matrices one plays a special role.

It is the neutral element for multiplication, as $0$ is for addition and $1$ is for numbers: for any $m \times n$ matrix $A$,

Note the two different sizes: $I_n$ on the right, $I_m$ on the left. Try it.

Addition, scalar multiplication and the identity all behave much as they do for numbers. The remaining laws of matrix arithmetic are these.

Parts (a) to (c) are Theorem 3.12 of the notes; part (d) is not stated there. The proof is a simple consequence of general properties of linear maps, which we come to later in the course.

The action of a matrix on a vector

As before, we may regard $x \in \mathbb{R}^n$ as a column matrix: an $n \times 1$ matrix with $n$ rows and one column,

Then an $m \times n$ matrix $A$ has $n$ columns and $x$ has $n$ rows, so the product $Ax$ is defined by the definition above, and is an $m \times 1$ matrix, that is, a vector in $\mathbb{R}^m$. Spelled out, that is the following.

Systems of linear equations in matrix form

This is what matrices were for. A system of $m$ linear equations in $n$ unknowns, as in Definition 3.3, is exactly the statement that $A$ sends $x$ to $b$: collecting the coefficients $a_{ij}$ into an $m \times n$ matrix $A$, the unknowns into $x \in \mathbb{R}^n$ and the right-hand sides into $b \in \mathbb{R}^m$, the whole system becomes the single equation

Every statement about systems of equations can now be made about matrices instead. For a worked case, go back to the three planes in $\mathbb{R}^3$ and switch on show the matrix form: the three equations there become one $3 \times 3$ matrix acting on $(x, y, z)$, and turning an equation off drops a row from $A$.

A matrix as a map

The product $Ax$ can be read as a function: it takes a vector, or a point, and returns another one. The shapes say where it sends things. Take

It has two columns, so it eats vectors with two entries, and three rows, so it returns vectors with three. It is a map

Points of the plane are carried to points of space. In particular, as we saw,

the two columns of $A$. Below, drag $v$ around the plane and watch $Av$ move in space.

The map $A : \mathbb{R}^n \to \mathbb{R}^m$ has an important property: it respects addition and scalar multiplication. That is, we may add two vectors and then apply the map, or apply the map to each and then add, and get the same answer.

So the action of a matrix is a linear map, since it respects addition and scalar multiplication. We return to linear maps in general later in the course.

Multiplying matrices composes their maps

The product was defined by a formula. That formula now pays for itself in one line.

Two proofs. The first is a one-line special case of Theorem 3.11; the second is the argument given in your lecture notes, which works with the entries directly.

Matrices and real numbers: what still holds?

Matrix algebra looks like ordinary algebra, and much of it is. But not all. For each statement below, decide whether it holds for matrices, for real numbers, or for both.

The pattern: addition, associativity and distributivity carry over unchanged. What fails is everything to do with order: products need not commute, and a product of non-zero matrices can vanish.

Square, diagonal and triangular matrices

A matrix is a square matrix if $m = n$. If $A = (a_{ij})$ is an $n \times n$ square matrix, the elements $a_{ii}$ are its diagonal elements, and the $a_{ij}$ with $i \neq j$ its off-diagonal elements. A square matrix is a diagonal matrix if all its off-diagonal elements are $0$.

Two more shapes worth naming. A square matrix $A = (a_{ij})$ is

• upper triangular if $a_{ij} = 0$ whenever $i > j$, so the zeros lie below the diagonal, for example $\begin{pmatrix} 1 & 3 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{pmatrix}$;
• lower triangular if $a_{ij} = 0$ whenever $i < j$, so the zeros lie above the diagonal, for example $\begin{pmatrix} 1 & 0 & 0 \\ 5 & 2 & 0 \\ 2 & -7 & 3 \end{pmatrix}$.

Test yourself

Seven questions on the words just defined.

The transpose

Note the shape: an $m \times n$ matrix transposes to an $n \times m$ one. With the matrix of Example 3.5,

The columns of $A$ have become the rows of $A^t$.

Symmetric and skew-symmetric matrices

A square matrix is symmetric if $A^t = A$, and anti-symmetric (or skew-symmetric) if $A^t = -A$. For example

Reflecting in the diagonal leaves the first unchanged and flips the sign of the second. Notice that the diagonal of an anti-symmetric matrix must be zero: $a_{ii} = -a_{ii}$ forces $a_{ii} = 0$.

Every square matrix splits into a symmetric part and an anti-symmetric part:

The transpose and the dot product

One reason the transpose matters is how it interacts with the dot product.

The simplest case is worth stating on its own. A vector $v \in \mathbb{R}^n$ is an $n \times 1$ matrix: one column, $n$ rows. Its transpose $v^t$ is therefore $1 \times n$, a single row. So for $v, w \in \mathbb{R}^n$ the product $v^t w$ is $1 \times n$ times $n \times 1$, which is $1 \times 1$, and a $1 \times 1$ matrix is just a number. Writing it out,

The dot product is a matrix product in disguise: transpose the left vector and multiply. Note the order matters for the shape as well as the meaning. Turning them round gives $v w^t$, an $n \times 1$ times a $1 \times n$, which is a whole $n \times n$ matrix rather than a number.

Two proofs. The first works with the entries directly; the second, which is the one in your lecture notes, uses Theorem 3.17 and never looks at an entry until the last step.

The set of solutions

So far we have only written systems down. Now we ask what their solutions look like, and how to get at them.

First, a name for the thing we are after.

Systems fall into two kinds according to their right-hand side.

A homogeneous system always has at least the solution $x = 0$. An inhomogeneous one need have no solution at all. But as soon as it has one, the homogeneous system determines all the rest: if $Ax_0 = b$ and $Ax = 0$, then

so $x_0 + x$ solves the system as well. Nothing else does.

In words: the general solution of $Ax = b$ is one particular solution of it, plus the general solution of the homogeneous system $Ax = 0$. So the system has exactly one solution precisely when $S(A,0) = \{0\}$, and the set $S(A,0)$ carries all the freedom there is.

Three operations that do not change the solutions

All three are facts about real numbers before they are facts about systems. Take any two equations of the system and write them

where $A, B, C, D, \lambda \in \mathbb{R}$ and each letter stands for one whole side. Then $A - B = 0$ and $C - D = 0$, so

and an equation may be multiplied through by a constant. Since adding zero changes nothing,

so $A + C = B + D$, and equals may be added to equals. Those two together say that a multiple of one equation may be added to another, and the order in which the equations are written plainly makes no difference. Stated for the whole system, they are the three operations below.

Write the system out in full again, as $m$ equations in $n$ unknowns:

Three things may be done to this list without changing which $x$ satisfy it:

1. multiply an equation by a non-zero constant;
2. add a multiple of one equation to another equation;
3. exchange two of the equations.

That (i) and (iii) change nothing is clear. For (ii), suppose $x$ solves the system, and form a new system by adding $\lambda$ times equation $i$ to equation $j$. Then $x$ solves the new system too. Conversely, if $x'$ solves the new system, subtracting $\lambda$ times equation $i$ from equation $j$ returns the original system, so $x'$ solves that one as well. The two systems therefore have exactly the same solutions.

The augmented matrix is a device for bookkeeping: each column belongs to one unknown, each row to one equation, and the right-hand side travels in the last column instead of being tracked separately. Every step taken on the equations is then a step on the rows of this one array, so nothing is dropped or double-counted on the way to the solutions.

These have names. The three operations themselves are the elementary row operations of Definition 3.23. The procedure is called Gaussian elimination, or Gauss–Jordan elimination. Both forms are defined in Definition 3.25 below, and Theorem 3.26 says the reduction can always be carried out.

To see an augmented matrix being built, go back to the three planes in $\mathbb{R}^3$ and switch on show the augmented matrix: turning an equation off drops a row, and the last column is always the right-hand side.

The three operations on equations now read as three operations on the rows of that matrix.

This is what makes the goal above reachable. Elementary row operations may be applied as often as we like and in any order, and the solution set never moves, so we are free to keep simplifying until the solutions can be read straight off.

Two forms matter in all of this, and they have names. They are the shapes we row-reduce towards, and everything below is about reaching them and reading the answer off.

Leading 1s are also sometimes called pivots. In the walk-throughs further down, the first of which is Example 3.30 in the notes, row echelon form is reached at step 5, and then at steps 4, 3, 3 and 3 for the four that follow; that is the point at which each one's verdict can be read off. Reduced row echelon form comes at the last step of every example except the one with no solution, which stops at row echelon form because its final row already reads $0 = 1$.

Try it: RREF or not?

Reading the three conditions is one thing; spotting them is another. Each matrix below is either in reduced row echelon form or fails exactly one of the conditions. Decide which, as quickly as you can.

Two things are worth knowing before working through the examples: that this can always be done, and what the procedure is called.

Solving a system by row operations

Theorem 3.26 says the reduction can always be carried out, and Theorem 3.24 says the solutions never move while we carry it out. Between them we are free to keep applying row operations until the answer can be read off. The first example below is Example 3.30 in the notes, worked one operation at a time. The others are a system with no solution at all, one with a whole line of solutions, one with a whole plane of them, and one in four unknowns, so that every outcome a system can have appears in the same setting.

The walk-throughs all ended by reading the answer off the last matrix. That reading is a theorem.

Each case has already appeared above. The no-solution example ended with a row reading $0 = 1$, which is a leading 1 in the last column. The one-solution example ended with a leading 1 in every column but the last. The two with infinitely many ended with fewer leading 1s than unknowns: one short gives a line, two short give a plane, and $n - k$ short gives $n - k$ unknowns to choose freely, which is why the example in four unknowns had a plane of solutions with $k = 2$.

Try it: $A$ acting on the standard vectors

Throughout these exercises, let

Now try the same trick on the other side. Note the shapes first: $A$ is $3 \times 2$, so it takes a $2$-vector on the right, but on the left it takes a row of length $3$.

In short, $A e_j$ is the $j$th column of $A$ and $e_i^t A$ is the $i$th row. Now put the two column answers together.

Reveal the steps one at a time.

The general case

Nothing above depended on the particular numbers. Write $e_i \in \mathbb{R}^n$ for the vector with a $1$ in the $i$th entry and $0$ everywhere else,

Then the same check works for any matrix at all.

The same three steps, with $n$ in place of $2$.

A matrix acting on a matrix, column by column

We have seen that $Ae_j$ is the $j$th column of $A$, and that $Ax$ is the linear combination of the columns of $A$ with the entries of $x$ as coefficients. There is one more thing of this kind worth knowing, and it is the most useful of the three. Suppose we have three vectors $v_1, v_2, v_3 \in \mathbb{R}^n$ and we lay them side by side as the columns of a matrix, which we write $\begin{pmatrix} v_1 & v_2 & v_3 \end{pmatrix}$. What happens if we multiply that by $A$?

Take it slowly. By the definition of the product, column $j$ of $A \begin{pmatrix} v_1 & v_2 & v_3 \end{pmatrix}$ is $A$ times column $j$ of $\begin{pmatrix} v_1 & v_2 & v_3 \end{pmatrix}$, and column $j$ of that is just $v_j$. So column $j$ of the answer is $Av_j$, and nothing else is going on.

The two columns below the product are $Ab_1$ and $Ab_2$, where $b_1 = \begin{pmatrix} 1 \\ 3 \end{pmatrix}$ and $b_2 = \begin{pmatrix} 2 \\ 4 \end{pmatrix}$ are the columns of $B$. They are not a second calculation: they are the two columns of $AB$, written out on their own. That is Exercise 3.30 in numbers.

Rows, columns, and single entries

Collecting what we now have, all of it the same rule read in different directions.

Multiplying by a standard vector picks out one row. Multiplying by a cleverer matrix can do something to every row at once, which is the next thing to look at.

Elementary operation matrices

Each of the three elementary row operations can be carried out by multiplying on the left by a single matrix, obtained by doing that very operation to the identity. Those matrices have a name.

All three have a general form. Blanks below are zeros, and a box marks every entry the operation changed.

Now some questions, with a different $A$: a matrix of plain letters, so that the answers cannot depend on a lucky choice of numbers. For the rest of this section let

Start by swapping. Let

the identity with its first two rows swapped.

Next, scale a row. Let

the identity with $\lambda$ in place of the $1$ in row $2$. Multiplying $A$ on the left by it multiplies row $2$ of $A$ by $\lambda$ and leaves the other two rows alone:

Row $i$ of $E_2(\lambda) A$ is row $i$ of $E_2(\lambda)$ combined with the rows of $A$. Rows $1$ and $3$ of $E_2(\lambda)$ are $e_1$ and $e_3$, so they hand back rows $1$ and $3$ of $A$ unchanged, while row $2$ is $(0, \lambda, 0)$, which hands back $\lambda$ times row $2$ of $A$.

One more. Let

the identity with $\lambda$ placed in row $2$, column $1$.

You can see all three of these operations in action, applied one at a time to a real system, in the interactive walk-through above: each step names the operation it applies and shows the matrix before and after it.

And what does a diagonal matrix do?

Now put a diagonal matrix beside the same $V$. Take the three columns in $\mathbb{R}^3$, so that $D$ fits on either side of $V$, and give them letters of their own, $v$, $w$ and $z$. That leaves the subscripts free to count entries down a column, which is what we want to watch. Write

Here the side matters, and this is worth pausing over, because it is the thing most people get backwards the first time. Multiplying on the left by $D$ scales the rows: row $i$ of $DV$ is $\lambda_i$ times row $i$ of $V$. Multiplying on the right by $D$ scales the columns:

If that seems arbitrary, look at where each entry has to come from. Column $j$ of $VD$ is $V$ times column $j$ of $D$, and column $j$ of $D$ is $\lambda_j e_j$. So column $j$ of $VD$ is $V(\lambda_j e_j) = \lambda_j (V e_j)$, which is $\lambda_j$ times the $j$th column of $V$. The $\lambda_j$ attaches to the $j$th column because it sits in the $j$th column of $D$.

Block matrices, and why a GPU can help

This last part is here because it explains the picture of Nvidia near the top of the page, and because it costs nothing once you have matrix multiplication.

A matrix may be cut into blocks by drawing lines between whole rows and whole columns. Write $A$ and $B$ each as four blocks,

Now the remarkable part: the blocks multiply exactly as single entries would.

Nothing about this depends on the matrices being $4 \times 4$, or on the cut falling in the middle. Take any $A \in M_{m,n}(\mathbb{R})$ and split its rows as $m = m_1 + m_2$ and its columns as $n = n_1 + n_2$, wherever you like:

so that $A_{11}$ is $m_1 \times n_1$, $A_{12}$ is $m_1 \times n_2$, $A_{21}$ is $m_2 \times n_1$ and $A_{22}$ is $m_2 \times n_2$.

For the $A$ and $B$ above this gives

which is indeed the top-left corner of

Two special cases have already appeared on this page. Cutting $A$ into its columns and leaving $B$ whole is the statement that $Ae_j$ is the $j$th column; cutting into rows is the statement that $e_i^t A$ is the $i$th row. Those are block multiplication with blocks one column, or one row, wide.

Why this suits a GPU

This goes beyond the lecture notes and is not examinable.

Look at where each block of $AB$ comes from. The block $C_{11}$ needs only the top band of $A$ and the left band of $B$; $C_{22}$ needs only the bottom band and the right band. No block of the answer needs any other block of the answer. All four can therefore be computed at the same time, by four workers that never speak to one another, and the same is true if the matrix is cut into a thousand blocks instead of four. This is the sense in which matrix multiplication is parallel by nature, and it is why a processor with thousands of small cores beats one with a few fast ones on this particular job.

There is a second reason, and it is about memory rather than arithmetic. Multiplying two $n \times n$ blocks takes about $2n^3$ arithmetic operations but touches only about $3n^2$ numbers. The ratio $2n/3$ grows with $n$, so a larger tile does more arithmetic for each number fetched:

Fetching a number from a GPU's main memory costs far more than multiplying two numbers already in hand, so the winning strategy is to copy a tile of $A$ and a tile of $B$ into the small fast memory shared by a group of threads, wring all the arithmetic out of them there, and only then go back for the next tile. That is exactly what a tiled matrix-multiply kernel does, and choosing the tile size is choosing a point in the table above.

Week 3

Inverting a matrix

Hide the clip

We ended with a question: an elementary row operation can be undone, so the matrix that performs it ought to have a matrix that undoes it. Which matrix is that, and which matrices in general have one? That is the rest of this chapter.

Writing $A^{-1} = B$ takes something for granted: that there is only one such $B$ to name. Lemma 3.38 below is what entitles us to the notation.

The definition has a practical drawback. It asks whether some matrix $B$ exists, and there are infinitely many candidates, so it tells you nothing about how to look. The next theorem repairs that. It says the question is settled by row reduction, which is a procedure you can actually carry out: reduce $A$ and see whether you reach the identity.

Three lemmas first. The proof of the theorem needs all three, and each is worth knowing on its own.

Here are the three, as $2 \times 2$ matrices. In each case the inverse is simply the matrix of the operation that undoes it, and you can check the claim by multiplying the pair together:

The first is its own inverse, because swapping twice gets you back where you started. The second needs $\lambda \neq 0$, which is exactly the condition the row operation came with. The third adds $\mu$ times the second row on, and then takes it off again.

The word square in that lemma is not decoration. Drop it and the conclusion goes. Take

Both give $B_1 A = B_2 A = I_2$, and $B_1 \neq B_2$: the third column of each is multiplied by the third row of $A$, which is zero, so it may be anything at all. A left inverse here is not unique. What is missing is the other half of the hypothesis, and it cannot be supplied: no $C \in M_{2,3}(\mathbb{R})$ has $AC = I_3$, because the third row of $A$ is zero, so the third row of $AC$ is zero too, and $I_3$ has a $1$ there. For a square matrix the two halves always arrive together, which is what makes the lemma bite.

So the magic happens exactly when $A$ is square. That is the essence of Theorem 3.36: for a square matrix, and only for a square matrix, undoing from one side and undoing from the other are the same demand, and row reduction to the identity settles both at once.

Now the theorem.

We have already used this, before stating it. In the proof of Theorem 3.36 the two displays read $A = E_1^{-1} E_2^{-1} \cdots E_k^{-1}$ and $A^{-1} = E_k E_{k-1} \cdots E_1$. Putting those side by side says exactly that

which is Lemma 3.40 applied $k - 1$ times over: the inverse of a product is the product of the inverses, in the opposite order. Peeling the elementary matrices off one at a time, as the proof did, is that statement being built up a factor at a time.

Computing the inverse

Theorem 3.36 tells you whether a matrix is invertible, and its proof quietly tells you what the inverse is: the product of the elementary matrices used along the way. Forming that product would be tedious. We obtain it for nothing instead, by a procedure that is very easy to understand once you have watched it work on a single number.

What is the inverse of $5$? It is $\tfrac{1}{5}$. Now write the number down with a $1$ beside it, and multiply the whole array by $\tfrac{1}{5}$:

The left slot has become $1$, which is what we were trying to arrange. The right slot has become $\tfrac{1}{5}$, which is the inverse. That $1$ we put there at the start did nothing of its own: it kept a record. Whatever multiplied the left half multiplied the right half too, so at the moment the left reaches $1$, the right is holding precisely the number that got it there.

Matrices behave in the same way. Apply an elementary matrix $E$ to the array $\left(\begin{array}{c|c} A & I \end{array}\right)$, and because the product can be taken block by block,

Every operation therefore hits both halves at once. Keep going until the left half has been reduced to the identity, say $E_k E_{k-1} \cdots E_1 A = I_n$. The right half is then $E_k E_{k-1} \cdots E_1 I_n$, the very same product, which by the Fact of life is $I_n$ with those same operations applied to it. So the right-hand side has been keeping track of the matrices the whole time, and what it has been keeping track of is $A^{-1}$.

That gives a procedure, the Gauss–Jordan method for inverting a matrix. The trick is to do both jobs in one pass, by writing $A$ and $I_n$ side by side in a single $n \times 2n$ array and reducing the whole thing at once.

Write the array and reduce. Swapping first keeps every entry a whole number:

The left half is $I_2$, so $A$ is invertible and the right half is the inverse:

It costs nothing to check, and you should: $A A^{-1} = A^{-1} A = I_2$.

The top-left entry is $0$, so the first operation has to be a swap:

The left half is $I_3$, so

The last two operations were done together because they act on different rows and neither uses the other's result. Doing them one at a time gives the same answer.

One operation is enough to settle it:

Stop there and answer two questions before reading on.

Determinants

The determinant is a function. It takes one square matrix and returns one real number,

so $\det A$ is a single number carrying something about the whole of $A$. The question worth asking straight away is what that number measures.

Here is the answer, and it is geometric. An $n \times n$ matrix is $n$ rows, and each row is a vector of $\mathbb{R}^n$; equally it is $n$ columns, each also a vector of $\mathbb{R}^n$. Either way we have $n$ vectors in $\mathbb{R}^n$, and $n$ such vectors span a parallelepiped: the solid of all sums $t_1 a_1 + \cdots + t_n a_n$ with every $t_i$ between $0$ and $1$. In two dimensions that is a parallelogram, in three a slanted box. The absolute value $|\det A|$ is the volume of that solid.

Rows or columns? It makes no difference. We shall prove later that

and transposing is exactly what turns the rows of $A$ into the columns, so the two readings give the same number. Having said that, we have to pick one to write the definitions with, and we shall take the rows.

The definition itself does not start from volume. It starts from three properties that the volume plainly has, and it turns out that those three properties pin down exactly one function. Here they are for $2 \times 2$ matrices, where the solid is a parallelogram and its volume is an area.

Each condition says something you would want of an area. Multilinearity says that stretching one row by $\lambda$ stretches the figure by $\lambda$ in that direction. Normalisation fixes the unit: the square on $e_1$ and $e_2$ has area $1$, so the function is measuring in those units and not some multiple of them. The alternating condition is the one that looks least like area, and it is the reason the answer carries a sign: it records which way round the two rows sit, and swapping them reverses that. The picture below is the place to meet it.

Two things are worth trying in it. Put the two rows on top of one another, or more generally make one a multiple of the other, and the parallelogram collapses to a segment of zero area: the determinant is $0$ exactly when the two rows lie on a single line through the origin. And move one row across the other and watch the sign change as it passes, going through $0$ on the way. A determinant of zero is not a small determinant; it is a flat one.

The determinant of an $n \times n$ matrix

Nothing in the three conditions is special to two rows. Written for $n$ rows they read as follows, and this is the definition the rest of the chapter rests on.

The notes follow the definition with a picture, and here it is for $n = 3$. Three rows span a slanted box, a parallelepiped, and $d_3(a_1, a_2, a_3)$ is its volume with a sign.

There is only one determinant

A definition can ask for more than anything delivers. Definition 4.2 asks for a function with three properties, and two questions follow at once: is there such a function at all, and could there be more than one? Both get the best possible answer.

So the three properties determine the function completely, and we can give it a name. For $A \in M_n(\mathbb{R})$ with rows $a_1, \dots, a_n$ we write

and call this number the determinant of $A$. The proof of Theorem 4.3 comes later in the chapter, once four lemmas about row operations are in place. First, here is the theorem at work for a single $2 \times 2$ matrix.

Nothing in those six steps used the particular numbers. Run them again on $A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$, whose rows are $a_1 = a_{11} e_1 + a_{12} e_2$ and $a_2 = a_{21} e_1 + a_{22} e_2$, and they give

So any 2-determinant function must be $a_{11} a_{22} - a_{12} a_{21}$, and there is at most one. Conversely this formula does have all three properties: it is linear in each row, it changes sign when the two rows are exchanged, and it gives $1$ at the identity. So there is exactly one, and for $n = 2$ that is Theorem 4.3 in full. The same idea, run with $n$ rows, is Proof 2 of the theorem further down.

Row operations and the determinant

The proof of Theorem 4.3 runs on four facts about what row operations do to a determinant function. Each follows from the three properties alone, so each holds for every function with those properties. That is exactly what the proof needs, since it has to work before we know that there is only one such function. In the four lemmas $d$ is any $n$-determinant function, and for $A \in M_n(\mathbb{R})$ we write $d(A)$ for its value on the rows of $A$.

Try a few $2 \times 2$ cases before reading the general statement.

With the four lemmas in hand, here is the proof of Theorem 4.3, twice. The first uses row reduction and the lemmas just proved; the second is the argument given in the notes.

The same decomposition gives the most useful property of the determinant almost for free.

Understanding the Leibniz formula

Proof 2 of Theorem 4.3 ended with the Leibniz formula. Here it is built by hand, first for a general $2 \times 2$ matrix and then for a general $3 \times 3$ one, by multilinearity alone, one row at a time. Once every row has been split, each term is a number times the determinant of a matrix whose rows are standard vectors. Either two of those rows are equal, and the determinant is $0$; or the rows are $e_1, \dots, e_n$ in some order. A matrix of the second kind is a permutation matrix. Exchanging its rows brings it to $I_n$, so by the alternating property and normalisation its determinant is $1$ or $-1$, according as the number of exchanges is even or odd.

A $2 \times 2$ matrix. Write the rows as $a_1 = a_{11} e_1 + a_{12} e_2$ and $a_2 = a_{21} e_1 + a_{22} e_2$.

Step 1, the first row. Multilinearity in the first row splits it into its two parts:

Step 2, the second row, split in the same way in each of the two terms:

Step 3, what is left. The first and the last matrix have two equal rows, so they give $0$. The other two are the two permutation matrices of size $2$: $I_2$, with determinant $1$, and $I_2$ with its rows exchanged, with determinant $-1$. So

Each term that survives takes one entry from each row, no two from the same column, and its sign is the determinant of the permutation matrix that records which columns were taken.

A $3 \times 3$ matrix. The same three steps, now with $a_i = a_{i1} e_1 + a_{i2} e_2 + a_{i3} e_3$ for $i = 1, 2, 3$.

Step 1, the first row, gives three terms:

Step 2, the second row. Each of the three terms splits into three more, nine in all. The first, for instance, gives

and its first term is $0$ already, since its first two rows are equal, whatever the third. In the same way, of the nine terms the three whose first two rows are the same standard vector vanish, and six are left.

Step 3, the third row. Each of the six splits into three once more, and of each three only one survives: the one whose third row is the standard vector the first two rows have not used. That leaves six terms, one for each permutation matrix of size $3$:

Now count the exchanges of rows that bring each permutation matrix to $I_3$: none for the first; one for the second, the third and the last; two for the fourth and the fifth. So their determinants are $1, -1, -1, 1, 1, -1$, and

which is formula (4.4) in the notes, with its terms in a different order.

That $\pm 1$ has a name. For a rearrangement $\sigma$ of $\{1, \dots, n\}$, the sign of $\sigma$ is

where $k$ is the number of exchanges of rows that bring the permutation matrix of $\sigma$ to $I_n$. What the count above shows is that the determinant of a permutation matrix is the sign of the permutation its rows record. Nothing but the alternating condition is at work: each exchange of two rows multiplies the determinant by $-1$, and after $k$ of them the matrix is $I_n$, whose determinant is $1$. Running that backwards, the determinant we started with was $(-1)^k$.

There is one thing to be careful of in that definition. The number $k$ is not determined by $\sigma$: having arrived at $I_n$ you may exchange two rows and exchange them straight back, which adds $2$ to the count, so there are routes of every length. What has to be true for the definition to mean anything is that all of them have a $k$ of the same parity. A permutation is then called even or odd accordingly, and its sign is $+1$ or $-1$.

It is tempting to read that off the determinant: every route computes $\det P_\sigma$, which is one number, so every route must give the same parity. As an argument here it goes in a circle, and it is worth seeing why. The page gets the existence of a determinant function from the Leibniz formula in Proof 2 of Theorem 4.3, and that formula cannot even be written down until $\operatorname{sign}(\sigma)$ is known to be well defined. So the independence of $k$ has to be proved first and by other means, which is the point that proof flagged as needing a little group theory. Granted it, the determinant does give the statement back, and that is a good way to remember which permutations are even and which are odd.

Any $n$. For an $n \times n$ matrix the same steps split $\det A$ into $n^n$ terms, one for each way of choosing a column in every row. A choice that uses some column twice gives two equal rows, and its term is $0$. A choice that uses every column once is a rearrangement $\sigma$ of $\{1, \dots, n\}$, and its term is $a_{1\sigma(1)} a_{2\sigma(2)} \cdots a_{n\sigma(n)}$ times the determinant of the permutation matrix with rows $e_{\sigma(1)}, \dots, e_{\sigma(n)}$, which is $\operatorname{sign}(\sigma) = \pm 1$. So

the Leibniz formula of Proof 2 of Theorem 4.3. It has $n!$ terms: $2$ for $n = 2$, $6$ for $n = 3$, and already $24$ for $n = 4$, which is why the next subsection looks for a better way to compute.

Week 4

Computing determinants

Recall how the three elementary row operations change the determinant (Lemma 4.6), and how they change the volume of the box spanned by the rows:

With these three facts you can show that the volume of the box spanned by the rows of $A$ is $|\det A|$: row reduce $A$, and follow both columns of the table at once.

The three properties pin the determinant down, but they are not a practical way to calculate it: Example 4.4 took six steps for a $2 \times 2$ matrix. The method used in practice turns one $n \times n$ determinant into $n$ determinants of size $n - 1$. For $A \in M_n(\mathbb{R})$ write $\hat{A}_{ij}$ for the $(n-1) \times (n-1)$ matrix obtained from $A$ by deleting row $i$ and column $j$. Its determinant $\det \hat{A}_{ij}$ is called the minor of the entry $a_{ij}$, and $(-1)^{i+j} \det \hat{A}_{ij}$ its signed minor (Definition 4.14 in the notes).

In the picture below you choose the row or the column, and the first step of the expansion is written out for you. It opens on the matrix of Example 4.18 in the notes.

Where the chessboard sign comes from

The Laplace expansion of Theorem 4.11 carries a factor $(-1)^{i+j}$ in front of every minor, and so far it has simply been part of the statement. It has a reason, and the reason is two steps: one lemma about a matrix with a $1$ in the corner, and a count of how far an entry has to travel to get to that corner.

Now take a matrix whose entry in position $(i, j)$ is $1$, with the rest of row $i$ and the rest of column $j$ all zero. Lemma 4.12 applies to it the moment that $1$ sits in the top left corner, so the question is what it costs to put it there. Move it up one row at a time and then left one column at a time: that is $i - 1$ exchanges of neighbouring rows and $j - 1$ of neighbouring columns, and each exchange turns the sign of the determinant over. So

since $(-1)^{-2} = 1$. That is the chessboard sign, and the picture below is the count.

Two consequences follow at once, and the second is less obvious than it looks.

The determinant of the transpose

At the start of the chapter we chose to write the definitions with rows, and promised that columns would have done just as well. Here is that promise kept. It is also what lets Theorem 4.11 expand by a column as freely as by a row.

So everything this chapter has said about rows holds for columns as well: a zero column gives determinant $0$, exchanging two columns changes the sign, and adding a multiple of one column to another changes nothing. That is the form in which the notes state these facts.

Three ways of saying the same thing

The determinant was introduced as a volume. The next exercise is where it becomes a test: one number that decides whether a matrix can be undone, and whether a system has an answer.

The determinant of a triangular matrix

Let us understand why the determinant of an upper or lower triangular matrix is the product of its diagonal entries. Start with the upper triangular matrix

Row 1 already has a $1$ on the diagonal, with zeros below it. By multilinearity we can factor $4$ out of row 2, which leaves a $1$ on the diagonal there:

Now use that $1$ to make the other entries of its column zero. Only the $2$ in row 1 is in the way, and $R_1 \to R_1 - 2R_2$ clears it. Remember that adding a multiple of one row to another row does not change the determinant (Lemma 4.6):

Similarly for the last row: factor $6$ out of it, and use the $1$ it leaves to clear its column, by $R_1 \to R_1 - \tfrac{1}{2} R_3$ and $R_2 \to R_2 - \tfrac{5}{4} R_3$:

since $\det I_3 = 1$. So $\det A = 1 \cdot 4 \cdot 6$, the product of the entries on the diagonal, and the entries $2$, $3$ and $5$ above it play no part. This is always so.

The determinant is not additive

The adjugate, and Cramer's rule

This last section is non-examinable, as it is in the notes. It is here because it answers a natural question: the determinant decides whether a matrix can be inverted, so can it also say what the inverse is? It can, by a formula, and the same idea then solves $Ax = b$ outright.

Recall from the Laplace expansion that $\hat{A}_{ij}$ is the matrix left when row $i$ and column $j$ are deleted, and that $A_{ij} := (-1)^{i+j} \det \hat{A}_{ij}$ is the signed minor. Collect all $n^2$ of them into one matrix and transpose it.

Everything rests on one identity, which is the Laplace expansion read twice over. The explicit formula for an inverse then drops straight out of it, so the two are gathered into a single theorem. Both parts are left to you, as is Cramer's rule just after it. There is a hint for the first part and one for Cramer's rule; the second part has neither, and is the better for it once you have the first. Written proofs will be added here in a couple of weeks, so there is time to try them.

The same identity solves a system outright. This is Cramer's rule.

The cross product

One more thing the determinant gives us, and it is the last of this chapter. Expanding a $3 \times 3$ determinant along its first row produces, alongside the entries of that row, three signed minors built from the other two. Reading those three minors as the components of a vector turns the expansion into a dot product, and that vector is what we are about to name. Write the three rows as $x$, $y$ and $z$.

There is a third way of writing it, and it is the one most people carry around. Give the standard vectors of $\mathbb{R}^3$ their traditional names,

so that $i = e_1$, $j = e_2$ and $k = e_3$. Then

meaning: expand along the first row, exactly as in the Laplace expansion, and collect the result. That gives

which is Definition 4.20 again, the minus in the middle being the chessboard sign $(-1)^{1+2}$. Example 4.21 reads $-19 i - 13 j + 4 k$ in this notation.

Strictly this is a mnemonic rather than a determinant. The top row holds vectors and the other two hold numbers, so the array is not a matrix in $M_3(\mathbb{R})$ and $\det$ has not been defined for it. What is meant is only the expansion written out above. It is worth keeping because it is almost impossible to misremember: the signs and the pairs of indices look after themselves.

The expansion we started from now reads

which is formula (4.8) in the notes. Almost everything below follows from it together with what this chapter has already proved about determinants.

Part (iii) is the one to hold on to: $x \times y$ is perpendicular to both $x$ and $y$, so it points along the normal to the plane they span. Part (iv) fixes how long it is. Writing $\theta$ for the angle between $x$ and $y$, and using $(x \cdot y)^2 = \|x\|^2 \|y\|^2 \cos^2 \theta$, part (iv) becomes

so $\|x \times y\| = \|x\| \|y\| |\sin \theta|$. Perpendicular to the plane, with that length: the only thing still undecided is which of the two directions along the normal it takes.

The right hand rule. That last choice is what the right hand rule settles, and it is worth getting straight. Let $n$ be the unit vector perpendicular to both $x$ and $y$ chosen like this: point the thumb of your right hand along $x$ and your index finger along $y$; your middle finger then points along $n$. The rule is not a convention about the formula, it is a reading of it, and the quickest way to check you have it the right way round is on the standard vectors:

Thumb along $e_1$, index along $e_2$, middle finger up: that is $e_3$. Swap the two and your middle finger points down, which is the antisymmetry of part (i) in your hand. The same rule gives $e_2 \times e_3 = e_1$ and $e_3 \times e_1 = e_2$, so the three standard vectors cycle.

Two consequences are worth naming. From part (v), the cross product is not associative: in general $(x \times y) \times z \neq x \times (y \times z)$. What replaces associativity is the Jacobi identity,

which part (v) gives after a short computation.

And the three products of this course now have three geometric readings, which is a good place to stop:

• $x \cdot x$ is the square of the length of $x$;
• $\|x \times y\|$ is the area of the parallelogram spanned by $x$ and $y$;
• $x \cdot (y \times z)$ is the signed volume of the parallelepiped spanned by $x$, $y$ and $z$, which is where this chapter began.

Revision: questions from past exam papers

These four are taken from a past MATH10015 paper, with the numbers changed a little. Work them before opening anything. Each one has a hint, which is only the definition or formula you need, and then a full solution.

One more, not from a past paper: a fact from Chapter 3, proved again with what this chapter adds.

Vector spaces, subspaces, and spans

Until now every scalar has been a real number. Yet all that the rules for vectors ever asked of the real numbers was how they add and multiply, so any number system that adds and multiplies the same way can supply the scalars instead. Such a system is a field: fields are where scalars come from.

A field has two operations, and each of them makes a group, in the following sense.

A field is a set with two operations, addition and multiplication. Each makes a commutative group, addition on the whole set and multiplication on the set without $0$, and the two operations interact through the distributivity property.

Fields are where the scalars come from; $V$ is where the vectors come from.

Write $(A \mid I)$ and row reduce, exactly as over $\mathbb{R}$, now with complex scalars:

In the first step $2 - i \cdot i = 2 + 1 = 3$, and in the last $1 - i \cdot \left(-\tfrac{i}{3}\right) = 1 - \tfrac{1}{3} = \tfrac{2}{3}$. The left half is $I_2$, so

and multiplying out, $A A^{-1} = I_2$.

Row reduce the augmented matrix to reduced row echelon form:

In the last step $-1 - 3i$ is $-1 - i \cdot 3$, and $1 - i$ is $0 - i(1 + i)$. This is reduced row echelon form. To read the solutions off, keep the unknowns carrying a leading 1 on the left-hand side and take every other unknown across to the right. The leading 1s are in the $x$ and $y$ columns, so $x$ and $y$ stay and $z$ crosses over: $x = 1 - i + (1 + 3i) z$ and $y = 1 + i - 3z$. Now $z$ may be chosen freely in $\mathbb{C}$, and writing the solutions as a set gives

Definition 5.2 is all we may assume about a vector space, so even facts that look obvious in $\mathbb{R}^n$ have to be proved from it. Here are four that we will use all the time.

Subspaces

Given a vector space, the natural next question is which of its subsets are vector spaces in their own right, with the same addition and the same scalar multiplication.

Checking all twelve properties of Definition 5.2 for a subset would be slow. Three checks are enough.

We call $S(A,0)$ the kernel of $A$. In words: the homogeneous system $Ax = \mathbf{0}$ always has the solution $x = \mathbf{0}$, the sum of two solutions is a solution, and a multiple of a solution is a solution.

The same holds over any field: for $A \in M_{m,n}(\mathbb{K})$, $S(A,0)$ is a $\mathbb{K}$-linear subspace of $\mathbb{K}^n$.

The span of a set of vectors

This is Chapter 5 material, brought forward because the picture is worth meeting alongside the definition.

Given some vectors in $\mathbb{R}^n$, their span is everything you can build from them using only the two operations you have: adding, and scaling.

Week 5

Sums and intersections of subspaces

Given two subspaces of the same vector space, we can combine them to make a new subspace.

The union $U \cup V = \{ w \in W : w \in U \text{ or } w \in V \}$ is, in general, not a subspace. In $\mathbb{R}^2$, let $L_1$ and $L_2$ be two different lines through the origin, and take $u \neq \mathbf{0}$ on $L_1$ and $v \neq \mathbf{0}$ on $L_2$. Both lie in $L_1 \cup L_2$, but $u + v$ does not. Two different lines through the origin meet only at $\mathbf{0}$. If $u + v$ were on $L_1$, then $v = (u + v) - u$ would be on $L_1$ as well as on $L_2$, so $v = \mathbf{0}$, which it is not; in the same way, $u + v$ is not on $L_2$. So $L_1 \cup L_2$ is not closed under addition. The picture below shows this. When the two lines are the same, the union is just that line, which is a subspace.

Another useful notion is the direct sum, which asks more than the sum of Theorem 5.21.

In the picture above, while the two lines are different, $L_1 \cap L_2 = \{\mathbf{0}\}$ and $L_1 + L_2 = \mathbb{R}^2$, so $\mathbb{R}^2 = L_1 \oplus L_2$. With $L_1$ the $x$-axis and $L_2$ the $y$-axis this is Example 5.30 in the notes. When they are the same, $L_1 + L_2 = L_1$, but $L_1 \cap L_2 = L_1 \neq \{\mathbf{0}\}$, so that sum is not direct.

If $V$ is the sum of $V_1$ and $V_2$, every element of $V$ is an element of $V_1$ plus an element of $V_2$. If the sum is direct, this can be done in only one way.

Linear independence, bases and dimension

We have met dimension informally, thinking about objects in two or three dimensions. We now begin to make it precise for subspaces, by asking how a subspace can be built from linear combinations of as few vectors as possible. Throughout this chapter $\mathbb{K}$ is a field.

Linear dependence and independence

One way to describe a vector space $V$ is to choose vectors $v_1, v_2, \dots, v_k \in V$ that span it, $V = \operatorname{span}\{v_1, v_2, \dots, v_k\}$. To do this efficiently we want as few vectors as possible. If one of them is a linear combination of the others it is redundant, and this leads to the following definition.

In each of the next four examples, $A$ is the matrix whose columns are the given vectors, each column in the colour of its vector, and the augmented matrix $(A \mid \mathbf{0})$ is already in reduced row echelon form.

Bases

We have built spaces from sets of vectors by taking their span, and linear independence now gives us a way to avoid any redundancy in our choice of vectors in a spanning set. First, a connection between linear dependence and spans.

If a collection of vectors spans a subspace and is linearly independent, it deserves a special name.

The definition of a basis means that every vector can be written as a linear combination of the basis vectors in exactly one way.

Given a basis $v_1, \dots, v_k$ of $V$, it is not always straightforward to write a vector $v$ in terms of it, that is, to find the numbers $\lambda_1, \dots, \lambda_k \in \mathbb{K}$. In general this leads to a system of linear equations for $\lambda_1, \dots, \lambda_k$.

We now want to show that the vector spaces we have been exploring have a basis. To do this we first introduce some terminology.

We start by showing that a linearly independent set cannot contain more vectors than a basis of the same space.

As well as taking a linearly dependent spanning set and removing vectors to get a basis, we can also start with a linearly independent set and add vectors to it until we have a basis.

You can watch Theorem 6.33 at work in the picture after Lemma 6.15: press its Theorem 6.33 button, and add vectors until the span is the whole space.

Dimension of a vector space

We saw that every finite-dimensional vector space has a basis. Generally there are many bases for a vector space, but they have something in common: any two bases of a finite-dimensional vector space have the same size.

We now collect some useful facts about the dimension.

This gives a simpler test for a basis than the definition. If we know $\dim V$, then a set with $\dim V$ elements is a basis as soon as it is linearly independent, or as soon as it spans $V$: in the finite-dimensional case we only have to check one of the two conditions.

Finally we turn to subspaces, where two facts follow from the counting above.

Complements and dimensions of direct sums

Chapter 5 put two subspaces together with the direct sum of Definition 5.22. Now that we can count, the question is what the dimension of the result is, and the answer is the one you would guess: dimensions add. The example to keep in mind is $\mathbb{R}^3$ cut into the $xy$-plane and the $z$-axis, which is Example 5.32 in the notes, where a space of dimension $3$ becomes the direct sum of spaces of dimensions $2$ and $1$.

Dropping the assumption $U \cap W = \{\mathbf{0}\}$ changes the count in the way you would expect: the overlap gets counted once instead of twice.

Given a subspace $U$ of $V$, we may want to know how to build it up into the whole of $V$. To do that with no overlap is to ask for a direct sum, which gives the following name.

The last of those is a recipe, and Theorem 6.33 says it never gets stuck, so a complement always exists.

More revision: a question on bases

From the same past MATH10015 paper as the earlier revision questions, with the numbers changed a little. That set needed only Chapters 1 to 4; this one needs Chapter 6, so it waits until here.