The crossings that will not come out even

A rearrangement of four things can be written as a table, and a table hides the only thing worth looking at. Draw it instead as four strings, running from a row of numbered pegs down to another row, each string going to the place its number is sent.

Now the crossings are visible, and each one means something: two strings cross exactly when the pair of places they join has been put out of order. So the number of crossings in the picture equals the number of pairs the rearrangement inverts, and the two counts are compared in every figure on this page rather than assumed to agree.

The count is not an invariant #

The trouble with the count is immediate. Nothing forces the strings to be straight. Push one of them sideways past its neighbour and back again, and it ends where it always ended — the rearrangement is unchanged — but the picture now has two more crossings.

So the crossing count is a property of the drawing, not of the rearrangement. It can be made as large as anybody likes. What it cannot be made is odd when it was even, because the only way to change it is to push a string across another and back, and that always adds or removes two.

That is the theorem, and it is worth stating in the form that makes it usable: every drawing of a given rearrangement has a crossing count of the same parity. The parity is therefore a property of the rearrangement itself, and it is called the sign — plus one for an even number of crossings, minus one for odd.

The same fact, said with swaps #

There is a second route to the sign and it is the one most textbooks take, so it is worth seeing that it is the same picture.

Any rearrangement can be built out of swaps of neighbours: bubble the numbers into place, exchanging adjacent pairs, and stop when everything is where it belongs. Each swap is one crossing, so a decomposition into $k$ adjacent swaps is a drawing with $k$ crossings.

Different decompositions have different lengths, exactly as different drawings have different crossing counts, and for the same reason: a swap repeated twice is nothing at all, and can be inserted anywhere. The parity is what survives, and the sign defined by the parity of the number of swaps is the sign defined by the parity of the crossings, because a stack of swaps is a drawing.

The claim that no rearrangement is both an even and an odd product of swaps is the whole content, and it is not obvious. Half the difficulty in a first algebra course is that the sign is defined before it is shown to exist. Drawn as strings, existence comes first: the crossings are there to be counted, and the count is only ambiguous by twos.

Half of everything #

Once the sign exists, a count follows immediately.

Exactly half of all rearrangements are even. The proof is one line and the figure performs it: take any rearrangement and swap its first two places. That changes the sign, it is its own undoing, and so it matches the even ones with the odd ones exactly.

The even rearrangements form a group of their own, since composing two even ones gives an even one. It has half as many elements as the whole, and it is one of the two most important groups in the subject. The three even rearrangements of three things are exactly the rotations of a triangle, with the odd ones being the reflections — the sign, on a symmetry group of a shape, is the answer to does this motion turn the shape over.

Why determinants exist #

The sign’s first consequence is the one that would justify the whole construction on its own.

The determinant of a square array is defined as a sum over all rearrangements: pick one entry from each row and column, multiply them, attach the sign of the rearrangement that did the picking, and add. That definition is unusable until the sign is known to exist, because otherwise the formula does not name a number.

And the sign is not decoration in it. It is what makes the determinant measure area rather than merely combine numbers: swapping two rows of the array swaps two entries in every term, flips every sign, and so negates the whole determinant. That single property — alternating under a swap — forces almost everything else the determinant does, including its vanishing when two rows agree, which is the statement that a map crushing two directions together leaves no room.

The puzzle nobody can finish #

The sign’s other famous consequence is a negative one, and it can be settled by exhaustion on a board small enough to walk.

Each slide exchanges the blank with a neighbour, which is one swap, so each move flips the sign of the arrangement. Each move also changes the blank’s distance from its home square by one, so it flips the parity of that distance. The two flips happen together, and therefore the sign of the arrangement times the parity of the blank’s distance never changes at all.

Start from the solved position and that combined quantity is even. Exchange two tiles and leave the blank alone, and it is odd. So no sequence of slides connects them, and the puzzle with two tiles exchanged has no solution — not “no known solution”, no solution.

The figure does not argue this. It walks every position reachable from the solved one, finds three hundred and sixty of the seven hundred and twenty, and checks the combined quantity at every one of them. On the four-by-four board the same argument holds and the search is far larger; the reasoning is what carries over, which is why a parity argument is worth more than an exhaustive search even when the search is available.

Two counts, and the one that is not a count #

It is worth being precise about what kind of object the sign is, because the two ways of reaching it look like two different kinds of thing.

The number of inversions is a genuine count: for each of the six pairs of four places, ask whether the rearrangement put them out of order, and add up the yeses. It is between zero and six, it is computed without drawing anything, and it is a fact about the rearrangement rather than about a picture of it.

The number of crossings is a fact about a picture. It agrees with the inversion count when the strings are straight, and it can be anything larger of the same parity when they are not.

So there are three quantities in play — the inversion count, the crossing count of a particular drawing, and the length of a particular decomposition into swaps — and only their common parity is an invariant. The first happens to be the smallest of the three, and it is the smallest for a reason worth stating: a drawing with fewer crossings than the inversion count would have to leave some out-of-order pair uncrossed, and two strings whose endpoints are in opposite orders must meet somewhere.

That last sentence is a use of the intermediate value theorem in disguise, and it is the reason the picture can be trusted at all. A continuous quantity — the horizontal gap between two strings — starts positive and ends negative, so it is zero somewhere, and the crossing is that somewhere. Every figure here checks the two counts against each other rather than assuming the agreement, because the agreement is the bridge between a drawing and an arithmetic fact and is exactly what a wrong routing would break.

Where it fails, and what it needs #

It is a statement about finite rearrangements. A permutation of infinitely many things need not be a product of finitely many swaps at all, and where it is not, no parity is defined. The sign is a feature of the finite world and does not survive being taken to the limit.

The strings have to be in general position. Three strings meeting at a single point is not a crossing count of three or of one; it is a drawing whose crossings are not defined. The figures perturb nothing because their strings are straight lines between distinct pegs and no three meet, but the general statement needs the clause.

Parity is one bit, and one bit is not much. Two rearrangements with the same sign can be entirely unalike, and the sign says nothing about how far apart they are. Its power comes from being preserved, not from being informative — an invariant that distinguishes two cases is worth having exactly when those two cases needed distinguishing.

And the puzzle argument needs the blank to come home. The invariant is the sign together with the blank’s distance, so a comparison between arrangements with the blank in different places has to account for both. Stating it as “an odd arrangement is unreachable” without that clause is the version that is quoted and is not quite true.

A surprise on the way out #

There is a consequence of the half-and-half count that is easy to miss and hard to forget once seen.

The even rearrangements of five or more things form a group with no interesting pieces inside it — no way of splitting it into a smaller group and a quotient, in the sense a normal subgroup provides. That is a fact about a group of sixty elements and upwards, and it is the reason the general quintic equation has no formula in radicals: solving by radicals corresponds to taking a group apart in exactly the way the even rearrangements of five things refuse.

So the bit counted here — one binary digit attached to a rearrangement, discovered by looking at where some strings crossed — is the first step of the argument that closes the oldest open problem in algebra. That is a long way from a wiring diagram, and the route runs entirely through the sign: without it, the even rearrangements are not a group at all, and there is nothing to say is indivisible.

Where it came from #

The sign appears in Cramer’s and Vandermonde’s work on determinants in the 1750s and 1770s, entirely as bookkeeping — an alternating pattern of pluses and minuses in an expansion nobody had a name for. Cauchy, in 1815, was the first to treat permutations as objects with a group structure and the sign as a function on them, and the modern definition is essentially his.

The sliding puzzle became a public obsession in 1880, with a prize offered for the arrangement that is now known to be unreachable. The impossibility was published the same year by Johnson and Story, and the argument is the one above; it is one of the earliest cases of a mathematical result reaching a wide audience because it explained why a large number of people were wasting their time.

The wiring-diagram picture is much later and belongs to a different tradition. It is how the symmetric group is drawn in the theory of braids, where the strings are not allowed to be pushed through one another and the crossings therefore do count — the braid group is what the symmetric group becomes when the parity argument is refused, and it is a great deal larger.

What the pictures cannot show #

The strings are drawn straight, and straightness is what makes the crossing count agree with the inversion count. A drawing with curved strings has the same parity and possibly a different number, which is the point of the second figure, and the reader has to supply the generality that the figures deliberately do not draw.

The puzzle is two-by-three rather than four-by-four because seven hundred and twenty arrangements can be exhausted on a page and twenty billion cannot. The famous puzzle is the larger one, and everything shown here is a statement about the smaller one plus an argument that carries.

And no figure here shows that the parity cannot be changed. Each figure shows a pair of drawings with the same parity, which is an instance rather than a proof; the proof is the observation that a crossing can only be created or destroyed by two strands passing across each other, and that observation is prose.

The ladder from here #

Below: eight ways to leave a square alone, where the symmetries of a shape are found as permutations of its corners, and the number that says how much room is left, which the sign makes possible. Sideways: the blocks a subgroup cuts out, where the even permutations are an index-two subgroup and Lagrange’s theorem prices it, and colourings nobody can tell apart, which counts orbits of a permutation action. Above: the alternating group’s simplicity, the braid group the parity argument is refused in, and the sign as the one non-trivial homomorphism the symmetric group has.

What is worth carrying away #

A quantity that can be changed at will is worthless, and a quantity that cannot be changed at all is often too rigid to exist. The useful ones sit in between: they can be changed, but only in steps of two, so something about them survives.

That is the whole technique. Find an operation that alters a count by an even number, and the parity becomes an invariant of everything the operation leaves alone. It settles the sliding puzzle, it makes the determinant well defined, and it is the same move as the crossing argument that keeps the linking number steady under deformation — crossings appearing and disappearing in pairs, and a total that cannot notice.