Algebra 1. Lecture 1

What algebra is

We are going to study algebra. Everyone knows from school that algebra is whatever is not geometry, but we will understand what we are doing a little differently. Historically, algebra is the science of solving all kinds of equations. Over time it turned out that to study the solutions of equations one needs additional structures that seem to have no direct connection with equations. When Galois and Abel proved that the equation of degree five is not solvable in radicals – that you cannot take an arbitrary quintic with real coefficients and write an explicit formula for its roots using only roots of some degree of something – it turned out that this fact follows directly from the theory of so-called groups. That will come much later and, most likely, not within this course, but once you have studied some algebraic things it is not very hard to do.

What is an algebraic structure? Roughly speaking, a set with some operations on it satisfying some properties. People notice that many objects have very similar properties, and it is natural to put them into one class, study the class as a whole, and only then apply the results to particular objects. The most basic algebraic structure, in my opinion, is the group.

Groups

Definition (Group). A group is an arbitrary set $G$ (from the first letter of the word "group") with one binary operation (it takes two elements of the group, in order, and produces a third element from them), traditionally called multiplication, $G \times G \to G$ , $(g_{1}, g_{2}) \mapsto g_{1} g_{2}$ , with the following properties:

associativity: $g_{1} (g_{2} g_{3}) = (g_{1} g_{2}) g_{3}$ for all $g_{1}, g_{2}, g_{3} \in G$ : brackets can be moved around;
there is a distinguished element $e \in G$ (the identity, or neutral element) such that $e g = g e = g$ for every $g \in G$ ;
for every $g \in G$ there is an inverse element $g^{- 1} \in G$ such that $g g^{- 1} = g^{- 1} g = e$ .

If in addition 4. $g_{1} g_{2} = g_{2} g_{1}$ for all $g_{1}, g_{2}$ , that is, the order of multiplication does not matter, then the group is called abelian.

In an abstract group we will omit the multiplication sign and write $g_{1} g_{2}$ instead of $g_{1} \cdot g_{2}$ , just as at school. The symbol $\exists$ means "there exists", $\forall$ means "for all".

Remark (uniqueness). The identity and the inverse $g^{- 1}$ are uniquely determined; the same goes for the identity and inverses in a ring and in a field, discussed below. Suppose a group has two elements $e_{1}$ , $e_{2}$ with the property of the identity. Multiply them: $e_{1} e_{2}$ . On the one hand, $e_{1}$ is an identity, so multiplying by it does not change the second element: $e_{1} e_{2} = e_{2}$ . On the other hand, $e_{2}$ is an identity: $e_{1} e_{2} = e_{1}$ . Altogether $e_{1} = e_{2}$ . The same with inverses: let $g_{1}^{- 1}$ and $g_{2}^{- 1}$ both be inverse to $g$ ; compute $g_{1}^{- 1} g g_{2}^{- 1}$ in two ways. Bracketing it as $(g_{1}^{- 1} g) g_{2}^{- 1}$ we get $e g_{2}^{- 1} = g_{2}^{- 1}$ ; bracketing it as $g_{1}^{- 1} (g g_{2}^{- 1})$ (which we may do by associativity) we get $g_{1}^{- 1} e = g_{1}^{- 1}$ . They are equal. So if you have proved that some element has the property of an inverse, then it is the inverse.

One more remark about groups in general: if $g = g_{1} g_{2} \dots g_{k}$ , then

g^{- 1} = g_{k}^{- 1} g_{k - 1}^{- 1} \dots g_{1}^{- 1}

that is, the elements in reverse order and to the power minus one. If you multiply $g$ by this element, everything cancels: $g_{k}$ with $g_{k}^{- 1}$ , then $g_{k - 1}$ with $g_{k - 1}^{- 1}$ , and so on, and you get the identity.

Example (groups).

The integers under addition, $(Z, +)$ . Here the role of the multiplication of the abstract group is played by addition: adding integers gives integers, addition is associative, there is a zero that changes nothing, and every number has an opposite. Under multiplication $Z$ is of course not a group: almost nothing has an inverse, least of all zero: you cannot divide by zero anywhere at all.
The rationals under addition $(Q, +)$ and the nonzero rationals under multiplication $(Q^{*}, \cdot)$ . The symbol $Q^{*}$ standardly denotes $Q$ without zero: zero cannot stay, since you cannot divide by it, and once it is thrown out everything becomes fine.
The same for the reals: $(R, +)$ and $(R^{*}, \cdot)$ .
The isometries of the plane under composition: a composition of isometries is an isometry, the inverse of an isometry is an isometry, the identity map is the identity element, and associativity holds by the very definition of composition.
More generally, all bijections of some set $X$ onto itself, again under composition. Or, the other way round, not all isometries of the plane but some of them: the symmetries of polygons, of polyhedra and so on.
For those who have read about it: linear groups of matrices: $GL_{n}$ (invertible $n \times n$ matrices under multiplication), $SL_{n}$ (with determinant one), $SU_{n}$ and the like.
An important special case of example 5, when $X = {1, \dots, n}$ , is the group $S_{n}$ . Today we will study it in great detail.

Remark (additive notation). In several examples the role of the operation is played by addition. This happens so often that, besides the multiplicative notation, which always works, there is an additive one: the operation is written $+$ , the identity $0$ , the inverse $- g$ . This is done only for abelian groups. In the group of isometries of the plane nobody ever writes a plus sign: the operation is non-commutative, and isometries composed in different orders give different compositions.

Rings

The next structure in importance and frequency is the ring. Here the terminology varies; first the more common version, then the variations.

Definition (Ring). A ring is a set $R$ (from "ring") with two binary operations, addition $+$ and multiplication $\cdot$ , such that:

1–4. $R$ is an abelian group under addition: $a + b = b + a$ ; $(a + b) + c = a + (b + c)$ ; there is a $0$ with $a + 0 = a$ ; for every $a$ there is a $- a$ with $a + (- a) = 0$ ; 5. both distributive laws: $(a + b) c = a c + b c$ and $a (b + c) = ab + a c$ ; 6. multiplication is associative: $(ab) c = a (b c)$ .

Since addition is denoted by a plus, it has to be abelian, as already said. In additive notation the inverse element is $- a$ , not $a^{- 1}$ . From now on I will not write that all elements lie in the ring – only where it is not obvious which element lies where.

Where there is definitely no disagreement: both distributive laws must hold in a ring. In most cases a ring is assumed to be associative by default; objects satisfying the first five axioms but not the sixth are called non-associative rings, but there are sources where associativity is not part of the basic set of axioms, and then a ring satisfying the sixth axiom is called associative. If in addition

$ab = ba$ , that is, the factors can be swapped,

the ring is called commutative (not "abelian"). If

there is an identity $1$ such that $1 \cdot a = a \cdot 1 = a$ for every $a$ ,

one says it is a ring with identity (a ring with one). It can happen that only $1 \cdot a = a$ holds; then the ring has a left identity. If only $a \cdot 1 = a$ , a right one. In English-language literature a ring is usually anything satisfying the first six axioms and also having an identity; a ring without identity is then called a rng – a ring with the i, that is, the identity, thrown out – which cannot even be pronounced properly. In short, each time one has to check separately which rings are meant; in a book on commutative algebra there is always an identity by default and multiplication is commutative, and this is said at the very beginning.

Example (rings).

The integers $Z$ are the most basic example: you can add and multiply.
$Q$ , $R$ , and for those who know them, the complex numbers $C$ .
A little more interesting: $Z / n Z$ , the set of remainders on division by $n$ . Remainders can be added and multiplied, and all the axioms hold.
Matrices of size $n \times n$ , for those who know what they are (we will discuss this later): they can be added and multiplied. This is an example of a non-commutative ring, but one with identity.
A ring without identity: $2 Z$ , the even numbers. They can be added and multiplied and stay even, but one is odd and is not there.

Fields and division rings

In rings addition is as good as it gets: you can not only add but also subtract. Division, though, is far from always possible. Fields are rings in which you can divide.

Definition (Field). A field is a set $F$ with two operations, addition and multiplication, satisfying ten axioms:

1–4. $F$ is an abelian group under addition (commutativity, associativity, zero, the opposite element $- a$ ); 5–8. the analogous axioms for multiplication: $ab = ba$ ; $(ab) c = a (b c)$ ; there is a $1$ with $1 \cdot a = a$ , the analogue of zero for multiplication (the second equality need not be written, commutativity is already given); for every $a \neq = 0$ there is an $a^{- 1}$ with $a a^{- 1} = 1$ ; 9. distributivity $(a + b) c = a c + b c$ : it connects addition with multiplication, brackets can be expanded; 10. $1 \neq = 0$ .

In the eighth axiom " $a \neq = 0$ " is essential: you cannot divide by zero anywhere, while all nonzero elements are invertible and you may safely divide by them. The tenth axiom looks strange. What is it for? To have at least two elements: it is not hard to show – anyone can do it at leisure, or there will be such a problem – that if $1 = 0$ and all the other axioms hold, the field has exactly one element. In itself there is nothing wrong with that, but all of linear algebra over such a "field" works completely differently from how it works over normal ones, and in a great many theorems one would have to say "let $F$ be a field other than this one". It is simpler to say at once that this is not a field and not clutter your head.

Definition (Division ring). A division ring (skew field) is a ring with identity in which all nonzero elements are invertible under multiplication. Roughly speaking, a field without commutativity of multiplication.

Example (fields and division rings).

$Q$ , $R$ , $C$ .
$Z / p Z$ for a prime $p$ : modulo a prime there is division as well.
Rational fractions, that is, rational functions over some field, ratios of polynomials; not necessarily in one variable, in ten as well: real-valued rational functions of the variables $t_{1}, \dots, t_{10}$ also form a field. The other examples are for later.
At the current level we cannot exhibit many division rings; from school, probably not a single one. The best-known example is the quaternions; most likely we will not consider them.

Vector spaces and modules

Definition (Vector space). A vector space over a field $F$ is a set $V$ with two operations: addition $V \times V \to V$ and multiplication by a scalar $F \times V \to V$ (the input is not two vectors but a number and a vector), such that:

1–4. $V$ is an abelian group under addition: $u + v = v + u$ ; $(u + v) + w = u + (v + w)$ ; there is a zero vector $0$ with $v + 0 = v$ ; for every $v$ there is a $- v$ with $v + (- v) = 0$ ; 5. $(α β) v = α (β v)$ : multiplying first by one number and then by another is the same as multiplying at once by their product; 6. $α (u + v) = α u + α v$ ; 7. $(α + β) v = α v + β v$ ; 8. $1 \cdot v = v$ .

Vectors are more commonly denoted by the letters $u, v, w$ . A whole science is built around this notion: linear algebra.

Example (vector spaces).

The simplest example is the space with a single element, zero: it can be added to itself any number of times and multiplied by any number, and you get it back.
A field over itself: everything written in the axioms is part of the field axioms.
More generally, any field over a subfield – a subset of the field with the same operations that is itself a field: $Q \subset R$ , $R \subset C$ . But $Z \subset Q$ is not a subfield: it is not a field.
Free vectors in the Euclidean plane. What is a vector? A segment with a chosen beginning and end; at school we learned to identify vectors, saying that one equals another, and after that to add them and multiply them by numbers. The set of classes of vectors that can be moved anywhere satisfies all the axioms.
Polynomials over a field $F$ .
For $F = R$ there are plenty of examples from analysis: continuous, differentiable, smooth functions defined on one and the same set (functions on $[0, 1]$ and on $[2, 3]$ cannot be added, but on one interval they can), the spaces $L^{2}$ and the like. And a great many more examples from differential equations.

Remark (modules). In this definition all that was required of the field was to add and multiply its elements; there is no division anywhere. So why take a field and not a ring? For a ring the notion also makes sense, it just has another name: a module – "a vector space over a ring". The precise definition is an exercise: think about which axioms are needed. We will need modules very actively literally three lectures from now.

Algebras

The last structure that will come up in the course.

Definition (Algebra over a field). An algebra over a field $F$ is a vector space $A$ over $F$ with one additional structure: a multiplication $A \times A \to A$ of elements of the algebra itself, such that

$(a + b) c = a c + b c$ and $a (b + c) = ab + a c$ for $a, b, c \in A$ ;
$(α a) (β b) = (α β) (ab)$ for $α, β \in F$ , $a, b \in A$ : compatibility with multiplication by elements of the field.

In one sentence: the multiplication is bilinear, linear in each argument; you can expand brackets and pull out factors. The field $F$ is usually not a subset of $A$ ; sometimes it can be identified with a subset – if the algebra has an identity, the element $α$ of the field corresponds to $α \cdot 1$ , and in this sense the field embeds in the algebra – but in general this need not be so.

Example (algebras). A field over itself is trivial and uninteresting. There are two interesting basic examples: polynomials, which can be multiplied not only by numbers but also by each other; and, for connoisseurs, the matrix algebra – matrices can not only be added and multiplied by numbers, but also multiplied together.

That was the introduction to what algebra does: it studies structures like these. Of course, not all of them were listed, but, in my view, the most important ones, those that will keep coming up in the course. Now to groups specifically; we will spend the next several classes on them.

The symmetric group

Definition (Permutation). A permutation (in Russian, both подстановка and перестановка) is a bijection of the set of the first $n$ natural numbers onto itself:

σ : {1, 2, \dots, n} \to {1, 2, \dots, n} .

Permutations form a group under composition, the symmetric group $S_{n}$ .

The two Russian terms are synonyms; I slightly prefer подстановка ("substitution"), out of a linguistic feeling that a substitution is the rule that sends something somewhere, while a перестановка ("rearrangement") is the result of applying that rule. I will denote permutations by Greek letters.

Why this is a group: a composition of bijections of a set onto itself is again such a map; the inverse is defined and is a bijection; the identity permutation, which sends every element to itself, is the identity element: if you first rearrange nothing and then rearrange, you get the second permutation, and vice versa.

Is this group commutative? Take $n = 3$ , let $σ_{1}$ swap $1$ and $2$ , and $σ_{2}$ swap $2$ and $3$ . Since the operation is composition of maps, a product is read from right to left: in $σ_{1} \circ σ_{2}$ first $σ_{2}$ is applied, then $σ_{1}$ . Then $σ_{1} \circ σ_{2}$ : $1 \mapsto 1 \mapsto 2$ , $2 \mapsto 3 \mapsto 3$ , $3 \mapsto 2 \mapsto 1$ . And $σ_{2} \circ σ_{1}$ : $1 \mapsto 2 \mapsto 3$ , $2 \mapsto 1 \mapsto 1$ , $3 \mapsto 3 \mapsto 2$ . Already from the first element one sees that they act differently. So $S_{n}$ is non-abelian for $n \geq 3$ .

Writing permutations

A permutation can be drawn as a diagram with arrows, but that is inconvenient. The first way is a $2 \times n$ table: on top, the numbers from $1$ to $n$ in some order; under each, where it goes:

σ = (a_{1} σ (a_{1}) a_{2} σ (a_{2}) \dots \dots a_{n} σ (a_{n})) .

There are many ways to write it: the top row can be rearranged arbitrarily; usually it is put in increasing order, why reinvent the wheel. But sometimes it is convenient, on the contrary, to put the bottom row in increasing order and the top row however it comes out. For example, the inverse permutation is easy to get in this notation: if $σ$ sent $a_{i}$ to $b_{i}$ , then $σ^{- 1}$ sends $b_{i}$ to $a_{i}$ – you just swap the rows.

How to multiply in these terms:

(14233241) \circ (12233144) = (13223441) :

$1$ goes to $2$ , and $2$ to $3$ , so $1 \mapsto 3$ ; $2 \mapsto 3 \mapsto 2$ ; $3 \mapsto 1 \mapsto 4$ ; $4 \mapsto 4 \mapsto 1$ . The standard multiplication, very simple.

Cycles and transpositions

Definition (Cycle). A permutation $σ$ is called a cycle if there are elements $a_{1}, a_{2}, \dots, a_{k} \in {1, \dots, n}$ such that

σ (a_{1}) = a_{2}, σ (a_{2}) = a_{3}, \dots, σ (a_{k - 1}) = a_{k}, σ (a_{k}) = a_{1},

and every $b$ different from all the $a_{i}$ stays in place: $σ (b) = b$ . Such a permutation is written $(a_{1}, a_{2}, \dots, a_{k})$ ; the number $k$ is the length of the cycle. A cycle of length two is called a transposition.

We see this notation and understand at once: the first goes to the second, the second to the third, …, the $k$ -th to the first, the rest stay in place. So $σ_{1} = (1, 2)$ and $σ_{2} = (2, 3)$ in the example above. A transposition swaps two elements and leaves the rest alone.

What is good about transpositions? They generate the whole group.

Theorem (Decomposition into transpositions). Every element of $S_{n}$ is a product of transpositions.

The idea: any rearrangement can be achieved by swapping two elements at a time; this is sorting. First swap so that the last element gets where it should, then the second to last, and so on.

Proof. Let us do it the other way round: take a permutation $σ$ and turn it into the identity using transpositions. Let $σ$ send $1 \mapsto σ (1)$ , …, $n \mapsto σ (n)$ . If $σ (n) = n$ , nothing needs to be done with this column, and we go on to the next one. If not, multiply $σ$ on the left by the transposition $(n, σ (n))$ . What have we achieved? Before, $n$ went to $σ (n)$ , and the transposition sends $σ (n)$ back to $n$ : in the permutation $τ = (n, σ (n)) \circ σ$ the element $n$ goes to $n$ . How $τ$ acts on the first elements we do not know exactly – it has changed something there – but $n \mapsto n$ for sure. Next we look at $τ (n - 1)$ : if it differs from $n - 1$ , we multiply by $(n - 1, τ (n - 1))$ , after which the last two elements go to themselves. Proceeding in this way we get

τ_{k} \circ \dots \circ τ_{2} \circ τ_{1} \circ σ = id

for some transpositions $τ_{i}$ . A transposition is its own inverse: swap two elements, then swap the same two again, as if nothing had been done. Therefore, multiplying the equality on the left by $τ_{k}$ , we kill $τ_{k}$ on the left and it appears on the right; then $τ_{k - 1}$ , and so on:

σ = τ_{1} \circ τ_{2} \circ \dots \circ τ_{k} .

The theorem says nothing about the uniqueness of such a decomposition: every permutation has infinitely many different decompositions into transpositions.

Disjoint permutations

There is another decomposition, into cycles, and that one is almost unique.

Definition (Disjoint permutations). The moved elements of a permutation are those that do not go to themselves. Permutations $σ$ and $τ$ are called disjoint (independent) if their sets of moved elements do not intersect.

The group $S_{n}$ is non-abelian, and very much so. But disjoint permutations always commute.

Lemma (Disjoint permutations commute). If $σ$ and $τ$ are disjoint, then $σ \circ τ = τ \circ σ$ .

Proof. These are two maps; to prove that they are equal it is enough to check that they send each element to the same place: $σ (τ (a)) = τ (σ (a))$ for every $a$ . We go through the cases.

$a$ is fixed by both. Then both $τ$ and $σ$ leave $a$ in place; both compositions give $a$ .

$a$ is fixed by $σ$ and moved by $τ$ . On the left: $σ$ does not change $a$ , then $τ$ moves it to $τ (a)$ ; altogether $τ (σ (a)) = τ (a)$ . On the right: first $τ (a)$ , and then $σ$ ; about what $σ$ does with $τ (a)$ we know nothing yet. Let us show that $τ (a)$ is fixed by $σ$ . The element $τ (a)$ is certainly moved by $τ$ : $τ$ sends $a$ to $τ (a)$ , and if $τ (a)$ were fixed, then $τ (a)$ would also go to $τ (a)$ – two different elements ( $a \neq = τ (a)$ ) would go to one, while a permutation is a bijection. So $τ (a)$ is moved by $τ$ , and then it cannot be moved by $σ$ : by disjointness their moved elements are completely different. Thus $σ (τ (a)) = τ (a)$ – they agree.

$a$ is moved by $σ$ and fixed by $τ$ : exactly the same.

$a$ is moved by both: this cannot happen, by disjointness.

The converse is false: commuting permutations need not be disjoint: $g$ commutes with $g$ and with $g^{- 1}$ .

Decomposition into disjoint cycles

Theorem (Decomposition into disjoint cycles). Every permutation can be written as a product of disjoint cycles, uniquely up to the order of the factors.

The proviso about the order is needed: as we have just seen, disjoint cycles can be rearranged in any way, and the product does not depend on it. (Another reason why I prefer the word подстановка: otherwise the Russian statement would contain перестановка twice.) Besides, cycles can be written in different ways: $(1, 2, 3)$ is the same as $(2, 3, 1)$ , the only difference is which element the walk starts from; this does not affect the permutation, and we will not fix it. Finally, cycles of one element are not written – they have no effect, and if they were written, uniqueness would fail.

Proof. Existence. We construct the decomposition. Look at the element $1$ . If it is fixed, move on. Suppose $1$ goes to $σ (1) \neq = 1$ ; write it after the one. The permutation also sends the element $σ (1)$ somewhere – to $σ (σ (1))$ ; then $σ (σ (σ (1)))$ , and so on. Sooner or later we will certainly loop: the set is finite, and eventually there is a repetition. The repetition can only be the one: if some element were mapped to, say, $σ (σ (1))$ , then both $σ (1)$ and that element would go to it – and this is a bijection. So the loop can only close at one, and we have constructed the cycle $(1, σ (1), σ (σ (1)), \dots)$ .

Then we take the first element not yet written down, say $2$ . If it goes to itself, we skip it; otherwise we build the cycle $(2, σ (2), σ (σ (2)), \dots)$ . Again by finiteness we must come to an element already written down; we cannot land in the first cycle – that contradicts bijectivity, something already goes there – nor in an element of the new cycle other than $2$ ; so only in $2$ . In this way at some point we go through all the elements: each either belongs to one of the cycles constructed or is fixed and not needed. By construction the cycles do not intersect – they are disjoint – and their product is $σ$ : if an element belongs to a cycle, the next one in the cycle is by definition $σ$ of it, and if it does not, it is fixed.

Uniqueness. Let $σ = σ_{1} \circ \dots \circ σ_{k} = σ_{1}^{'} \circ \dots \circ σ_{k^{'}}^{'}$ be two decompositions into disjoint cycles ( $k$ and $k^{'}$ may differ). Take an element $a$ . If $σ (a) = a$ , then $a$ belongs to no cycle of either decomposition. If $a$ is moved, the first decomposition has a cycle containing $a$ , and it looks like this: $a$ , then $σ (a)$ , then $σ (σ (a))$ , and so on. But exactly the same cycle must be in the second decomposition too. We cancel equal cycles and pass to the remaining ones – by induction everything cancels.

A rather trivial statement, but a very useful one.

Example (a random permutation).

σ = (1224354751637886) .

One goes to $2$ , $2$ to $4$ , $4$ to $7$ , $7$ to $8$ , $8$ to $6$ , $6$ to $3$ , $3$ to $5$ , $5$ to $1$ : $σ = (1, 2, 4, 7, 8, 6, 3, 5)$ , for some reason a single cycle. What is the probability of that? There are $n!$ permutations in total: where the first element goes can be chosen in $n$ ways, where the second goes in $n - 1$ ways, and so on. Cycles of length $n$ containing all the elements: one can be sent to any of the $n - 1$ others, that one to any of the remaining ones, …, and the last one must go to one; altogether $(n - 1)!$ . The probability is $1/ n$ , here $1/8$ .

Powers

Why do we need decompositions into disjoint cycles? One reason: raising a permutation to a power becomes very easy. In an arbitrary group $(ab)^{k} = a^{k} b^{k}$ is, generally speaking, false: on the left we have $ab ab \dots ab$ ( $k$ times), on the right first $k$ times $a$ , then $k$ times $b$ , and nothing implies that one equals the other. But if $a$ and $b$ commute, the factors can be rearranged so that all the $a$ 's are on the left and all the $b$ 's on the right, and the equality holds. Disjoint cycles commute, so if $σ = σ_{1} \circ \dots \circ σ_{k}$ is a decomposition into disjoint cycles, then

σ^{m} = σ_{1}^{m} \circ σ_{2}^{m} \circ \dots \circ σ_{k}^{m} .

And raising cycles to powers is a pleasure. A cycle of length $k$ to the $k$ -th power is the identity permutation: we apply it $k$ times, each time shifting the elements along the cycle by one; if you rotate a regular $k$ -gon $k$ times by one vertex, it comes back onto itself. So the powers $2 k$ , $3 k$ , … are the identity too, and to raise a cycle to a large power $m$ you divide $m$ by its length with remainder and raise it to the power of the remainder.

Is it true that a power of a cycle is again a single cycle of the same length? No:

(1, 2, 3, 4)^{2} = (1, 3) \circ (2, 4) :

$1 \mapsto 2 \mapsto 3$ , $3 \mapsto 4 \mapsto 1$ , and similarly $2 \mapsto 4$ , $4 \mapsto 2$ . When raised to a power, cycles sometimes break up into disjoint cycles, but that is not a problem: the task has still become much simpler – instead of checking a thousand times where everything goes, you decompose into disjoint cycles once and see what happened to each of them.

TikZ diagram — Rotating the square by $9 0^{\circ}$ clockwise is the cycle $(1, 2, 3, 4)$ on the vertices. Rotating twice means applying the central symmetry: it swaps $1$ and $3$ , $2$ and $4$ , two disjoint cycles.

The parity of a permutation

One more crucial property of permutations: their parity. Write $σ$ in the standard form, with top row $1, 2, \dots, n$ .

Definition (Inversion, parity, sign). An inversion of a permutation $σ$ is a pair of numbers $i < j$ such that $σ (i) > σ (j)$ : a correctly ordered pair becomes incorrectly ordered after the permutation: the larger number stands to the left of the smaller one in the bottom row. The parity of a permutation is the parity of the number of its inversions. The sign of a permutation is

sgn (σ) = (- 1)^{σ} = (- 1)^{number of inversions of σ},

plus for even and minus for odd; $sgn$ comes from the word sign, and both notations are standard.

(This is not a "derangement": a derangement is a permutation none of whose elements goes to itself.)

Theorem (Multiplying by a transposition changes the sign). Let $τ$ be a transposition. Then the parities and the signs of the permutations $σ$ and $τ \circ σ$ are different.

In other words, if you swap two elements in the bottom row, the sign changes.

Proof. Let $τ$ swap $σ (i)$ and $σ (j)$ , $i < j$ : in $τ \circ σ$ the element $i$ goes to $σ (j)$ , $j$ goes to $σ (i)$ , and all the others go where they went before. Let us see what happened to the inversions – where they disappeared, where they appeared, where nothing changed. For a pair $k < l$ we check whether there is an inversion in $σ$ and in $τ \circ σ$ .

Neither $k$ nor $l$ equals $i$ or $j$ . $τ$ does not touch their images: an inversion, if there was one, stays; if there was none, none appears. The number of such inversions does not change.
$k = i$ , $l = j$ . If there was an inversion, it disappears after the swap; if there was none, one appears. The number of inversions changes by $\pm 1$ .
$k < i$ , $l \in {i, j}$ . If there was an inversion in the pair $(k, i)$ , that is, $σ (k) > σ (i)$ , then after the swap the same inequality gives an inversion in the pair $(k, j)$ , and vice versa: the inversions with $i$ and with $j$ trade places, and no inversion goes to no inversion. The number of inversions does not change.
$l > j$ , $k \in {i, j}$ . The same: the inversions with $i$ and with $j$ trade roles, the number does not change.
$i < k < j$ , the other element of the pair is $i$ or $j$ . Look at how $σ (k)$ lies relative to $σ (i)$ and $σ (j)$ . If $σ (k)$ is greater than both, then both before and after the swap there is exactly one inversion among the pairs $(i, k)$ and $(k, j)$ – the number does not change; if it is smaller than both – similarly, again exactly one. If $σ (k)$ is squeezed between them – say, $σ (i) < σ (k) < σ (j)$ – then before the swap these three elements were in order and there were no inversions in the pairs with $k$ , and afterwards two appear at once; in the opposite case two disappear. Altogether, for each such $k$ the number changes by $0$ or by $\pm 2$ .

Adding up: one $\pm 1$ and some number of $\pm 2$ 's and zeros give an odd number. The numbers of inversions of $σ$ and $τ \circ σ$ differ by an odd number, the parity has changed, the sign has changed.

Theorem (Corollary). An even permutation is a product of an even number of transpositions, an odd one of an odd number. The product of two even permutations is even, of two odd ones even, of an even and an odd one, in either order, odd.

Proof. The identity permutation has exactly zero inversions; it is even. Each multiplication by a transposition changes the parity: after an odd number of transpositions we get an odd permutation, after an even number an even one. Hence the second statement: the product of two even permutations is a product of an even number of transpositions, and likewise in the other cases. Parity behaves exactly as with addition of numbers: the sum of evens is even, the sum of odds is even, of an even and an odd, odd.

Related works