Лати́нский квадра́т n-го порядка — таблица L=(lij) размеров n × n, заполненная n элементами множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3-го порядка:
который может быть представлен в виде {(1,1,A), (1,2,B), (1,3,C), (2,1,C), (2,2,A), (2,3,B), (3,1,B), (3,2,C), (3,3,A)}, где первый и второй элемент — позиция элемента в матрице, а третий — значение.
В настоящее время в качестве множества M обычно берётся множество натуральных чисел {1,2,…,n} или множество {0,1,…,n-1}, однако Леонард Эйлер использовал буквы латинского алфавита, откуда латинские квадраты и получили своё название.
Латинские квадраты существуют для любого n, достаточно взять таблицу Кэли группы порядка n, например, .
История исследований латинских квадратов
Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль-Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.
В 1700 году латинские квадраты были описаны корейским математиком Чхве Сок Чон, где он сформулировал «задачу о шестиугольной черепахе», полностью эквивалентную «задаче о 36 офицерах», которая будет вновь сформулирована Эйлером через 67 лет.
Пары ортогональных латинских квадратов были упомянуты Жаком Озанамом в 1725 году. В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача: Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз. Эта задача имеет 6912 решений (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).
Важной вехой в истории исследований латинских квадратов стала работа Эйлера. Он занимался в ней методами построения магических квадратов и предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n, делящихся на 4 и для нечётных n. Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских квадратов для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4t+2. Для n = 6 он сформулировал «задачу о 36 офицерах»: Необходимо разместить 36 офицеров шести различных полков и шести различных воинских званий в каре так, чтобы в каждой колонне и в каждом ряду был ровно один офицер каждого полка и каждого воинского звания.
В 1890 году Кэли вывел формулу для числа латинских прямоугольников из двух строк (частный случай классической комбинаторной «задачи о встречах», поставленной P. Montmort в 1708 году).
В 1900 году гипотеза Эйлера для n = 6 была подтверждена . Он построил все 9408 нормализованных латинских квадратов, разбил их на 17 типов и показал, что при любом их сочетании невозможно построить пару ортогональных квадратов. Таким образом, он отрицательно решил «задачу о 36 офицерах».
В 1922 году MacNeish впервые применил теоретико-групповой подход к решению задач относительно латинских квадратов. В частности, он предложил метод конструирования латинских квадратов порядка n1•n2 из латинских квадратов порядков n1 и n2, при этом свойство ортогональности сохраняется.
В 1925 году Роналд Фишер предложил использовать ортогональные латинские квадраты для планирования сельскохозяйственных экспериментов.
В 1920—1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры, что привело, в частности, к созданию теории квазигрупп, тесно связанной с изучением латинских квадратов, так как между латинскими квадратами и таблицами Кэли квазигрупп существует взаимно-однозначное соответствие.
В 1959 году Bose и Shrikhande построили 2 ортогональных латинских квадрата для n = 22, а в 1960 году они же и Parker построили с использованием ЭВМ минимальный контрпример для n = 10. Таким образом, спустя 177 лет гипотеза Эйлера была опровергнута.
Число латинских квадратов Точная формула для числа L(n) латинских квадратов n-го порядка неизвестна. Наилучшие оценки для L(n) даёт формула
Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком, заданном на множестве M. Пример нормализованного латинского квадрата:
Число R(n) нормализованных латинских квадратов n-го порядка () в n!(n-1)! раз меньше, чем L(n) ().
Точные значения величины L(n) известны для n от 1 до 11:
+ Число латинских квадратов n R(n) L(n) Автор и год 1 1 1 2 1 2 3 1 12 4 4 576 5 56 161280 Euler (1782) 6 9408 812851200 Frolov (1890) 7 16942080 61479419904000 Sade (1948) 8 535281401856 108776032459082956800 Wells (1967) 9 377597570964258816 5524751496156892842531225600 Bammel и Rothstein (1975) 10 7580721483160132811489280 9982437658213039871725064756920320000 McKay и Rogoyski (1995) 11 5363937773277371298119673540771840 776966836171770144107444346734230682311065600000 McKay и Wanless (2005)
Отношения эквивалентности на множестве латинских квадратов Два латинских квадрата называют изотопными, если один из них может быть получен из другого в результате изотопии — композиции из перестановки строк, перестановки столбцов и замены элементов множества M по подстановке из симметрической группы S(M).
Изотопия является отношением эквивалентности, поэтому множество латинских квадратов n-го порядка разбивается на непересекающиеся изотопические классы. Из одного латинского квадрата можно получить с помощью изотопии (n!)3 эквивалентных, но некоторые из них при этом могут совпасть с исходным, это называется автопаратопией. Доля латинских квадратов с нетривиальной группой автопаратопий стремится к нулю с ростом n.
Латинский квадрат можно рассматривать как ортогональный массив. Меняя порядок элементов в каждой упорядоченной тройке этого массива, можно получить 6 латинских квадратов, которые называются парастрофами. В частности, парастрофом является латинский квадрат, полученный в результате транспонирования.
Композиция изотопии и парастрофии называется изострофией. Это ещё одно отношение эквивалентности, его классы называются главными классами. Каждый главный класс содержит 1, 2, 3 или 6 изотопических классов. В случае совпадения исходного латинского квадрата и изострофного ему, говорят об автострофии. С ростом n почти все латинские квадраты имеют тривиальную группу автострофий.
+ Число классов эквивалентности n Число главных классов Число изотопических классов 1 1 1 2 1 1 3 1 1 4 2 2 5 2 2 6 12 22 7 147 564 8 283657 1676267 9 19270853541 115618721533 10 34817397894749939 208904371354363006 11 2036029552582883134196099 12216177315369229261482540
Ортогональные латинские квадраты
Два латинских квадрата L=(lij) и K=(kij) n-го порядка называются ортогональными, если все упорядоченные пары (lij,kij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:
Эйлер называл такие квадраты «полными». В его честь в научной литературе их раньше называли «эйлеровыми» или «греко-латинскими» (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).
Ортогональные латинские квадраты существуют для любого n, не равного 2 и 6.
Латинский квадрат L n-го порядка имеет ортогональный ему квадрат тогда и только тогда, когда в L существует n непересекающихся трансверсалей.
Особый интерес в связи с многочисленными приложениями вызывают множества из нескольких попарно ортогональных латинских квадратов n-го порядка. Максимально возможная мощность N(n) такого множества равна n-1, в этом случае множество называется полным.
При n, стремящемуся к ∞, величина N(n) тоже стремится к ∞.
Для n, являющегося степенью простого числа, всегда существует полное множество попарно ортогональных латинских квадратов, его можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n. Для его построения применяется метод Боуза, использующий для заполнения квадратов значения многочленов вида при ненулевом a над полем . Пример построения полного множества попарно ортогональных латинских квадратов 4-го порядка (d — корень примитивного многочлена над ):
Если n ≡ 1 (mod 4) или n ≡ 2 (mod 4) и свободная от квадрата часть числа n содержит хотя бы один простой множитель p ≡ 3 (mod 4), то для таких n полного множества попарно ортогональных латинских квадратов не существует.
Известные нижние оценки числа N(n) при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):
+ Нижние оценки числа N(n) n 1234567891011121314151617181920212223242526272829303132 N(n)≥ 2346782105123415163184532262442652843031
Построение ортогональных квадратов — сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсали, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы. К первой группе относятся методы, основанные на выборе базового латинского квадрата, к которому отыскиваются изотопные ортогональные латинские квадраты. Например, пять попарно ортогональных латинских квадратов 12-го порядка были найдены в результате построения четырёх ортоморфизмов абелевой группы, являющейся прямым произведением циклических групп порядков 6 и 2.
Ко второй группе относятся методы, использующие для построения ортогональных латинских квадратов комбинаторные объекты (включая сами латинские квадраты) меньших порядков. Например, два латинских квадрата 22-го порядка были построены Bose и Shrikhande на основе двух дизайнов 15-го и 7-го порядка.
Диагональные латинские квадраты Латинский квадрат называется диагональным, если в дополнение к требованиям уникальности элементов в строках и столбцах, свойственным для латинского квадрата, добавляются требования уникальности элементов на главной и побочной диагоналяхColbourn C. J., Dinitz J. H. Handbook of Combinatorial Designs. Second Edition. Chapman&Hall, 2006. 984 p.. Аналитическая оценка числа диагональных латинских квадратов неизвестна, их число для размерностей N<10 было определено в 2016 г. в проекте добровольных распределённых вычислений Gerasim@Home ( и ). Для диагональных латинских квадратов, как и для просто латинских, возможно построение ортогональных пар, часть из которых (порядка 9 и 10) была найдена в проекте добровольных распределённых вычислений SAT@home с использованием SAT-подхода. В настоящее время поиск пар ортогональных диагональных латинских квадратов 10-го порядка производится в проекте добровольных распределённых вычислений Gerasim@Home с использованием трансверсалей, а также в BOINC-проектах ODLK и ODLK1. 25 апреля 2018 г. найден диагональный латинский квадрат 10-го порядка, имеющий 10 ортогональных диагональных латинских квадратов. Это максимальное известное количество ортогональных диагональных квадратов у диагонального латинского квадрата 10-го порядка (). Открытой математической проблемой является существование тройки попарно ортогональных диагональных латинских квадратов порядка 10 (на текущий момент наилучшим приближением к её решению является тройка квадратов, в которой две пары квадратов ортогональны, а третья частично ортогональна в 74 ячейках).
Частичные квадраты Квадрат, в котором каждый элемент множества M в каждой строке и в каждом столбце встречается не более одного раза, называется частичным.
Задача распознавания того, может ли частичный квадрат быть дополнен до латинского, является NP-полной.
Введено понятие критического множества, соответствующего частичному квадрату, который однозначно может быть дополнен до латинского, причём никакое его собственное подмножество условию однозначности не удовлетворяет.