Латинский квадрат - Latin square

Отображение латинского квадрата 7 × 7, этот витраж почести Рональд Фишер, чей Дизайн экспериментов обсуждали латинские квадраты.

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

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

История

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

Уменьшенная форма

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

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

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

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

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

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

является

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

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

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

Это означает, что п² упорядоченные пары (р, c) все пары (я, j) с 1 ≤ я, j ≤ п, по одному разу. То же самое и с упорядоченными парами (р, s) и упорядоченные пары (c, s).

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

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

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

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

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

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

Число

Нет известной легко вычислимой формулы для числа L_п из п × п Латинские квадраты с символами 1,2,...,п. Наиболее точные верхние и нижние границы, известные для больших п далеки друг от друга. Один классический результат^[5] в том, что

${displaystyle prod _ {k = 1} ^ {n} left (k! ight) ^ {n / k} geq L_ {n} geq {frac {left (n! ight) ^ {2n}} {n ^ {n ^ {2}}}}.}$

Простая и явная формула для числа латинских квадратов была опубликована в 1992 году, но ее до сих пор нелегко вычислить из-за экспоненциального увеличения числа членов. Эта формула для числа L_п из п × п Латинские квадраты

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

куда B_п это набор всех п × п {0, 1} матрицы, σ₀(А) это количество нулевых элементов в матрице А, и на (А) это постоянный матрицы А.^[6]

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

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

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

Примеры

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

${displaystyle {egin {bmatrix} 1end {bmatrix}} quad {egin {bmatrix} 1 & 2 2 & 1end {bmatrix}} quad {egin {bmatrix} 1 & 2 & 3 2 & 3 & 1 3 & 1 & 2end {bmatrix}}}$

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

${displaystyle {egin {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 & 2end {bmatrix}} quad {egin {bmatrix} 1 & 2 & 3 & 4 & 5 & 2 & 1 & 5 & 5 & 2 & 4 & 1 & 5}$

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

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

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

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

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

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

Некоторые латинские квадраты не имеют поперечного сечения. Например, когда п четный, п-к-п Латинский квадрат, в котором значение ячейки я, j является (я+j) мод п не имеет поперечного. Вот два примера:

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

В 1967 г. Х. Дж. Райзер предположил, что когда п является странный, каждый п-к-п Латинский квадрат имеет поперечную.^[8]

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

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

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

• Каждый п-к-п Латинский квадрат имеет частичный поперечный размер 2.п/3.^[10]
• Каждый п-к-п Латинский квадрат имеет частичный поперечный размер п - sqrt (п).^[11]
• Каждый п-к-п Латинский квадрат имеет частичный поперечный размер п - 11 журнал₂²(п).^[12]

Алгоритмы

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

Приложения

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

• в дизайн экспериментов, Латинские квадраты - это частный случай строковые конструкции для двух блокирующие факторы:^[14][15]

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

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

Наборы латинских квадратов, которые ортогональный друг другу нашли применение как коды исправления ошибок в ситуациях, когда общению мешает больше видов шума, чем простой белый шум, например, при попытке передачи широкополосного Интернета по линиям электропередач.^[16][17][18]

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

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

Кодировка из двенадцати букв состоит из трех латинских квадратов, ортогональных друг другу. А теперь представьте, что в каналах 1 и 2 на протяжении всей передачи появляется дополнительный шум. Тогда буква А будет воспринята как:

${displaystyle {egin {matrix} 12 & 12 & 123 & 124 end {matrix}}}$

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

${displaystyle {egin {matrix} 1 & 2 & 1234 & 4 end {matrix}}}$

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

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

Проблема определения того, можно ли заполнить частично заполненный квадрат для образования латинского квадрата, заключается в следующем: НП-полный.^[19]

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

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

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

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

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

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

Геральдика

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

Обобщения

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

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

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

Примечания

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

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

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

• Dénes, J. H .; Кидвелл, А. Д. (1991). Латинские квадраты: новые разработки в теории и приложениях. Анналы дискретной математики. 46. Пол Эрдёш (предисловие). Амстердам: Academic Press. 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). Искусство программирования, Том 4A: Комбинаторные алгоритмы, Часть 1. Ридинг, Массачусетс: Эддисон-Уэсли. ISBN  978-0-201-03804-0.
• Laywine, Charles F .; Маллен, Гэри Л. (1998). Дискретная математика с использованием латинских квадратов. Серия Wiley-Interscience по дискретной математике и оптимизации. Нью-Йорк: John Wiley & Sons, Inc. ISBN  0-471-24064-8. МИСТЕР  1644242.
• Shah, K. R .; Синха, Бикас К. (1996). «Рядно-столбчатые конструкции». В С. Гош и К. Р. Рао (ред.). Планирование и анализ экспериментов. Справочник по статистике. 13. Амстердам: Издательство Северной Голландии, стр. 903–937. ISBN  0-444-82061-2. МИСТЕР  1492586.
• Рагхаварао, Дамараджу (1988). Конструкции и комбинаторные задачи при планировании экспериментов. (исправленное переиздание изд. Wiley 1971 г.). Нью-Йорк: Дувр. ISBN  0-486-65685-3. МИСТЕР  1102899.
• Улица, Энн Пенфолд; Улица, Дебора Дж. (1987). Комбинаторика экспериментального дизайна. Нью-Йорк: Издательство Оксфордского университета. ISBN  0-19-853256-3. МИСТЕР  0908490.

внешняя ссылка

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