Much of the terminology is standard in the study of latin squares.  Where I introduce new terms of my own, I put the new term in double quotes (“ “) at first mention.

Definition.  A latin square of order n is an n-by-n matrix in which each entry is chosen from a set of n distinct symbols, in which each symbol appears once in each row and once in each column.

Alternatively:  A latin square of order n is a set of n² ordered triples (r, c, s), where r is an element of the n-set R, c is an element of the n-set C, and s is an element of the n-set S, in which every possible combination of RxC, RxS, and CxS is represented.  The three sets R, C, and S are called the constraints of the latin square.  (This definition shows the symmetry of a latin square on its constraints.)

Examples:

A latin square with symbols chosen from an ordered set (such as the integers), written so that the symbols appear in sequence in the top row and the leftmost column, is said to be in reduced form.  The four examples above are in reduced form.

The ordered pairs of RxC are called cells.

An intercalary square is a 2x2 latin subsquare.  Note that the cells of an intercalary square need not be adjacent in a representation of a latin square.

A set of n cells in which every row and every column is represented once I call a “rookery.”

Example:

Taking the columns left to right, the cells with symbols 2 2 2 1 3 are a rookery.

A rookery in which the n symbols are all distinct is called a transversal.

Example:

Taking the columns left to right, the cells with symbols 2 4 3 1 are a transversal.

In general the symbols of the cells of a rookery form a partition of n:  that is, a division of n into several distinct sets.  For example, 5 can be partitioned as 1 + 1 + 1 + 1 + 1, or 2 + 1 + 1 + 1, or 2 + 2 + 1, or 3 + 1 + 1, or 3 + 2, or 4 + 1, or simply 5.  The order of the addends is irrelevant, so these are all the possible ways of partitioning 5.

I will write partitions in the notation [a₁ a₂ a₃ ... a_n], where a_i is the number of symbols in a rookery that occur exactly i times.  Thus for example, a rookery in a latin square of order 5 which contains each symbol once (that is, a transversal) partitions 5 as 1 + 1 + 1 + 1 + 1, and I propose to write this rookery-pattern as [5 0 0 0 0].  If the order of the latin square is understood, we can ignore trailing zeros and simply write [5].  For example, a transversal's pattern is simply [n].

The reason for defining this notation is that I wish to generalize the notion of a transversal to include rookeries with other patterns.  A rookery that has a pattern of [(n-2) 1], that is, one in which every symbol occurs except one, and in which one symbol therefore occurs twice, I call a pentransversal.

Pentransversal Theorem.  Every latin square has an even number of pentransversals.

Proof.  Note that a rookery is a permutation of R onto C.  Let s₁ be the symbol that occurs twice in the pentransversal, and let X = (r₁, c₁, s₁) be one of the cells of the pentransversal that contains s₁.  (Note that we have two choices for X.)  Let s₀ be the symbol that does not occur in the pentransversal.  Then there is a cell Y in the latin square, (r₂, c₁, s₀), in the same column as X and containing the symbol that does not occur in the pentransversal.  And there is another cell of the pentransversal, say Z = (r₂, c₃, s₃), in the same row as Y.  Now if X and Z are removed from the pentransversal, and replaced with Y and the cell (r₁, c₃, s₄), then the resulting rookery is another pentransversal.  Furthermore, this new rookery resulted from the original pentransversal by an interchange of one row and one column:  hence the parity of the permutation of R onto C is opposite that of the original pentransversal.  Now suppose we continue this process on the new pentransversal; it too has two cells with a repeated symbol, and choosing one of them as our new X will lead directly back to our original pentransversal.  Therefore choose the other one and continue.  Eventually this process must return to the original pentransversal, since the number of pentransversals is finite and each one has only two ways of choosing the cell X that begins the process.  Therefore the pentransversals exist in "cycles" that alternate between even and odd permutations, and so must always contain an even number of rookeries.  This completes the proof.

Another interesting point is that a latin square made from the addition table of a group cannot have any pentransversals.  The sum of all the elements of a finite group is the group’s identity; from this it follows that the sum of all the elements in a rookery of the group’s addition table must be the identity; and it also follows that the sum of the elements in a pentransversal (that is, the sum of all group elements, with one removed and another duplicated) cannot be the identity.

Definition.  The vector which gives the number of rookeries in a latin square with each possible pattern I call the “signature“ of the latin square.  In order to express the following ideas symbolically, I will write <a₁ a₂ a₃ ... a_n> for the number of rookeries in a latin square that have the pattern [a₁ a₂ a₃ ... a_n].

Examples.

The reader will note that the sum of the entries in a signature is n!, since the total number of rookeries is simply the number of permutations of rows onto columns.  When the entries in a signature are given in reverse lexical order, the first entry is the number of transversals in the latin square and the second entry is the number of pentransversals.  The last entry is always n, which simply counts the rookeries in which only one symbol appears.

The second to last entry in a square of order 4 or greater is exactly twice the number of intercalary squares.  This is because it counts rookeries with patterns like < 0 1 0 0 0 ... 1>, which therefore contain one symbol exactly twice and another symbol exactly n-2 times.  Very informally (this is easier to see than read):

Hence two [0 1 0 0 0 ... 1]’s and one intercalary square.

But the most substantive thing I can say about signatures follows.  Recall from combinatorics that a derangement is a permutation that leaves no element fixed.  A recurrence relation that gives the number of derangements of n items is:
d(1) = 0
d(2) = 1
d(n) = (n - 1)[ d(n-1) + d(n-2) ]

Therefore d(3) = 2, d(4) = 9, d(5) = 44, d(6) = 265, etc.  In the following I will adopt a convention that d(0) = 1.  (Is this standard in studying derangements?  Perhaps someone who knows more combinatorics than I can tell me.  I suppose it is no more counter-intuitive than the convention that 0! = 1, and I note that the recurrence relation still works if the basis is given as d(0) = 1, d(1) = 0.  In any case, such a convention allows the Signature Theorem below to be stated more elegantly.)

(As a sidetrack, since we’re mentioning derangements in a page on latin squares, rows 2 through n of a latin square in reduced form are derangements of the first row; another way of defining of a latin square is as a maximal set of mutual derangements.)

Now back to business ...

Theorem (The Signature Theorem). For any latin square of order n, the dot product of the column vector formed by taking the i^th components of the p separate rookery patterns (where p is the number of partitions of n), [a_1,i a_2,i a_3,i ... a_p,i], and the signature of the latin square, [<a_1,1 a_1,2 a_1,3 ... a_1,n>, <a_2,1 a_2,2 a_2,3 ... a_2,n>, <a_3,1 a_3,2 a_3,3 ... a_3,n>, ...
<a_p,1 a_p,2 a_p,3 ... a_p,n>], is equal to (n) times (n choose i) times (the number of derangements of n-i).

Examples.  At this point the motivation for my notation for partitions will become apparent.

Proof.  The proof is apparent enough that it could be an exercise in an undergraduate combinatorics text, except that defining the problem requires such lengthy preliminaries.  In outline:  consider how you would count the number of rookeries that contain exactly i of one symbol or other.  One way, if you have the signature available, would be to take the indicated dot products of the signature with column i of the partitions.  But another way would be to refer to the square directly.  There are n different symbols.  For a given symbol, there are (n choose i) different sets of i cells containing that symbol.  And given such a set, the number of ways of choosing other cells from the remaining rows and columns, without hitting another cell that contains the given symbol, is d(n - i).  (The last sentence is the only moderately tricky part.)  Since the two formulas count the same objects, they must give equal results.

Signatures of latin squares therefore have some structure to them, and several of their components count features in which we are interested.  But the Signature Theorem is not particularly strong since the number of partitions of n, giving the number of components of the signature vector, increases much more quickly than the number of linear equations it gives us to describe the signature vectors.  However, I still feel there is some hope for signatures to be a useful line of study of latin squares, because my empirical study of the signatures of squares of order 6 demonstrates a further relationship that I still can’t explain.  The rest of my remarks describe “math under construction.”

Theorem-in-waiting.  In any latin square of order 6, 3 x <6> + <4 1> + <0 1 0 1> = 162.

This is true, as computer investigation verifies, but I have no explanatory proof of it.  As I remember there are about 19 latin squares of order 6 that are “different” cases to be considered, and the relationship above holds in all of them, so it can hardly be coincidental.  And it does not follow from the Signature Theorem.  Is it an example of some relationship that also holds for larger squares?

There is one detail I can add now to the inquiry into the Theorem-in-waiting.

Definition.  A “pentad“ is a set of 5 cells of a latin square of order 6 with no two in the same row or column and no two containing the same symbol.  Hence the number of pentads is twice the number of pentransversals plus six times the number of transversals.  (Each transversal has (6 choose 5), or 6, pentads “inside” it, while each pentransversal has exactly 2.  Every pentad can be extended either to a transversal or pentransversal, so these are all of them.)

Hence the Theorem-in-waiting is equivalent to:  In any latin square of order 6, the number of pentads plus four times the number of intercalary squares is 324.

Computer investigation further confirms the following statement:  In any row of a latin square of order 6, the number of pentads containing any cell of the row plus twice the number of intercalary squares containing any cell of the row equals 270 minus (four times the number of intercalary squares in the entire square).  Now this is stronger than the Theorem-in-waiting, in that the Theorem follows from this fact (add up the equations for all six rows), but this fact does not follow from the Theorem-in-waiting.  The Theorem-in-waiting tells us nothing about individual rows.  Hence I believe that explaining this latter statement is the way to reach the Theorem-in-waiting, but I don’t yet see how to explain the stronger fact either.

For some years I haven’t had time to pursue these researches, but various lines of attack suggest themselves.  Do the signatures of higher-order squares also span a smaller vector space than the Signature Theorem would suggest?  Can a computer find any relationship between the numbers of “pentads” (or analogous sets of cells) and intercalary squares, or other latin subsquares, at higher orders?  I hope to live long enough to understand all this.

Questions, corrections, comments:  Send me e-mail at  markthom@flash.net