Number theory: Part I

Table of contents:

• Introduction: the general strategy of finding homomorphic spaces
• Integral points on hyperplanes: prerequisites
• Integral points on hyperplanes: Bezout, Euclid's algorithm, Gaussian elimination and Smith normal form

---

Introduction

Number theory is just algebra done over the integers. This seems kind of weird at first -- the integer lattice seems like a rather arbitrary lattice to care about; I mean, if you're looking for solutions for an equation over the reals, you can always show existence and approximate the solution by analytic means, but whether or not an arbitrary real number is an integer is just so arbitrary, why would you even CARE about that--

But the integers do have some special structure. The most obvious interesting thing about the integers is divisibility. One can show something isn't a solution by taking both sides $\mod b$ for some $b$ -- i.e. one can get restrictions on the space of possible solutions by considering the problem in $\mathbb{Z} \mod b$. 

This is an example of a much more general strategy in mathematics to restrict the space of possible solutions -- apply a homomorphism to both sides and eliminate non-solutions in the homomorphic space. If you apply an isomorphism, you can also do the converse -- i.e. accept solutions in the isomorphic space.

So we're interested in the structure of $\mathbb{Z}$, so as to know what it can homomorph to. Addition and multiplication are rather important to the structure of $\mathbb{Z}$ -- we like to call this a ring. In fact, $\mathbb{Z}$ is the "free ring". If you know any category theory, this means $\mathbb{Z}$ is the ring that has homomorphisms to every other ring. 

Actually, $\mathbb{Z}$ is the "free ring with no generators" -- the free ring with some generators $X_1,\dots X_n$ is called the polynomial ring with these variables, and is the free object in the category of "rings that contain the elements $X_1,\dots X_n$". BTW this is why Galois theory is so important, because it studies quotients of $K[X]$, the free ring with one generator. Also $\mathbb{Q}$ is the free field, and the rational functions form the free fields with some generators. 

In basic number theory, there are two sorts of such rings to which we will be interested in homomorphisms to: $\mathbb{Z}/b\mathbb{Z}$ (which we've discussed) and $\mathbb{Z}[\alpha]$ for some non-integer $\alpha$. 

This is why the algebraic properties of these rings are of so much importance in number theory -- that's why algebra is so important in number theory. The Chinese remainder theorem -- the statement that the obvious projection map $\mathbb{Z}/(n_1\dots n_k)\mathbb{Z}\to\mathbb{Z}/n_1\mathbb{Z}\times\dots\times\mathbb{Z}/n_k\mathbb{Z}$ is a ring isomorphism -- is such an algebraic property. Stuff about quadratic and higher residues (squares mod $b$) are such algebraic properties. Stuff about when $\mathbb{Z}[\alpha]$ is a UFD, PID blabla are such algebraic properties. We will make reference to them throughout this course without getting into the details of things.

So the topic is solving equations over the integers. In particular, solving polynomial equations over the integers. 

---

Integral points on hyperplanes: prerequisites

The following animation is a picture illustration of Euclid's algorithm:

Make sure you understand exactly what this algorithm is doing at each step, and how it corresponds to Euclid's algorithm as you know it (think of it with a particular example). Why does this work -- how do we know we will finish up the rectangle in a finite number of steps (i.e. actually get a GCD), what property of the integers ensures this?

Anyone got intuition for Bezout's identity? I can say that I'm not a fan of using Euclid's algorithm -- instead, I prefer the following argument: let $d$ be the smallest positive $ax+by$ -- certainly the gcd must divide $d$, but also $d$ must divide $x$ (and analogously $y$), or its remainder will be smaller than $d$. So $d$ must be the gcd.

---

Integral points on hyperplanes: Bezout, Euclid's algorithm, Gaussian elimination and Smith normal form

$$381x+66y=b$$

So Bezout's identity tells us that the equation $a_1x+a_2y=b$ (by convention $a_1, a_2, b$ are known/"constants" while $x, y, z$ are to be solved for/"variables") is solvable iff $\mathrm{gcd}(a_1,a_2)$ divides $b$. In fact it says the equation $\sum a_ix_i=b$ is solvable iff $\mathrm{gcd}((a_i))$ divides $b$. 

In fact it tells us there is an algorithm to compute this solution $x_i$ -- namely, Euclid's algorithm. 

To help us generalize this: the nicest way to think of Euclid's algorithm algorithmically is as a sequence of matrix multiplications. E.g.

$$\begin{align}381&=5\times 66+51\\ 66&=1\times 51+15\\ 51&=3\times 15+6\\15&=2\times 6+3\\6&=2\times 3+0\end{align}$$

$$\begin{align}\left[\begin{array}{c}381\\66\end{array}\right]&=\left[\begin{array}{cc}5&1\\1&0\end{array}\right]\left[\begin{array}{cc}1&1\\1&0\end{array}\right]\left[\begin{array}{cc}3&1\\1&0\end{array}\right]\left[\begin{array}{cc}2&1\\1&0\end{array}\right]\left[\begin{array}{cc}2&1\\1&0\end{array}\right]\left[\begin{array}{c}3\\0\end{array}\right]\\&=\left[\begin{array}{cc}127&52\\22&9\end{array}\right]\left[\begin{array}{c}3\\0\end{array}\right]\\ \left[\begin{array}{cc}3&0\end{array}\right] &= \left[\begin{array}{cc}381&66\end{array}\right]\left[\begin{array}{cc}-9&22\\52&-127\end{array}\right] \end{align}$$

So in effect, we're solving the linear equation (where $\mathbf{a},\mathbf{d}$ are row vectors) $\mathbf{a}\mathbf{x}=b$ by instead solving $\mathbf{d}\mathbf{y}=b$ where $\mathbf{d}=\mathbf{a}\mathbf{T}$ is of the form $(d,0)$ and $\mathbf{T}\in\mathrm{GL}(\mathbb{Z}^2)$. 

Note also that left- (resp. right-) multiplication by $\left[\begin{array}{cc}\lambda&1\\1&0\end{array}\right]$ can also be understood as "add $\lambda$ copies of Row 1 to Row (resp. Col) 2, then switch Row (resp. Col) 1 and Row (resp. Col) 2"  -- i.e.

$$\left[\begin{array}{cc}\lambda&1\\1&0\end{array}\right]=\left[\begin{array}{cc}0&1\\1&0\end{array}\right]\left[\begin{array}{cc}1&0\\\lambda&1\end{array}\right]$$

The group $\mathrm{GL}(\mathbb{Z}^2)$ can be understood as the group of GCD-preserving transformations. (The algorithm to simplify $\mathrm{gcd}(ax+by,cx+dy)$ -- using the identity $\mathrm{gcd}(x+\lambda y, y)=\mathrm{gcd}(x,y)$ -- is precisely Euclid's algorithm.)

But the nice thing about this matrix approach is that it can be used to solve systems of linear equations. It is not sufficient to solve these equations independently and state the conditions as $d_1\mid c_1,\dots d_m\mid c_m$, because the solution sets for each equation needn't intersect (think: $3x+6y=3, 3x+9y=3$). 

Instead, we solve $\mathbf{A}\mathbf{x}=\mathbf{b}$ by solving $\mathbf{D}\mathbf{y}=\mathbf{c}$ where $\mathbf{D}=\mathbf{S}\mathbf{A}\mathbf{T}$, $\mathbf{c}=\mathbf{S}\mathbf{b}$ and $\mathbf{D}$ is diagonal, $\mathbf{S},\mathbf{T}\in\mathrm{GL}(\mathbb{Z}^n)$. This $\mathbf{D}$ is called the Smith normal form of $\mathbf{A}$, and can be seen as a generalization of the Greatest Common Divisor to a set of integer vectors.

If anyone has a good thorough exposition for the algorithm to calculate the Smith normal form -- and some analogous intuition to that for its special case the Euclidean algorithm -- let me know.

Motivating ring theory, domains with integer-polynomial analogies

When you were first introduced to polynomial long division, you were struck by how a process that worked for integers worked for abstract polynomials. Integer division seemed rather "specific" -- focused on details like the resulting quotient having to be an integer -- and it seems bizarre that even the notion of integer division could be generalized beyond the integers.

It's not like integer division is just polynomial division with $x=10$ or something -- the results of the division are different, because integer division does not assume a base of 10.

But polynomial division also focuses on an analogous detail: the resulting quotient having to be a polynomial. And the essential lesson of mathematics, and the idea of abstract mathematics, is that serious analogies are the sign of abstraction.

So what makes polynomials and integers similar -- in what sense are they similar? -- that we can perform a "long division" algorithm on them?

And you know: this is not the only analogy between integers and polynomials either. Here's a list, with a general "abstract" phrasing that works for both integers and polynomials:

• Division with remainder: For any $a,b$, there is some "unique" representation $a=qb+r$, where "uniqueness" is with respect to the property that $r<b$ (this $<$ ordering on the integers refers to the the ordering of the absolute value, and on the polynomials refers to the degree).
• Bezout's identity: For any $a, b$, the set $\{\lambda a + \mu b\}$ is precisely the multiples of $\mathrm{gcd}(a, b)$.
• Unique factorization: For any $a$, there exists a unique representation $a=p_1\dots p_n$ among $p_i$ that are "prime" ("irreducible") in the sense of not having any further factors. Well, is that really true? Not exactly: prime numbers can be factored with $-1$s and $1$s, and irreducible polynomials can be factored with constant polynomials. Well, this caveat has to do with stuff having itself as a factor, e.g. $x-2=(1/2)\cdot(2)\cdot(x-2)$ or $37=(-1)\cdot(-1)\cdot 1\cdot 37$. This means the other elements of this "factorization of the prime number" multiply to 1/are each "invertible" ("units"). So we should say we have unique factorization is "up to units". 
• Greatest common divisors: For any $a, b$, there is a $\delta$ that divides both and is divided by all $d$ that divide both $a$ and $b$ (note that the term "divides" can exist in more generality than the assumptions of "division with remainder").

Well, the first thing we observe is that we should assume the existence of some notions of addition, subtraction and multiplication -- these seem to be the "fundamental" structures present among integers and polynomials (as opposed to e.g. rational numbers, rational functions which also require division or natural numbers which don't have subtraction). 

We will omit discussing the properties of these operations for now, as we don't yet have enough to motivate them on. 

Next, each of these discussed properties can be considered as special axioms for special cases of rings, domains where specific important theorems hold -- we call them, respectively: 

• Euclidean domain: The ring is equipped with a natural number-valued magnitude function $\|\cdot\|:R\to\mathbb{Z}^{\ge 0}$, called the Euclidean function. For all $a,b$ in $R$ with $b$ non-zero (intuit out this condition), there exist $q, r$ with $\|r\|<\|b\|$ such that $a=qb+r$. 
• Principal Ideal Domain: A ring where all ideals (additive subgroups invariant under multiplication by a ring element) are principal (a set of multiples of a generating element). Another abstraction is a "Bezout domain", which only requires that linear combinations of principal ideals are principal, but a PID should be seen as a more "natural" generalization.
• Unique factorization domain: A ring where every element has a unique factorization into irreducibles, modulo multiplication by a unit. 
• GCD domain: A ring in which any two elements has a GCD. 

(Quick comments on why the Euclidean function must map to the naturals: in fact, they could map to any "well-ordered set" (a totally ordered set in which every subset has a least element). The reason why this property is needed -- why we can't, e.g. map to the nonnegative reals -- is to ensure Euclid's algorithm terminates.)

The abstractions of the basic theorems about integers and polynomials occur as relationships between these domains. As it turns out, we will see that:

\[{\rm{ED}} \Rightarrow {\rm{PID}} \Rightarrow {\rm{UFD}} \Rightarrow {\rm{GCD}}\]

Before that, though, we can already play with some basic results we'd like, to get a feel of what axioms about ring addition and multiplication we should assume.

E.g.

• What should $\|0\|$ equal? Prove that 0 must have the least magnitude of any ring element, making up the axioms you need on the fly. You should require: additive identity, additive inverse, additive associativity.
• Try to prove some obvious results regarding Bezout's identity, like with $a$ and $b$ equal. You should require: left-distributivity, right-distributivity. 
• Consider generalizations of two-element properties, like the Bezout identity, to multiple elements. You should require additive associativity, multiplicative associativity, additive commutativity, multiplicative commutativity.

Well, to be honest these all seem like fairly elementary properties that would be useful outside the cases of these special domains. Out of the following properties:

1. Left-distributivity
2. Right-distributivity
3. Additive associativity
4. Additive identity
5. Additive inverse
6. Additive commutativity
7. Multiplicative associativity
8. Multiplicative identity
9. Multiplicative commutativity
10. Multiplicative inverse

10 is not a ring axiom (because integers and polynomials don't have it). 1-7 essentially always are. 8 sometimes is, but not if you want e.g. the even numbers to be a ring. 9 typically isn't, although this is once again mostly just a matter of convention -- you can't really "see" that non-commutative rings appear often enough to justify their classification of rings, etc.

Presumably 6 (additive commutativity) is hardest to see the importance of, but it's relevant to note the relationships between these axioms. In fact, it is fairly simple to show that 1, 2 and 8 imply 6 (consider $(1+1)(x+y)$). As a result, addition -- the operation that multiplication distributes over -- is just generically seen as commutative.

Another important property often seen in algebraic problems is the ability to factor to find roots, i.e. to say that if $ab=0$, either $a$ or $b$ should be 0. This is known as an integral domain. The full sequence of inclusions, as we will see, is actually given by:
\[{\rm{ED}} \Rightarrow {\rm{PID}} \Rightarrow {\rm{UFD}} \Rightarrow {\rm{GCD}} \Rightarrow {\rm{ID}} \Rightarrow {\rm{Ring}}\]
The broader point of all this is that you should start often thinking of a lot of basic mathematical facts in the language of abstract algebra -- what kind of ring/domain is this result valid in? etc. -- because this is the most general setting in which a result is valid in, and you know exactly what it is "saying", i.e. what implies what. 

What even are pure and applied math, anyway?

Not really a serious post.

I see the words "pure math" and "applied math" used a lot, and there seem to be some completely distinct meanings of the phrases:

1. Formal math and informal math -- you can certainly approach things like summing divergent series completely formally (follow the link for proof!), and I'm sure you could in principle be hand-wavy with category theory. So this is really about the method with which you do mathematics, not the field itself. An example of where you see this is the distinction between analysis and calculus (well, a distinction -- sometimes calculus is defined specifically as having to do with differentials and integrals while analysis is a broader field).
2. Abstract math and concrete math -- this really has multiple levels: category theory, abstract mathematics, mathematics, science, engineering, specific numerical calculation. The line is often drawn either before or after "mathematics".
3. Theoretical and applied -- closely related to the previous point, differing by the purely social question of the purpose of the study.
4. Everything else vs statistics -- I think this arises from a conflation between statistics and applied/concrete statistics. Statistics can really be a totally formal field of mathematics or even abstract mathematics, but I guess people often fail to draw the distinction (unlike, say, between "differential equations" and "applied differential equations in engineering").
5. Algebra vs everything else -- Perhaps a result of the fact that analysis and geometry often restrict to handling special concrete objects like the real and complex numbers.

I guess the reason these distinctions are often taken as synonymous is that they're quite correlated. As you get more abstract, you may feel a stronger obligation to be more formal to make sure you haven't missed out on some so-called pathological cases (although I think it's perfectly possible to develop intuition for such pathological situations, see e.g. my e^(-1/x) article, or the topology series). When working for an applied purpose, it may not be useful to be too formal, for practical constraints.

The correlation really lines up with the fundamental "purpose of mathematics". The point of having axiomatisations is that someone applying abstract ideas in concrete situations can just check if the axioms are satisfied -- and so you really must formally deduce things from them to make sure you're not making some assumptions specific to one concrete situation that you have in mind.

(Another example of such ambiguity is the distinction between "theoretical science" and "practical science". I've still not figured out if the latter refers to experimental science or applied science, and there isn't even any correlation between the ideas here.)

Intuition, analogies and abstraction

$$-1=\sqrt{-1}\sqrt{-1}=\sqrt{(-1)(-1)}=\sqrt{1}=1$$
I bet you've seen the fake "proof" above that minus one and one are equal. And the standard explanation as to why it's wrong is that the statement $\sqrt{ab}=\sqrt{a}\sqrt{b}$ only applies when $\sqrt{a}$ and $\sqrt{b}$ are real, or something like that (maybe only one of them needs to be real -- something like that -- who cares?).

But if you're like me, that isn't a very satisfactory proof. Why does the identity not hold for complex numbers? For that matter, why does it hold for real numbers? Well, that is a good question, and one way of answering it would be to try and prove the identity for real numbers, and see what properties of the real numbers (or of the real square root, in particular) you use. And if this article were being filed under "MAR1104: Introduction to formal mathematics", that's how I might explain things -- but that doesn't give us too much insight -- not about square roots and complex numbers, anyway.

Let's think about what $\sqrt{ab}=\sqrt{a}\sqrt{b}$ means.

What does the square root of a real number mean, anyway? It's some property related to multiplying a real number by itself. What does multiplication mean? What does a real number mean? The picture I have in my head of the real numbers is of a line. But what exactly is this line? -- the real numbers are just a set. Why did you put them on this line in this specific way? In doing so, you gave the real numbers a structure, a specific type of structure called an "order", defined by the operation $<$.

But there are other ways to think about/structure the real numbers. One way is to think of real numbers as (one-dimensional) scalings. You can scale things like mass, and volume, using real numbers, representing the scalings as real numbers. Scaling a mass by 2 is equivalent to multiplication by 2. So this gives the real numbers a multiplicative structure, defined by the operation $\times$ (or whatever notation -- or lack thereof -- you prefer). And the "real line" then just represents the image of "1" under all scalings.

So the way to think about square roots is to think of numbers as linear transformations called scalings, and think about the scaling that when done twice, gives you the number you're taking the square root of. So what's $\sqrt{-1}$? What's $-1$? $-1$, multiplicative, is a reflection. What's its square root? Try to think of a (linear!) transformation that when done twice gives you a reflection. It can't be done in one dimension. And can you think of another such transformation? Can you prove these are the only two? Are you sure -- what about if you add a dimension?

So the natural way to think about square roots of numbers that may or may not be complex, is with so-called "Argand diagrams", on the complex plane, the image of "1" under all complex numbers multiplicative.

Click "edit graph" to play with a and b!

To simplify things, consider only unit complex numbers (this is okay, because all complex numbers can be written as a real multiple of a unit complex number and a real number). The product of complex numbers $a$ and $b$ involves rotating by $a$, then rotating by $b$. The square roots of $a$ and $b$ involve going halfway around the circle as $a$ and $b$, and the square root of $ab$ goes halfway around the circle as $ab$.

So it seems like the identity should hold, doesn't it? $\sqrt{ab}$ goes half as much as $a$ and $b$ put together -- this seems to be exactly what $\sqrt{a}\sqrt{b}$ does -- go around half as much as $a$, then half as much as $b$. Isn't $\frac{\theta+\phi}2=\frac{\theta}2+\frac{\phi}2$?

The problem is that $\sqrt{ab}$ doesn't really go $\frac{\theta+\phi}2$ around the circle, if $\theta+\phi$ is greater than $2\pi$. You can see this in the diagram courtesy of Desmos above -- $ab$ has gone a full circle, and its square root is defined to halve the argument of $ab$, but the argument isn't $\arg (ab)=\arg (a) + \arg (b)$, rather:

$$\arg (ab) \equiv \arg (a) + \arg (b) \pmod{2\pi}$$
But halving is not an operation that the $\bmod$ equivalence relation respects -- not in general, anyway. It is not true that

$$\arg (ab)/2 \equiv (\arg (a) + \arg (b))/2 \pmod{2\pi}$$
Instead:

$$\arg (ab)/2 \equiv (\arg (a) + \arg (b))/2 \pmod{\pi}$$
Let's recall from basic number theory -- on integers, the general result regarding multiplication on mods. If $a\equiv b\pmod{m}$, then $na\equiv nb \pmod{nm}$, certainly, and also $na\equiv nb \pmod{m}$ iff $n$ is an integer*. But $1/2$ isn't an integer, which is why only the former result is relevant.

This is also why $(ab)^2=a^2b^2$ does hold for complex numbers.

*when $n$ isn't an integer, we need $na$, $nb$ to be integers for the statement to even be well-defined in standard number theory, and then you have a result for division on mods involving $\gcd(d,m)$, etc. This isn't a concern for us here because we're dealing with divisibility over the reals -- if you want to be formal, a real number is divisible by another real number if the former can be written as an integer multiple of the latter.

So there you have it -- I just demonstrated a very fundamental analogy between two seemingly incredibly unrelated ideas: complex numbers modular arithmetic -- square roots of complex numbers don't multiply naturally, because mod doesn't respect division. It's almost as if somehow, somewhere, somehow magically, exactly the same kind of math was used to derive results, to prove things, about these unrelated objects.

As if they're just two instances of the same thing.

I wonder what that thing could be.

---

Let's talk about something completely unrelated (no, genuinely -- completely unrelated -- I won't tell you this is an instance of the "same thing" too). Let's talk about logical operators, specifically: do $\forall$ and $\exists$ commute? I.e. is $\forall t, \exists s, P(s,t)$ equivalent to $\exists s, \forall t, P(s,t)$?

You just need to read the statements aloud to realise they don't. To use a classical example, "all men have wives" and "there is a woman who is the wife of all men" are two very different statements (okay, in this case both statements are false, so they're equivalent in that sense, so you get my point).

But let's think more deeply about why they don't commute. What do $\forall t, \exists s, P(s,t)$ and $\exists s, \forall t, P(s,t)$ mean, anyway? $\forall$ and $\exists$ are just infinite $\land$ and $\lor$ statements , i.e. $\forall t$ is just an $\land$ statement ranging over all possible values that $t$ can take and $\exists s$ is just an $\lor$ statement ranging over all possible values $s$ can take.

So $\forall t, \exists s, P_{st}$ just means (letting $s$ and $t$ be natural numbers for simplicity, but they don't have to):

$$({P_{11}} \lor {P_{21}} \lor ...) \land ({P_{12}} \lor {P_{22}} \lor ...) \land ...$$
And $\exists s, \forall t, P(s,t)$ means:

$$({P_{11}} \land {P_{12}} \land ...) \lor ({P_{21}} \land {P_{22}} \land ...) \lor ...$$
This is a bit complicated, so let's instead look at the simpler case where you have only 2 by 2 statements -- i.e. just construct the analogy between $\forall,\exists$ and actual $\land,\lor$ statements.

So the question is if:

$$({P_{11}} \lor {P_{21}}) \land ({P_{12}} \lor {P_{22}}) \Leftrightarrow ({P_{11}} \land {P_{12}}) \lor ({P_{21}} \lor {P_{22}})$$
This is interesting. Maybe you see where this is going. Let me just do a notation change -- I'll use "$\times$" for $\land$, "$+$" for $\lor$, "$=$" for $\Leftrightarrow$" and some new letters for the propositions. Under this new notation, where $\times$ is invisible as always, we're asking if:

$$(a + b)(c + d) = ac + bd$$

Aha! This is Freshman's dream, isn't it? And we know it's not true -- it's a dream, after all, don't be delusional -- and we know why it's not true too.

But wait -- we aren't talking about elementary algebra here. I just gave you some silly notation and made it look like Freshman's dream. But here's the thing: the proof (or algebraic proof -- a counter-example is also a proof, but that isn't so interesting... not here, anyway) that these propositions aren't equivalent is exactly the same as in algebra. We expand out the brackets (because we know that $\land$ distributes over $\lor$ -- we also know that $\lor$ distributes over $\land$, incidentally, something that is not true in standard algebra) and point out that there are extra terms, and point out that these extra terms change the value of the expression (they aren't zero).

So there's some kind of relationship between the boolean algebra and an elementary algebra. A lot of proofs that can be done in one of these algebras can be written almost identically in the other. Not all these proofs, mind you -- then the algebras would just be isomorphic to each other -- but some of them can. Maybe a lot of important ones can.

An abstraction that produces such proofs simultaneously for both elementary algebra and boolean algebra may be more complicated than you think -- there's no real sense in which a statement is "always zero" in boolean algebra. Take for instance, distributivity of $\lor$ over $\land$ -- $a+bc=(a+b)(a+c)$. This is not true in elementary algebra, because the extra term $ab+ac$ is not always equal to zero ($a^2\ne a$ is not really an example, because $a^2=a$ for $a\in\{0,1\}$ -- but $a(b+c)=0$ is not true for all $a,b,c\in\{0,1\}$). It's just that it leaves the value of the existing terms unchanged in this specific instance.

---

I've just illustrated two examples here -- the first one is a type of group, by the way, but you've probably seen dozens of other such "connections between different areas of mathematics" yourself. I've made these sorts of analogies fundamental to a lot of the articles I've written here (I think). You might've just thought of them as interesting insights, but in reality, abstract mathematics/abstract algebra -- or really just mathematics in general -- is all about these analogies.

In a sense, mathematics is largely about abstraction. I mean, that's not what mathematics fundamentally is -- fundamentally, math is just logic -- but it's how mathematics largely functions. Whenever one talks of axioms, you could think of them as fundamental defining ideas of mathematical objects, and you can also think of them as "interfaces" between mathematics and reality (see my introduction to linear transformations). There are a massive number of different physical phenomena that we can study, and rather than prove everything from scratch for each one of them, it is much better -- and more insightful in terms of understanding the connections between things -- to show that they satisfy a certain set of axioms that apply to a whole range of things, and then deduce that all the logical consequences of these axioms -- all theorems -- are satisfied by the objects.

If we can do that with physical phenomena, we can sure as well do it with mathematical phenomena too -- instead of proving something from scratch for every new mathematical object, we prove that it is a group, or a ring, or a field, or a module, or an algebra, or a topology, or a geometry of some sort, by verifying it matches the axioms -- and then use all the abstract knowledge we have about these things and deduce they must necessarily apply to our new object, because they are logical consequences of our axioms.

Abstract mathematics is, in this sense, all about generalising things by finding the "smallest set of axioms" the thing requires.

(Well, not really -- the most general statement is "true", and everything else is just a logical deduction from this statement. So in that sense mathematics is all about finding special cases. But in order to know what to take a special case of, and what special case that "what" is of "true", you need to generalise.)

List some weird analogies you've seen before in math. Something about divisibility sound familiar?

Introduction to linear transformations

Linear algebra, and algebra in general (algebra is one of the trinity of pure mathematics -- algebra, analysis and geometry) concerns itself with mathematical objects and their transformations.

Linear algebra actually deals with a specific kind of active/passive transformations, called linear transformations, but let's remain general for now, as our intention is to introduce algebra in entirety and try to understand the motivation to study linear algebra in particular.

There are two broad categories of mathematical objects that we call transformations: active and passive transformations. An active transformation is basically a function that maps an element (called a "vector") to another -- it involves actually changing the mathematical object in concern. On the other hand, a passive transformation is a transformation of the co-ordinate basis so that the representation in the basis transforms in precisely the opposite way as the basis so that the object itself remains the same.

A couple of analogies help reinforce this classification:

• Numerical bases − Consider the number "101" in base 10. If we wanted to convert this into base 2, we would write 1100101. This is a passive transformation -- the actual mathematical object (101) remains the same, while the representation changes. On the other hand, suppose we kept the representation "101" but instead talked about the number that was 101 in base 2 (i.e. 5). This is an active transformation, because the actual number has stayed the same -- it's just that our "basis vectors" (1, 10, 100...) have been transformed to a new basis (1, 2, 4...) and our mathematical object itself, which is always the linear sum of 1 times the third basis "vector" (100 or 4) plus 0 times the second basis vector (10 or 2) plus 1 times the first basis vector (1 or 1) has transformed under this transformation.
• Definitions − Suppose I made the statement "Bananas are yellow". This statement is true. But now if I were to redefine the word "banana" to mean what we usually call (or to be more precise, called in our previous system of definitions) "apple", then the statement would be false (the property of truth is not invariant under the transformation). This was an active transformation. On the other hand, if we redefined "apples" to mean "bananas" and changed the form of the sentence to read "Apples are yellow", the statement remains the same, and it remains true. This is a passive transformation.

An example of a co-ordinate (passive) transformation would be $(x,y)\rightarrow(\sqrt{x^2+y^2},\arctan y/x)$, which converts from Cartesian to polar co-ordinates. Alternatively, one could create an active transformation where $r$ takes on the value of the former x-coordinate and $\theta$ takes on the value of the former y-coordinate. It would be clumsy and pointless in this case, but it could be done.

Both passive and active transformations find a variety of uses in physics -- passive transformations are of central importance in relativity, while active transformations are an important tool in quantum mechanics.

Linear algebra deals with a specific kind of transformations, called linear transformations. A linear transformation is a transformation that satisfies the property that $L(ax+by)=aL(x)+bL(y)$ where L is the linear transformation, a and b are objects called "scalars", and x and y are objects called "vectors". Another way of putting this is that a linear transformation commutes with every linear sum operator.

A linear sum operator, of course, is an operator that takes in some number of vectors, scales each by some scalar that depends on the linear sum operator and adds the scaled results. You will learn that this is equivalent to multiplying the matrix with these vectors as columns with a vector that represents the operator itself.

Then this linear transformation acts on elements from a set of vectors (called a "vector space"), over a field of scalars. Common choices for the vector space are $\mathbb R^n$, $\mathbb C^n$, etc. and common choices for the scalar field are $\mathbb R$, $\mathbb C$, etc. In these cases, the vectors can be represented as tuples of real or complex numbers, and (especially in the case of the reals) are often used to represent various physical quantities with a direction in Newtonian physics.

The formal definition of a vector space is given by the following axioms:

1. There exists an operation called "addition" on the vector space that satisfies the following properties:
1. associativity -- $(u+v)+w=u+(v+w)$
2. commutativity -- $u+v=v+u$
3. identity -- there exists a vector $0$ such that $v+0=v$
4. inverse -- there exists a vector $-v$ for every v such that $v+(-v)=0$
2. There exists an operation called scalar multiplication on the vector space that satisfies the following properties:
1. compatibility with field multiplication -- $a(bv)=(ab)v$
2. shared identity element with field multiplication -- $1v=v$ where 1 is also the identity of field multiplication
3. distributivity over vector addition -- $a(u+v)=au+av$
4. distributivity over scalar addition -- $(a+b)v=av+bv$

Therefore our vectors need not be anything of the sort you'd encounter in a high-school physics or math class -- they can be functions, SVG files, arrays in computer programming, whatever, and a lot of other mathematical objects (one such object you'll eventually encounter is the tensor).

One of the reasons linear algebra is taught early is to introduce how mathematics works, and axioms are at the very foundation of mathematics. To a pure mathematician, axiomatic systems represent entire universes -- a pure mathematician unknowingly adopts a Platonist metaphysics, where our universe, the domain of physics, is just one among all the other possible axiomatic systems, all within the domain of mathematics.

On a fundamental level, this is not a testable or even meaningful claim -- however, it's a useful picture to keep in mind while thinking about mathematics and about being precise when you hear people talking about "existence", etc.

An equally interesting picture, though, is that of the applied mathematician. The applied mathematician is concerned with the physical world as it is. He observes the universe and finds that certain rules of logic based on some starting points turn up all the time in the real world -- in physics, in computer science, in finance, and practically everything else. For example, kinematics and relativity, quantum mechanics, and computer programming all seem to make use of certain logical ideas -- certain mathematical structures -- in very different ways. This idea I'm talking about is a vector and its linear transformations. So the applied mathematician probes for some set of logical assumptions from which these conclusions can be logically derived, called axioms. In the case of linear algebra, the axioms are the eight listed above.

So to an applied mathematician, axioms are more like an "interface" between the mathematical theory and its various applications. From the axioms, one can derive all the "theorems" of the mathematical theory, all its features. Rather than re-discovering all these facts about the various physical phenomenon, if the physicist or engineer or computer scientist or whoever can show that one can make a precise correspondence from the things in his field to the objects in the mathematical theory (such as mapping the quantities of "velocity", "momentum", "position", etc. to "vectors", producing a sensible idea of addition and dot products, etc.), then all the results (theorems) involving these mathematical objects will also apply to the things in his field. This is why mathematics is often called the art of identifying different things with analogous logical structures.

For the record, this is also why mathematics -- or to be more accurate, applied mathematics, or the mathematics we study is so useful in describing things -- it's designed that way. "Things" produce the motivation for us to do math, and specifically the kind of math that is useful to describe these things. Think of some other mathematical theories you know of -- calculus, the elementary algebra of the real numbers, of the complex numbers, of the integers, of the natural numbers, of the rational numbers, etc. What physical phenomena do they describe?

The idea of an axiomatic basis -- whether interpreted in the pure-mathematician sense or in the applied-mathematician sense, for there is no real difference except in how humans think of it -- is central to modern mathematics. Richard Feynman called it the "Greek school" of mathematics and science, as opposed to the "Babylonian school", which does not isolate a set of axioms from all the statements of the theory. The Babylonian school tends to be how physics and the other sciences operate, but only under the assumption that the mathematicians will eventually bring rigor to their field (e.g. with mathematical physics).

A set of axioms is seldom unique. There are always multiple different possible sets of statements that one can choose from which all the other statements of the theory can be derived (e.g. in Euclidean geometry, the Pythagorean theorem can be an axiom, replacing the parallel postulate). It's much like the concept of a defining property -- e.g. the function "$\sin(\theta)" can be defined in terms of the unit circle, where its Taylor expansion is a theorem, or the latter can be considered a definition, with the unit circle property being derived from it as a theorem.

Another example would be the number e. One definition would be the real number approached by the limit of $(1+\frac1n)^n$ as $n\to\infty$, while the other would be as the value of $\exp(1)$ where $\exp(x)$ is the function such that $\frac{d}{dx}\exp(x)=\exp(x)$ and $\exp(0)=1$. Both are defining properties, and can be derived from one another.

Coming back to the topic of linear algebra, the axioms can also be thought of as saying: a linear transformation is a transformation such that if the transformation is applied to all points on the plane, all lines (e.g. gridlines) remain lines (they don't curve) and the origin does not move (think about why these two are equivalent). The former is equivalent to stating that the gridlines (any set of evenly-spaced parallel lines) not only remain lines, but also remain evenly spaced and parallel, otherwise some other line would have to curve (try it out).

In the case that the origin does move, the transformation is called an affine transformation, which is the combination of a linear transformation and a translation, and is the generalisation of $y=mx+c$ to vectors and their transformations.

Something of interest to note here is the different ways to generalise the same thing to a more general domain -- if one wants to generalise a function or some other mathematical object $f(x)$ from a domain $x\in X$ to some $F(y)$ for $y\in Y$ where $X\subset Y$, then we do it based on some property satisfied by $f(x)$, where we decide on $F(y)$ so that it also satisfies this property.

However, we can also make the generalisation on basis of some other property -- this is exactly what's happening here, we can say that an affine transformation is a generalisation of a linear relationship among the real numbers to vectors, or that a scaling plus translation is (the cases where the first has an effect similar to the latter will be studied later when we look at eignvalues and eigenvectors). In the former case, the generalisation is based on the standard properties of a linear transformation also satisfied by $y=mx+c$, whereas in the latter case, the generalisation is based on simply scaling by a real number.

This allows one to easily determine visually if a transformation is linear. For example, it becomes clear that the Cartesian-to-Polar thing above was not a linear transformation, because the axis that is mapped to the theta-axis becomes curved.

Here's a random thought about linearity being nice. Suppose you have a relationship between $X$ and $Y$. Now if you jiggle $X$ around a bit, $Y$ jiggles a bit too. The average value of $Y$ during this jiggling period corresponds exactly on the line to the average value of $X$ during the jiggling.

On the other hand, if you have a non-linear correlation -- say with a peak in the middle -- this is no longer true. The average x-co-ordinate might give you the peak, but the average value of the y-co-ordinate is certainly not the maximum value of it. You might wonder if we can approximate non-linear things with linear things, such as by zooming close into a curve -- indeed, this is the point of calculus.

1. Prove the relation between the two different axiomatic descriptions of a linear transformation described above.
2. Hence or otherwise, prove that the following are all linear transformations:
1. Rotation around the origin
2. Scaling (along any line passing through the origin, the x- or y- axis, the line y = x, whatever)
3. Shearing
4. A combination of two (and by induction, $n$) linear transformations
3. Prove that for all linear transformations $A,B$ there exists a unique linear transformation $C$ such that $Cv=ABv$ for all $v\in V$. We then say that $C=AB$, and can define transformation composition in this way for an arbitrarily number of compositions by induction.
4. Is $(AB)C=A(BC)$ for all linear transformations $A,B,C$? Prove your answer.
5. Is $AB=BA$ for all linear transformations $A,B$? Prove your answer.

Notes about associativity and matrix multiplication (added on 2018.10.31, related to 1103-004)

If you didn't try question 3 above -- or if you didn't try it before you tried question 4 -- go try it, go think about it. It's important.

You'll often see "proofs" of the associativity of matrix multiplication, where they write out the matrix in its full, unglorifiying form -- perhaps as a row of column vectors or a column of row vectors -- and they work out both products $(AB)C$ and $A(BC)$, then say "hey, look, they're the same!"

That's a nonsensical proof. It escapes every single insight behind matrix multiplication and why matrix multiplication is important, and pretends that the rules for matrix multiplication were simply "given to us" by some god-emperor who wrote some crappy textbook. That's not useful, and that gives you absolutely no insight as to why matrix products are defined the way they are.

First of all, it's important to recognise that there really are two separate questions: Does $A(Bv)=(AB)v$, and does $A(BC)=(AB)C$. From these two you can really figure out (by repetition/induction) all other bracket combinations for whatever number of matrices.

Let's consider the matrix-vector product first. And let's say we haven't yet defined matrix multiplication.

So how on earth could we talk about multiplying $A$ and $B$ first, if we haven't yet defined multiplication on matrices? We can talk about $A(Bv)$ (because nowhere here are you multiplying two matrices), but not $(AB)v$. The idea is that we make this the definition of matrix multiplication -- we say that matrix multiplication is the composition of the transformations associated with the matrices. But for this to still be a matrix, this requires that the composition of the two matrices always be the same matrix.

I.e. if we know that there exists some $C$, such that $A(Bv)=Cv$ for all $v$.

How do we go about proving this? Well, you might have a picture in your head of linear transformations/matrices transforming the entire space/entire vector field, rather than an individual vector, i.e. linear transformations transform all vectors in the "same way" in some sense (more formally, we're re-stating the definition of a linear transformation). And the statement above just means that the composition of two linear transformations is a linear transformation.

We can prove this easily (do it for yourself), and this implies our statement earlier, because we know all linear transformations are represented by a unique matrix.

In other words -- the images of the basis vectors under any transformation are independent (i.e. we need all of them to define the transformation) and also uniquely define the transformation (i.e. there is only one transformation that transforms all the basis vectors in this way), by definition of linearity, dimensionality and basis vectors. So we can determine $C$ from this independence, i.e. ensuring that $A(Bu)=Cu$ for all basis vectors $u$, and since any vector can be written as a linear combination of these basis vectors, i.e. the basis vector images determine the transformation, we can show $A(Bv)=Cv$ for all vectors $v$.

We move on to the second kind of associativity, $(AB)C=A(BC)$.

We've really just defined everything about matrices, including matrix multiplication, in terms of vectors so far, and all the intuition in our head is in terms of vectors and vector spaces (not the matrices themselves), so the best way to understand this identity, which contains only matrices, is to recognise both sides as linear transformations, i.e. explicitly write out the vector being operated on:

$$(AB)Cv=A((BC)v)$$
Recall our definition of matrix multiplication, $(AB)v:=A(Bv)$. We can apply this on both sides, rewriting the above as:

$$A(B(Cv))=A(B(Cv))$$
Which is obviously true.