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

пара латинских квадратов А=|| а ij||, В=||bij|| порядка птаких, что при . Квадраты Аи В наз. ортогональными соквадратами. Матрица, получаемая наложением Ана В, наз. греко-латинским, или эйлеровым, квадратом, ее элементы все и ² упорядоченных пар элементов 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, то упорядоченный набор перестановок , определяемых равенствами si(j)= а ij, однозначно определяет латинский квадрат А. Не каждый упорядоченный набор перестановок соответствует какому-либо латинскому квадрату. Если А= [s1 ,..., sn]. и В=[t1,...,tn] два латинских квадрата, заданных указанным способом перестановками 0; п т, множества S, то тогда и только тогда, когда латинский квадрат. Если определить произведения aA=[as1,...,asn], Ab=[s1b,...,snb], где a и b перестановки S, то, напр., тогда и только тогда, когда [s1^-1as1,...,sn^-1asn] латинский квадрат.

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

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

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

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