Латинский квадрат

Латинский квадрат 7-го порядка (окно памяти Рональда Эйлмера Фишера в Gonville and Caius College , Кембридж)

Латинский квадрат представляет собой квадратную схему с рядами и колоннами, с каждым полем, занимаемых одним из различных символов, так что каждый символ появляется ровно один раз в каждой строке и в каждом столбце. Натуральное число называется порядком латинского квадрата. ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n}$ ${\ displaystyle n}$

В качестве символов часто используются цифры от до , разные буквы или разные цвета. Математик Леонард Эйлер интенсивно занимался такими квадратами; он использовал латинский алфавит как набор символов . Ему восходит название «Латинский квадрат». ${\ displaystyle 1}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n}$

В современной комбинаторике и дискретной математике символом является сумма, в основном числа вверх , реже числа, которые будут использоваться, и схема такая же особенная - рассматривается матрица . ${\ displaystyle 1}$${\ displaystyle n}$${\ displaystyle 0}$${\ displaystyle n-1}$${\ Displaystyle п \ раз п}$

Каждый латинский квадрат можно понимать как таблицу соединений (таблицу Кэли) конечной квазигруппы , и наоборот, каждая конечная квазигруппа определяет класс эквивалентности латинских квадратов.

Два разных латинских квадрата одного порядка могут быть ортогональны друг другу. В синтетической геометрии задаются определенные наборы попарно ортогональных латинских квадратов конечного порядка аффинных плоскостей . Это приводит к необходимому и достаточному комбинаторному условию существования уровней порядка : такой уровень существует тогда и только тогда, когда существует полный список попарно ортогональных квадратов порядка . ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n}$

Помимо математики в более узком смысле, латинские квадраты используются, среди прочего, в сельскохозяйственном экспериментальном планировании как блочные системы и в статистическом экспериментальном планировании.

Представление, свойства и условия

Представление в виде матрицы

Латинский квадрат порядка - это квадратная матрица , все элементы которой являются натуральными числами от до , таким образом, что каждое из этих чисел появляется ровно один раз в каждой строке и в каждом столбце матрицы. Это свойство можно проверить для матрицы (например, с помощью системы компьютерной алгебры, такой как Maple ) следующим образом: Для записей в матрице должны выполняться следующие уравнения:${\ displaystyle n}$${\ Displaystyle п \ раз п}$${\ displaystyle 1}$${\ displaystyle n}$${\ displaystyle M_ {j, k}}$${\ displaystyle M}$

• Для каждой линии , и${\ Displaystyle к, \, 1 \ Leq к \ Leq п}$${\ displaystyle \ sum _ {j = 1} ^ {n} 2 ^ {M_ {j, k} -1} = 2 ^ {n} -1}$
• должен применяться к каждому столбцу .${\ Displaystyle J, \, 1 \ Leq J \ Leq N}$${\ displaystyle \ sum _ {k = 1} ^ {n} 2 ^ {M_ {j, k} -1} = 2 ^ {n} -1}$

Тройное представление: ВЕСЛО

Латинский квадрат порядка также может быть представлен в виде набора из различных троек . Таким образом, это номер строки («строки») в латинском квадрате, номер столбца и номер в квадрате. Правило латинских квадратов выполняется тогда и только тогда, когда никакие две тройки в двух записях не совпадают. Это представление известно как представление ортогонального массива (OAR) латинского квадрата. ${\ displaystyle n}$${\ displaystyle Q}$${\ Displaystyle п ^ {2}}$ ${\ Displaystyle (г, s, z) \ в \ {1,2, \ ldots п \} ^ {3}}$${\ displaystyle r}$${\ displaystyle s}$${\ displaystyle z}$

OAR предлагает геометрическую интерпретацию латинского квадрата: число в ячейке латинского квадрата можно понимать как высоту кубоида, который должен быть построен на этой ячейке в качестве основы. Это превращает латинский квадрат в пространственную гистограмму - сравните иллюстрацию с примером ниже.

Связанную интерпретацию латинского квадрата порядка можно также увидеть на рисунке : если заполнить куб только в верхней части каждого столбца гистограммы, то получится трехмерное изображение параллельной оси единицы. кубики в большем осевом параллельном кубе с длиной ребра . Подкуб с координатами сетки «заполнен» тогда и только тогда, когда латинский квадрат принадлежит OAR. Расположение частичных кубов в таком кубе с длиной ребра относится к латинскому квадрату порядка именно тогда, когда большой куб непрозрачен, если смотреть через частичные кубы в трех параллельных в осевом направлении направлениях, т.е. когда проецируется в одном осевом направлении, он кажется полностью заполненным. . ${\ displaystyle n}$${\ Displaystyle п ^ {2}}$${\ displaystyle n}$${\ displaystyle (r, s, z)}$${\ displaystyle (r, s, z)}$${\ Displaystyle п ^ {2}}$${\ displaystyle n}$${\ displaystyle n}$

Тройки представления OAR можно интерпретировать как пространственные координаты или как высоту столбцов на латинском квадрате. На этом рисунке для ясности только первый и последний столбцы (s = 1 и s = 4) латинского квадрата четвертого порядка (красные числа на основании) показаны в виде столбцов. Куб в верхней части этих столбцов выделен цветом.

Эта интерпретация проясняет, что OAR латинского квадрата становится OAR латинского квадрата не только тогда, когда меняются местами номера строк и столбцов ( транспозиция в матричном представлении), но даже когда все номера символов меняются местами с номерами строк. или номера столбцов!

пример

Пример на рисунке справа показывает первый латинский квадрат C ниже, второй, D , создается путем замены оси « -» на « -» . Если поменять местами - с по - осям в первом квадратном C , квадрат D также создаются , потому что его матрица является симметричной. ${\ displaystyle r}$${\ displaystyle z}$${\ displaystyle s}$${\ displaystyle z}$

${\ displaystyle C = \ left [{\ begin {array} {cccc} 3 & 4 & 2 & 1 \\ 4 & 3 & 1 & 2 \\ 1 & 2 & 4 & 3 \\ 2 & 1 & 3 & 4 \ end {array}} \ right]; \; D = \ left [{\ begin {array} {cccc} 4 & 3 & 1 & 2 \\ 3 & 4 & 2 & 1 \\ 1 & 2 & 4 & 3 \\ 2 & 1 & 3 & 4 \ end {array}} \ right]}$

Тройные представления:

${\ displaystyle {\ begin {array} {rllll} Q_ {C} = \ {& (1,1,3), & (1,2,4), & (1,3,2), & (1, 4,1), \\ & (2,1,4), & (2,2,3), & (2,3,1), & (2,4,2), \\ & (3,1 , 1), & (3,2,2), & (3,3,4), & (3,4,3), \\ & (4,1,2), & (4,2,1) , & (4,3,3), & (4,4,4) \ quad \} \ end {array}}}$

соответственно.

${\ displaystyle {\ begin {array} {rllll} Q_ {D} = \ {& (1,3,1), & (1,4,2), & (1,2,3), & (1, 1,4), \\ & (2,4,1), & (2,3,2), & (2,1,3), & (2,2,4), \\ & (3,1 , 1), & (3,2,2), & (3,4,3), & (3,3,4), \\ & (4,2,1), & (4,1,2) , & (4,3,3), & (4,4,4) \ quad \} \ end {array}}}$

Количество латинских квадратов

Номера латинских квадратов последовательности бланка заказа A002860 в OEIS . Нет известной формулы для последовательности, которую легко вычислить . Самые известные нижние и верхние границы для крупных заказов все еще далеки друг от друга. Классическая оценка:${\ Displaystyle L (п)}$${\ Displaystyle п = 1,2,3, \ ldots}$${\ Displaystyle L (п)}$${\ displaystyle n}$

${\ displaystyle {\ frac {\ left (n! \ right) ^ {2n}} {n ^ {n ^ {2}}}} \ leq L (n) \ leq \ prod _ {k = 1} ^ { n} \ left (k! \ right) ^ {n / k}.}$

Числа структурно различных латинских квадратов (т.е. квадраты не могут быть идентичны поворотом, зеркальным отображением или перестановкой символов) до 7-го порядка образуют последовательность A264603 в OEIS .

Уменьшенные латинские квадраты

Латинский квадрат называется сокращенным или нормализованным, если различные символы находятся в их «естественном порядке» в 1-м ряду и 1-м столбце . В тройном отображении с числами в качестве символов это означает: для первой строки и для первого столбца. Нормализации любого латинского квадрата всегда можно добиться, поменяв местами строки и столбцы. Квадрат 3-го порядка в приведенных ниже примерах нормализуется заменой 2-го ряда на третью, квадрат 4-го порядка уже уменьшен. ${\ displaystyle n}$${\ Displaystyle \ {(1,1,1); (1,2,2); \ ldots (1, n, n) \} \ подмножество Q}$${\ Displaystyle \ {(1,1,1); (2,1,2); \ ldots (n, 1, n) \} \ подмножество Q}$

Номера приведенных латинских квадратов последовательности бланка заказа A000315 в OEIS . Следующее относится к количеству всех латинских квадратов.${\ Displaystyle l (п)}$${\ Displaystyle п = 1,2,3, \ ldots}$${\ Displaystyle L (п)}$${\ displaystyle L (n) = n! \ cdot (n-1)! \ cdot l (n).}$

Примеры

Латинские квадраты третьего или четвертого порядка в матричном представлении:

${\ displaystyle {\ begin {bmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \ end {bmatrix}} \ quad {\ begin {bmatrix} 1 & 2 & 3 & 4 \ \ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \ end {bmatrix}}}$

Tripeldarstellung левый квадрат: . Если бы вы поменяли местами числа 1 и 2 в первой строке, тройка (1-я строка, 1-й столбец содержит 2) и тройка (3-я строка, 1-й столбец содержит 2) были бы в двух местах (столбец и символ) совпадают и квадрат больше не будет латинским квадратом. ${\ Displaystyle \ {(1,1,1); (1,2,2); (1,3,3); (2,1,3); (2,2,1); (2,3, 2); (3,1,2); (3,2,3); (3,3,1) \}}$${\ Displaystyle (1,1,2)}$${\ Displaystyle (3,1,2)}$

Указать латинский квадрат для любого заданного порядка легко : для этого произвольно распределяют различные символы в первой строке квадрата. Следующие строки теперь заполняются последовательно, заменяя предыдущую строку, сдвинутую на единицу вправо. Самый правый символ предыдущего ряда выпадет из квадрата; вместо этого он вводится в новую строку слева. ${\ displaystyle n}$${\ displaystyle n}$

Пример порядка 3 построен таким образом, в примере порядка 4 вместо сдвига вправо каждая строка циклически перемещалась влево . Если вы начнете с этой конструкции, как в показанном примере, с отсортированной первой строки с числами , вы всегда получите уменьшенный латинский квадрат, который можно интерпретировать как таблицу связей группы классов остатка . Для этого все введенные числа должны быть уменьшены на 1. ${\ displaystyle 1,2, \ ldots n}$ ${\ Displaystyle \ влево (\ mathbb {Z} / п \ mathbb {Z}, + \ right)}$

Ортогональные латинские квадраты и MOLS

Два латинских квадрата и называются ортогональными, если никакие две пары не совпадают с этим результатом, когда вы записываете записи друг за другом и рядом друг с другом в новую схему квадратов . В матричном представлении:${\ displaystyle Q}$${\ displaystyle R}$${\ Displaystyle п ^ {2}}$${\ displaystyle Q}$${\ displaystyle R}$${\ displaystyle S}$

${\ displaystyle Q: = {\ begin {bmatrix} 3 & 2 & 1 \\ 2 & 1 & 3 \\ 1 & 3 & 2 \ end {bmatrix}} \ quad R: = {\ begin {bmatrix} 2 & 3 & 1 \\ 1 & 2 & 3 \\ 3 & 1 & 2 \ end {bmatrix}} \ longrightarrow S = {\ begin {bmatrix} 32 & 23 & 11 \\ 21 & 12 & 33 \\ 13 & 31 & 22 \ end {bmatrix}}}$

Латинские квадраты и объединенные здесь для формирования матрицы ортогональны. В этом случае квадрат, обозначенный значком, называется греко-латинским квадратом . Номера пар ортогональных латинских квадратов последовательности A072377 в порядке формы в OEIS . ${\ displaystyle S}$${\ displaystyle Q}$${\ displaystyle R}$${\ displaystyle S}$${\ Displaystyle п = 1,2,3, \ ldots}$

Следующее предложение важно для использования в геометрии:

Позвольте быть набором латинских квадратов, порядок , с тем свойством, что два разных латинских квадрата всегда ортогональны друг другу. Тогда содержит не более элементов.${\ Displaystyle {\ mathfrak {L}}}$${\ Displaystyle п \ geq 2}$${\ Displaystyle L_ {1}, L_ {2} \ in {\ mathfrak {L}}}$${\ Displaystyle {\ mathfrak {L}}}$${\ displaystyle n-1}$

(предполагаемое) максимальное количество MOLS

Заказать n	R (п)
0	${\ displaystyle \ infty}$
1	${\ displaystyle \ infty}$
2	1
3	2
4-й	3
5	4-й
Шестой	1
7-е	Шестой
8-е	7-е
9	8-е
10	${\ Displaystyle {} \ geq 2 \; ({} = 2?)}$
11	10
12-е	${\ displaystyle {} \ geq 5}$
13-е	12-е

Список попарно ортогональных латинских квадратов порядка будет сказать , будет завершена . Последовательность максимально возможного числа попарно ортогональных латинских квадратов ( MOLS = взаимно ортогональные латинские квадраты ) порядка - это последовательность A001438 в OEIS , то, что известно о значениях, показано в таблице справа, значения Для 0 и 1 являются условными. Применимо следующее: ${\ displaystyle n-1}$${\ displaystyle n}$${\ Displaystyle R (п)}$${\ displaystyle n}$${\ displaystyle n = 13}$

• Есть и , значит, есть , потому что список попарно ортогональных латинских квадратов всегда можно дополнить.${\ displaystyle n> 4}$${\ Displaystyle R (п) \ GEQ п-3}$${\ Displaystyle R (п) = п-1}$${\ Displaystyle п-3 \ geq 2}$
• Для есть , для есть${\ displaystyle n> 6}$${\ Displaystyle R (п) \ geq 2}$${\ displaystyle n> 52}$${\ Displaystyle R (п) \ geq 4.}$
• Является ли простое число , и тогда .${\ displaystyle p}$${\ Displaystyle г \ в \ mathbb {N}}$${\ Displaystyle R (p ^ {r}) = p ^ {r} -1}$
• На сегодняшний день неизвестно, существует ли натуральное число , которое не является степенью простого числа и к которому применимо.${\ displaystyle n}$${\ Displaystyle R (п) = п-1}$
• Ибо достаточно большое есть , так оно и есть .${\ displaystyle n}$${\ Displaystyle R (п) \ geq п ^ {1/17} -2}$${\ Displaystyle \ lim _ {п \ к \ infty} R (п) = \ infty}$
• Это действительно всегда , потому что список MOLS заказа и список t MOLS заказа всегда может быть списком заказа MOLS, произведенного. Процедура демонстрируется здесь на простом примере:${\ Displaystyle п, м \ geq 3}$${\ Displaystyle Р (п \ CDOT м) \ GEQ \ мин (р (п), р (м))}$${\ displaystyle t}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle t}$${\ displaystyle n \ cdot m}$

${\ displaystyle A = {\ begin {bmatrix} {\ color {Red} 1} & {\ color {Blue} 2} \\ {\ color {Green} 2} & {\ color {Cyan} 1} \ end { bmatrix}} {\ mathrel {\ widehat {=}}} {\ begin {bmatrix} {\ color {Red} 0} & {\ color {Blue} 1} \\ {\ color {Green} 1} & {\ цвет {голубой} 0} \ end {bmatrix}}, \ quad B = {\ begin {bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\\ end {bmatrix}} }$

${\ displaystyle \ longrightarrow {\ begin {bmatrix} {\ color {Red} 0} \ cdot 3 + 1 & {\ color {Red} 0} \ cdot 3 + 2 & {\ color {Red} 0} \ cdot 3 + 3 & {\ color {Blue} 1} \ times 3 + 1 & {\ color {Blue} 1} \ times 3 + 2 & {\ color {Blue} 1} \ times 3 + 3 \\ {\ color { Красный} 0} \ cdot 3 + 2 & {\ color {Red} 0} \ cdot 3 + 3 & {\ color {Red} 0} \ cdot 3 + 1 & {\ color {Blue} 1} \ cdot 3 + 2 & {\ color {Blue} 1} \ times 3 + 3 & {\ color {Blue} 1} \ times 3 + 1 \\ {\ color {Red} 0} \ times 3 + 3 & {\ color {Red } 0} \ times 3 + 1 & {\ color {Red} 0} \ times 3 + 2 & {\ color {Blue} 1} \ times 3 + 3 & {\ color {Blue} 1} \ times 3 + 1 & {\ color {Blue} 1} \ times 3 + 2 \ \ {\ color {Green} 1} \ times 3 + 1 & {\ color {Green} 1} \ times 3 + 2 & {\ color {Green} 1} \ times 3 + 3 & {\ color {Cyan} 0} \ times 3 + 1 & {\ color {Cyan} 0} \ times 3 + 2 & {\ color {Cyan} 0} \ times 3 + 3 \ \ {\ color {Green} 1} \ times 3 + 2 & {\ color {Green} 1} \ times 3 + 3 & {\ color {Green} 1} \ times 3 + 1 & {\ color {Cyan} 0 } \ times 3 + 2 & {\ color {Cyan} 0} \ times 3 + 3 & {\ color {Cyan} 0} \ times 3 + 1 \\ {\ color {Green} 1} \ times 3 + 3 & {\ color {Green} 1} \ times 3 + 1 & {\ color {Green} 1} \ times 3 + 2 & {\ color {Cyan} 0} \ times 3 + 3 & {\ color {Cyan} 0} \ times 3 + 1 & {\ color {Cyan} 0} \ times 3 + 2 \ end {bmatrix} } = {\ begin {bmatrix} {\ color {Red} 1} & {\ color {Red} 2} & {\ color {Red} 3} & {\ color {Blue} 4} & {\ color {Blue} 5} & {\ color {Blue} 6} \\ {\ color {Red} 2} & {\ color {Red} 3} & {\ color {Red} 1} & {\ color {Blue} 5} & { \ color {Blue} 6} & {\ color {Blue} 4} \\ {\ color {Red} 3} & {\ color {Red} 1} & {\ color {Red} 2} & {\ color {Blue } 6} & {\ color {Blue} 4} & {\ color {Blue} 5} \\ {\ color {Green} 4} & {\ color {Green} 5} & {\ color {Green} 6} & {\ color {Cyan} 1} & {\ color {Cyan} 2} & {\ color {Cyan} 3} \\ {\ color {Green} 5} & {\ color {Green} 6} & {\ color { Зеленый} 4} & {\ color {Cyan} 2} & {\ color {Cyan} 3} & {\ color {Cyan} 1} \\ {\ color {Green} 6} & {\ color {Green} 4} & {\ color {Зеленый} 5} & {\ color {Cyan} 3} & {\ color {Cyan} 1} & {\ color {Cyan} 2} \\\ end {bmatrix}}}$

Магические квадраты

Согласно его построению , если пары чисел биективно перекодированы в последовательные натуральные числа в греко-латинском квадрате порядка n - например, Б. - все суммы строк и суммы строк одинаковы, например квадрат S может быть квадратом${\ Displaystyle (J, K) \ mapsto (J-1) \ CDOT N + K}$${\ displaystyle {\ hat {S}}}$

${\ displaystyle S = {\ begin {bmatrix} 32 & 23 & 11 \\ 21 & 12 & 33 \\ 13 & 31 & 22 \ end {bmatrix}} \ quad \ longrightarrow \ quad {\ hat {S}} = {\ begin {bmatrix} 8 & 6 & 1 \\ 4 & 2 & 9 \\ 3 & 7 & 5 \ end {bmatrix}}}$

назначьте, где каждая строка и каждый столбец имеют магическую сумму . ${\ displaystyle s = 15}$

Если сумма двух диагоналей в таком квадрате также равна сумме строк и столбцов, то говорят о магическом квадрате .

Приложения

Алгебра: латинские квадраты и таблицы связей

Связывающая таблица циклической группы C ₅ в виде латинского квадрата в цвете. Нейтральный элемент имеет черный цвет. Цветные таблицы ссылок используются в онлайн-математической энциклопедии MathWorld , как и таблицы в оттенках серого.

Первое изображение слева показывает полную таблицу связей группы : ${\ Displaystyle C_ {5} = \ влево (\ mathbb {Z} / 5 \ mathbb {Z}, + \ right)}$

${\ displaystyle +}$ 0 1 2 3 4-й 0 0 1 2 3 4-й 1 1 2 3 4-й 0 2 2 3 4-й 0 1 3 3 4-й 0 1 2 4-й 4-й 0 1 2 3

${\ displaystyle \ longrightarrow \ left [{\ begin {array} {ccccc} 0 & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 0 \\ 2 & 3 & 4 & 0 & 1 \\ 3 & 4 & 0 & 1 & 2 \\ 4 & 0 & 1 & 2 & 3 \ end {array}} \ right {array} \ longright \ left [{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \\ 3 & 4 & 5 & 1 & 2 \\ 4 & 5 & 1 & 2 & 3 \\ 5 & 1 & 2 & 3 & 4 \ end {array}} \ right ]}$

В средней матрице заголовки строк и столбцов, то есть элементы группы, связанные знаком "+", были опущены, поэтому эта матрица представляет латинский квадрат с набором символов, который является общим для остаточных классов. Если вы добавите 1 к каждая запись, результат - латинский квадрат со стандартным количеством символов . Этот латинский квадрат нормализован здесь, потому что элементы группы группы для таблицы связей были расположены в их «естественном порядке» как кратное порождающему элементу 1, и эта группа является циклической . ${\ Displaystyle \ {0,1,2,3,4 \}}$${\ displaystyle \ {1,2,3,4,5 \}}$${\ displaystyle C_ {5}}$

Следует отметить , что не существует вообще никакого расположения специфического для элементов группы или квази-группы: Если симметричная группа на основе элементов, то перестановка , которая последовательно применяется к строкам и столбцам таблицы связи ( в том числе их строк или заголовки столбцов), другая действительная таблица ссылок той же группы из исходной таблицы (слева); латинский квадрат, назначенный группе (справа), также изменяется. ${\ displaystyle S_ {n}}$${\ displaystyle n}$${\ displaystyle \ pi \ in S_ {n}}$

Формально и в более общем смысле применяется следующее: если порядок в матрице представляет собой латинский квадрат , то существует квазигруппа с элементами, которые - при подходящем расположении и нумерации их элементов - матрица имеет в качестве содержимого своей ссылки. стол. Просто латинские квадраты путем подобной перестановки строк и столбцов и «перенумерации» из-за возникновения, таким образом, истинного, могут рассматриваться как связующие таблицы этой квазигруппы. ${\ Displaystyle M = (M_ {j, k})}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle (M_ {j, k})}$${\ Displaystyle N = (N_ {j, k})}$${\ displaystyle \ pi \ in S_ {n}}$${\ displaystyle \ rho \ in S_ {n}}$${\ Displaystyle M = (M_ {j, k})}$${\ Displaystyle N _ {\ pi (j), \ pi (k)} = \ rho \ left (M_ {j, k} \ right) \, (1 \ leq j, k \ leq n)}$

• Если вы выбираете расположение элементов конечного цикла , то есть квази-группы с левым и правым нейтральным элементом в то же время , так что первый появляется элемент в таблице ссылок и назначают номера к элементам в их иначе в произвольном порядке в последовательности , тогда содержимое их таблицы ассоциаций, записанное с соответствующими натуральными числами, представляет собой сокращенный латинский квадрат порядка . (Число обозначает число элементов в ).${\ displaystyle L}$${\ displaystyle e}$${\ displaystyle e}$${\ displaystyle 1,2, \ ldots \ #L}$${\ displaystyle \ #L}$${\ displaystyle \ #L}$${\ displaystyle L}$
• Квазигруппа, которая имеет латинский квадрат порядка в качестве содержимого своей таблицы соединений, является коммутативной тогда и только тогда, когда матрица симметрична , то есть если выполняется. В случае коммутативной квазигруппы элементы всегда можно пронумеровать так, чтобы содержимое таблицы умножения представляло собой сокращенный латинский квадрат. Следует отметить, что здесь первая строка квадрата может быть приведена в соответствие только с заголовками столбцов таблицы ссылок - и, таким образом, одновременно с первым столбцом с заголовками строк - если квазигруппа представляет собой цикл.${\ Displaystyle M = (M_ {j, k})}$${\ displaystyle n}$${\ displaystyle (M_ {j, k})}$ ${\ Displaystyle M_ {к, j} = M_ {j, k} \, (1 \ Leq J, к \ Leq п)}$

Геометрия: ортогональные латинские квадраты и конечные плоскости

Из полного списка попарно ортогональных латинских квадратов порядка можно построить конечную аффинную плоскость порядка и наоборот. Вот как это работает:${\ Displaystyle {\ mathfrak {L}} = \ {L_ {1}, L_ {2}, \ ldots L_ {n-1} \}}$${\ displaystyle n}$${\ displaystyle n}$

• Набор точек состоит из пар натуральных чисел от 1 до :${\ displaystyle n}$

${\ displaystyle {\ mathcal {P}} = \ {(j, k): 1 \ leq j, k \ leq n \}.}$

• Каждый латинский квадрат определяет набор параллелей на плоскости:${\ Displaystyle L_ {я} \ ин {\ mathfrak {L}}, \; (1 \ leq i \ leq n-1)}$${\ displaystyle R_ {i}}$
• Семейство параллелей состоит из прямых${\ Displaystyle R_ {я} = \ {g_ {я, м}: 1 \ leq м \ leq n-1 \}}$

${\ Displaystyle g_ {я, m} = \ {(j, k): \, 1 \ leq j, k \ leq n \, \ land \, (L_ {i}) _ {j, k} = m \ }.}$

• Также есть два «направления оси», причем с прямыми линиями${\ Displaystyle R_ {0} = \ {g_ {0, m}: 1 \ leq m \ leq n \}}$${\ Displaystyle R_ {п} = \ {g_ {n, m}: 1 \ leq m \ leq n \}}$

${\ displaystyle g_ {0, m} = \ {(j, m): 1 \ leq j \ leq n \} \ quad \ mathrm {или} \ quad g_ {n, m} = \ {(m, k) : 1 \ leq k \ leq n \}.}$

• Прямой набор является объединение тех же толпы , как определено: .${\ Displaystyle {\ mathcal {G}} = \ bigcup _ {я = 0} ^ {п} R_ {я}}$

С другой стороны , можно выбрать в аффинной системе координат в конечной аффинной плоскости порядка п и присваивать номера , как «комбинаторные координаты» к точкам на первую оси, т.е. троичных элементы тела через любую биекцию для архетипа , за исключением п о происхождении O , так что ${\ displaystyle (O, E_ {1}, E_ {2})}$${\ displaystyle \ beta: \ {1,2, \ ldots n \} \ rightarrow K = OE_ {1}}$

${\ Displaystyle К = OE_ {1} = \ {\ beta (1), \ beta (2), \ beta (3), \ ldots \ beta (n) = O \}}$ применимо.

Это дает вам уникальную пару чисел для каждой точки на плоскости с использованием координатного представления, связанного с базой точки . Каждый из наборов параллелей, за исключением двух наборов, параллельных осям, определяет латинский квадрат, как описано выше, и квадраты, определенные таким образом, попарно ортогональны. Выраженные тройной связью T - также определяемой списком ортогональных латинских квадратов - прямые линии затем имеют уравнения прямой линии: ${\ displaystyle (O, E_ {1}, E_ {2})}$${\ Displaystyle (х, у) \ в К ^ {2} = (OE_ {1}) ^ {2}}$${\ displaystyle (\ beta ^ {- 1} (x), \ beta ^ {- 1} (y)) = (j, k) \ in \ {1,2, \ ldots n \} ^ {2}}$${\ displaystyle n-1}$

• ${\ displaystyle g_ {0, m}: \; y = \ beta (m) \; (1 \ leq m \ leq n)}$,
• ${\ displaystyle g_ {n, m}: \; T (O, y, x) = x = \ beta (m) \; (1 \ leq m \ leq n)}$ а также
• ${\ displaystyle g_ {i, m}: \; T (\ beta (i), y, x) = \ beta (m) \ Leftrightarrow (L_ {i}) _ {j, k} = m \ land \ beta (j) = x \ land \ beta (k) = y \; (1 \ leq m \ leq n, 1 \ leq i \ leq n-1).}$

Поскольку каждая конечная аффинная плоскость порядка имеет в проективную плоскость того же порядка, проективное замыкания и любой конечной проективной плоскости может быть прорези таким образом , что конечная аффинная плоскость того же порядка возникает, применимо следующее: ${\ displaystyle n}$

Для каждого существует проективная плоскость порядка тогда и только тогда, когда существуют попарно ортогональные латинские квадраты порядка .${\ Displaystyle п \ geq 2}$${\ displaystyle n}$${\ displaystyle n-1}$${\ displaystyle n}$

Если конструкция , описанная здесь, осуществляется с неполным списком MOLS, один получает структуру заболеваемости с точками на каждой прямой линии и наборов параллелей, то есть так называемой - сети . ${\ displaystyle m}$${\ displaystyle n}$${\ Displaystyle м + 2 <п + 1}$${\ Displaystyle (м + 2, п)}$

Построение ортогональных латинских квадратов из тройных тел

Является конечным тернарным полем , тогда для каждого из них через связь становится квазигруппой . При одинаковом расположении элементов для таблиц умножения латинские квадраты для двух таких связей всегда ортогональны друг другу с разными множителями . Тройное тело порядка всегда дает полный список попарно ортогональных латинских квадратов. ${\ Displaystyle (К, Т, 0,1)}$${\ displaystyle K}$${\ Displaystyle а \ ин К \ setminus \ {0 \}}$${\ Displaystyle х \ звезда _ {а} у = Т (а, у, х)}$${\ Displaystyle (К, \ звезда _ {а})}$${\ displaystyle K}$${\ displaystyle \ star _ {a}, \ star _ {b}}$${\ displaystyle a \ neq b; \, a, b \ in K \ setminus \ {0 \}}$${\ displaystyle n}$${\ displaystyle n-1}$

Примеры

Поле класса остатка является тернарным полем. Содержимое таблиц умножения для описанных выше квазигрупповых связей - поскольку существует тело, здесь применяется следующее : ${\ Displaystyle К = \ mathbb {Z} / 5 \ mathbb {Z}}$${\ displaystyle \ star _ {a}, a \ in \ {1,2,3,4 \}}$${\ displaystyle K}$${\ displaystyle x \ star _ {a} y = T (a, y, x) = x + a \ cdot y}$

${\ displaystyle \ left [{\ begin {array} {ccccc} 0 & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 0 \\ 2 & 3 & 4 & 0 & 1 \\ 3 & 4 & 0 & 1 & 2 \\ 4 & 0 & 1 & 2 & 3 \ end {array}} \ right], \ left [{\ begin {array} {ccccc} 0 & 2 & 4 & 1 & 3 \ \ 1 & 3 & 0 & 2 & 4 \\ 2 & 4 & 1 & 3 & 0 \\ 3 & 0 & 2 & 4 & 1 \\ 4 & 1 & 3 & 0 & 2 \ end {array}} \ right], \ left [{\ begin {array} {ccccc} 0 & 3 & 1 & 4 & 2 \\ 1 & 3 & 1 & 2 & 4 \ 3 \\ 1 & 3 & 4 \ 2 & 4 & 3 \ 3 & 3 & 4 \ 2 & 4 & 3 & 3 {массив}} \ right], \ left [{\ begin {array} {ccccc} 0 & 4 & 3 & 2 & 1 \\ 1 & 0 & 4 & 3 & 2 \\ 2 & 1 & 0 & 4 & 3 \\ 3 & 2 & 1 & 0 & 4 \\ 4 & 3 & 2 & 1 & 0 \ end {array}} \ right].}$

Для стандартной записи 0 нужно заменить на 5, тогда вы создали набор из 4 попарно ортогональных латинских квадратов. Аналогично, попарно ортогональные латинские квадраты всегда можно определить для каждой степени простого числа, используя соответствующие квазигрупповые связи в конечном поле . ${\ displaystyle p ^ {r}}$${\ displaystyle \ star _ {a}, a \ in \ mathbb {F} _ {p ^ {r}} \ setminus \ {0 \}}$ ${\ displaystyle \ mathbb {F} _ {p ^ {r}}}$${\ displaystyle p ^ {r} -1}$

Затем каждый из этих латинских квадратов описывает отношение инцидентности в одном из наборов параллелей аффинной плоскости, как показано в предыдущем разделе. ${\ displaystyle p ^ {r} +1}$${\ displaystyle \ mathbb {F} _ {p ^ {r}}}$

Математические головоломки

• Вопрос о том, можно ли частично заполненный квадрат будет завершен в латинский квадрат NP-полная задача на языке теории сложности .
• Латинский квадрат 9-го порядка с дополнительным условием, что при делении на девять квадратов в каждом из этих квадратов все символы появляются ровно один раз, приводит к головоломке с числами судоку .${\ displaystyle 3 \ times 3}$

Иллюстрации

Визиты политиков и компьютерщиков

4 политика хотят посетить 4 ученых-информатиков. Каждый политик посещает ровно одного ученого-компьютерщика каждые 4 дня. Каждый компьютерный ученый должен посетить ровно одного политика в каждый из 4 дней. По прошествии 4 дней каждый политик посетил каждого компьютерного ученого ровно один раз.

Эта последовательность может быть представлена ​​латинским квадратом 4-го порядка. Строки представляют политиков, столбцы представляют компьютерных ученых, а цвета представляют дни. Количество возможностей для групп посещений за 4 дня равно количеству латинских квадратов порядка 4 (последовательность A002860 в OEIS ) . Итак, существует 576 возможных созвездий.

Статистический план экспериментов

Агроном хочет выяснить, какая концентрация удобрений позволит максимально увеличить урожай. Для этого он делит свое поле на четыре по четыре отдельных участка. В каждой из областей 16 является одним из четырех концентраций удобрений , , или с б. Однако условия выращивания на 16 участках неоднородны. В -направлении градиент увеличивается, а в -направлении земля становится все глубже и глубже. Помимо концентрации удобрений, два фактора уклона и глубины также могут влиять на урожайность, что необходимо учитывать в плане испытаний. Если у вас есть два блочных фактора и один интересующий фактор, используйте латинский квадрат в качестве дизайна. Каждый из трех факторов имеет четыре уровня факторов, которые в R генерируют следующий экспериментальный план с функцией из пакета : ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$${\ displaystyle D}$${\ displaystyle DC = CB = BA> 0}$${\ displaystyle x}$${\ displaystyle y}$design.lsdagricolae

Классы эквивалентности латинских квадратов

Есть много различных преобразований, которые можно применить к латинскому квадрату для создания нового латинского квадрата:

1. Вы можете отразить квадрат (в матричной записи) на главной диагонали, т.е. транспонировать матричное представление,
2. вы можете переставлять строки и / или столбцы латинского квадрата,
3. можно однозначно переименовывать введенные цифровые символы,
4. вы можете читать квадрат «снизу вверх» или «справа налево» ...

Преобразования, упомянутые в пункте 4., являются частными случаями перестановок строк или столбцов.

Для применения важных и для подсчета возможных латинских квадратов фиксированного порядка, количества преобразований, описанных ниже, вводятся все латинские квадраты порядка по соответствующему Äquivalenklasseneinteilung на сумму (с символами из ). ${\ displaystyle n}$${\ Displaystyle \ {1,2, \ ldots, п \}}$

Парастрофия

Два латинских квадрата называются парастрофическими по отношению друг к другу, если они выходят один из другого в OAR как тройка путем перестановки , то есть если применимо следующее. Например, номер строки меняется на номер столбца и, таким образом, соответствует транспонированию на матричном дисплее. Каждый класс парастрофических латинских квадратов содержит 1, 2, 3 или 6 различных латинских квадратов, это следствие формулы орбиты . См. Также квазигруппу # Parastrophies . ${\ displaystyle Q_ {1}, Q_ {2}}$${\ displaystyle \ pi \ in S_ {3}}$${\ displaystyle (r, s, z) \ in Q_ {1} \ Leftrightarrow \ pi (r, s, z) \ in Q_ {2}}$${\ Displaystyle \ pi = (1,2) \ в S_ {3}}$

Изотопия

Два латинских квадрата называются изотопными друг другу, если они расходятся в результате комбинации перестановок строк и столбцов и взаимно однозначного переименования записей. Числа изотопных классов латинских квадратов порядка последовательности форм A040082 в OEIS . См. Также морфизмы # квазигруппы . ${\ displaystyle a_ {n}}$${\ displaystyle n}$

Основные классы

Если объединить парастрофию и изотопию отношений эквивалентности, получится новое разделение классов эквивалентности, разделение на так называемые основные классы . Два латинских квадрата принадлежат к одному и тому же основному классу, если они могут быть преобразованы друг в друга комбинацией парастрофических и изотопных операций. Каждый основной класс содержит 1, 2, 3 или 6 изотопных классов. Число основных классов латинских квадратов порядка последовательности форм A003090 в OEIS . ${\ displaystyle h_ {n}}$${\ displaystyle n}$

литература

Технические статьи по отдельным вопросам

• Чарльз Колборн : Сложность заполнения частичных латинских квадратов . В кн . : Дискретная прикладная математика . Лента 8 , 1984, стр. 25-30 , DOI : 10.1016 / 0166-218X (84) 90075-1 . 

Дизайн экспериментов и теория дизайна

• Юрген Борц: Статистика для ученых-гуманитариев и социологов . 6-е издание. Springer Medizin Verlag, Heidelberg 2005, ISBN 978-3-540-21271-3 . 
• Юрген Борц: Методы исследования и оценки для ученых-гуманитариев и социологов . 4-е издание. Springer Medizin Verlag, Heidelberg 2006, ISBN 978-3-540-33305-0 . 
• Джеффри Х. Диниц , Дуглас Роберт Стинсон: краткое введение в теорию дизайна . В: JH Dinitz и DR Stinson (Eds.): Contemporary Design Theory: A Collection of Surveys . John Wiley & Sons, Нью-Йорк 1992, ISBN 0-471-53141-3 , гл. 1 , стр. 1-12 . 
• Клаус Хинкельманн, Оскар Кемпторн: Дизайн и анализ набора экспериментов . 2-е издание. I и II. John Wiley & Sons, New York 2008, ISBN 978-0-470-38551-7 (английский язык, страница издателя о книге [доступ 28 февраля 2012 г.]). 

Комбинаторика и дискретная математика

• Якобус Хендрикус ван Линт , Р. М. Уилсон: Курс комбинаторики . 2-е издание. Издательство Кембриджского университета, Кембридж 2001, ISBN 0-521-80340-3 . 
• Иржи Матушек, Ярослав Нешетржил: Дискретная математика . Путешествие открытий. Springer, Берлин / Гейдельберг / Нью-Йорк / ... 2002, ISBN 3-540-42386-9 , стр. 157 ff . ( Онлайн - английский: приглашение к дискретной математике . Перевод Ханса Мильке, учебник, требующий небольших предварительных знаний - математика для продвинутых классов до 2 семестра изучения математики). 

программирование

• Дональд Э. Кнут : Том 4A: Комбинаторные алгоритмы, часть 1 . В кн . : Искусство программирования . 1-е издание. Аддисон-Уэсли, Ридинг, Массачусетс 2011, ISBN 0-201-03804-8 , стр. XV и 883 ff . (Английский, обзор полного собрания сочинений [доступ 28 февраля 2012 г.]). 

веб ссылки

• Эрик В. Вайсштейн : Латинский квадрат . В: MathWorld (английский).
• В.М. Михеев (составитель): Латинский квадрат . В: Michiel Hazewinkel (Ed.): Encyclopedia of Mathematics . Springer-Verlag и EMS Press, Берлин 2002, ISBN 978-1-55608-010-4 (английский, онлайн ). Шаблон: EoM / id
• В.М. Михеев (составитель): Ортогональные латинские квадраты . В: Michiel Hazewinkel (Ed.): Encyclopedia of Mathematics . Springer-Verlag и EMS Press, Берлин 2002, ISBN 978-1-55608-010-4 (английский, онлайн ). Шаблон: EoM / id
• Ларс Девлинг Андерсен: История латинских площадей. (PDF; 1,2 МБ) препринт. В кн . : История комбинаторики. Робин Дж. Уилсон, декабрь 2007 г., по состоянию на 28 февраля 2012 г. (История латинских квадратов). 
• Ганс Петер Граматке: Квадраты Эйлера. Отступление. В кн .: Математико-техническая-алгоритмически-лингвистическая конгломерация Ганса Петерса. 2 апреля 2003 г., доступ 28 февраля 2012 г. (приватная страница с интересными и забавными фактами о латинских и магических квадратах и ​​некоторых вариантах). 
• Аале де Винкель: Волшебная энциклопедия. 8 января 2001 г., получено 28 февраля 2012 г. (программы электронных таблиц ( Microsoft Excel ) для создания магических и латинских квадратов). 

Отдельные ссылки и комментарии

1. ↑ Хинкельманн и Кемпторн (2008)
2. ^ Латинский квадрат. В: Полевое руководство по экспериментальному дизайну. Университет штата Вашингтон, фруктовых деревьев и научно - исследовательский центр Extension, 16 августа 2000, доступ к 28 февраля 2012 . 
3. ↑ Сумма устанавливает «бит» с валентностью в n- значном двоичном числе для каждого числа, которое появляется в строке или столбце . Чтобы проверяемая матрица с уверенностью представляла латинский квадрат, необходимо выполнить дополнительное требование, чтобы все записи были натуральными числами. Сам тест не гарантирует этого. (Кнут, 2011).${\ displaystyle I}$${\ displaystyle 2 ^ {l-1}}$
4. ^ Линт и Уилсон
5. ↑ ^{a b c d e} Matoušek & Nešetřil, 8.3 Ортогональные латинские квадраты .
6. ↑ Такое использование атрибута "ортогональный" не имеет ничего общего с английским термином "представление ортогонального массива", объясненным в статье!
7. ↑ Формально более корректно, но менее ясно, элементы матрицы S должны быть записаны как пары чисел.
8. ↑ Дж. Ден, А. Д. Кидвелл: Латинские квадраты и их приложения . Акад. Пресса, 1974 г.
9. ↑ Есть , матрица не принадлежит ни одному нетривиальному списку MOLS.${\ Displaystyle R (2) = 1}$${\ displaystyle A}$
10. ↑ MathWorld: Cyclic Group C_8 Циклическая группа C ₅ не включена, но, например , C ₈ .
11. ↑ Колборн (1984).
12. ↑ Claupein, Link, Mayus: Создание и реализация полевых испытаний. (PDF) Университет Hohenheim, 2 апреля 2007 г., в архиве с оригинала на 23 февраля 2017 года ; Доступ к 22 февраля 2017 года . 
13. ↑ Фелипе де Мендибуру: Agricolae: Статистические процедуры для сельскохозяйственных исследований. 12 июня, 2016. Проверено 22 февраля, 2017 . 
14. ↑ Формально: Группа перестановок действует на множестве всех троек от натуральных чисел до n . ВЕСЛО оригинального латинского квадрата отображается на весло латинского квадрата, которое также может совпадать с начальным квадратом.${\ displaystyle S_ {3}}$ ${\ Displaystyle \ {1,2, \ ldots п \} ^ {3}}$