One cell short of a transversal

The thirty-six officers needed one idea to explain why Euler’s arrangement of order six cannot exist for the most natural square: a transversal, a choice of one cell in each row and each column with every symbol different. A square with an orthogonal mate can be cut into transversals, so a square with none has no mate. The cyclic square of order six has none, and the reason was parity: its symbols are row plus column, and at even order the totals cannot be made to agree.

That essay was about orthogonal mates, and transversals were the tool. Here they are the object. The questions are simple to state. Which squares have a transversal? If a square has none, how close can a partial choice come? And how many transversals does a square have when it has any? The answers turn out to include a conjecture from 1967 that is still open, and one from 1975 that was settled in 2023 for large squares only.

Five cells out of six #

The shaded cells in the figure are a partial transversal: one cell in each of five rows, in five different columns, carrying five different symbols. It is as large as a partial transversal of this square can be, since a full one of six would be a transversal and the parity argument forbids that. The search that found it tried every way of skipping one row and filling the rest, and settled on this one.

So the cyclic square of order six misses by exactly one. The same is true of every even cyclic square: a full transversal is forbidden, and a partial one of $n - 1$ cells always exists. That observation invites a guess about all Latin squares, and the guess was made twice, independently, in 1975 by Richard Brualdi and Sherman Stein: every Latin square of order $n$ has a partial transversal of at least $n - 1$ cells. If true, the even cyclic squares are the worst case there is, and they are only one cell short.

The reason the guess is plausible is a matching argument of the kind Hall’s theorem makes. A transversal is a perfect matching between rows and columns, with the extra condition that the symbols on the matched pairs all differ — a rainbow matching, in the language of edge-coloured graphs, where each symbol is a colour. Perfect matchings in a Latin square’s grid are everywhere, $n!$ of them; the question is whether one of them can be made to avoid repeating a colour, and the conjecture says a matching of all but one row always can.

Every square of orders five and six #

For small orders the question can be answered by looking at every square. A Latin square can be put into reduced form — first row and first column in the order $0, 1, \dots, n - 1$ — by permuting its rows, columns and symbols, and none of those operations changes how many transversals a square has. So counting transversals over reduced squares covers every square there is.

Order five is striking for how little variety there is. Every one of its 56 reduced squares has either 3 transversals or 15, and none has zero. The 15 belongs to the squares that are essentially the cyclic one; the 3 belongs to the only other kind of square of order five, which is not the table of any group. Either way, a transversal exists.

Order six is different. The counts are 0, 8, 24 or 32 — nothing in between — and 2,100 of the 9,408 reduced squares have none at all. The even cyclic square is not a lonely exception: nearly a quarter of all squares of order six share its failure. And yet every one of them has a partial transversal of five cells, as Brualdi and Stein predicted. At order six the conjecture’s bound is reached exactly and never beaten, by more than two thousand squares.

Ryser’s conjecture, for odd orders #

The picture at orders five and six is the general expectation in miniature. At odd orders, transversals seem always to exist; at even orders, some squares have none. Herbert Ryser conjectured in 1967 that every Latin square of odd order has a transversal. It has been checked by computer for every odd order small enough to search — order five in the figure above, and considerably further by others — and never failed.

It is also known in a strong asymptotic form: squares of odd order not only seem always to have a transversal, they seem to have enormously many. But no proof covers every odd order. The difficulty is that the obstruction for even orders is a single clean argument about sums, and at odd orders there is no corresponding argument to show that nothing else can go wrong. Every approach so far proves that transversals exist in almost every square, or that a partial transversal very nearly as large as $n$ exists in every square, and stops short of a full one in every square.

The combined statement — a full transversal at odd order, one of $n - 1$ cells at every order — is known as the Ryser–Brualdi–Stein conjecture, and until recently nothing close to it was proved. In 2023 Richard Montgomery proved that for every sufficiently large $n$, every Latin square of order $n$ has a partial transversal of $n - 1$ cells. For even orders that is the whole conjecture for large squares, and the even cyclic squares show it cannot be improved. For odd orders it leaves exactly one cell unaccounted for: the full transversal Ryser predicted.

When the square is a group’s table #

One family of squares is completely understood, and the understanding took half a century.

The multiplication table of a finite group is a Latin square, and sixteen of five hundred and seventy-six met the rule that decides whether it has a transversal. Marshall Hall and Lowell Paige conjectured in 1955 that a group’s table has one exactly when its largest subgroup whose order is a power of two — its Sylow 2-subgroup — is either trivial or not cyclic. The figure checks the rule on twenty-two groups of order at most twelve, each table built from the group’s definition and searched: the cyclic group of order twelve fails, because its Sylow 2-subgroup is cyclic of order four, while the alternating group of order twelve succeeds, because its Sylow 2-subgroup is the four-element group in which every element is its own inverse.

Odd-order groups all pass, since their Sylow 2-subgroup is trivial — which is Ryser’s conjecture confirmed for every square that happens to be a group table. The theorem was finally proved in 2009, by Stewart Wilcox, Anthony Evans and John Bray, and the proof uses the classification of finite simple groups: the reduction to simple groups was known, and checking every simple group needed the list of them. Among Latin squares, group tables are a vanishing fraction, and they are the only family for which the existence of a transversal has a complete answer.

Counting the cyclic square’s transversals #

When a square has transversals, how many? For the cyclic square the question has a surprisingly visual form.

In the cyclic square the symbol in row $i$ and column $j$ is $i + j$ modulo $n$, so the cells holding one symbol form a diagonal that wraps round the edges of the board. A transversal is then a placement of $n$ pieces with no two in a row, no two in a column and no two on a wrapped diagonal — the rule for chess queens, except that these pieces attack along only one of the two diagonal directions, on a board rolled into a torus. At order seven there are 133 placements.

The counts grow very fast, and in 2019 Sean Eberhard, Freddie Manners and Rudi Mrazović found exactly how fast.

The formula has a transparent heuristic behind it. There are $n!$ ways to place one piece in each row and column. If the $n$ symbols they land on were independent and uniformly random, the chance that they are all different would be $n!/n^n$, giving $n!^2/n^n$ transversals. But the symbols are not independent: the sum of the $n$ symbols is the sum of all row indices plus all column indices, which is fixed, and at odd order that removes one degree of freedom and multiplies the chance by $n$. The final factor $e^{-1/2}$ is the correction for the remaining correlations, and it is the part that needed proof. The counts computed here land within two per cent of the formula at orders seven and eleven.

The same formula, with the same $n!^2$ at its heart, connects to the permanent: a transversal count is a sum over all $n!$ placements of a product of indicators, which is the permanent of a structured array, and permanents are the functions that are easy to define and hard to compute.

A transversal is one-nth of a mate #

The reason transversals mattered in the first place was orthogonal mates, and the connection runs both ways. A square has an orthogonal mate exactly when its cells can be split into $n$ transversals that share no cell: each symbol of the mate marks out one of them. So the existence of one transversal is a first, necessary step, and the full requirement is a partition into $n$ of them.

For the cyclic square of odd order the partition is easy to write down. The cells where $i + 2j$ has a given remainder form a transversal — each row and column contains exactly one such cell, and the symbols $i + j$ on them are all different because doubling is a one-to-one map when $n$ is odd — and the $n$ remainders give $n$ disjoint transversals. The square $i + 2j$ is then an orthogonal mate of $i + j$, which is the simplest case of the field construction that produces whole families of mutually orthogonal squares — families that at prime orders assemble into the plane hiding in the squares, where every transversal used in the construction becomes a line. At even order the doubling map is two-to-one, the construction collapses, and the parity argument says nothing can replace it.

The counts in the table say something about how much room there is. The cyclic square of order seven has 133 transversals, and a mate needs only seven disjoint ones; the order-five square with just three transversals cannot possibly be split into five, so it has no mate at all, although it has transversals. A square can have transversals and still have no mate, and the gap between the two questions is exactly the gap between finding one rainbow matching and covering the grid with them. For squares that are the tables of groups, the Hall–Paige condition answers both at once — a group table with one transversal can always be split into $n$ — which is another way that group tables are special among Latin squares.

What the exhaustive counts can and cannot say #

The histograms over orders five and six are complete — every square, every transversal — and the conclusions drawn from them are theorems for those orders. At order five, every square has a transversal. At order six, every square has a partial transversal of five cells, and 2,100 of the reduced squares have no full one.

What they cannot say is anything about order seven, and there the numbers change character. There are about seventeen million reduced squares of order seven, and about $7.8 \times 10^{47}$ of order eleven. Checking Ryser’s conjecture by enumeration means searching every one for a transversal. For a single square that is quick — a search that places one cell per row and abandons a branch as soon as a column or symbol repeats finds a transversal of an order-eleven square in a fraction of a second — so the obstacle is never the search, it is the number of squares to search. Exhaustion is feasible only while that number is; beyond that, the evidence is either a proof or a sample, and a sample of Latin squares is a sample from a population that can hide very rare exceptions. Nine thousand four hundred and eight counted how quickly the population grows, and the growth is why the conjecture is open at all: a statement that is easy to check for any one square is impossible to check for all of them.

The group tables are the opposite situation. There are few groups of each order, and a complete theory covers every one. The Hall–Paige theorem is a proof that works for every order at once, and the figure’s twenty-two checks confirm its instances rather than supporting it as evidence.

What the squares cannot show #

Why odd orders should be different. The figures show every square of order five with a transversal and many squares of order six without, and the parity argument explains the even cyclic squares. What no figure can show is why an odd-order square of some other kind could not fail for some other reason. The absence of an obstruction is not visible; it can only be proved. A proof would have to find a property that every odd-order square shares and that every failing even-order square lacks, and a picture shows only instances of each.

The asymptotic regime. The growth table stops at order eleven, where the search finds 37,851 transversals. The theorem it is compared with is a statement about the limit, and five data points with a ratio drifting between 1.016 and 1.091 are consistent with it and could not have discovered it. Eberhard, Manners and Mrazović proved the formula by analysing sums over the group, not by extrapolating counts.

The large squares where the recent proof works. Montgomery’s theorem holds for $n$ larger than some bound, and the bound is enormous. No square small enough to draw is covered by it; the squares drawn here are covered by exhaustive search instead, and between the two lies a range of orders where Brualdi–Stein is believed, not known.

Still open: a transversal in every odd square #

Ryser’s conjecture — that every Latin square of odd order has a transversal — is open. It is true for group tables, by the Hall–Paige theorem; true for every square small enough to check; true in the sense that almost every large square of any order has many transversals. It is not known to hold for every square of order thirteen, or of any single odd order beyond the reach of computers.

The obstacle is structural. Every known method for producing transversals in arbitrary squares either leaves a small number of cells uncovered, as Montgomery’s does, or works only for squares with extra structure, as Hall–Paige does. Closing the last cell at odd order, for every square, needs an argument that distinguishes odd from even without relying on any structure beyond the Latin property itself, and nobody has found one.

One cell, and which one #

The even cyclic squares have no transversal, and miss by exactly one cell. At order six a quarter of all squares miss the same way, and none misses by more. At order five none misses at all. The conjecture that odd orders never miss is from 1967; the conjecture that no square misses by more than one cell is from 1975 and was proved for large squares in 2023.

Group tables are the one family where the answer is complete, and it needed the classification of finite simple groups. For the cyclic square the count of transversals is known asymptotically, and it is the count of ways to place non-attacking pieces on a torus. And for an arbitrary square of odd order, whether a full transversal always exists is still one cell away from being known.