Математическая энциклопедия - латинский квадрат

квадратная матрица порядка п, каждая строка и каждый столбец к-рой являются перестановкой элементов конечного множества S, состоящего из пэлементов. Говорят, что Л. к. построен на множестве 5; обычно

Л. к. существует для любого n; напр., где

есть Л. к.

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

По двум Л. к. порядка n и порядка тможно всегда построить Л. к. порядка mn, напр. следующим образом:

Для числа Ln Л. к. порядка пверна оценка снизу:

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

Два Л. к., построенные на одном и том же множестве S, наз. эквивалентными, если один из другого получается перестановкой строк, столбцов и переименованием элементов. Пусть knчисло классов эквивалентности Л. к. порядка n. Известны следующие первые значения ln и kn:

Кроме того, l9=377 597 570 964 258 816. Задача получения оценок для ln остается нерешенной (1982).

В теории планирования экспериментов требуется строить Л. к. с различными ограничениями на расположения элементов в них. Л. к. наз. полным, если для любых натуральных существуют такие i, j, k, l, что

Известны алгоритмы построения полных Л. к. только в случае четных n, для нек-рых нечетных пимеются примеры полных Л. к.

Латинским подквадратом данного Л. к. порядка пназ. такая его подматрица, что она сама является Л. к. порядка k, k<n. Любой Л. к. порядка kможет быть латинским подквадратом Л. к. порядка n при

При построении ортогональных латинских квадратов существенную роль играет понятие трансверсали Л. к. Частичной трансверсалью длины tЛ. к. наз. такое множество Т, состоящее из tклеток Л. к.

Всегда при t-n частичная трансверсаль наз. трансверсалью. Существование в Л. к. порядка пмножества из га непересекающихся трансверсалей является необходимым и достаточным условием существования для него ортогонального соквадрата. Л. к. 6-го порядка

не имеет ни одной трансверсали. В любом Л. к. порядка существует по крайней мере одна частичная трансверсаль длины При всегда можно построить Л. к. такой, что обе его главные диагонали являются трансверсалями.

Несколько обобщений Л. к. Ч а с т и ч н ы м, или неполным, Л. к. порядка пназ. матрица порядка п, у к-рой только часть клеток заполнена элементами множества Sмощности п, но в каждой строке и в каждом столбце элементы Sвстречаются не более одного раза. Существуют частичные Л. к., к-рые нельзя дополнить до Л. к., напр.:

Неполный Л. к., содержащий точно п-1 элементов, может быть дополнен до Л. к. Известно, что две таблицы Кэли двух разных групп порядка потличаются друг от друга по крайней мере на 2п местах.

Бесконечным Л. к. наз. бесконечная матрица, элементы к-рой натуральные числа, встречающиеся в каждой строке и в каждом столбце точно один раз. Имеется несколько обобщений понятия Л. к. на многомерный случай. Так, m-мерным перестановочным кубом порядка пназ. m-мерная матрица

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

есть перестановка первых пнатуральных чисел. А m-мерным гиперкубом порядка n и класса r наз. m-мерная матрица порядка п, элементы к-рой принадлежат множеству из п ^r элементов, каждый элемент встречается в матрице п ^т-r раз, а в каждом ( п-1)-мерном сечении матрицы (т. е. среди элементов

где а остальные индексы пробегают все n значений) встречается п ^т-r-1 раз.

Лит.:[1] Сачков В. Н., Комбинаторные методы дискретной математики, М., 1977; [2] Denes J., Keedwell A. D., Latin Squares and their Applications, Budapest, 1974; [3] Холл М., Комбинаторика, пер. с англ., М., 1970; [4] Р а й з е р Г.Д ж., Комбинаторная математика, пер. с англ., М., 1966. В. М. Михеев.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985