Введение
В комбинаторной математике два латинских квадрата одного размера (порядка) называются ортогональными, если при наложении друг на друга упорядоченные парные элементы в соответствующих позициях все различны. Множество латинских квадратов, все одного и того же порядка, любые два из которых ортогональны, называется набором взаимно ортогональных латинских квадратов. Эта концепция ортогональности в комбинаторике тесно связана с понятием блокировки в статистике, обеспечивающим истинную независимость независимых переменных и отсутствие скрытых влияющих корреляций. Таким образом, "ортогональный" является синонимом "независимого", поскольку знание значения одной переменной не предоставляет никакой дополнительной информации о вероятном значении другой переменной. Устаревшим названием для пары ортогональных латинских квадратов является греко-латинский квадрат, встречающийся в старой литературе.
In combinatorial mathematics, two Latin squares of the same size (order) are said to be orthogonal if when superimposed the ordered paired entries in the positions are all distinct. A set of Latin squares, all of the same order, all pairs of which are orthogonal is called a set of mutually orthogonal Latin squares. This concept of orthogonality in combinatorics is strongly related to the concept of blocking in statistics, which ensures that independent variables are truly independent with no hidden confounding correlations. "Orthogonal" is thus synonymous with "independent" in that knowing one variable's value gives no further information about another variable's likely value. An outdated term for pair of orthogonal Latin squares is Graeco Latin square, found in older literature.
Греко-латинские квадраты
Греко-латинский квадрат, или эйлеровский квадрат, или пара ортогональных латинских квадратов порядка n над двумя множествами S и T (которые могут совпадать), каждое из которых состоит из n символов, представляет собой таблицу размером n × n, каждая ячейка которой содержит упорядоченную пару (s, t), где s принадлежит S, а t принадлежит T, таким образом, что каждая строка и каждый столбец содержат каждый элемент S и каждый элемент T ровно один раз, и никакие две ячейки не содержат одну и ту же упорядоченную пару. Расположение только s-координат (которые можно рассматривать как латинские символы) и только t-координат (греческие символы) каждое образует латинский квадрат. Следовательно, греко-латинский квадрат можно разложить на два ортогональных латинских квадрата. Ортогональность в данном случае означает, что каждая пара (s, t) из декартова произведения S × T встречается ровно один раз. Ортогональные латинские квадраты были подробно изучены Леонардом Эйлером, который в качестве множеств S и T принимал 1=S = {A, B, C, …}, первые n заглавных букв латинского алфавита, и 1=T = {α, β, γ, …}, первые n строчных букв греческого алфавита, – отсюда и название «греко-латинский квадрат».
the first n lower case letters from the Greek alphabet—hence the name Graeco Latin square.
Существование
Когда греко-латинский квадрат рассматривается как пара ортогональных латинских квадратов, каждый из латинских квадратов считается имеющим ортогональный компаньон. В произвольном латинском квадрате выбор позиций, по одной в каждой строке и по одному в каждом столбце, элементы которых все различны, называется поперечным сечением этого квадрата. Рассмотрим один символ в греко-латинском квадрате. Позиции, содержащие этот символ, должны располагаться в разных строках и столбцах, и, кроме того, другие символы в этих позициях должны быть все различными. Следовательно, при рассмотрении как пары латинских квадратов, позиции, содержащие один символ в первом квадрате, соответствуют поперечному сечению во втором квадрате (и наоборот). Данный латинский квадрат порядка n обладает ортогональным компаньоном тогда и только тогда, когда у него есть n непересекающихся поперечных сечений. Таблица Кэли (без рамок) любой группы нечетного порядка образует латинский квадрат, обладающий ортогональным компаньоном.
Конструкция конечного поля
Полный набор MOLS(q) существует всякий раз, когда q является простым числом или степенью простого числа. Это следует из построения, основанного на конечном поле GF(q), которое существует только если q является простым числом или степенью простого числа. Мультипликативная группа GF(q) является циклической группой и, следовательно, имеет генератор λ, что означает, что все ненулевые элементы поля можно представить как различные степени λ. Обозначим q элементов GF(q) следующим образом: α0 = 0, α1 = 1, α2 = λ, α3 = λ2, ..., αq-1 = λq-1. Теперь λq-1 = 1, и правило произведения в терминах α выражается как αiαj = αt, где t = i + j - 1 (mod q - 1). Латинские квадраты строятся следующим образом: элемент (i, j) латинского квадрата Lr (при r ≠ 0) равен Lr(i,j) = αi + αrαj, где все операции выполняются в GF(q). В случае, когда поле является простым (q = p, где p – простое число), и элементы поля представлены обычным способом, как целые числа по модулю p, указанное соглашение об именовании можно опустить, и правило построения упрощается до Lr(i,j) = i + rj, где r ≠ 0 и i, j и r являются элементами GF(p), а все операции выполняются в GF(p). Приведенные выше примеры MOLS(4) и MOLS(5) были получены из этой конструкции, хотя и с изменением алфавита. Не все полные наборы MOLS возникают из этой конструкции. Проективная плоскость, связанная с полным набором MOLS, полученным из этой полевой конструкции, является специальным типом – дезаргезианской проективной плоскостью. Существуют недезаргезианские проективные плоскости, и соответствующие им полные наборы MOLS не могут быть получены из конечных полей.
α0 = 0, α1 = 1, α2 = λ, α3 = λ2, , αq 1 = λq 2. Now, λq 1 = 1 and the product rule in terms of the α's is αiαj = αt, where t = i + j 1 (mod q 1). The Latin squares are constructed as follows, the (i, j)th entry in Latin square Lr (with r ≠ 0) is Lr(i,j) = αi + αrαj, where all the operations occur in GF(q). In the case that the field is a prime field (q = p a prime), where the field elements are represented in the usual way, as the integers modulo p, the naming convention above can be dropped and the construction rule can be simplified to Lr(i,j) = i + rj, where r ≠ 0 and i, j and r are elements of GF(p) and all operations are in GF(p). The MOLS(4) and MOLS(5) examples above arose from this construction, although with a change of alphabet. Not all complete sets of MOLS arise from this construction. The projective plane that is associated with the complete set of MOLS obtained from this field construction is a special type, a Desarguesian projective plane. There exist non Desarguesian projective planes and their corresponding complete sets of MOLS can not be obtained from finite fields.
Теория графов
Набор из k MOLS(n) эквивалентен разделению ребер полного (k+2)-дольного графа Kn,n на полные подграфы порядка k+2.
Приложения
Взаимно ортогональные латинские квадраты имеют широкий спектр применений. Они используются как основа для построений в статистическом планировании экспериментов, составлении расписаний турниров, а также в кодах, предназначенных для исправления и обнаружения ошибок. Интерес Эйлера к греко-латинским квадратам был связан с его стремлением создавать магические квадраты. Французский писатель Жорж Перек построил структуру своего романа 1978 года "Жизнь: Руководство по эксплуатации" вокруг греко-латинского квадрата 10×10.