ОРТОГОНАЛЬНЫЕ ЛАТИНСКИЕ КВАДРАТЫ

Значение ОРТОГОНАЛЬНЫЕ ЛАТИНСКИЕ КВАДРАТЫ в математической энциклопедии:

пара латинских квадратов А=|| а _ij||, В=||b_ij|| порядка птаких, что при . Квадраты Аи В наз. ортогональными соквадратами. Матрица, получаемая наложением Ана В, наз. греко-латинским, или эйлеровым, квадратом, ее элементы - все и ² упорядоченных пар элементов S. Ортогональность Аи Вобозначается . Пример пары О. л. к. и их эйлерова квадрата для n=3:

Латинский квадрат Апорядка пимеет ортогональный соквадрат тогда и только тогда, когда в Асуществует пнепересекающихся трансверсалей (см. Латинский квадрат). Если А - латинский квадрат порядка 4t+2 (или 4t+l) с подквадратом порядка 2t+l (соответственно 2t), все клетки к-рого за исключением, быть может, t(соответственно [(t-1)/2]) клеток заполнены не более чем 2t+l (соответственно 2t) элементами, то для Ане существует ортогонального соквадрата. Для всех n>2, , имеются примеры пар О. л. к., а для n=6 путем перебора всех возможностей доказано, что таких пар нет [3].

Несколько латинских квадратов одного порядка наз. попарно ортогональными, если любые два из них ортогональны. Если N(п) - максимальное возможное число попарно О. л. к., то . Для N(п).получены следующие оценки снизу:

Кроме того,

и доказано, что при ; напр., при достаточно большом п(см. [2]).

Множество из n=1 попарно О. л. к. порядка пназ . полным. При n>4 множество из п-3 попарно О. л. к. всегда может быть дополнено до полного. В настоящее время (1983) полные множества известны только в случае n=р ^k, где k - натуральное, р - простое числа (то есть N( р ^k)= р ^k-1). Если же n=1 (mod 4) или n=2 (mod 4) и свободная от квадрата часть числа псодержит хотя бы один простой множитель p=3(mod 4), то не существует полного множества попарно О. л. к. порядка п. Напр., не существует полных множеств при п=2р,p=3(mod 4).

Полные множества попарно О. л. к. находят приложение в статистике при построении симметрических уравновешенных неполных блок-схем с параметрами n²=n+1, k=n+1,l=1. Полные множества могут интерпретироваться и как конечные проективные плоскости (см. [2]).

Предложено много методов построения О. л. к. (см. [2]). Все они созданы с целью получения как можно большего множества попарно О. л. к. порядка п. Каждый из методов может быть отнесен к одной из следующих двух групп. К первой группе принадлежат методы, характерной особенностью к-рых является то, что они дают способ построения "основного" латинского квадрата и указывают, как переставить в нем строки и столбцы, чтобы получить ортогональный соквадрат. Ко второй группе относятся методы, к-рые используют известные приемы построения О. л. к. меньшего порядка для построения О. л. к. заданного порядка.

Если A=|| а _ij||-латинский квадрат порядка п, построенный на множестве S, то упорядоченный набор перестановок , определяемых равенствами s_i(j)= а _ij, однозначно определяет латинский квадрат А. Не каждый упорядоченный набор перестановок соответствует какому-либо латинскому квадрату. Если А= [s₁ ,..., s_n]. и В=[t₁,...,t_n] - два латинских квадрата, заданных указанным способом перестановками 0; п т, множества S, то тогда и только тогда, когда - латинский квадрат. Если определить произведения aA=[as₁,...,as_n], Ab=[s₁b,...,s_nb], где a и b - перестановки S, то, напр., тогда и только тогда, когда [s₁^-1as₁,...,s_n^-1as_n] - латинский квадрат.

Методы первой группы обычно используются в случае, когда А - таблица умножения конечной группы G, то есть ; отличие одного метода от другого заключается в выборе группы G, в выборе взаимно однозначных отображений a, b группы Gна себя и в использовании произведений a А, Аb,a^-1Aa и т. д.

Если G - аддитивная группа, то условие сводится к тому, что a - ортоморфизм G, т. е. такое взаимно однозначное отображение Gна себя, что если для выполняется равенство a(g₁)-g₁= a(g₂)-g₂, то g₁=g₂ Напр., пять попарно О. л. к. порядка 12 были найдены после определения четырех нетривиальных ортоморфизмов абелевой группы, являющейся прямым произведением циклич. групп 0-го и 2-го порядков (см. [2], [6]).

Если G - аддитивная группа конечного поля GF(p^r).{a₀=0, a₁=1, a₂, ... , a_n}, п=р ^r, то все построения значительно упрощаются и получается следующее полное множество попарно О. л. к.:

Следует отметить, что для п, удовлетворяющих условиям (mod 4), (mod 9) п (mod 9), оказалось возможным всегда построить такой латинский квадрат Апорядка п, что

Использование прямого произведения латинских квадратов составляет основу следующего метода, относящегося ко второй группе. Пусть A₁ и В ₁ - О. л. к. порядка п, построенные на множестве X, а А ₂ и В ₂ - О. л. к. порядка т, построенные на множестве Y, тогда прямые произведения матриц А ₁ х А ₂ и В ₁ х В ₂ будут О. л. к. порядка тп, построенные на множестве

Xx Y. Если , то указанный метод приводит к оценке

В основе многих других методов второй группы лежит следующее построение. Пусть A₁ B₁ C₁ - попарно О. л. к. порядка , построенные на S₁={1, 2,... , т}, А₂, B₂ - О. л. к. порядка n, построенные на S₂={m+1,...,m+n}. Чтобы получить теперь два латинских квадрата Аи В порядка т+п, построенные на , добавляют к Астроки и столбцы с номерами m+1,...,m+n с незаполненными клетками, в результате чего получают частичный латинский квадрат порядка m+n, содержащий A₁ в верхнем левом углу. Клетки A₁ и B₁, имеющие те же номера, что и клетки С ₁, содержащие элемент i, составляют общую для A₁ и В ₁ i-ю трансверсаль, i=1, 2, ... , т. Элементы i- йтрансверсали в А, при i=l, 2, ... , ппомещают в (m+i) -й столбец (и в (m+i).ю строку) в том же порядке, в каком они располагались в строках (соответственно столбцах) A₁, а на их место ставится число m+i. Остается в правый нижний угол частичного квадрата поставить A₂, чтобы завершить построение А.

Построение Bпроводится аналогичным образом из В ₁ и B₂, но только с использованием трансверсалей с номерами n+1, n+2, ... , 2n. Квадраты Аи Вбудут латинскими, но не обязательно ортогональными. Всегда можно получить пару О. л. к. порядка m+n при т=, где р- нечетное, и n=(m-1)/2; показано, как, используя приведенное выше построение, получить пару О. л. к. порядка n при (mod 4), n>6 (см. [2]).

Приложения О. л. к. в статистике, теории информации и в теории планирования эксперимента требуют построения О. л. к. специального вида и перенесения понятия ортогональности на другие объекты. Так, обобщением О. л. к. являются ортогональные таблицы. Два частичных латинских квадрата одного порядка наз. ортогональными, если при наложении их друг на друга получаемые в клетках упорядоченные пары будут все различны. Говорят, что частичный латинский квадрат Авложен в латинский квадрат В, если Асовпадает с нек-рой подматрицей В(за исключением пустых клеток А). Каждый квадрат из множества попарно ортогональных частичных латинских квадратов может быть вложен в латинский квадрат таким образом, что полученные латинские квадраты будут О. л. к. (см. [6]).

Лит.:[1] Сачков В. Н., Комбинаторные методы дискретной математики, М,, 1977; [2] Denеs J., Кееdwe11 А. D., Latin Squares and their applications, Bdpst, 1974; [3]XojuiM., Комбинаторика, пер. с англ., М., 1970; [4] Райзер Г.-Дж., Комбинаторная математика, пер. с англ., М., 1966; [5] Hеdауat A., Sеidеn Е., "Pacif. J. Math.", 1977, v. 54, № 2, p. 85-113; [6] Liindner Сh., "Proc. Amer. Math. Soc.", 1976, v. 59, № 1, p. 184-86. В. М. Михеев.