Н. Макарова

 

ПОСТРОЕНИЕ ГРУПП 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

4

5

6

7

8

9

10

11

12

13

14

2

1

6

10

4

13

8

12

14

5

7

9

11

3

3

4

1

7

11

5

14

9

13

2

6

8

10

12

4

13

5

1

8

12

6

2

10

14

3

7

9

11

5

12

14

6

1

9

13

7

3

11

2

4

8

10

6

11

13

2

7

1

10

14

8

4

12

3

5

9

7

10

12

14

3

8

1

11

2

9

5

13

4

6

8

7

11

13

2

4

9

1

12

3

10

6

14

5

9

6

8

12

14

3

5

10

1

13

4

11

7

2

10

3

7

9

13

2

4

6

11

1

14

5

12

8

11

9

4

8

10

14

3

5

7

12

1

2

6

13

12

14

10

5

9

11

2

4

6

8

13

1

3

7

13

8

2

11

6

10

12

3

5

7

9

14

1

4

14

5

9

3

12

7

11

13

4

6

8

10

2

1

 

Рис. 1

 

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

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

4

10

7

1

3

8

12

2

6

11

14

5

9

13

5

14

11

8

1

4

9

13

3

7

12

2

6

10

6

11

2

12

9

1

5

10

14

4

8

13

3

7

7

8

12

3

13

10

1

6

11

2

5

9

14

4

8

5

9

13

4

14

11

1

7

12

3

6

10

2

9

3

6

10

14

5

2

12

1

8

13

4

7

11

10

12

4

7

11

2

6

3

13

1

9

14

5

8

11

9

13

5

8

12

3

7

4

14

1

10

2

6

12

7

10

14

6

9

13

4

8

5

2

1

11

3

13

4

8

11

2

7

10

14

5

9

6

3

1

12

14

13

5

9

12

3

8

11

2

6

10

7

4

1

2

1

14

6

10

13

4

9

12

3

7

11

8

5

3

6

1

2

7

11

14

5

10

13

4

8

12

9

 

Рис. 2

 

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

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

14

3

11

13

8

10

6

5

2

12

9

4

7

1

2

1

4

12

14

9

11

7

6

3

13

10

5

8

3

9

1

5

13

2

10

12

8

7

4

14

11

6

4

7

10

1

6

14

3

11

13

9

8

5

2

12

5

13

8

11

1

7

2

4

12

14

10

9

6

3

6

4

14

9

12

1

8

3

5

13

2

11

10

7

7

8

5

2

10

13

1

9

4

6

14

3

12

11

8

12

9

6

3

11

14

1

10

5

7

2

4

13

9

14

13

10

7

4

12

2

1

11

6

8

3

5

10

6

2

14

11

8

5

13

3

1

12

7

9

4

11

5

7

3

2

12

9

6

14

4

1

13

8

10

12

11

6

8

4

3

13

10

7

2

5

1

14

9

13

10

12

7

9

5

4

14

11

8

3

6

1

2

 

Рис. 3

 

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

 

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

 

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

 

1

13

11

1

7

13

1

11

9

-

8

1

2

7

10

5

1

11

11

1

6

12

1

5

1

-

9

4

6

2

5

13

1

3

5

1

13

8

1

12

1

-

10

3

4

11

5

13

12

8

9

4

10

2

12

8

9

-

1

1

6

3

7

11

5

13

7

6

3

4

10

2

1

-

1

 

Рис. 4

 

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

 

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

 

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

 

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

4

1

9

11

5

8

2

12

14

6

3

13

10

7

2

11

5

2

10

12

6

9

3

13

14

7

4

1

8

3

2

12

6

3

11

13

7

10

4

1

14

8

5

9

4

6

3

13

7

4

12

1

8

11

5

2

14

9

10

5

10

7

4

1

8

5

13

2

9

12

6

3

14

11

6

14

11

8

5

2

9

6

1

3

10

13

7

4

12

7

5

14

12

9

6

3

10

7

2

4

11

1

8

13

8

9

6

14

13

10

7

4

11

8

3

5

12

2

1

9

3

10

7

14

1

11

8

5

12

9

4

6

13

2

10

1

4

11

8

14

2

12

9

6

13

10

5

7

3

11

8

2

5

12

9

14

3

13

10

7

1

11

6

4

12

7

9

3

6

13

10

14

4

1

11

8

2

12

5

13

13

8

10

4

7

1

11

14

5

2

12

9

3

6

14

12

13

1

2

3

4

5

6

7

8

9

10

11

14

 

Рис. 5

 

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

 

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

4

11

2

6

10

14

5

9

3

1

8

7

13

12

2

1

5

12

3

7

11

14

6

10

4

2

9

8

13

3

9

2

6

13

4

8

12

14

7

11

5

3

10

1

4

11

10

3

7

1

5

9

13

14

8

12

6

4

2

5

5

12

11

4

8

2

6

10

1

14

9

13

7

3

6

8

6

13

12

5

9

3

7

11

2

14

10

1

4

7

2

9

7

1

13

6

10

4

8

12

3

14

11

5

8

12

3

10

8

2

1

7

11

5

9

13

4

14

6

9

14

13

4

11

9

3

2

8

12

6

10

1

5

7

10

6

14

1

5

12

10

4

3

9

13

7

11

2

8

11

3

7

14

2

6

13

11

5

4

10

1

8

12

9

12

13

4

8

14

3

7

1

12

6

5

11

2

9

10

13

10

1

5

9

14

4

8

2

13

7

6

12

3

11

14

7

8

9

10

11

12

13

1

2

3

4

5

6

14

 

Рис. 6

 

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

 

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

 

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

 

3

6

14

13

11

5

10

2

9

7

12

4

8

1

9

4

7

14

1

12

6

11

3

10

8

13

5

2

6

10

5

8

14

2

13

7

12

4

11

9

1

3

2

7

11

6

9

14

3

1

8

13

5

12

10

4

11

3

8

12

7

10

14

4

2

9

1

6

13

5

1

12

4

9

13

8

11

14

5

3

10

2

7

6

8

2

13

5

10

1

9

12

14

6

4

11

3

7

4

9

3

1

6

11

2

10

13

14

7

5

12

8

13

5

10

4

2

7

12

3

11

1

14

8

6

9

7

1

6

11

5

3

8

13

4

12

2

14

9

10

10

8

2

7

12

6

4

9

1

5

13

3

14

11

14

11

9

3

8

13

7

5

10

2

6

1

4

12

5

14

12

10

4

9

1

8

6

11

3

7

2

13

12

13

1

2

3

4

5

6

7

8

9

10

11

14

 

Рис. 7

 

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

 

10

4

13

9

6

5

1

12

2

8

11

7

14

3

14

11

5

1

10

7

6

2

13

3

9

12

8

4

9

14

12

6

2

11

8

7

3

1

4

10

13

5

1

10

14

13

7

3

12

9

8

4

2

5

11

6

12

2

11

14

1

8

4

13

10

9

5

3

6

7

7

13

3

12

14

2

9

5

1

11

10

6

4

8

5

8

1

4

13

14

3

10

6

2

12

11

7

9

8

6

9

2

5

1

14

4

11

7

3

13

12

10

13

9

7

10

3

6

2

14

5

12

8

4

1

11

2

1

10

8

11

4

7

3

14

6

13

9

5

12

6

3

2

11

9

12

5

8

4

14

7

1

10

13

11

7

4

3

12

10

13

6

9

5

14

8

2

1

3

12

8

5

4

13

11

1

7

10

6

14

9

2

4

5

6

7

8

9

10

11

12

13

1

2

3

14

 

Рис. 8

 

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

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

 

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

2

4

3

5

6

7

8

9

10

11

12

13

1

1

3

13

11

8

10

6

5

2

12

9

4

7

1

2

3

10

6

4

13

8

12

1

5

7

9

11

1

4

13

10

7

3

8

12

2

6

11

1

5

9

 

Рис. 9

 

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

 

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

 

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

 

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

14

8

6

12

3

7

11

13

5

4

10

9

2

1

2

3

14

9

7

13

4

8

12

1

6

5

11

10

2

3

11

4

14

10

8

1

5

9

13

2

7

6

12

3

4

13

12

5

14

11

9

2

6

10

1

3

8

7

4

5

8

1

13

6

14

12

10

3

7

11

2

4

9

5

6

10

9

2

1

7

14

13

11

4

8

12

3

5

6

7

6

11

10

3

2

8

14

1

12

5

9

13

4

7

8

5

7

12

11

4

3

9

14

2

13

6

10

1

8

9

2

6

8

13

12

5

4

10

14

3

1

7

11

9

10

12

3

7

9

1

13

6

5

11

14

4

2

8

10

11

9

13

4

8

10

2

1

7

6

12

14

5

3

11

12

4

10

1

5

9

11

3

2

8

7

13

14

6

12

13

7

5

11

2

6

10

12

4

3

9

8

1

14

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

 

Рис. 10

 

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

 

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

 

3

12

11

10

9

6

5

2

8

13

7

4

14

1

14

4

13

12

11

10

7

6

3

9

1

8

5

2

6

14

5

1

13

12

11

8

7

4

10

2

9

3

10

7

14

6

2

1

13

12

9

8

5

11

3

4

4

11

8

14

7

3

2

1

13

10

9

6

12

5

13

5

12

9

14

8

4

3

2

1

11

10

7

6

8

1

6

13

10

14

9

5

4

3

2

12

11

7

12

9

2

7

1

11

14

10

6

5

4

3

13

8

1

13

10

3

8

2

12

14

11

7

6

5

4

9

5

2

1

11

4

9

3

13

14

12

8

7

6

10

7

6

3

2

12

5

10

4

1

14

13

9

8

11

9

8

7

4

3

13

6

11

5

2

14

1

10

12

11

10

9

8

5

4

1

7

12

6

3

14

2

13

2

3

4

5

6

7

8

9

10

11

12

13

1

14

 

Рис. 11

 

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

 

13

10

7

4

2

11

8

6

3

12

14

5

9

1

10

1

11

8

5

3

12

9

7

4

13

14

6

2

7

11

2

12

9

6

4

13

10

8

5

1

14

3

14

8

12

3

13

10

7

5

1

11

9

6

2

4

3

14

9

13

4

1

11

8

6

2

12

10

7

5

8

4

14

10

1

5

2

12

9

7

3

13

11

6

12

9

5

14

11

2

6

3

13

10

8

4

1

7

2

13

10

6

14

12

3

7

4

1

11

9

5

8

6

3

1

11

7

14

13

4

8

5

2

12

10

9

11

7

4

2

12

8

14

1

5

9

6

3

13

10

1

12

8

5

3

13

9

14

2

6

10

7

4

11

5

2

13

9

6

4

1

10

14

3

7

11

8

12

9

6

3

1

10

7

5

2

11

14

4

8

12

13

4

5

6

7

8

9

10

11

12

13

1

2

3

14

 

Рис. 12

 

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

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

 

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

2

4

3

5

6

7

8

9

10

11

12

13

1

1

8

5

6

9

11

2

4

3

7

13

10

12

1

2

8

13

5

11

4

6

9

12

1

3

7

10

1

4

5

13

10

2

7

12

3

11

9

1

8

6

 

Рис. 13

 

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

 

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

 

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

14

13

12

3

11

8

10

9

6

5

2

4

7

1

2

8

14

1

13

4

12

9

11

10

7

6

3

5

2

3

6

9

14

2

1

5

13

10

12

11

8

7

4

3

4

5

7

10

14

3

2

6

1

11

13

12

9

8

4

5

9

6

8

11

14

4

3

7

2

12

1

13

10

5

6

11

10

7

9

12

14

5

4

8

3

13

2

1

6

7

2

12

11

8

10

13

14

6

5

9

4

1

3

7

8

4

3

13

12

9

11

1

14

7

6

10

5

2

8

9

3

5

4

1

13

10

12

2

14

8

7

11

6

9

10

7

4

6

5

2

1

11

13

3

14

9

8

12

10

11

13

8

5

7

6

3

2

12

1

4

14

10

9

11

12

10

1

9

6

8

7

4

3

13

2

5

14

11

12

13

12

11

2

10

7

9

8

5

4

1

3

6

14

13

14

1

2

3

4

5

6

7

8

9

10

11

12

13

14

 

Рис. 14

 

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

 

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

 

8

11

9

6

5

4

2

13

12

7

10

3

14

1

14

9

12

10

7

6

5

3

1

13

8

11

4

2

5

14

10

13

11

8

7

6

4

2

1

9

12

3

13

6

14

11

1

12

9

8

7

5

3

2

10

4

11

1

7

14

12

2

13

10

9

8

6

4

3

5

4

12

2

8

14

13

3

1

11

10

9

7

5

6

6

5

13

3

9

14

1

4

2

12

11

10

8

7

9

7

6

1

4

10

14

2

5

3

13

12

11

8

12

10

8

7

2

5

11

14

3

6

4

1

13

9

1

13

11

9

8

3

6

12

14

4

7

5

2

10

3

2

1

12

10

9

4

7

13

14

5

8

6

11

7

4

3

2

13

11

10

5

8

1

14

6

9

12

10

8

5

4

3

1

12

11

6

9

2

14

7

13

2

3

4

5

6

7

8

9

10

11

12

13

1

14

 

Рис. 15

 

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

 

5

7

10

4

13

3

9

6

2

11

14

8

12

1

13

6

8

11

5

1

4

10

7

3

12

14

9

2

10

1

7

9

12

6

2

5

11

8

4

13

14

3

14

11

2

8

10

13

7

3

6

12

9

5

1

4

2

14

12

3

9

11

1

8

4

7

13

10

6

5

7

3

14

13

4

10

12

2

9

5

8

1

11

6

12

8

4

14

1

5

11

13

3

10

6

9

2

7

3

13

9

5

14

2

6

12

1

4

11

7

10

8

11

4

1

10

6

14

3

7

13

2

5

12

8

9

9

12

5

2

11

7

14

4

8

1

3

6

13

10

1

10

13

6

3

12

8

14

5

9

2

4

7

11

8

2

11

1

7

4

13

9

14

6

10

3

5

12

6

9

3

12

2

8

5

1

10

14

7

11

4

13

4

5

6

7

8

9

10

11

12

13

1

2

3

14

 

Рис. 16

 

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

 

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

2

4

3

5

6

7

8

9

10

11

12

13

1

1

11

7

10

13

4

8

12

6

9

3

5

2

1

2

11

3

8

7

12

1

9

5

13

6

10

4

1

4

7

3

5

12

10

2

13

8

6

1

9

11

 

Рис. 17

 

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

 

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

 

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

1

14

3

7

6

13

11

5

2

12

9

4

8

10

1

2

11

14

4

8

7

1

12

6

3

13

10

5

9

2

3

10

12

14

5

9

8

2

13

7

4

1

11

6

3

4

7

11

13

14

6