Ортогональные латинские квадраты

пара латинских квадратов А=|| а ij||, В=||bij|| порядка птаких, что [img: http://localhost:8080/file/041609-22.jpg] при [img: http://localhost:8080/file/041609-23.jpg] [img: http://localhost:8080/file/041609-24.jpg]. Квадраты Аи В наз. ортогональными соквадратами. Матрица, получаемая наложением Ана В, наз. греко-латинским, или эйлеровым, квадратом, ее элементы - все и 2 упорядоченных пар элементов S. Ортогональность Аи Вобозначается [img: http://localhost:8080/file/041609-25.jpg]. Пример пары О. л. к. и их эйлерова квадрата для n=3: [img: http://localhost:8080/file/041609-26.jpg] Латинский квадрат Апорядка пимеет ортогональный соквадрат тогда и только тогда, когда в Асуществует пнепересекающихся трансверсалей (см. Латинский квадрат). Если А - латинский квадрат порядка 4t+2 (или 4t+l) с подквадратом порядка 2t+l (соответственно 2t), все клетки к-рого за исключением, быть может, t(соответственно [(t-1)/2]) клеток заполнены не более чем 2t+l (соответственно 2t) элементами, то для Ане существует ортогонального соквадрата. Для всех n>2, [img: http://localhost:8080/file/041609-27.jpg], имеются примеры пар О. л. к., а для n=6 путем перебора всех возможностей доказано, что таких пар нет [3]. Несколько латинских квадратов одного порядка наз. попарно ортогональными, если любые два из них ортогональны. Если N(п) - максимальное возможное число попарно О. л. к., то [img: http://localhost:8080/file/041609-28.jpg]. Для N(п).получены следующие оценки снизу: [img: http://localhost:8080/file/041609-29.jpg] Кроме того, [img: http://localhost:8080/file/041609-30.jpg] [img: http://localhost:8080/file/041609-31.jpg] и доказано, что [img: http://localhost:8080/file/041609-32.jpg] при [img: http://localhost:8080/file/041609-33.jpg]; напр., [img: http://localhost:8080/file/041609-34.jpg] при достаточно большом п(см. [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). Полные множества попарно О. л. к. находят приложение в статистике при построении симметрических уравновешенных неполных блок-схем с параметрами n2=n+1, k=n+1,l=1. Полные множества могут интерпретироваться и как конечные проективные плоскости (см. [2]). Предложено много методов построения О. л. к. (см. [2]). Все они созданы с целью получения как можно большего множества попарно О. л. к. порядка п. Каждый из методов может быть отнесен к одной из следующих двух групп. К первой группе принадлежат методы, характерной особенностью к-рых является то, что они дают способ построения "основного" латинского квадрата и указывают, как переставить в нем строки и столбцы, чтобы получить ортогональный соквадрат. Ко второй группе относятся методы, к-рые используют известные приемы построения О. л. к. меньшего порядка для построения О. л. к. заданного порядка. Если A=|| а ij||-латинский квадрат порядка п, построенный на множестве S, то упорядоченный набор перестановок [img: http://localhost:8080/file/041609-35.jpg], определяемых равенствами si(j)= а ij, однозначно определяет латинский квадрат А. Не каждый упорядоченный набор перестановок соответствует какому-либо латинскому квадрату. Если А= [s1,..., sn]. и В=[t1,...,tn] - два латинских квадрата, заданных указанным способом перестановками 0; п т, множества S, то [img: http://localhost:8080/file/041609-36.jpg] тогда и только тогда, когда [img: http://localhost:8080/file/041609-37.jpg] - латинский квадрат. Если определить произведения aA=[as1,...,asn], Ab=[s1b,...,snb], где a и b - перестановки S, то, напр., [img: http://localhost:8080/file/041609-38.jpg] тогда и только тогда, когда [s1-1as1,...,sn-1asn] - латинский квадрат. Методы первой группы обычно используются в случае, когда А - таблица умножения конечной группы G, то есть [img: http://localhost:8080/file/041609-39.jpg]; отличие одного метода от другого заключается в выборе группы G, в выборе взаимно однозначных отображений a, b группы Gна себя и в использовании произведений a А, Аb,a-1Aa и т. д. Если G - аддитивная группа, то условие [img: http://localhost:8080/file/041609-40.jpg] сводится к тому, что a - ортоморфизм G, т. е. такое взаимно однозначное отображение Gна себя, что если для [img: http://localhost:8080/file/041609-41.jpg] выполняется равенство a(g1)-g1= a(g2)-g2, то g1=g2 Напр., пять попарно О. л. к. порядка 12 были найдены после определения четырех нетривиальных ортоморфизмов абелевой группы, являющейся прямым произведением циклич. групп 0-го и 2-го порядков (см. [2], [6]). Если G - аддитивная группа конечного поля GF(pr).{a0=0, a1=1, a2,..., an}, п=р r, то все построения значительно упрощаются и получается следующее полное множество попарно О. л. к.: [img: http://localhost:8080/file/041609-42.jpg] Следует отметить, что для п, удовлетворяющих условиям [img: http://localhost:8080/file/041609-43.jpg] (mod 4), [img: http://localhost:8080/file/041609-44.jpg] (mod 9) п [img: http://localhost:8080/file/041609-45.jpg] (mod 9), оказалось возможным всегда построить такой латинский квадрат Апорядка п, что [img: http://localhost:8080/file/041609-46.jpg] Использование прямого произведения латинских квадратов составляет основу следующего метода, относящегося ко второй группе. Пусть A1 и В 1 - О. л. к. порядка п, построенные на множестве X, а А 2 и В 2 - О. л. к. порядка т, построенные на множестве Y, тогда прямые произведения матриц А 1 х А 2 и В 1 х В 2 будут О. л. к. порядка тп, построенные на множестве Xx Y. Если [img: http://localhost:8080/file/041609-47.jpg], то указанный метод приводит к оценке [img: http://localhost:8080/file/041609-48.jpg] В основе многих других методов второй группы лежит следующее построение. Пусть A1 B1 C1 - попарно О. л. к. порядка [img: http://localhost:8080/file/041609-49.jpg], построенные на S1={1, 2,..., т}, А2, B2 - О. л. к. порядка n, построенные на S2={m+1,...,m+n}. Чтобы получить теперь два латинских квадрата Аи В порядка т+п, построенные на [img: http://localhost:8080/file/041609-50.jpg], добавляют к Астроки и столбцы с номерами m+1,...,m+n с незаполненными клетками, в результате чего получают частичный латинский квадрат порядка m+n, содержащий A1 в верхнем левом углу. Клетки A1 и B1, имеющие те же номера, что и клетки С 1, содержащие элемент i, составляют общую для A1 и В 1 i-ю трансверсаль, i=1, 2,..., т. Элементы i- йтрансверсали в А, при i=l, 2,..., ппомещают в (m+i) -й столбец (и в (m+i).ю строку) в том же порядке, в каком они располагались в строках (соответственно столбцах) A1, а на их место ставится число m+i. Остается в правый нижний угол частичного квадрата поставить A2, чтобы завершить построение А. Построение Bпроводится аналогичным образом из В 1 и B2, но только с использованием трансверсалей с номерами n+1, n+2,..., 2n. Квадраты Аи Вбудут латинскими, но не обязательно ортогональными. Всегда можно получить пару О. л. к. порядка m+n при т= [img: http://localhost:8080/file/041609-51.jpg], где р- нечетное, и n=(m-1)/2; показано, как, используя приведенное выше построение, получить пару О. л. к. порядка n при [img: http://localhost:8080/file/041609-52.jpg] (mod 4), n>6 (см. [2]). Приложения О. л. к. в статистике, теории информации и в теории планирования эксперимента требуют построения О. л. к. специального вида и перенесения понятия ортогональности на другие объекты. Так, обобщением О. л. к. являются ортогональные таблицы. Два частичных латинских квадрата одного порядка наз. ортогональными, если при наложении их друг на друга получаемые в клетках упорядоченные пары будут все различны. Говорят, что частичный латинский квадрат Авложен в латинский квадрат В, если Асовпадает с нек-рой подматрицей В(за исключением пустых клеток А). Каждый квадрат из множества попарно ортогональных частичных латинских квадратов может быть вложен в латинский квадрат таким образом, что полученные латинские квадраты будут О. л. к. (см. [6]).