Modular Latin squares.
Version of Thursday 27 February 2020.
Dave Barber's other pages.

Latin squares have been studied by mathematicians for many years; presented here is a variant based on modular arithmetic.

As would be expected in the modular environment, all numbers in this report are integers. Both the remainders and quotients from modular division will be used, with the modulus serving as divisor. Moduli are positive and all other numbers are nonnegative. With that, the following customary practice is observed here:

 Given a dividend and modulus, chosen as a remainder will always be the smallest nonnegative value that will satisfy the following equation: dividend − remainder = modulus × quotient As a consequence, the quotient will be unique and nonnegative.

⇒ LS(s) stands for a ordinary Latin square:

• It has with s rows and s columns.
• It contains s different values.
• Within each row, and within each column, each value must occur once.

⇒ MLS(s, v) stands for a modular Latin square:

• It has s rows and s columns.
• It contains v different values.
• v must be a divisor of s.
• Within each row, and within each column, each value must occur s ÷ v times.

When s = v, an MLS(s, v) becomes an LS(s). Examples of both are labeled below.

Although the matter is not developed here, the extension to three dimensions and more is straightforward.

Square 1a is an ordinary Latin square of size six. Because modular arithmetic will be performed, the numbers chosen for the contents are the smallest nonnegative integers. The rows and columns are labeled with letters for reference.

1aUVWXYZ
A531042
B014523
C352104
D425310
E140235
F203451
LS(6)

The next squares are various remainders and quotients.

1bUVWXYZ
A201012
B011220
C022101
D122010
E110202
F200121
MLS(6, 3):
remainder modulo 3 of square 1a
1cUVWXYZ
A110010
B001101
C110001
D101100
E010011
F001110
MLS(6, 2):
quotient modulo 3 of square 1a
1dUVWXYZ
A111000
B010101
C110100
D001110
E100011
F001011
MLS(6, 2):
remainder modulo 2 of square 1a
1eUVWXYZ
A210021
B002211
C121002
D212100
E020112
F101220
MLS(6, 3):
quotient modulo 2 of square 1a

Square 1f is a NON-example of a modular Latin square. Even though all rows and columns contain the same complement of values, each row and column considered individually is unbalanced, containing 2 zeroes and 2 ones, but only 1 two and 1 three. This fails because four is not a factor of six.

1fUVWXYZ
A131002
B010123
C312100
D021310
E100231
F203011
NOT MLS:
remainder modulo 4 of square 1a

The table below shows how many permutations of symbols can occur within a row or column of some MLSs:

MLS typepermutationsexample
LS(1, 1)1! = 1 0
LS(2, 2)2! = 2 1 0
LS(3, 3)3! = 6 2 0 1
LS(4, 4)4! = 24 0 3 2 1
LS(5, 5)5! = 120 4 2 0 1 3
MLS(4, 2)4! ÷ (2!)2 = 6 0 1 0 1 1 0
MLS(6, 2)6! ÷ (3!)2 = 20 1 0 1 1 0 0
MLS(8, 2)8! ÷ (4!)2 = 70 0 1 1 0 0 1 0 1
MLS(6, 3)6! ÷ (2!)3 = 90 2 0 1 1 2 0
MLS(9, 3)9! ÷ (3!)3 = 1680 1 0 2 2 2 0 0 1 1
MSL(s, v) s! ÷ ((s ÷ v)!)v

For many applications, an equivalence relation is defined for Latin squares:

• If two rows of a Latin square are exchanged, the result is deemed equivalent to the original.
• If two columns of a Latin square are exchanged, the result is deemed equivalent to the original.

By contrast, if a row is exchanged with a column, the result will probably not be a Latin square.

A standard practice is to exchange rows multiple times until the numbers in the first column are increasing; and then similarly with the columns. When this is done to square 1a, the result is 2a. In this case, the rows were sorted before the colums were; had the columns been sorted first, a different, but equally valid, representation would have been produced.

2aUVYZWX
B012345
E143502
F205134
C350421
D421053
A534210
LS(6):
sorted version of square 1a

In an ordinary Latin square, where no number is repeated within a row or column, a procedure to sort the rows need consider only the numbers in the first column; to sort columns, only the first row. On the other hand, in a modular Latin square where numbers are repeated, more is required: a lexicographical approach is suggested.

If two rows differ in the first column, the less-than relationship between them is established. If the rows are equal in the first column but are unequal in the second column, the second column prevails. This continues to further columns if necessary. Of course, columns are handled analogously.

As an explicit example, what follows is a lexicographical listing, from least to most, of all the possible rows in a size-six Latin square formed with modulo-two remainders or modulo-three quotients — an MLS(6, 2). Those rows and columns that happen to appear in square 2d, which appears below, are marked.

 0 0 0 1 1 1 0 0 1 0 1 1 – D, W 0 0 1 1 0 1 0 0 1 1 1 0 – F 0 1 0 0 1 1 0 1 0 1 0 1 – B, U 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 – Y 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 1 – V 1 0 0 1 1 0 – X 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 – E 1 1 0 0 0 1 – C 1 1 0 0 1 0 – A 1 1 0 1 0 0 1 1 1 0 0 0 – Z

When a sorted square is modularly reduced, whether by remainder or quotient, it might become unsorted. Below are reductions of square 2a, with listings of inversions of consecutive rows or columns. In 2e, the rows and columns happen to end up sorted for no particular reason.

2bUVYZWXrow <col <
B012012C < FZ < Y
E110202
F202101
C020121
D121020
A201210
MLS(6,3):
remainder modulo 3 of square 2a
2cUVYZWXrow <col <
B000111F < E
D < C
W < Z
E011100
F001011
C110100
D100011
A111000
MLS(6,2):
quotient modulo 3 of square 2a
2dUVYZWXrow <col <
B010101F < E
D < C
Y < V
W < Z
E101100
F001110
C110001
D001011
A110010
MLS(6,2):
remainder modulo 2 of square 2a
2eUVYZWXrow <col <
B001122nonenone
E021201
F102012
C120210
D210021
A212100
MLS(6,3):
quotient modulo 2 of square 2a

With an ordinary Latin square, it is always possible to sort both the rows and columns into ascending order. On the other hand, this is not generally true with modular Latin squares. For instance, square 3a is in order by rows but not columns; but when 3a is sorted by columns, producing 3b, it is no longer in order by rows.

3aUVWXYZrow <col <
A000111noneW < V
Z < Y
B010110
C011001
D101010
E101100
F110001
LS(6,2):
sorted by rows
3bUWVZXYrow <col <
A000111F < Enone
B001011
C011100
D110001
E110010
F101100
LS(6,2):
sorted by columns

Square 3c shows that a modular square sorted by both rows and columns might not be symmetrical around the main diagonal; highlighted are the exceptions.

3cUVWXYZrow <col <
A 000 111 nonenone
B 011 001
C 011 010
D 100 110
E 101 001
F 110 100
LS(6,2):
sorted by rows and columns

More will be said about symmetry later.

Here are some enumerations:

quantities of Latin squares
total sorted by
row or column
sorted by
row and column
LS(1,1)111
LS(2,2)211
LS(3,3)1221
LS(4,4)576244
LS(5,5)161,2801,34456
LS(6,6)812,851,2001,128,9609,408
LS(7,7)61,479,419,904,00012,198,297,60016,942,080
see: OEIS A002860 OEIS A000315

quantities of modular Latin squares
total sorted by
row or column
sorted by
row and column
MLS(2,2) 211
MLS(4,2) 9062
MLS(6,2) 297,20055025
MLS(8,2) 116,963,796,2503,330,9157,776
see:OEIS A058527

quantities of modular Latin squares
total sorted by
row or column
sorted by
row and column
MLS(3,3) 1221
MLS(6,3) 35,599,50050,115873

There is an obvious definition of diagonal symmetry for modular Latin squares; it is the same as used in matrix arithmetic, and is mentioned in connection with square 3c.

Let A be an MLS, and let A(r, c) be the value in the rth row and cth column. If A(r, c) equals A(c, r) for all r and c, then A is diagonally symmetric.

Because modular reduction is a function in the strict sense, a diagonally symmetric MLS remains that way when reduced.

Quite a different kind of symmetry has been investigated by E. I. Vatutin and others, with examples here.

Start with an even number s and an MLS(s, v) named A. Within A, the first row and column are numbered zero, and the last s − 1.

• Suppose that there exist particular values of r, c, x, and y such that A(r, c) = x and A(r, sc − 1) = y.
• And suppose that for all values of r and c, it is true that A(r, c) = x implies A(r, sc − 1) = y.
• Then A is said to be horizontally symmetric.

Horizontal symmetry can be defined for not just Latin squares, but adapted to any rectangular arrays of numbers.

An example will be helpful. Square 4a is horizontally symmetric, and 4b is an extract that may make the arrangement clearer. Within any row, if the value 1 appears n cells to the left of the dividing bar, the value 3 will appear n cells to the right of the bar.

4aUVWXYZ
A015234
B453120
C342501
D534012
E201345
F120453
LS(6):
horizontally symmetric
4b U V W X Y 1 3 3 1 3 1 3 1 1 3 1 3 extract ofsquare 4a

Naturally, the analogous vertical symmetry is achieved by exchanging rows and columns. Horizontal and vertical symmetries are preserved in modular reduction.