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.
Contents
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
Drag to rotate. A plane and a line, both through the origin. Turn them any way you like — they stay flat and straight.
Flat objects, passing through the origin.
What we don't study
Drag to rotate the saddle $x_3 = x_1^2 - x_2^2$.
Curved objects. Beautiful, but not linear algebra.
Finding solution(s) to linear equations
If $\;2x = 5,\;$ then $x = \;?$
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.
What is $\;\begin{pmatrix} 1 \\ 3 \end{pmatrix} + \begin{pmatrix} 4 \\ 5 \\ 7 \end{pmatrix}$?
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}$,
\[ \lambda_1 v_1 + \lambda_2 v_2 + \dots + \lambda_k v_k = \sum_{i=1}^{k} \lambda_i v_i. \]What is the second component of $\;8\,(3, \pi, 6) \; - \; 3\,(2, \pi, 1)$?
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$.
Drag near the tip of $v$ or $w$ to move it — you do not have to hit the dot exactly. Or focus a dot and use the arrow keys.
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
- $x \cdot y = y \cdot x$.
- $x \cdot (v + w) = x \cdot v + x \cdot w$ and $(x + y) \cdot v = x \cdot v + y \cdot v$.
- $(\lambda x) \cdot y = \lambda (x \cdot y)$ and $x \cdot (\lambda y) = \lambda (x \cdot y)$.
- $x \cdot x \geq 0$, and $x \cdot x = 0$ is equivalent to $x = \mathbf{0}$.
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.
Proof (choosing $t$)
If $y = \mathbf{0}$ both sides are $0$, so assume $y \neq \mathbf{0}$. For every $t \in \mathbb{R}$, Theorem 1.8 (iv) gives $(x - ty) \cdot (x - ty) \geq 0$, and expanding with parts (i)–(iii), \[ 0 \;\leq\; (x - ty) \cdot (x - ty) \;=\; x \cdot x \;-\; 2t \, (x \cdot y) \;+\; t^2 \, (y \cdot y). \] Now choose $t = \dfrac{x \cdot y}{y \cdot y}$, the value of $t$ minimising the right-hand side. Substituting, \[ 0 \;\leq\; \|x\|^2 - \frac{(x \cdot y)^2}{\|y\|^2}, \] so $(x \cdot y)^2 \leq \|x\|^2 \|y\|^2$, and taking square roots gives $|x \cdot y| \leq \|x\| \, \|y\|$.□Proof (discriminant)
Again assume $y \neq \mathbf{0}$, and regard the same expression as a quadratic in $t$: \[ q(t) \;=\; \|x - ty\|^2 \;=\; \underbrace{\|y\|^2}_{A} t^2 \; \underbrace{-\, 2(x \cdot y)}_{B} \, t \;+\; \underbrace{\|x\|^2}_{C}. \] Being a squared norm, $q(t) \geq 0$ for every real $t$. For a real quadratic with $A > 0$, \[ At^2 + Bt + C \geq 0 \ \text{ for all } t \in \mathbb{R} \quad \Longleftrightarrow \quad \Delta = B^2 - 4AC \leq 0 . \] Here $A = \|y\|^2 > 0$ precisely because $y \neq \mathbf{0}$, which is what the case split is for. So $\Delta \leq 0$, that is \[ 4(x \cdot y)^2 - 4\|y\|^2\|x\|^2 \leq 0, \qquad\text{i.e.}\qquad (x \cdot y)^2 \leq \|x\|^2\|y\|^2, \] and taking square roots gives the result.□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
- $\|v\| \geq 0$ for all $v \in \mathbb{R}^n$, and $\|v\| = 0$ if and only if $v = \mathbf{0}$.
- $\|\lambda v\| = |\lambda| \, \|v\|$ for all $\lambda \in \mathbb{R}$, $v \in \mathbb{R}^n$.
- $\|v + w\| \leq \|v\| + \|w\|$ for all $v, w \in \mathbb{R}^n$ (this is known as the triangle inequality).
Proof
- By Theorem 1.8 (iv), $v \cdot v \geq 0$, so $\|v\| = \sqrt{v \cdot v}$ is a well-defined non-negative real number; and the same part gives $v \cdot v = 0 \iff v = \mathbf{0}$, so $\|v\| = 0 \iff v = \mathbf{0}$.
- A direct computation: \[ \|\lambda v\| = \sqrt{(\lambda v_1)^2 + \dots + (\lambda v_n)^2} = \sqrt{\lambda^2 \bigl(v_1^2 + \dots + v_n^2\bigr)} = \sqrt{\lambda^2} \, \sqrt{v_1^2 + \dots + v_n^2} = |\lambda| \, \|v\| , \] using $\sqrt{\lambda^2} = |\lambda|$ rather than $\lambda$. That is exactly where the modulus on the right-hand side comes from.
- Expand the squared norm and apply Cauchy–Schwarz: \[ \|v + w\|^2 = (v+w) \cdot (v+w) = v \cdot v + 2 \, v \cdot w + w \cdot w = \|v\|^2 + 2 \, v \cdot w + \|w\|^2 . \] By Theorem 1.13, $v \cdot w \leq |v \cdot w| \leq \|v\| \, \|w\|$, so \[ \|v + w\|^2 \leq \|v\|^2 + 2\|v\| \, \|w\| + \|w\|^2 = \bigl( \|v\| + \|w\| \bigr)^2 , \] and taking square roots gives $\|v + w\| \leq \|v\| + \|w\|$.□
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
\[ 150 \times 150 \times 3 = 67\,500 \]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.
Two photographs of the same cat, one shifted a single pixel to the left, are far apart in $\mathbb{R}^{67500}$, because almost every coordinate has changed. Raw distance between pixels is a crude measure of similarity, and most of the work in the subject goes into finding a better vector to measure, rather than a better way to measure. The distance stays; what changes is what you take the distance between.
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
\[ -1 \;\leq\; \frac{x \cdot y}{\|x\| \, \|y\|} \;\leq\; 1, \]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.
How do we visualise the dot product?
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
\[ \begin{pmatrix} \cos \theta \\ \sin \theta \end{pmatrix}, \qquad \left\| \begin{pmatrix} \cos \theta \\ \sin \theta \end{pmatrix} \right\| = 1 . \]Multiplying it by a positive scalar reaches any non-zero vector of the plane, and the scalar needed is exactly the norm.
Proof
Writing $v = (v_1, v_2)$, we need $\lambda > 0$ and $\theta \in [0, 2\pi)$ with \[ \begin{pmatrix} v_1 \\ v_2 \end{pmatrix} = \lambda \, \begin{pmatrix} \cos \theta \\ \sin \theta \end{pmatrix} = \begin{pmatrix} \lambda \cos \theta \\ \lambda \sin \theta \end{pmatrix} . \] Taking norms and using Theorem 1.14 (ii), the right-hand side has norm $|\lambda| \cdot 1 = \lambda$, since $\lambda > 0$ and the column vector above is a unit vector. So $\lambda$ is forced: \[ \lambda = \|v\| . \] It remains to solve \[ \cos \theta = \frac{v_1}{\|v\|}, \qquad \sin \theta = \frac{v_2}{\|v\|} . \] These two numbers satisfy $\bigl(v_1/\|v\|\bigr)^2 + \bigl(v_2/\|v\|\bigr)^2 = 1$, so the pair lies on the unit circle, and there is exactly one $\theta \in [0, 2\pi)$ with those cosine and sine. Hence $\theta$ is forced too.□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.
What would be an analogue of polar coordinates in three dimensions?
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
Which number on the real line do you multiply $1$ by to get $-1$?
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.
So which rotation, applied twice to $1$, gives $-1$?
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:
\[ z \bar{z} = (x + iy)(x - iy) = x^2 + y^2 = \|v(z)\|^2 , \]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$,
\[ |z| := \sqrt{\bar{z} z} = \sqrt{x^2 + y^2} . \]This is what makes division work: for $z \neq 0$,
\[ \frac{1}{z} = \frac{\bar{z}}{\bar{z} z} = \frac{\bar{z}}{|z|^2} = \frac{x}{x^2 + y^2} - i \, \frac{y}{x^2 + y^2}, \qquad\text{and so}\qquad \frac{z_1}{z_2} = \frac{\bar{z_2} z_1}{|z_2|^2} . \]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,
\[ z = x + iy = |z| \bigl( \cos \theta + i \sin \theta \bigr) . \]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
\[ e^z := 1 + z + \frac{1}{2} z^2 + \frac{1}{3!} z^3 + \frac{1}{4!} z^4 + \dots = \sum_{n=0}^{\infty} \frac{1}{n!} z^n , \tag{2.1} \]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$,
\[ e^{z_1} e^{z_2} = e^{z_1 + z_2} . \tag{2.2} \]Proof (sketch)
This is really a calculus result, and a full justification needs more calculus than we have here. Like $(2.1)$, sine and cosine can be defined by power series: \[ \sin z = z - \frac{1}{3!} z^3 + \frac{1}{5!} z^5 - \dots , \qquad \cos z = 1 - \frac{1}{2} z^2 + \frac{1}{4!} z^4 - \dots \] Put $z = i\theta$ in $(2.1)$. Since $(i\theta)^2 = -\theta^2$, $(i\theta)^3 = -i\theta^3$, $(i\theta)^4 = \theta^4$, $(i\theta)^5 = i\theta^5$, and so on, the terms alternate between real and imaginary:Putting $\theta = \pi$ into Euler's formula gives $e^{i\pi} = \cos\pi + i\sin\pi = -1$, that is
\[ e^{i\pi} + 1 = 0 , \]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
\[ z = \lambda e^{i\theta}, \]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)$,
\[ z_1 z_2 = \lambda_1 \lambda_2 \, e^{i(\theta_1 + \theta_2)}, \qquad \frac{z_1}{z_2} = \frac{\lambda_1}{\lambda_2} \, e^{i(\theta_1 - \theta_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.
Proof
By Theorem 2.7, $\cos\theta + i\sin\theta = e^{i\theta}$, so the left-hand side is $(e^{i\theta})^n$. Repeated use of $(2.2)$ gives $(e^{i\theta})^n = e^{in\theta}$, and applying Theorem 2.7 once more to $e^{in\theta}$ gives $\cos(n\theta) + i\sin(n\theta)$.□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
\[ \cos(2\theta) = \cos^2\theta - \sin^2\theta, \qquad \sin(2\theta) = 2 \sin\theta \cos\theta . \]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
\[ z^n = 1 \, ? \]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,
\[ \omega_k = e^{2\pi i k / n} = \cos\!\left(\frac{2\pi k}{n}\right) + i \sin\!\left(\frac{2\pi k}{n}\right), \qquad k = 0, 1, \dots, n-1 . \]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 films, 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 film 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$.
- In one unknown the solution set is \[ \{ x \in \mathbb{R} \;:\; x = 0 \} = \{0\}, \] a single point of $\mathbb{R}$.
- In two unknowns $y$ is unconstrained, so the solution set is \[ \{ (x,y) \in \mathbb{R}^2 \;:\; x = 0 \}, \] a line in $\mathbb{R}^2$: the $y$-axis.
- In three unknowns both $y$ and $z$ are unconstrained, so the solution set is \[ \{ (x,y,z) \in \mathbb{R}^3 \;:\; x = 0 \}, \] a plane in $\mathbb{R}^3$: the $yz$-plane.
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
\[ M_{1,2}(\mathbb{Z}) \subseteq M_{1,2}(\mathbb{Q}) \subseteq M_{1,2}(\mathbb{R}) \subseteq M_{1,2}(\mathbb{C}) . \]$X \subseteq Y$ means every element of $X$ is also an element of $Y$. This allows $X = Y$. Most mathematical texts write $X \subset Y$ for exactly the same statement, so for us the two are interchangeable. This is worth saying because it is not the pattern you are used to from $\le$ and $<$, where the second really does exclude equality; $\subset$ carries no such implication unless an author says so.
When we do want to exclude equality we write $\subsetneq$, and to deny containment altogether we write $\nsubseteq$:
- $\mathbb{Z} \subseteq \mathbb{Q}$, and in fact $\mathbb{Z} \subsetneq \mathbb{Q}$, since $\tfrac{1}{2} \in \mathbb{Q}$ but $\tfrac{1}{2} \notin \mathbb{Z}$.
- $\{1, 2\} \subsetneq \{1, 2, 3\}$: contained, and the containment is strict.
- $\{1, 2\} \subseteq \{1, 2\}$ is true, but $\{1, 2\} \subsetneq \{1, 2\}$ is false: a set is a subset of itself, but not a strict one.
- $\{1, 2, 4\} \nsubseteq \{1, 2, 3\}$, because $4 \notin \{1, 2, 3\}$.
- $\varnothing \subseteq X$ for every set $X$, and $X \subseteq X$ for every set $X$.
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
\[ A = \begin{pmatrix} r_1 \\ r_2 \\ \vdots \\ r_m \end{pmatrix} , \]and if the columns of $A$ are $c_1, c_2, \dots, c_n$ we may write
\[ A = \begin{pmatrix} c_1 & c_2 & \cdots & c_n \end{pmatrix} . \]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,
\[ \begin{pmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix} + \begin{pmatrix} 0 & -1 \\ 3 & 3 \\ -3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 3 \\ 5 & 8 \\ 0 & 7 \end{pmatrix} , \qquad 2 \begin{pmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix} = \begin{pmatrix} 2 & 8 \\ 4 & 10 \\ 6 & 12 \end{pmatrix} . \]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})$,
\[ A + 0 = 0 + A = A , \]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:
\[ \begin{pmatrix} 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} 4 \\ 5 \\ 6 \end{pmatrix} = \begin{pmatrix} 1 \cdot 4 + 2 \cdot 5 + 3 \cdot 6 \end{pmatrix} = \begin{pmatrix} 32 \end{pmatrix} . \]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$,
\[ A I_n = I_m A = 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.
- If $A, B$ are $m \times n$ and $C$ is $l \times m$, then $C(A+B) = CA + CB$.
- If $A, B$ are $m \times n$ and $C$ is $n \times l$, then $(A+B)C = AC + BC$.
- If $A$ is $m \times n$, $B$ is $n \times l$ and $C$ is $l \times k$, then $A(BC) = (AB)C$.
- If $A$ is $m \times n$, $B$ is $n \times l$ and $\lambda \in \mathbb{R}$, then $A(\lambda B) = \lambda (AB)$.
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,
\[ x = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \in M_{n,1}(\mathbb{R}) . \]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
\[ Ax = b . \]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
\[ A = \begin{pmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix} \in M_{3,2}(\mathbb{R}) . \]It has two columns, so it eats vectors with two entries, and three rows, so it returns vectors with three. It is a map
\[ A : \mathbb{R}^2 \to \mathbb{R}^3 , \qquad A \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} a + 4b \\ 2a + 5b \\ 3a + 6b \end{pmatrix} . \]Points of the plane are carried to points of space. In particular, as we saw,
\[ A \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} , \qquad A \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 4 \\ 5 \\ 6 \end{pmatrix} , \]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.
- $A(x + y) = Ax + Ay$ for all $x, y \in \mathbb{R}^n$,
- $A(\lambda x) = \lambda Ax$ for all $x \in \mathbb{R}^n$ and $\lambda \in \mathbb{R}$.
Proof
Take the first property. Both $A(x+y)$ and $Ax + Ay$ are vectors in $\mathbb{R}^m$, so to show they are equal it is enough to show that their $i$th components agree, for each $i = 1, 2, \dots, m$. Write $z = A(x+y)$. By Definition 3.12 its $i$th component is
\[ z_i = a_{i1}(x_1 + y_1) + a_{i2}(x_2 + y_2) + \cdots + a_{in}(x_n + y_n) . \]In sigma notation, $\displaystyle z_i = \sum_{j=1}^{n} a_{ij}(x_j + y_j)$.
Multiplying out and gathering the $x$ terms together and the $y$ terms together,
\[ z_i = \bigl( a_{i1} x_1 + a_{i2} x_2 + \cdots + a_{in} x_n \bigr) + \bigl( a_{i1} y_1 + a_{i2} y_2 + \cdots + a_{in} y_n \bigr) . \]In sigma notation, $\displaystyle z_i = \sum_{j=1}^{n} a_{ij} x_j + \sum_{j=1}^{n} a_{ij} y_j$.
The first bracket is the $i$th component of $Ax$ and the second is the $i$th component of $Ay$, again by Definition 3.12. Writing the whole column out at once, this says
\[ A(x+y) = \begin{pmatrix} a_{11}(x_1 + y_1) + \cdots + a_{1n}(x_n + y_n) \\ \vdots \\ a_{m1}(x_1 + y_1) + \cdots + a_{mn}(x_n + y_n) \end{pmatrix} \] \[ = \begin{pmatrix} a_{11} x_1 + \cdots + a_{1n} x_n \\ \vdots \\ a_{m1} x_1 + \cdots + a_{mn} x_n \end{pmatrix} + \begin{pmatrix} a_{11} y_1 + \cdots + a_{1n} y_n \\ \vdots \\ a_{m1} y_1 + \cdots + a_{mn} y_n \end{pmatrix} = Ax + Ay . \]In sigma notation, $\displaystyle A(x+y) = \Bigl( \sum_{j=1}^{n} a_{ij}(x_j + y_j) \Bigr)_{i=1,\dots,m} = \Bigl( \sum_{j=1}^{n} a_{ij} x_j \Bigr)_i + \Bigl( \sum_{j=1}^{n} a_{ij} y_j \Bigr)_i = Ax + Ay$.
The second property goes the same way. Every entry of the column has a factor of $\lambda$, and pulling it out of the column is exactly scalar multiplication of a vector:
\[ A(\lambda x) = \begin{pmatrix} a_{11}\lambda x_1 + \cdots + a_{1n}\lambda x_n \\ \vdots \\ a_{m1}\lambda x_1 + \cdots + a_{mn}\lambda x_n \end{pmatrix} = \begin{pmatrix} \lambda\bigl( a_{11} x_1 + \cdots + a_{1n} x_n \bigr) \\ \vdots \\ \lambda\bigl( a_{m1} x_1 + \cdots + a_{mn} x_n \bigr) \end{pmatrix} \] \[ = \lambda \begin{pmatrix} a_{11} x_1 + \cdots + a_{1n} x_n \\ \vdots \\ a_{m1} x_1 + \cdots + a_{mn} x_n \end{pmatrix} = \lambda A x . \]In sigma notation, $\displaystyle A(\lambda x) = \Bigl( \sum_{j=1}^{n} a_{ij} \lambda x_j \Bigr)_i = \Bigl( \lambda \sum_{j=1}^{n} a_{ij} x_j \Bigr)_i = \lambda \Bigl( \sum_{j=1}^{n} a_{ij} x_j \Bigr)_i = \lambda A x$.□
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.
Proof 1 (a special case of Theorem 3.11(c))
As we agreed when the action was defined, a vector $x \in \mathbb{R}^n$ is regarded as a column matrix, an element of $M_{n,1}(\mathbb{R})$. So multiplying a matrix by a vector is already a product of two matrices, and we may apply part (c) of Theorem 3.11 to
\[ B \in M_{l,m}(\mathbb{R}), \qquad A \in M_{m,n}(\mathbb{R}), \qquad x \in M_{n,1}(\mathbb{R}) , \]whose shapes match in exactly the way part (c) asks: $l \times m$ times $m \times n$ times $n \times 1$. Associativity then reads
\[ B(Ax) = (BA)x , \]which is the statement.□
This is not circular. Theorem 3.11 is proved from general properties of linear maps, not from this corollary, so associativity is already available here.
Proof 2 (as in the notes, entry by entry)
Write $y = Ax$, so that $y = (y_1, \dots, y_m)$ with
\[ y_k = \sum_{j=1}^{n} a_{kj} x_j , \]and write $z = By$, so that $z = (z_1, \dots, z_l)$ with
\[ z_i = \sum_{k=1}^{m} b_{ik} y_k . \]Substituting the first into the second and exchanging the order of summation,
\[ z_i = \sum_{k=1}^{m} b_{ik} \sum_{j=1}^{n} a_{kj} x_j = \sum_{j=1}^{n} \Bigl( \sum_{k=1}^{m} b_{ik} a_{kj} \Bigr) x_j = \sum_{j=1}^{n} c_{ij} x_j , \]which is the $i$th component of $(BA)x$ by Definition 3.12. This holds for every $i$, so the two vectors agree.□
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,
\[ A = \begin{pmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix} \in M_{3,2}(\mathbb{R}) , \qquad A^t = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} \in M_{2,3}(\mathbb{R}) . \]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
\[ \begin{pmatrix} 1 & 2 & 3 \\ 2 & -1 & 0 \\ 3 & 0 & 1 \end{pmatrix} \text{ is symmetric}, \qquad \begin{pmatrix} 0 & -1 & 2 \\ 1 & 0 & 3 \\ -2 & -3 & 0 \end{pmatrix} \text{ is anti-symmetric}. \]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:
\[ A = \tfrac{1}{2}\bigl( A + A^t \bigr) + \tfrac{1}{2}\bigl( A - A^t \bigr) . \]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.
Proof
The $i$th component of $Ax$ is $\sum_{j=1}^{n} a_{ij} x_j$, so
\[ y \cdot Ax = \sum_{i=1}^{m} \sum_{j=1}^{n} y_i a_{ij} x_j . \]On the other hand the $j$th component of $A^t y$ is $\sum_{i=1}^{m} a_{ij} y_i$, so
\[ (A^t y) \cdot x = \sum_{j=1}^{n} \sum_{i=1}^{m} x_j a_{ij} y_i . \]The order of summation does not matter in a finite double sum, so the two agree.□
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.
Proof 1 (directly, entry by entry)
Both sides are $k \times m$ matrices, so it is enough to check that they agree in every entry. By Definition 3.16, entry $(i,j)$ of $(AB)^t$ is entry $(j,i)$ of $AB$, which by the definition of the product is
\[ \bigl( (AB)^t \bigr)_{ij} = (AB)_{ji} = \sum_{l=1}^{n} a_{jl} b_{li} . \]On the other side, using the definition of the product and then Definition 3.16 twice,
\[ \bigl( B^t A^t \bigr)_{ij} = \sum_{l=1}^{n} b_{li} a_{jl} . \]The two sums have the same terms, so the entries agree for all $i$ and $j$.□
Proof 2 (as in the notes, via Theorem 3.17)
Apply Theorem 3.17 to the matrix $AB$:
\[ \bigl( (AB)^t y \bigr) \cdot x = y \cdot (ABx) . \]Now apply Theorem 3.17 twice on the right, first to $A$ and then to $B$:
\[ y \cdot (ABx) = (A^t y) \cdot (Bx) = \bigl( B^t A^t y \bigr) \cdot x , \]and therefore
\[ \bigl( (AB)^t y \bigr) \cdot x = \bigl( B^t A^t y \bigr) \cdot x \qquad \text{for all } x, y . \]It remains to see why that forces the two matrices to be equal, and this is where the standard vectors earn their keep. For any matrix $M$, take $y = e_i$ and $x = e_j$. Then $M e_i$ is the $i$th column of $M$, proved in The general case below, and dotting with $e_j$ picks out its $j$th component:
\[ (M e_i) \cdot e_j = M_{ji} . \]So each choice of $i$ and $j$ reads off a single entry. Applying this to both sides gives $\bigl( (AB)^t \bigr)_{ji} = \bigl( B^t A^t \bigr)_{ji}$, and since $i$ and $j$ were arbitrary, every entry of the two matrices agrees.□
Note the order of the indices: with $y = e_i$ and $x = e_j$ you read off entry $(j,i)$, not $(i,j)$, because $y$ multiplies the matrix and $x$ selects the component. Taking $y = e_j$ and $x = e_i$ instead gives entry $(i,j)$ directly; either way, all entries are covered.
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
\[ A(x_0 + x) = Ax_0 + Ax = b + 0 = b , \]so $x_0 + x$ solves the system as well. Nothing else does.
Proof
We show that each set contains the other. If $x \in S(A,0)$, the calculation above gives $A(x_0 + x) = b$, so $\{x_0\} + S(A,0) \subseteq S(A,b)$.
Conversely, let $y \in S(A,b)$. Then
\[ A(y - x_0) = Ay - Ax_0 = b - b = 0 , \]so $y - x_0 \in S(A,0)$, and therefore $y = x_0 + (y - x_0)$ lies in $\{x_0\} + S(A,0)$. Hence $S(A,b) \subseteq \{x_0\} + S(A,0)$, and the two sets are equal.□
Showing each of two sets contains the other is the standard way to prove they are equal.
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
\[ \begin{cases} A = B , \\ C = D , \end{cases} \]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
\[ \lambda (A - B) = 0 , \qquad\text{that is}\qquad \lambda A = \lambda B , \]and an equation may be multiplied through by a constant. Since adding zero changes nothing,
\[ 0 = C - D = (C - D) + 0 = (C - D) + (A - B) = (A + C) - (B + D) , \]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:
- multiply an equation by a non-zero constant;
- add a multiple of one equation to another equation;
- 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.
- multiply a row by a non-zero number, $\text{row } i \to \lambda \times \text{row } i$;
- add a multiple of one row to another, $\text{row } i \to \text{row } i + \lambda \times \text{row } j$;
- exchange two rows, $\text{row } i \leftrightarrow \text{row } j$.
Proof
Applied to the augmented matrix of a system, the three elementary row operations are exactly the three operations (i), (ii) and (iii) on the equations themselves, and we have just seen that none of those changes the set of solutions. So the system read off from the new matrix has the same solutions as the system we started with.□
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.
- each row is either all zeros, or its leftmost non-zero number is $1$, called the leading 1 in that row, and
- if row $i$ is above row $j$, then the leading 1 of row $i$ is to the left of the leading 1 of row $j$; any zero rows are below any non-zero rows.
- in each column which contains a leading 1, all other numbers are $0$.
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.
- the system has no solutions if and only if the last column of $M$ contains a leading 1;
- the system has exactly one solution if and only if every column of $M$ except the last contains a leading 1;
- the system has infinitely many solutions if and only if the last column of $M$ contains no leading 1 and there are fewer than $n$ leading 1s in all. In that case, if $M$ has $k$ leading 1s, then $n - k$ of the unknowns may be chosen freely.
A matrix has many row echelon forms, but they all have their leading 1s in the same columns, so it does not matter which one you reduce to.
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
\[ A = \begin{pmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{pmatrix} . \]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.
Step 1
Split the vector into the two standard ones:
\[ \begin{pmatrix} a \\ b \end{pmatrix} = a \begin{pmatrix} 1 \\ 0 \end{pmatrix} + b \begin{pmatrix} 0 \\ 1 \end{pmatrix} . \]Step 2
Apply $A$ and use Theorem 3.13: the first property turns the sum into a sum, and the second pulls the scalars out.
\[ A \begin{pmatrix} a \\ b \end{pmatrix} = A \left( a \begin{pmatrix} 1 \\ 0 \end{pmatrix} + b \begin{pmatrix} 0 \\ 1 \end{pmatrix} \right) = a\, A \begin{pmatrix} 1 \\ 0 \end{pmatrix} + b\, A \begin{pmatrix} 0 \\ 1 \end{pmatrix} . \]Step 3
By the two questions above, $A\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ is the first column of $A$ and $A\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ is the second. So
\[ A \begin{pmatrix} a \\ b \end{pmatrix} = a \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} + b \begin{pmatrix} 4 \\ 5 \\ 6 \end{pmatrix} . \]□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,
\[ e_i = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} \begin{matrix} \phantom{0} \\ \phantom{\vdots} \\ \phantom{0} \\ \leftarrow i \\ \phantom{0} \\ \phantom{\vdots} \\ \phantom{0} \end{matrix} \]Then the same check works for any matrix at all.
Why
By Definition 3.12 the $k$th component of $A e_i$ is
\[ a_{k1} \cdot 0 + \cdots + a_{k,i-1} \cdot 0 + a_{ki} \cdot 1 + a_{k,i+1} \cdot 0 + \cdots + a_{kn} \cdot 0 = a_{ki} , \]since every term except the $i$th is multiplied by zero. So the $k$th component of $A e_i$ is $a_{ki}$, for every $k$, and that column of entries is exactly the $i$th column of $A$.□
The same three steps, with $n$ in place of $2$.
Step 1
Split $x$ into the standard vectors:
\[ x = x_1 e_1 + x_2 e_2 + \cdots + x_n e_n . \]Step 2
Apply $A$ and use Theorem 3.13 again:
\[ A x = A \bigl( x_1 e_1 + \cdots + x_n e_n \bigr) = x_1 \, A e_1 + x_2 \, A e_2 + \cdots + x_n \, A e_n . \]Step 3
By the box above, $A e_i = c_i$ for each $i$, so
\[ A x = x_1 c_1 + x_2 c_2 + \cdots + x_n c_n . \]□$Ax$ is the linear combination of the columns of $A$ with the entries of $x$ as coefficients.
Say it out loud, then again tomorrow. Nearly everything ahead is easier once that sentence is the first thing you think when you see $Ax$: it turns a page of arithmetic into a statement about columns.
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.
Hint, if you would like one
Write $V = \begin{pmatrix} v_1 & v_2 & v_3 \end{pmatrix}$ and pick out its $j$th column with a standard vector: $V e_j = v_j$. Now apply that idea to the product:
\[ (AV) e_j = A (V e_j) = A v_j , \]using associativity of the product in the middle step. The left-hand side is the $j$th column of $AV$ and the right-hand side is $Av_j$, so the two matrices agree column by column, and therefore agree.□
This is block multiplication again, with $V$ cut into blocks one column wide. Once you have seen it that way, the result stops looking like a trick.
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.
- $A e_j$ is the $j$th column of $A$, a vector in $\mathbb{R}^m$;
- $e_i^t A$ is the $i$th row of $A$, a $1 \times n$ row;
- $e_i^t A e_j = a_{ij}$, the single entry in row $i$ and column $j$.
The pattern is worth saying once: multiplying on the right acts on columns, multiplying on the left acts on rows, and doing both at once leaves one number. Watch the shapes and you cannot mix them up: $A e_j$ is $m \times 1$, while $e_i^t A$ is $1 \times n$.
Solution
The row. Here $e_i \in \mathbb{R}^m$, so $e_i^t$ is a $1 \times m$ row whose $k$th entry is $1$ when $k = i$ and $0$ otherwise. Since $A$ is $m \times n$, the product $e_i^t A$ is $1 \times n$, and its $j$th entry is the row against the $j$th column of $A$:
\[ \bigl( e_i^t A \bigr)_j = \sum_{k=1}^{m} (e_i)_k \, a_{kj} = 0 \cdot a_{1j} + \cdots + 1 \cdot a_{ij} + \cdots + 0 \cdot a_{mj} = a_{ij} , \]every term but the $i$th being multiplied by zero. This holds for each $j = 1, \dots, n$, so
\[ e_i^t A = \begin{pmatrix} a_{i1} & a_{i2} & \cdots & a_{in} \end{pmatrix} , \]which is exactly the $i$th row of $A$.
The entry. Now multiply that row on the right by $e_j \in \mathbb{R}^n$. It is a $1 \times n$ times an $n \times 1$, so the answer is $1 \times 1$, a single number, and by the same argument only the $j$th term survives:
\[ \bigl( e_i^t A \bigr) e_j = \sum_{k=1}^{n} a_{ik} \, (e_j)_k = a_{ij} . \]The brackets were never needed: the product is associative, so $e_i^t A e_j$ may equally be read as $e_i^t (A e_j)$, picking the $i$th entry of the $j$th column. Either reading gives $a_{ij}$, as it must.□
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.
- $\text{row } i \to \lambda \times \text{row } i$, with $\lambda \neq 0$. One box, on
the diagonal, in row $i$ and column $i$:
\[ E \;=\; \begin{pmatrix} 1 & & & & \\ & \ddots & & & \\ & & \boxed{\lambda} & & \\ & & & \ddots & \\ & & & & 1 \end{pmatrix} \begin{matrix} \\ \\ \leftarrow i \\ \\ \\ \end{matrix} \]
- $\text{row } i \to \text{row } i + \lambda \times \text{row } j$. Two boxes, both in
row $i$: the $1$ it already had in column $i$, and a new $\lambda$ in column $j$:
\[ E \;=\; \begin{pmatrix} 1 & & & & & \\ & \ddots & & & & \\ & & 1 & & & \\ & & \boxed{\lambda} & \boxed{1} & & \\ & & & & \ddots & \\ & & & & & 1 \end{pmatrix} \begin{matrix} \\ \\ \\ \leftarrow i \\ \\ \\ \end{matrix} \]
with the $\lambda$ standing in column $j$ and the $1$ in column $i$.
- $\text{row } i \leftrightarrow \text{row } j$. Four boxes, at the corners of the square
cut out by rows $i, j$ and columns $i, j$: the two diagonal $1$s become $0$s and two $1$s
appear off the diagonal:
\[ E \;=\; \begin{pmatrix} 1 & & & & \\ & \boxed{0} & & \boxed{1} & \\ & & \ddots & & \\ & \boxed{1} & & \boxed{0} & \\ & & & & 1 \end{pmatrix} \begin{matrix} \\ \leftarrow i \\ \\ \leftarrow j \\ \\ \end{matrix} \]
the boxed columns being $i$ and $j$ in the same order.
Reading a row of $E$ tells you how that row of $EA$ is built: a $1$ in column $k$ takes row $k$ of $A$ as it stands, a $\lambda$ there takes $\lambda$ times it, and a blank takes none of it. Row $i$ in (ii) carries a $1$ in column $i$ and a $\lambda$ in column $j$, which says exactly that row $i$ of $EA$ is row $i$ of $A$ plus $\lambda$ times row $j$.
Reveal
Take an elementary matrix $E$, obtained by applying one particular elementary row operation to $I_m$. Then for any matrix $A \in M_{m,n}(\mathbb{R})$, multiplying on the left gives
\[ EA = \text{the matrix obtained by applying that same operation to } A . \]The operation is carried in the matrix. Build $E$ once by doing the operation to the identity, and from then on it performs that operation on anything you put to its right.
- multiply a row by a non-zero number, here
$\text{row } 2 \to \lambda \times \text{row } 2$:
\[ E = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \lambda & 0 \\ 0 & 0 & 1 \end{pmatrix} , \qquad EA = \begin{pmatrix} 1 & 4 & 7 \\ 2\lambda & 5\lambda & 8\lambda \\ 3 & 6 & 9 \end{pmatrix} , \qquad\text{and at } \lambda = 3 ,\quad EA = \begin{pmatrix} 1 & 4 & 7 \\ 6 & 15 & 24 \\ 3 & 6 & 9 \end{pmatrix} \]
- add a multiple of one row to another, here
$\text{row } 3 \to \text{row } 3 + \lambda \times \text{row } 1$:
\[ E = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \lambda & 0 & 1 \end{pmatrix} , \qquad EA = \begin{pmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 + \lambda & 6 + 4\lambda & 9 + 7\lambda \end{pmatrix} , \qquad\text{and at } \lambda = -2 ,\quad EA = \begin{pmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 1 & -2 & -5 \end{pmatrix} \]
- exchange two rows, here $\text{row } 1 \leftrightarrow \text{row } 2$:
\[ E = E_{12} = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} , \qquad EA = \begin{pmatrix} 2 & 5 & 8 \\ 1 & 4 & 7 \\ 3 & 6 & 9 \end{pmatrix} . \]
In each case $E$ is the identity with the operation already done to it, and nothing else. The entries say how the rows are mixed: row $i$ of $EA$ is $\sum_k E_{ik} \cdot (\text{row } k \text{ of } A)$. In (ii) the first column of $E$ is $(1, 0, \lambda)$, which says how much of row 1 of $A$ reaches each row of $EA$: all of it into row 1, none into row 2, and $\lambda$ times it into row 3. Multiplying on the right instead would act on columns, which is what the questions above were about.
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
\[ A = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & k \end{pmatrix} , \]Start by swapping. Let
\[ E_{12} = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} , \]the identity with its first two rows swapped.
Next, scale a row. Let
\[ E_2(\lambda) = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \lambda & 0 \\ 0 & 0 & 1 \end{pmatrix} , \]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
\[ E = \begin{pmatrix} 1 & 0 & 0 \\ \lambda & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} , \]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$.
You might revisit this when you study eigenvalues and eigenvectors.
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$.
It is the $2 \times 2$ rule from Definition 3.9 with numbers replaced by blocks. One thing does change: blocks are matrices, so $A_{11}B_{11}$ and $B_{11}A_{11}$ need not agree, and the order in every product above must be kept. The shared split $n_1 + n_2$ is what makes each product line up: $A_{11}$ has $n_1$ columns and $B_{11}$ has $n_1$ rows.
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.
- G. H. Golub and C. F. Van Loan, Matrix Computations, 4th edition, Johns Hopkins University Press, 2013. Chapter 1 sets up block matrices and blocked algorithms, and is the standard reference for the numerical side.
- NVIDIA, CUDA C++ Programming Guide, the section Shared Memory. It works the tiled matrix multiplication above as its main example: each thread block loads one tile of $A$ and one of $B$ into shared memory, multiplies them, accumulates, and moves on.
Week 3
Inverting a matrix
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.
- $A$ is invertible.
- There are elementary matrices $E_1, \dots, E_k$ with $E_k E_{k-1} \cdots E_1 A = I_n$.
By the Fact of life, multiplying by those elementary matrices is the same as performing the corresponding elementary row operations, so the condition says exactly that row reduction takes $A$ to $I_n$. The implication from right to left is Theorem 3.43 in the notes.
Why
This uses the two lemmas below, so it is worth coming back to once you have read them.
Suppose first that $BA = I_n$. If $Ax = 0$ then $x = I_n x = (BA)x = B(Ax) = B0 = 0$, so $x = 0$ is the only solution of $Ax = 0$. By Theorem 3.27 every column of a row echelon form of $A$ then carries a leading 1, and a square matrix in reduced row echelon form with a leading 1 in every column is $I_n$. So row reduction takes $A$ to $I_n$, and the theorem gives that $A$ is invertible. In particular $A$ has a right inverse, and by Lemma 3.38 it is $B$ itself.
Now suppose instead that $AC = I_n$. Read that equation from the other side: it says that $C$ has a left inverse, and that left inverse is $A$ itself. By what we have just proved, applied to $C$, the matrix $C$ is invertible, so $C^{-1}$ exists and
\[ A = A I_n = A\bigl(C C^{-1}\bigr) = (AC) C^{-1} = I_n C^{-1} = C^{-1} . \]Hence $CA = C C^{-1} = I_n$, so $C$ is a left inverse of $A$ as well.□
Squareness is carrying all of this. Exercise 3.41 shows what is left without it: a non-square matrix can have a left inverse, and not a unique one, while having no right inverse at all.
Three lemmas first. The proof of the theorem needs all three, and each is worth knowing on its own.
Proof
Every elementary row operation can be undone, and the operation that undoes it is an elementary row operation of the same kind:
- swapping rows $i$ and $j$ is undone by swapping them again;
- multiplying row $i$ by $\lambda \neq 0$ is undone by multiplying it by $1/\lambda$, and this is where the condition $\lambda \neq 0$ earns its keep;
- adding $\mu$ times row $j$ to row $i$ is undone by subtracting $\mu$ times row $j$ from row $i$.
Let $F$ be the elementary matrix of the undoing operation. By the Fact of life, for any matrix $A$ the product $EA$ is $A$ with the operation applied, and $F(EA)$ is that with the undoing applied, which is $A$ again. So $F(EA) = A$ for every $A$, and by associativity $(FE)A = A$ for every $A$. Taking $A = I$ gives $FE = I$. Running the same argument with the two operations the other way round gives $EF = I$. So $F$ meets the definition, $E$ is invertible with $E^{-1} = F$, and $F$ is elementary by construction.□
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.
Proof
Associativity does all the work:
\[ B = B I_n = B(AC) = (BA)C = I_n C = C . \]So anything undoing $A$ from the left and anything undoing it from the right are the same matrix. Uniqueness is the same computation run twice more.
Suppose $B'$ also satisfies $B'A = I_n$. Putting $B'$ where $B$ stood gives
\[ B' = B' I_n = B'(AC) = (B'A)C = I_n C = C , \]so $B' = C = B$: there was only ever one left inverse. Now suppose $C'$ also satisfies $AC' = I_n$. Putting $C'$ where $C$ stood gives
\[ B = B I_n = B(AC') = (BA)C' = I_n C' = C' , \]so $C' = B = C$, and there was only ever one right inverse either. The three matrices $B$, $C$ and anything else undoing $A$ on either side therefore all coincide, and that one matrix is $A^{-1}$.□
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.
Proof
There is at least one solution, because $x = A^{-1}b$ is one:
\[ A\bigl(A^{-1} b\bigr) = \bigl(A A^{-1}\bigr) b = I_n b = b . \]And there is at most one. Suppose $Ax = b$. Multiplying on the left by $A^{-1}$ gives $A^{-1}(Ax) = A^{-1}b$, and the left-hand side regroups as $\bigl(A^{-1}A\bigr)x = I_n x = x$. So $x = A^{-1}b$, and every solution is that one.□
The case the next proof needs is $b = 0$: if $A$ is invertible then $Ax = 0$ has only the solution $x = 0$.
Now the theorem.
Proof
Step 0. Take a deep breath.
First we prove: if elementary matrices turn $A$ into the identity, then $A$ is invertible. This is (b) implies (a).
Step 1. Suppose $E_k E_{k-1} \cdots E_1 A = I_n$, and write $B = E_k E_{k-1} \cdots E_1$. Then $BA = I_n$ at once, which is half of what the definition asks for.
Step 2. For the other half, each $E_i$ is invertible by Lemma 3.37. Multiply $E_k \cdots E_1 A = I_n$ on the left by $E_k^{-1}$, then by $E_{k-1}^{-1}$, and so on, peeling one matrix off at a time:
Now multiply on the right by $E_k E_{k-1} \cdots E_1$, which is $B$:
the innermost pair cancelling first and the rest following one at a time. So $AB = BA = I_n$, and $A$ is invertible. By Lemma 3.38 no other matrix does that job, so the name $A^{-1}$ is unambiguous and we may write $A^{-1} = E_k E_{k-1} \cdots E_1$.
Second we prove: if $A$ is invertible, then elementary matrices turn it into the identity. This is (a) implies (b).
Step 3. Suppose $A$ is invertible. By Lemma 3.39, applied with $b = 0$, the equation $Ax = 0$ has exactly one solution; and $x = 0$ is plainly a solution, so it is the only one. By Theorem 3.27, a system with exactly one solution has a leading 1 in every column of its row echelon form except the last, and for $Ax = 0$ that means all $n$ columns coming from $A$. A square matrix in reduced row echelon form with a leading 1 in every column is $I_n$: there are $n$ leading 1s in $n$ rows, so one per row, they move strictly rightwards as you go down, and every other entry of a column holding one is zero. So elementary row operations take $A$ to $I_n$, and by the Fact of life their elementary matrices do the same.□
Proof
There is nothing to find: the candidate is written down for us, and we only have to check it from both sides. Using associativity to regroup,
\[ (AB)\bigl(B^{-1} A^{-1}\bigr) = A\bigl(B B^{-1}\bigr)A^{-1} = A I A^{-1} = A A^{-1} = I , \]and the same regrouping the other way round gives
\[ \bigl(B^{-1} A^{-1}\bigr)(AB) = B^{-1}\bigl(A^{-1} A\bigr)B = B^{-1} I B = B^{-1} B = I . \]So $B^{-1}A^{-1}$ undoes $AB$ from both sides, which is what Definition 3.35 asks for, and by Lemma 3.38 it is the only matrix that does.□
The order reverses, and it has to. Undoing a composite means undoing the last thing done first: $AB$ applies $B$ and then $A$, so its inverse applies $A^{-1}$ and then $B^{-1}$.
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.
Reducing $A$ to the identity does two things at once. It tells you $A$ is invertible, and the elementary matrices you used along the way multiply together to give $A^{-1}$. In fact you do not have to form them: apply the same sequence of operations to $I_n$ and you have $A^{-1}$ directly, which is Theorem 3.43 in the notes and the Gauss–Jordan procedure for inverting a matrix.
- Let $A \in M_{m,n}(\mathbb{R})$, let $b \in \mathbb{R}^m$, and suppose some $B \in M_{n,m}(\mathbb{R})$ has $BA = I_n$. Show that $Ax = b$ has at most one solution, and that the only candidate is $x = Bb$. Then show with \[ A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{pmatrix} , \qquad B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} , \qquad b = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \] that there may be no solution at all.
- Suppose instead that some $C \in M_{n,m}(\mathbb{R})$ has $AC = I_m$. Show that $Ax = b$ has at least one solution. Then show with $A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ that it need not be unique.
- Part (a) says a left inverse makes the solution unique whenever there is one. It is tempting to read that as invertibility and conclude that some $C$ must satisfy $AC = I_m$ after all. Show that no such $C$ exists for the $A$ of part (a), and say which step of the square-matrix story has no counterpart here.
- Now go back through the proof of Theorem 3.36 with a non-square $A$ in mind. Which steps stop making sense, and which single step of the second direction is false rather than merely ill-shaped? Give a counterexample to it.
Solution
(a) Suppose $Ax = b$. Multiplying on the left by $B$ and regrouping,
\[ Bb = B(Ax) = (BA)x = I_n x = x , \]so every solution equals $Bb$, and there is at most one. Notice what this does not say: nothing here checks that $Bb$ is a solution. For the matrices given, $BA = I_2$, and $Bb = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$, but
\[ A \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \neq \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = b , \]so $Ax = b$ has no solution. The third entry of $Ax$ is always $0$, so this system is solvable only when $b_3 = 0$.
(b) This time $x = Cb$ is a solution, because
\[ A(Cb) = (AC)b = I_m b = b . \]Uniqueness is what goes. With $A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ take $C = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{pmatrix}$, so that $AC = I_2$. Now $A \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$, so for any $t$ the vector $Cb + t\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}$ is another solution, and there are infinitely many.
Parts (a) and (b) together are Lemma 3.39 taken apart. Its proof used both halves of $BA = AB = I$, and used them for different things: $BA = I$ gave uniqueness and $AB = I$ gave existence. For a square matrix Lemma 3.38 says the two halves always arrive together, so you get both conclusions at once. Drop squareness and they come apart, each half of the conclusion staying with its own half of the hypothesis.
(c) The tempting move is to take $C = B$. But $BA = I_n$ says nothing about $AB$, which for the matrices of part (a) is the $3 \times 3$ matrix
\[ AB = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} \neq I_3 . \]And no other $C$ does any better: the third row of $A$ is zero, so the third row of $AC$ is zero for every $C \in M_{2,3}(\mathbb{R})$, while $I_3$ has a $1$ there. The step with no counterpart is the one that manufactures a right inverse. Lemma 3.38 does not do it: it says a left inverse and a right inverse must agree, but only once you have both. What produces the second one, for a square matrix, is Theorem 3.36, by reducing $A$ to $I_n$; and that is precisely the argument part (d) shows breaking down.
(d) Take $A \in M_{m,n}(\mathbb{R})$ with $m \neq n$.
The first direction never starts. Elementary matrices act on rows, so for such an $A$ every $E_i$ is $m \times m$ and $E_k E_{k-1} \cdots E_1 A$ is again $m \times n$. Asking that product to be an identity already forces $m = n$, so statement (b) of the theorem cannot even be posed. Step 1 says the same thing in the other direction: it writes $BA = I_n$ with $B$ of size $m \times m$ and $A$ of size $m \times n$, and that product is $m \times n$, so the equation is correctly shaped only when $m = n$. These steps are not false; they are ill-shaped.
The second direction gets further. Step 3 runs unchanged: $Ax = 0$ having only the solution $x = 0$ still gives, by Theorem 3.27, a leading 1 in every one of the $n$ columns coming from $A$. The step that is genuinely false is the one after it, that a matrix in reduced row echelon form with a leading 1 in every column must be the identity. A counterexample is the matrix from part (a):
It is already in reduced row echelon form, both of its columns carry a leading 1, and it is not an identity matrix. It is $I_2$ with a row of zeros underneath. In general, when $m > n$ that argument delivers $I_n$ sitting on top of $m - n$ zero rows, and when $m < n$ there are not enough rows to carry $n$ leading 1s, so the hypothesis cannot be met at all. Squareness is exactly what closes the gap between a leading 1 in every column and the identity.□
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}$:
\[ \left(\begin{array}{c|c} 5 & 1 \end{array}\right) \ \xrightarrow{\ \times\, \frac{1}{5}\ }\ \left(\begin{array}{c|c} 1 & \tfrac{1}{5} \end{array}\right) . \]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,
\[ E \left(\begin{array}{c|c} A & I \end{array}\right) = \left(\begin{array}{c|c} EA & EI \end{array}\right) . \]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.
- Form the $n \times 2n$ array $\left(\begin{array}{c|c} A & I_n \end{array}\right)$.
- Apply elementary row operations to the whole array until the left half is in reduced row echelon form. Say the array has become $\left(\begin{array}{c|c} C & B \end{array}\right)$.
- If $C = I_n$, then $A$ is invertible and $A^{-1} = B$.
- If $C \neq I_n$, then $A$ is singular, and there is no inverse to find.
Part (d) is not a failure of the method but an answer from it. By Theorem 3.36, if row reduction cannot reach $I_n$ then no sequence of operations can, and $A$ is not invertible.
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:
\[ A^{-1} = \begin{pmatrix} 1 & -1 \\ -1 & 2 \end{pmatrix} . \]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
\[ A^{-1} = \frac{1}{2}\begin{pmatrix} -1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end{pmatrix} . \]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.
Answer
Yes. Go through Definition 3.25 one condition at a time. The one zero row is at the bottom. The leading entry of the non-zero row is a $1$. There is only one leading 1, so nothing has to be to the right of anything. And the column holding it, the first, is $\begin{pmatrix} 1 \\ 0 \end{pmatrix}$, zero everywhere else.
The $2$ in the top right is the part that makes people hesitate, and it is allowed. The rule about zeros applies to the columns that carry a leading 1, and the second column carries none.□
Answer
That $A$ is singular, and that we stop. The left half has reached reduced row echelon form and it is not $I_2$, so we are in part (d) of the method: there is no inverse to find. By Theorem 3.36 this settles it for good, since no other sequence of row operations could reach $I_2$ either.
Theorem 3.27 says the same thing in terms of solutions. The second column carries no leading 1, so $Ax = 0$ has infinitely many solutions; $\begin{pmatrix} 2 \\ -1 \end{pmatrix}$ is one of them. An invertible matrix cannot allow that, because Lemma 3.39 would make the solution unique.
One thing not to do: the right half now reads $\begin{pmatrix} 1 & 0 \\ -2 & 1 \end{pmatrix}$, and it means nothing. You only read an inverse off the right half when the left half has become the identity.
None of this should be a surprise. The second row of $A$ is twice the first, so a row operation was always going to turn one of them into zeros.