Латинская площадь

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

Этот витраж в колледже Гонвилл и Кайус в Кембридже, изображающий латинский квадрат 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. Ортогональные массивы обычно записываются в форме массива, где тройки являются строками, например:

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

• Латинский квадрат — это набор из n ² троек ( 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 ) by ( c , s , r ), что является более сложной операцией. Всего существует 6 возможностей, включая «ничего не делать», что дает нам 6 латинских квадратов, называемых сопряженными (также парастрофами ) исходного квадрата. ^[5]

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

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

Неизвестна легко вычислимая формула для количества 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 имеет вид

$${\displaystyle L_{n}=n!\sum _{A\in B_{n}}^{}(-1)^{\sigma _{0}(A)}{\binom {\operatorname {per} A}{n}},}$$

B _nn × nσ ₀ ( A )Aper( A )перманентA. ^[7]

В таблице ниже приведены все известные точные значения. Видно, что цифры растут чрезвычайно быстро. Для каждого n общее количество латинских квадратов (последовательность A002860 в OEIS ) равно 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, не имеет трансверсали. Вот два примера:

$${\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}}}$$

ВХ. Дж. Райзерnnn^[9]

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

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

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

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

Алгоритмы

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

Приложения

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

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

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

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

Во-первых, сообщение отправляется с использованием нескольких частот или каналов — распространенный метод, который делает сигнал менее уязвимым к шуму на любой конкретной частоте. Буква в отправляемом сообщении кодируется путем отправки серии сигналов на разных частотах через последовательные промежутки времени. В приведенном ниже примере буквы от A до L кодируются путем отправки сигналов на четырех разных частотах в четырех временных интервалах. Например, буква С кодируется путем отправки сначала на частоте 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 добавляется шум. Тогда буква А будет восприниматься как:

$${\displaystyle {\begin{matrix}12&12&123&124\end{matrix}}}$$

Другими словами, в первом слоте мы принимаем сигналы как с частоты 1, так и с частоты 2; в то время как третий слот имеет сигналы с частотами 1, 2 и 3. Из-за шума мы больше не можем сказать, были ли первые два слота 1,1 или 1,2, 2,1 или 2,2. Но случай 1,2 — единственный, который дает последовательность, соответствующую букве А в приведенной выше таблице. Аналогичным образом мы можем представить всплеск помех на всех частотах в третьем слоте:

$${\displaystyle {\begin{matrix}1&2&1234&4\end{matrix}}}$$

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

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

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

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

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

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

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

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

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

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

геральдика

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

Обобщения

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

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

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

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

Примечания

1. Басби, Матта (27 июня 2020 г.). «Кембриджский колледж уберет окно в память о евгенике» . Хранитель . Проверено 28 июня 2020 г.
2. Уоллис, WD; Джордж, Дж.К. (2011), Введение в комбинаторику, CRC Press, стр. 212, ISBN 978-1-4398-0623-4
3. Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2 ноября 2006 г.). Справочник по комбинаторным планам (2-е изд.). ЦРК Пресс. п. 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. дои : 10.1016/0012-365x(92)90722-r .
8. Дьярфас, Андрас; Саркози, Габор Н. (2012). «Радужные паросочетания и частичные трансверсали латинских квадратов». arXiv : 1208.5670 [CO math. СО].
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. Штейн, Шерман (1 августа 1975 г.). «Трансверсали латинских квадратов и их обобщения». Тихоокеанский математический журнал . 59 (2): 567–575. дои : 10.2140/pjm.1975.59.567 . ISSN  0030-8730.
11. Коксма, Клаас К. (1 июля 1969). «Нижняя оценка порядка частичной трансверсали в латинском квадрате». Журнал комбинаторной теории . 7 (1): 94–95. дои : 10.1016/s0021-9800(69)80009-8 . ISSN  0021-9800.
12. Вулбрайт, Дэвид Э (1 марта 1978). «Латинский квадрат размера n × n имеет трансверсаль, содержащую как минимум n−n различных символов». Журнал комбинаторной теории, серия А. 24 (2): 235–237. дои : 10.1016/0097-3165(78)90009-2 . ISSN  0097-3165.
13. Хатами, Пуя; Шор, Питер В. (1 октября 2008 г.). «Нижняя оценка длины частичной трансверсали в латинском квадрате». Журнал комбинаторной теории, серия А. 115 (7): 1103–1113. дои : 10.1016/j.jcta.2008.01.002 . ISSN  0097-3165.
14. Киваш, Питер; Покровский, Алексей; Судаков, Бенни; Епремян, Лиана (15.04.2022). «Новые границы гипотезы Райзера и связанных с ней проблем». Труды Американского математического общества, серия B. 9 (8): 288–321. дои : 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 о латинских квадратах», Дизайн сравнительных экспериментов , Cambridge University Press, ISBN 978-0-521-68357-9, МР  2422352
18. Шах, Кирти Р.; Синха, Бикас К. (1989), «Схемы с 4 строками и столбцами», Теория оптимальных планов , Конспекты лекций по статистике, том. 54, Springer-Verlag, стр. 66–84, ISBN. 0-387-96991-8, МР  1016151 {{citation}}: Внешняя ссылка |series=( помощь )
19. Колборн, CJ ; Клёве, Т.; Линг, ACH (2004). «Массивы перестановок для связи по линиям электропередачи». IEEE Транс. Инф. Теория . 50 : 1289–1291. дои : 10.1109/tit.2004.828150. S2CID  15920471.
20. Революция Эйлера , New Scientist, 24 марта 2007 г., стр. 48–51.
21. Гучинская, Софи (2006). «ЛЭП и проблема 36 офицеров». Философские труды Королевского общества А. 364 (1849): 3199–3214. Бибкод : 2006RSPTA.364.3199H. дои : 10.1098/rsta.2006.1885. PMID  17090455. S2CID  17662664.
22. К. Колборн (1984). «Сложность заполнения частичных латинских квадратов». Дискретная прикладная математика . 8 : 25–30. дои : 10.1016/0166-218X(84)90075-1 .
23. Применение латинского квадрата в агрономических исследованиях.
24. "Патентные письма, подтверждающие оружие SSC" . ssc.ca. _ Архивировано из оригинала 21 мая 2013 г.
25. Международное биометрическое общество. Архивировано 7 мая 2005 г. в Wayback Machine.

Рекомендации

• Бейли, РА (2008). «6 конструкций строк и столбцов и еще 9 о латинских квадратах». План сравнительных экспериментов . Издательство Кембриджского университета. ISBN 978-0-521-68357-9. МР  2422352.
• Денес, Ж.; Кидуэлл, AD (1974). Латинские квадраты и их приложения . Нью-Йорк-Лондон: Академическая пресса. п. 547. ИСБН 0-12-209350-Х. МР  0351850.
• Шах, Кирти Р.; Синха, Бикас К. (1989). «Конструкции из 4 строк и столбцов». Теория оптимальных планов . Конспект лекций по статистике. Том. 54. Шпрингер-Верлаг. стр. 66–84. ISBN 0-387-96991-8. МР  1016151.
• ван Линт, Дж. Х.; Уилсон, Р.М. (1992). Курс комбинаторики . Издательство Кембриджского университета. п. 157. ИСБН 0-521-42260-4.

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

• Денес, Дж. Х.; Кидуэлл, AD (1991). Латинские квадраты: Новые достижения в теории и приложениях . Анналы дискретной математики. Том. 46. ​​Пол Эрдеш (предисловие). Амстердам: Академическая пресса. ISBN 0-444-88899-3. МР  1096296.
• Хинкельманн, Клаус; Кемпторн, Оскар (2008). Планирование и анализ экспериментов. Том. I, II (Второе изд.). Уайли. ISBN 978-0-470-38551-7. МР  2363107.
  • Хинкельманн, Клаус; Кемпторн, Оскар (2008). Планирование и анализ экспериментов, Том I: Введение в планирование экспериментов (второе изд.). Уайли. ISBN 978-0-471-72756-9. МР  2363107.
  • Хинкельманн, Клаус; Кемпторн, Оскар (2005). Планирование и анализ экспериментов, Том 2: Расширенный план экспериментов (Первое изд.). Уайли. ISBN 978-0-471-55177-5. МР  2129060.
• Кнут, Дональд (2011). Искусство компьютерного программирования, Том 4А: Комбинаторные алгоритмы, Часть 1 . Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 978-0-201-03804-0.
• Лейвин, Чарльз Ф.; Маллен, Гэри Л. (1998). Дискретная математика с использованием латинских квадратов . Серия Wiley-Interscience по дискретной математике и оптимизации. Нью-Йорк: ISBN John Wiley & Sons, Inc. 0-471-24064-8. МР  1644242.
• Шах, КР; Синха, Бикас К. (1996). «Конструкции строк-столбцов». В С. Гоше и Ч.Р. Рао (ред.). Планирование и анализ экспериментов . Справочник по статистике. Том. 13. Амстердам: Издательство North-Holland Publishing Co., стр. 903–937. ISBN 0-444-82061-2. МР  1492586.
• Рагхаварао, Дамараджу (1988). Конструкции и комбинаторные проблемы планирования экспериментов (исправленное переиздание издания Wiley 1971 года). Нью-Йорк: Дувр. ISBN 0-486-65685-3. МР  1102899.
• Стрит, Энн Пенфолд ; Стрит, Дебора Дж. (1987). Комбинаторика планирования эксперимента . Нью-Йорк: Издательство Оксфордского университета. ISBN 0-19-853256-3. МР  0908490.
• Бергер, Пол Д.; Маурер, Роберт Э.; Челли, Джована Б. (28 ноября 2017 г.). Экспериментальный дизайн с применением в менеджменте, технике и науке (2-е издание (28 ноября 2017 г.) изд.). Спрингер. стр. 267–282.

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

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