Н. Макарова

 

ПОСТРОЕНИЕ ГРУПП MOLS ЧЕТЫРНАДЦАТОГО ПОРЯДКА

 

В статье “Построение ортогональных латинских квадратов из ортогонального массива” (http://www.natalimak1.narod.ru/arry.htm ) было показано построение пары ОЛК 14-го порядка по описанию, приведённому в книге М. Холла. Здесь будет показано построение групп взаимно ортогональных латинских квадратов 14-го порядка, состоящих из трёх квадратов. При написании статьи использовалась следующая литература:

[1] “Handbook of Combinatorial Designs” (издание 1996 г.);

[2] “Handbook of Combinatorial Designs” (издание 2007 г.);

[3] D. T. Todorov. “Three Mutually Orthogonal Latin Squares of Order 14”;

[4] Stinson. 6. Latin Squares (видимо, глава из какой-то книги).

Кроме того, хочу выразить благодарность участникам форума http://dxdy.ru/topic12959.html за данные разъяснения, с помощью которых мне удалось построить все группы MOLS 14-го порядка, приведённые в настоящей статье.

Сразу отмечу, что все построенные здесь латинские квадраты записаны в нетрадиционной форме, то есть заполнены числами от 1 до 14. Чтобы привести их к традиционной форме записи (заполнить числами от 0 до 13), надо просто уменьшить все элементы в приведённых латинских квадратах на единицу.

 

Начну с группы MOLS 14-го порядка, приведённой в [1]. Я не буду использовать символьные элементы a, b, c, d, e, как это сделано в книге, а заполню квадраты числами от 1 до 14. Мне совершенно непонятно, зачем авторы ввели эти символьные элементы, поэтому я их просто заменяю числами. На рис. 1 – 3 вы видите эту группу MOLS.

 

Первый латинский квадрат

 

 

Рис. 1

 

Второй латинский квадрат

 

 

Рис. 2

 

Третий латинский квадрат

 

 

Рис. 3

 

Поскольку эта группа приведена в книге в явном виде, я не знаю, по какому алгоритму она построена.

 

Примечание: смотрите Добавление в конце данной статьи.

 

В [2] группа MOLS 14-го порядка строится по так называемой квази-разностной матрице (quasi-difference matrix). Это как раз матрица подобная приведённой в статье Тодорова. После разъяснений на форуме, мне стало понятно, как строить группу MOLS по такой матрице. Сначала покажу квази-разностную матрицу из [2] (рис. 4).

 

 

Рис. 4

 

Примечание: все элементы матрицы увеличены на единицу, потому что латинские квадраты я буду заполнять числами от 1 до 14, как и в группе, показанной выше.

 

Как строить латинские квадраты по этой квази-разностной матрице, опишу кратко и покажу наглядно на построении первого латинского квадрата (рис. 5). Первый две строки в квази-разностной матрице – это координаты или иными словами – номера строк и столбцов в латинских квадратах. Теперь берём, например, первый столбец матрицы; имеем: в первой строке и пятом столбце (1,5) в первом латинском квадрате запишем число 5, во втором латинском квадрате – число 11, в третьем латинском квадрате – число 6. Прочерк означает последнюю строку, последний столбец или число 14 (соответственно). От записанных в ячейки чисел заполнение идёт по диагонали вправо и вниз, числа пишутся в порядке возрастания, после числа 13 пишется число 1. Такое заполнение происходит в квадрате 13х13, последняя строка и последний столбец в этом не участвуют. При достижении краёв квадрата 13х13 происходит переход на другую сторону квадрата, как если бы этот квадрат был свёрнут в трубочку по горизонтальной или вертикальной оси. Всё это очень похоже на то, как строятся латинские квадраты по ортогональному массиву (см. указанную выше статью). На рис. 5 перед квадратом и над квадратом приведены номера строк и столбцов, чтобы было хорошо видно, в какие ячейки вписываются числа из квази-разностной матрицы. Ячейки с числами из квази-разностной матрицы выделены жёлтым цветом. В последней строке и последнем столбце вписано по одному числу. далее заполнение идёт от вписанного числа по возрастанию с таким же зацикливанием после числа 13.

 

Первый латинский квадрат

 

 

Рис. 5

 

Примечание: следует отметить, что можно первую и вторую координаты – номер строки и столбца – рассматривать в обратном порядке, то есть первое число в столбце квази-разностной матрицы считать номером столбца, а второе число – номером строки. На рис. 6 показан первый латинский квадрат, построенный в такой системе координат.

 

 

Рис. 6

 

Очевидно, что полученный в этом случае латинский квадрат эквивалентен квадрату с рис. 5, он получается из него отражением относительно главной диагонали.

 

Совершенно аналогично строятся второй и третий латинские квадраты. На рис. 7 – 8 показаны эти квадраты без подробностей построения.

 

Второй латинский квадрат

 

 

Рис. 7

 

Третий латинский квадрат

 

 

Рис. 8

 

Легко видеть, что две приведённые группы MOLS 14-го порядка не изоморфны.

Теперь перехожу к построению групп по квази-разностным матрицам, приведённым в [3]. Я долго на могла построить эти группы, потому что не знала, как надо по квази-разностной матрице строить сами ортогональные латинские квадраты. На рис.  9 показываю первую квази-разностную матрицу Тодорова.

 

 

Рис. 9

 

Примечание: во всех квази-разностных матрицах Тодорова тоже все элементы увеличены на единицу.

 

На рис. 10 показано подробное построение первого латинского квадрат 14-го порядка по данной матрице. Во всех построениях по матрицам Тодорова система координат выбрана так: первая координата (x) – номер столбца, вторая координата (y) – номер строки. Положительная полуось x направлена вправо, положительная полуось y направлена вниз. Жёлтым цветом выделены ячейки, содержащие числа из квази-разностной матрицы.

 

Первый латинский квадрат

 

 

Рис. 10

 

На рис. 11 – 12 вы видите второй и третий латинские квадраты из данной группы MOLS.

 

Второй латинский квадрат

 

 

Рис. 11

 

Третий латинский квадрат

 

 

Рис. 12

 

Это третья группа, не являющаяся изоморфной двум группам из [1] и [2].

Тодоров привёл в своей статье три квази-разностные матрицы, которые содержат подматрицу 4х4, имеющую одинаковую структуру. На рис. 13 показана вторая квази-разностная матрица Тодорова. Одинаковая подматрица выделена зелёным цветом. В статье написано, что можно составить 375 различных квази-разностных матриц, содержащих такую подматрицу. Это легко сделать с помощью компьютера. Понятно, что каждая такая квази-разностная матрица даст новую группу MOLS.

 

 

Рис. 13

 

На рис. 14 показано построение первого латинского квадрата по данной матрице.

 

Первый латинский квадрат

 

 

Рис. 14

 

На рис. 15 – 16 показаны второй и третий латинские квадраты из этой группы.

 

Второй латинский квадрат

 

 

Рис. 15

 

Третий латинский квадрат

 

 

Рис. 16

 

Наконец, последняя квази-разностная матрица Тодорова показана на рис. 17.

 

 

Рис. 17

 

На рис. 18 вы видите построение первого латинского квадрата по данной матрице.

 

Первый латинский квадрат