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

Квадратный массив с символами, которые встречаются один раз в строке и столбце.

Витражное окно в колледже Гонвилля и Кая в Кембридже, изображающее латинский квадрат 7 × 7, было посвящено Рональду Фишеру , чей «Дизайн экспериментов» обсуждал латинские квадраты. Окно сэра Рональда Фишера было удалено в 2020 году из-за связи Фишера с евгеникой. ^[1]

В комбинаторике и экспериментальном проектировании латинский квадрат — это  массив n  ×  n , заполненный  n различными символами, каждый из которых встречается ровно один раз в каждой строке и ровно один раз в каждом столбце. Примером латинского квадрата 3×3 является

Название «латинский квадрат» возникло под влиянием математических работ Леонарда Эйлера (1707–1783), который использовал в качестве символов латинские буквы ^[2], но можно использовать любой набор символов: в приведенном выше примере буквенную последовательность A, B, C можно заменить целочисленной последовательностью 1 , 2, 3. Эйлер положил начало общей теории латинских квадратов.

История

Корейский математик Чхве Сок-Джон был первым, кто опубликовал пример латинских квадратов девятого порядка, чтобы построить магический квадрат в 1700 году, опередив Леонарда Эйлера на 67 лет. ^[3]

Сокращенная форма

Латинский квадрат называется редуцированным ( также нормализованным или приведенным в стандартную форму ), если и его первая строка, и его первый столбец находятся в естественном порядке. ^[4] Например, латинский квадрат выше не является редуцированным, потому что его первый столбец — это A, C, B, а не A, B, C.

Любой латинский квадрат можно сократить, переставив (то есть, переупорядочив) строки и столбцы. Здесь перестановка второй и третьей строк матрицы выше дает следующий квадрат:

Этот латинский квадрат является сокращенным; его первая строка и первый столбец расположены в алфавитном порядке A, B, C.

Характеристики

Представление ортогонального массива

Если каждый элемент латинского квадрата n × n записать в виде тройки ( r , c , s ), где r — строка, c — столбец, а s — символ, то мы получим набор из n ² троек, называемый ортогональным представлением массива квадрата. Например, ортогональное представление массива латинского квадрата

является

{ (1, 1, 1), (1, 2, 2), (1, 3, 3), (2, 1, 2), (2, 2, 3), (2, 3, 1), ( 3, 1, 3), (3, 2, 1), (3, 3, 2) },

где, например, тройка (2, 3, 1) означает, что в строке 2 и столбце 3 находится символ 1. Ортогональные массивы обычно записываются в виде массива, где тройки являются строками, например:

Определение латинского квадрата можно записать в терминах ортогональных массивов:

• Латинский квадрат — это набор из n2 троек ( r , c , s ), где 1 ≤ r , ^c , s ≤ n , такой, что все упорядоченные пары ( r , c ) различны, все упорядоченные пары ( r , s ) различны и все упорядоченные пары ( c , s ) различны.

Это означает, что n ² упорядоченных пар ( r , c ) — это все пары ( i , j ) с 1 ≤ i , j ≤ n , по одному разу каждая. То же самое верно для упорядоченных пар ( r , s ) и упорядоченных пар ( c , s ).

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

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

Многие операции с латинским квадратом приводят к получению другого латинского квадрата (например, переворачивание его вверх дном).

Если мы переставим строки, переставим столбцы или переставим названия символов латинского квадрата, мы получим новый латинский квадрат, который называется изотопным первому. Изотопизм — это отношение эквивалентности , поэтому множество всех латинских квадратов делится на подмножества, называемые классами изотопии , так что два квадрата в одном классе изотопны, а два квадрата в разных классах не изотопны.

Другой тип операции проще всего объяснить, используя представление латинского квадрата в виде ортогонального массива. Если мы систематически и последовательно переупорядочиваем три элемента в каждой тройке (то есть переставляем три столбца в форме массива), то получаем другой ортогональный массив (и, таким образом, другой латинский квадрат). Например, мы можем заменить каждую тройку ( r , c , s ) на ( c , r , s ), что соответствует транспонированию квадрата (отражая его главную диагональ), или мы могли бы заменить каждую тройку ( r , c , s ) на ( c , s , r ), что является более сложной операцией. Всего есть 6 возможностей, включая «ничего не делать», что дает нам 6 латинских квадратов, называемых конъюгатами (также парастрофами ) исходного квадрата. ^[5]

Наконец, мы можем объединить эти две операции эквивалентности: два латинских квадрата называются паратопическими , а также изотопными основного класса , если один из них изотопен сопряженному другому. Это снова отношение эквивалентности, с классами эквивалентности, называемыми основными классами , видами или классами паратопии . ^[5] Каждый основной класс содержит до шести изотопических классов.

Количествоп × платинские квадраты

Не существует известной легко вычисляемой формулы для числа L _n латинских квадратов n × n с символами 1, 2, ..., n . Наиболее точные верхние и нижние границы, известные для больших n, далеки друг от друга. Один классический результат ^[6] заключается в том, что $${\displaystyle \prod _{k=1}^{n}\left(k!\right)^{n/k}\geq L_{n}\geq {\frac {\left(n!\right)^{2n}}{n^{n^{2}}}}.}$$

Простая и явная формула для числа латинских квадратов была опубликована в 1992 году, но ее все еще нелегко вычислить из-за экспоненциального роста числа членов. Эта формула для числа L _n латинских квадратов n × n имеет вид где B _n — множество всех n × n {0, 1}-матриц, σ ₀ ( A ) — число нулевых элементов в матрице A , а per( A ) — перманент матрицы A . ^[7] $${\displaystyle L_{n}=n!\sum _{A\in B_{n}}^{}(-1)^{\sigma _{0}(A)}{\binom {\operatorname {per} A}{n}},}$$

Таблица ниже содержит все известные точные значения. Видно, что числа растут чрезвычайно быстро. Для каждого n общее количество латинских квадратов (последовательность A002860 в OEIS ) равно n ! ( n − 1)! раз больше количества сокращенных латинских квадратов (последовательность A000315 в OEIS ).

Для каждого n каждый класс изотопии (последовательность A040082 в OEIS ) содержит до ( n !) ³ латинских квадратов (точное число варьируется), в то время как каждый основной класс (последовательность A003090 в OEIS ) содержит 1, 2, 3 или 6 классов изотопии.

Число структурно различных латинских квадратов (т.е. квадраты не могут быть сделаны идентичными посредством вращения, отражения и/или перестановки символов) для n = 1 до 7 составляет 1, 1, 1, 12, 192, 145164, 1524901344 соответственно (последовательность A264603 в OEIS ).

Примеры

Приведем по одному примеру латинского квадрата из каждого основного класса до пятого порядка.

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

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

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

Они представляют собой таблицы умножения следующих групп:

• {0} – тривиальная 1-элементная группа
• ${\displaystyle \mathbb {Z} _{2}}$– бинарная группа
• ${\displaystyle \mathbb {Z} _{3}}$– циклическая группа порядка 3
• ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}}$– четверная группа Клейна
• ${\displaystyle \mathbb {Z} _{4}}$– циклическая группа порядка 4
• ${\displaystyle \mathbb {Z} _{5}}$– циклическая группа порядка 5
• последний пример — квазигруппа , или, скорее, цикл , который не является ассоциативным.

Трансверсали и радужные соответствия

Трансверсаль в латинском квадрате — это выбор из n ячеек, где каждая строка содержит одну ячейку, каждый столбец содержит одну ячейку и есть одна ячейка, содержащая каждый символ.

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

Поэтому многие результаты по латинским квадратам/прямоугольникам содержатся в статьях, в названии которых содержится термин «радужное соответствие», и наоборот. ^[8]

Некоторые латинские квадраты не имеют трансверсали. Например, когда n четно, латинский квадрат n на n , в котором значение ячейки i , j равно ( i + j ) mod n, не имеет трансверсали. Вот два примера: В 1967 году Х. Дж. Райзер предположил, что когда n нечетно , каждый латинский квадрат n на n имеет трансверсаль. ^[9] $${\displaystyle {\begin{bmatrix}1&2\\2&1\end{bmatrix}}\quad {\begin{bmatrix}1&2&3&4\\2&3&4&1\\3&4&1&2\\4&1&2&3\end{bmatrix}}}$$

В 1975 году С. К. Штейн и Бруальди предположили, что при четном n каждый латинский квадрат n на n имеет частичную трансверсаль размера n −1. ^[10]

Более общая гипотеза Штейна заключается в том, что трансверсаль размера n −1 существует не только в латинских квадратах, но и в любом массиве nxn из n символов, при условии, что каждый символ появляется ровно n раз. ^[9]

Были доказаны некоторые более слабые версии этих гипотез:

• Каждый латинский квадрат n на n имеет частичную трансверсаль размера 2 n /3. ^[11]
• Каждый латинский квадрат n на n имеет частичную трансверсаль размера n − sqrt( n ). ^[12]
• Каждый латинский квадрат n на n имеет частичную трансверсаль размера n − 11 log²
  ₂( сущ. ). ^[13]
• Каждый латинский квадрат n на n имеет частичную трансверсаль размера n − O(log n/loglog n). ^[14]
• Каждый достаточно большой латинский квадрат nxn имеет частичную трансверсаль размера n −1. ^[15] (Препринт)

Алгоритмы

Для маленьких квадратов можно генерировать перестановки и проверять, выполняется ли свойство латинского квадрата. Для больших квадратов алгоритм Якобсона и Мэтьюза позволяет производить выборку из равномерного распределения по пространству n  ×  n латинских квадратов. ^[16]

Приложения

Статистика и математика

• В планировании экспериментов латинские квадраты являются частным случаем строчно-столбцовых планов для двух блокирующих факторов . ^{[17] [18]}
• В алгебре латинские квадраты связаны с обобщениями групп ; в частности, латинские квадраты характеризуются как таблицы умножения ( таблицы Кэли ) квазигрупп . Говорят, что бинарная операция, таблица значений которой образует латинский квадрат, подчиняется свойству латинского квадрата .

Коды исправления ошибок

Наборы латинских квадратов, которые ортогональны друг другу, нашли применение в качестве кодов исправления ошибок в ситуациях, когда связь нарушается большим количеством типов шума, чем простой белый шум , например, при попытке передачи широкополосного Интернета по линиям электропередач. ^{[19] [20] [21]}

Во-первых, сообщение отправляется с использованием нескольких частот или каналов, распространенный метод, который делает сигнал менее уязвимым к шуму на любой конкретной частоте. Буква в отправляемом сообщении кодируется путем отправки серии сигналов на разных частотах в последовательные интервалы времени. В примере ниже буквы от A до L кодируются путем отправки сигналов на четырех разных частотах в четырех временных интервалах. Буква C, например, кодируется путем первой отправки на частоте 3, затем 4, 1 и 2.

$${\displaystyle {\begin{matrix}A\\B\\C\\D\\\end{matrix}}{\begin{bmatrix}1&2&3&4\\2&1&4&3\\3&4&1&2\\4&3&2&1\\\end{bmatrix}}\quad {\begin{matrix}E\\F\\G\\H\\\end{matrix}}{\begin{bmatrix}1&3&4&2\\2&4&3&1\\3&1&2&4\\4&2&1&3\\\end{bmatrix}}\quad {\begin{matrix}I\\J\\K\\L\\\end{matrix}}{\begin{bmatrix}1&4&2&3\\2&3&1&4\\3&2&4&1\\4&1&3&2\\\end{bmatrix}}}$$

Кодировка двенадцати букв образована тремя латинскими квадратами, которые ортогональны друг другу. Теперь представьте, что в каналах 1 и 2 во время всей передачи есть дополнительный шум. Буква A тогда будет восприниматься как: $${\displaystyle {\begin{matrix}12&12&123&124\end{matrix}}}$$

Другими словами, в первом слоте мы получаем сигналы как с частоты 1, так и с частоты 2; в то время как третий слот имеет сигналы с частот 1, 2 и 3. Из-за шума мы больше не можем сказать, были ли первые два слота 1,1 или 1,2 или 2,1 или 2,2. Но случай 1,2 является единственным, который дает последовательность, соответствующую букве в приведенной выше таблице, букве A. Аналогично, мы можем представить себе всплеск статики по всем частотам в третьем слоте: $${\displaystyle {\begin{matrix}1&2&1234&4\end{matrix}}}$$

Опять же, из таблицы кодировок мы можем сделать вывод, что передавалась буква A. Количество ошибок, которые может обнаружить этот код, на единицу меньше количества временных интервалов. Также было доказано, что если количество частот является простым числом или степенью простого числа, то ортогональные латинские квадраты создают коды обнаружения ошибок, которые являются максимально эффективными.

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

Построение магического квадрата дня рождения Рамануджана из латинского квадрата 4×4 с отдельными диагоналями и значениями дня (D), месяца (M), столетия (C) и года (Y), а также пример дня рождения Рамануджана

Задача определения того, можно ли дополнить частично заполненный квадрат, чтобы сформировать латинский квадрат, является NP-полной . ^[22]

Популярные головоломки судоку являются частным случаем латинских квадратов; любое решение головоломки судоку является латинским квадратом. Судоку накладывает дополнительное ограничение, что девять конкретных 3×3 смежных подквадратов также должны содержать цифры 1–9 (в стандартной версии). См. также Математика судоку .

Более поздние головоломки KenKen и Strimko также являются примерами латинских квадратов.

Настольные игры

Латинские квадраты послужили основой для нескольких настольных игр, в частности, популярной абстрактной стратегической игры «Камисадо» .

Агрономические исследования

Латинские квадраты используются при планировании агрономических исследовательских экспериментов для минимизации экспериментальных ошибок. ^[23]

Геральдика

Латинский квадрат также фигурирует в гербе Статистического общества Канады , ^[24] будучи специально упомянутым в его блазоне . Также он появляется в логотипе Международного биометрического общества . ^[25]

Обобщения

Латинский куб четвертого порядка взорвался

• Латинский прямоугольник — это обобщение латинского квадрата, в котором есть n столбцов и n возможных значений, но количество строк может быть меньше n . Каждое значение по-прежнему появляется не более одного раза в каждой строке и столбце.
• Греко -латинский квадрат — это пара из двух латинских квадратов, при наложении которых одна на другую каждая упорядоченная пара символов появляется ровно один раз.
• Латинский гиперкуб — ​​это обобщение латинского квадрата с двух измерений на много измерений.

Смотрите также

• Блочная конструкция
• Комбинаторный дизайн
• Головоломка «Восемь королев»
• Футошики
• Магический квадрат
• Задачи на латинские квадраты
• Граф ладьи , граф, раскрашенный в латинские квадраты .
• Площадь Сатор
• Ведический квадрат
• Слово квадратное

Примечания

1. Басби, Матта (27 июня 2020 г.). «Кембриджский колледж уберет окно, посвященное евгенисту». The Guardian . Получено 28 июня 2020 г.
2. Уоллис, У. Д.; Джордж, Дж. К. (2011), Введение в комбинаторику, CRC Press, стр. 212, ISBN 978-1-4398-0623-4
3. Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2 ноября 2006 г.). Справочник комбинаторных конструкций (2-е изд.). CRC Press. стр. 12. ISBN 9781420010541. Получено 28 марта 2017 г.
4. Денес и Кидуэлл 1974, с. 128
5. Dénes & Keedwell 1974, с. 126
6. ван Линт и Уилсон 1992, стр. 161-162.
7. Цзя-юй Шао; Вань-ди Вэй (1992). «Формула для числа латинских квадратов». Дискретная математика . 110 (1–3): 293–296. doi : 10.1016/0012-365x(92)90722-r .
8. Gyarfas, Andras; Sarkozy, Gabor N. (2012). «Радужные соответствия и частичные трансверсали латинских квадратов». arXiv : 1208.5670 [CO math. CO].
9. Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (04 января 2017 г.). «О догадке Штейна». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211. дои : 10.1007/s12188-016-0160-3. ISSN  0025-5858. S2CID  119139740.
10. Стайн, Шерман (1975-08-01). «Трансверсали латинских квадратов и их обобщения». Pacific Journal of Mathematics . 59 (2): 567–575. doi : 10.2140/pjm.1975.59.567 . ISSN  0030-8730.
11. Коксма, Клаас К. (1969-07-01). «Нижняя граница порядка частичной трансверсали в латинском квадрате». Журнал комбинаторной теории . 7 (1): 94–95. doi : 10.1016/s0021-9800(69)80009-8 . ISSN  0021-9800.
12. Вулбрайт, Дэвид Э. (1978-03-01). «Латинский квадрат n × n имеет трансверсаль с по крайней мере n−n различными символами». Журнал комбинаторной теории, Серия A. 24 ( 2): 235–237. doi : 10.1016/0097-3165(78)90009-2 . ISSN  0097-3165.
13. Хатами, Пуйя; Шор, Питер В. (2008-10-01). «Нижняя граница длины частичной трансверсали в латинском квадрате». Журнал комбинаторной теории, Серия A. 115 ( 7): 1103–1113. doi : 10.1016/j.jcta.2008.01.002 . ISSN  0097-3165.
14. Киваш, Питер; Покровский, Алексей; Судаков, Бенни; Епремян, Лиана (2022-04-15). «Новые границы для гипотезы Райзера и связанные с ней проблемы». Труды Американского математического общества, серия B. 9 ( 8): 288–321. doi : 10.1090/btran/92 . hdl : 20.500.11850/592212 . ISSN  2330-0000.
15. Монтгомери, Ричард (2023). «Доказательство гипотезы Райзера-Бруальди-Стейна для больших четных n». arXiv : 2310.19779 [math.CO].
16. Якобсон, М. Т.; Мэтьюз, П. (1996). «Создание равномерно распределенных случайных латинских квадратов». Журнал комбинаторных разработок . 4 (6): 405–437. doi :10.1002/(sici)1520-6610(1996)4:6<405::aid-jcd3>3.0.co;2-j.
17. Бейли, РА (2008), «6 конструкций строк и столбцов и еще 9 о латинских квадратах», Design of Comparative Experiments , Cambridge University Press, ISBN 978-0-521-68357-9, г-н  2422352
18. Шах, Кирти Р.; Синха, Бикас К. (1989), «4-строчные-столбцовые планы», Теория оптимальных планов , Конспект лекций по статистике, т. 54, Springer-Verlag, стр. 66–84, ISBN 0-387-96991-8, МР  1016151
19. Colbourn, CJ ; Kløve, T.; Ling, ACH (2004). «Массивы перестановок для связи по линиям электропередач». IEEE Trans. Inf. Theory . 50 : 1289–1291. doi :10.1109/tit.2004.828150. S2CID  15920471.
20. Революция Эйлера , New Scientist, 24 марта 2007 г., стр. 48–51.
21. Хучинска, Софи (2006). «Связь по линиям электропередач и проблема 36 офицеров». Philosophical Transactions of the Royal Society A. 364 ( 1849): 3199–3214. Bibcode : 2006RSPTA.364.3199H. doi : 10.1098/rsta.2006.1885. PMID  17090455. S2CID  17662664.
22. C. Colbourn (1984). «Сложность завершения частичных латинских квадратов». Дискретная прикладная математика . 8 : 25–30. doi : 10.1016/0166-218X(84)90075-1 .
23. Применение латинского квадрата в агрономических исследованиях
24. "Патентные письма о предоставлении оружия SSC". ssc.ca. Архивировано из оригинала 21.05.2013.
25. Международное биометрическое общество. Архивировано 07.05.2005 на Wayback Machine.

Ссылки

• Бейли, РА (2008). "6 конструкций строк-столбцов и еще 9 о латинских квадратах". Дизайн сравнительных экспериментов . Cambridge University Press. ISBN 978-0-521-68357-9. МР  2422352.
• Dénes, J.; Keedwell, AD (1974). Латинские квадраты и их приложения . Нью-Йорк-Лондон: Academic Press. стр. 547. ISBN 0-12-209350-X. МР  0351850.
• Шах, Кирти Р.; Синха, Бикас К. (1989). "4-строчные-столбцовые планы". Теория оптимальных планов . Конспект лекций по статистике. Том 54. Springer-Verlag. С. 66–84. ISBN 0-387-96991-8. МР  1016151.
• ван Линт, Дж. Х.; Уилсон, Р. М. (1992). Курс комбинаторики . Cambridge University Press. стр. 157. ISBN 0-521-42260-4.

Дальнейшее чтение

• Dénes, JH; Keedwell, AD (1991). Латинские квадраты: Новые разработки в теории и приложениях . Annals of Discrete Mathematics. Том 46. Paul Erdős (предисловие). Amsterdam: Academic Press. ISBN 0-444-88899-3. МР  1096296.
• Хинкельманн, Клаус; Кемпторн, Оскар (2008). Планирование и анализ экспериментов. Том I, II (Второе издание). Wiley. ISBN 978-0-470-38551-7. МР  2363107.
  • Хинкельманн, Клаус; Кемпторн, Оскар (2008). Планирование и анализ экспериментов, том I: Введение в экспериментальное проектирование (второе издание). Wiley. ISBN 978-0-471-72756-9. МР  2363107.
  • Хинкельманн, Клаус; Кемпторн, Оскар (2005). Планирование и анализ экспериментов, том 2: Расширенный экспериментальный план (первое издание). Wiley. ISBN 978-0-471-55177-5. МР  2129060.
• Кнут, Дональд (2011). Искусство программирования, том 4А: Комбинаторные алгоритмы, часть 1. Рединг, Массачусетс: Addison-Wesley. ISBN 978-0-201-03804-0.
• Laywine, Charles F.; Mullen, Gary L. (1998). Дискретная математика с использованием латинских квадратов . Wiley-Interscience Series in Discrete Mathematics and Optimization. Нью-Йорк: John Wiley & Sons, Inc. ISBN 0-471-24064-8. МР  1644242.
• Шах, К. Р.; Синха, Бикас К. (1996). «Строчно-столбцовые конструкции». В S. Ghosh и CR Rao (ред.). Планирование и анализ экспериментов . Справочник по статистике. Том 13. Амстердам: North-Holland Publishing Co., стр. 903–937. ISBN 0-444-82061-2. МР  1492586.
• Рагхаварао, Дамараджу (1988). Конструкции и комбинаторные проблемы в планировании экспериментов (исправленное переиздание издания Wiley 1971 г.). Нью-Йорк: Довер. ISBN 0-486-65685-3. МР  1102899.
• Стрит, Энн Пенфолд ; Стрит, Дебора Дж. (1987). Комбинаторика экспериментального проектирования . Нью-Йорк: Oxford University Press. ISBN 0-19-853256-3. МР  0908490.
• Бергер, Пол Д.; Маурер, Роберт Э.; Челли, Джована Б. (28 ноября 2017 г.). Экспериментальное проектирование с применением в менеджменте, инжиниринге и науках (2-е издание (ред. 28 ноября 2017 г.)). Springer. стр. 267–282.

Внешние ссылки

• Вайсштейн, Эрик В. «Латинский квадрат». MathWorld .
• Латинские квадраты в энциклопедии математики
• Латинские квадраты в онлайн-энциклопедии целочисленных последовательностей