Н. Макарова

 

НЕИЗОМОРФНЫЕ ГРУППЫ MOLS 18-го и 26-го ПОРЯДКА

 

 

В предыдущей статье показано построение неизоморфных пар ортогональных латинских квадратов (ОЛК). Для этого используется очень оригинальный приём варьирования секции квази-разностной матрицы (КРМ). Здесь я покажу построение неизоморфных групп MOLS 18-го и 26-го порядка таким же способом.

 

Начну с группы MOLS 18-го порядка, состоящей из трёх попарно ортогональных латинских квадратов (рис. 1 - 3).

 

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

 

1

5

x1

x2

x3

x4

2

9

11

6

8

10

12

7

14

4

13

3

8

2

6

x1

x2

x3

x4

3

10

12

7

9

11

13

1

5

14

4

14

9

3

7

x1

x2

x3

x4

4

11

13

8

10

12

2

6

1

5

13

1

10

4

8

x1

x2

x3

x4

5

12

14

9

11

3

7

2

6

12

14

2

11

5

9

x1

x2

x3

x4

6

13

1

10

4

8

3

7

11

13

1

3

12

6

10

x1

x2

x3

x4

7

14

2

5

9

4

8

3

12

14

2

4

13

7

11

x1

x2

x3

x4

8

1

6

10

5

9

2

4

13

1

3

5

14

8

12

x1

x2

x3

x4

9

7

11

6

10

10

3

5

14

2

4

6

1

9

13

x1

x2

x3

x4

8

12

7

11

x4

11

4

6

1

3

5

7

2

10

14

x1

x2

x3

9

13

8

12

x3

x4

12

5

7

2

4

6

8

3

11

1

x1

x2

10

14

9

13

x2

x3

x4

13

6

8

3

5

7

9

4

12

2

x1

11

1

10

14

x1

x2

x3

x4

14

7

9

4

6

8

10

5

13

3

12

2

11

1

4

x1

x2

x3

x4

1

8

10

5

7

9

11

6

14

13

3

12

2

9

10

11

12

13

14

1

2

3

4

5

6

7

8

x1

x2

x3

x4

6

7

8

9

10

11

12

13

14

1

2

3

4

5

x4

x3

x2

x1

5

6

7

8

9

10

11

12

13

14

1

2

3

4

x2

x1

x4

x3

7

8

9

10

11

12

13

14

1

2

3

4

5

6

x3

x4

x1

x2

 

Рис. 1

 

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

 

1

8

14

13

12

11

3

2

10

x4

x3

x2

x1

4

9

6

5

7

5

2

9

1

14

13

12

4

3

11

x4

x3

x2

x1

10

7

6

8

x1

6

3

10

2

1

14

13

5

4

12

x4

x3

x2

11

8

7

9

x2

x1

7

4

11

3

2

1

14

6

5

13

x4

x3

12

9

8

10

x3

x2

x1

8

5

12

4

3

2

1

7

6

14

x4

13

10

9

11

x4

x3

x2

x1

9

6

13

5

4

3

2

8

7

1

14

11

10

12

2

x4

x3

x2

x1

10

7

14

6

5

4

3

9

8

1

12

11

13

9

3

x4

x3

x2

x1

11

8

1

7

6

5

4

10

2

13

12

14

11

10

4

x4

x3

x2

x1

12

9

2

8

7

6

5

3

14

13

1

6

12

11

5

x4

x3

x2

x1

13

10

3

9

8

7

4

1

14

2

8

7

13

12

6

x4

x3

x2

x1

14

11

4

10

9

5

2

1

3

10

9

8

14

13

7

x4

x3

x2

x1

1

12

5

11

6

3

2

4

12

11

10

9

1

14

8

x4

x3

x2

x1

2

13

6

7

4

3

5

7

13

12

11

10

2

1

9

x4

x3

x2

x1

3

14

8

5

4

6

14

1

2

3

4

5

6

7

8

9

10

11

12

13

x1

x2

x3

x4

4

5

6

7

8

9

10

11

12

13

14

1

2

3

x3

x4

x1

x2

13

14

1

2

3

4

5

6

7

8

9

10

11

12

x4

x3

x2

x1

3

4

5

6

7

8

9

10

11

12

13

14

1

2

x2

x1

x4

x3

 

Рис. 2

 

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

 

x1

x3

14

7

10

8

5

x2

13

3

6

4

12

x4

1

11

9

2

x4

x1

x3

1

8

11

9

6

x2

14

4

7

5

13

2

12

10

3

14

x4

x1

x3

2

9

12

10

7

x2

1

5

8

6

3

13

11

4

7

1

x4

x1

x3

3

10

13

11

8

x2

2

6

9

4

14

12

5

10

8

2

x4

x1

x3

4

11

14

12

9

x2

3

7

5

1

13

6

8

11

9

3

x4

x1

x3

5

12

1

13

10

x2

4

6

2

14

7

5

9

12

10

4

x4

x1

x3

6

13

2

14

11

x2

7

3

1

8

x2

6

10

13

11

5

x4

x1

x3

7

14

3

1

12

8

4

2

9

13

x2

7

11

14

12

6

x4

x1

x3

8

1

4

2

9

5

3

10

3

14

x2

8

12

1

13

7

x4

x1

x3

9

2

5

10

6

4

11

6

4

1

x2

9

13

2

14

8

x4

x1

x3

10

3

11

7

5

12

4

7

5

2

x2

10

14

3

1

9

x4

x1

x3

11

12

8

6

13

12

5

8

6

3

x2

11

1

4

2

10

x4

x1

x3

13

9

7

14

x3

13

6

9

7

4

x2

12

2

5

3

11

x4

x1

14

10

8

1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

x1

x2

x3

x4

11

12

13

14

1

2

3

4

5

6

7

8

9

10

x2

x1

x4

x3

9

10

11

12

13

14

1

2

3

4

5

6

7

8

x3

x4

x1

x2

2

3

4

5

6

7

8

9

10

11

12

13

14

1

x4

x3

x2

x1

 

Рис. 3

 

 

Построение этой группы MOLS описано в статье http://www.natalimak1.narod.ru/mols18.htm . Латинские квадраты группы обладают интересной симметрией. Они содержат латинский подквадрат 4х4.

Вот как выглядит КРМ этой группы MOLS в том виде, какой я получила по описанию, приведённому в книге “Handbook of Combinatorial Designs” (рис. 4):

 

 

Рис. 4

 

Символьные элементы x1, x2, x3, x4 принимают значения 15, 16, 17, 18 (или 15, 16, 17, 0) в любой комбинации. Если использовать первую группу значений, то латинские квадраты будут заполнены в нетрадиционной форме – числами от 1 до 18. Если использовать группу значений 15, 16, 17, 0, квадраты будут заполнены в традиционной форме – числами от 0 до 17.

 

А теперь преобразую КРМ к виду, придуманному мной. Именно в таком виде очень хорошо видно ту секцию КРМ, которую можно варьировать. Преобразованная КРМ показана на рис. 5.

 

 

Рис. 5

 

В этой КРМ выделена секция, в которой возможно варьирование групп чисел. При этом полностью сохранится симметрия латинских квадратов. Группы чисел, подвергаемых варьированию: 3, 4, 13, 14;  5, 6, 7, 9 и  1, 2, 9, 11. В третьей и четвёртой строках КРМ перестановки групп чисел берутся одинаковые, в пятой строке перестановка группы чисел берётся одна и та же. Разумеется, из всех возможных перестановок выбираются только те, которые не нарушают совместимость всех строк КРМ по известному критерию. Составив и выполнив программу, я получила 24 решения. Покажу все решения, ибо это очень интересный результат. Решения выводятся в виде выделенной секции КРМ.

 

№ 1                                        2                                       № 3                                        № 4

 3  4  13  14  7  6  5  9            3  4  14  13  7  6  9  5             3  13  4  14  7  5  6  9             3  13  14  4  7  5  9  6

 7  6  5  9  3  4  13  14            7  6  9  5  3  4  14  13             7  5  6  9  3  13  4  14             7  5  9  6  3  13  14  4

            2  11  9  1  2  11  9  1             2  11  1  9  2  11  1  9             2  9  11  1  2  9  11  1             2  9  1  11  2  9  1  11

 

№ 5                                        № 6                                        № 7                                        № 8

            3  14  4  13  7  9  6  5             3  14  13  4  7  9  5  6             4  3  13  14  6  7  5  9             4  3  14  13  6  7  9  5 

            7  9  6  5  3  14  4  13             7  9  5  6  3  14  13  4             6  7  5  9  4  3  13  14             6  7  9  5  4  3  14  13   

 2  1  11  9  2  1  11  9            2  1  9  11  2  1  9  11             11  2  9  1  11  2  9  1             11  2  1  9  11  2  1  9    

 

№ 9                                        № 10                                     № 11                                      № 12

 4  13  3  14  6  5  7  9            4  13  14  3  6  5  9  7            4  14  3  13  6  9  7  5             4  14  13  3  6  9  5  7

 6  5  7  9  4  13  3  14            6  5  9  7  4  13  14  3            6  9  7  5  4  14  3  13             6  9  5  7  4  14  13  3

 11  9  2  1  11  9  2  1            11  9  1  2  11  9  1  2             11  1  2  9  11  1  2  9             11  1  9  2  11  1  9  2   

 

№ 13                                      № 14                                     № 15                                      № 16

 13  3  4  14  5  7  6  9            13  3  14  4  5  7  9  6             13  4  3  14  5  6  7  9             13  4  14  3  5  6  9  7    

 5  7  6  9  13  3  4  14            5  7  9  6  13  3  14  4             5  6  7  9  13  4  3  14             5  6  9  7  13  4  14  3    

 9  2  11  1  9  2  11  1            9  2  1  11  9  2  1  11             9  11  2  1  9  11  2  1             9  11  1  2  9  11  1  2

 

№ 17                                      № 18                                      № 19                                     № 20

 13  14  3  4  5  9  7  6            13  14  4  3  5  9  6  7             14  3  4  13  9  7  6  5             14  3  13  4  9  7  5  6

 5  9  7  6  13  14  3  4            5  9  6  7  13  14  4  3             9  7  6  5  14  3  4  13             9  7  5  6  14  3  13  4

 9  1  2  11  9  1  2  11            9  1  11  2  9  1  11  2             1  2  11  9  1  2  11  9             1  2  9  11  1  2  9  11

 

№ 21                                      № 22                                      № 23                                      № 24  

 14  4  3  13  9  6  7  5            14  4  13  3  9  6  5  7             14  13  3  4  9  5  7  6             14  13  4  3  9  5  6  7

 9  6  7  5  14  4  3  13            9  6  5  7  14  4  13  3             9  5  7  6  14  13  3  4             9  5  6  7  14  13  4  3

 1  11  2  9  1  11  2  9            1  11  9  2  1  11  9  2             1  9  2  11  1  9  2  11             1  9  11  2  1  9  11  2

 

Примечание: все перестановки в данном примере соответственные. Определение соответственных перестановок смотрите в предыдущей статье “Неизоморфные пары ортогональных латинских квадратов”.

 

Очевидно, что КРМ, изображённая на рис. 5, соответствует решению № 22.

А теперь покажу решение № 1. Сначала КРМ (рис. 6), а затем группу MOLS (рис. 7 – 9). В латинских квадратах группы символьные элементы заменены конкретными числовыми значениями: x1 = 15, x2 = 16, x3 = 17, x4 = 18.

 

Квази-разностная матрица (решение № 1)

 

 

Рис. 6

 

 Первый латинский квадрат (решение № 1)

 

1

5

15

16

17

18

2

9

11

6

8

10

12

7

3

4

13

14

8

2

6

15

16

17

18

3

10

12

7

9

11

13

4

5

14

1

14

9

3

7

15

16

17

18

4

11

13

8

10

12

5

6

1

2

13

1

10

4

8

15

16

17

18

5

12

14

9

11

6

7

2

3

12

14

2

11

5

9

15

16

17

18

6

13

1

10

7

8

3

4

11

13

1

3

12

6

10

15

16

17

18

7

14

2

8

9

4

5

3

12

14

2

4

13

7

11

15

16

17

18

8

1

9

10

5

6

2

4

13

1

3

5

14

8

12

15

16

17

18

9

10

11

6

7

10

3

5

14

2

4

6

1

9

13

15

16

17

18

11

12

7

8

18

11

4

6

1

3

5

7

2

10

14

15

16

17

12

13

8

9

17

18

12

5

7

2

4

6

8

3

11

1

15

16

13

14

9

10

16

17

18

13

6

8

3

5

7

9

4

12

2

15

14

1

10

11

15

16

17

18

14

7

9

4

6

8

10

5

13

3

1

2

11

12

4

15

16

17

18

1

8

10

5

7

9

11

6

14

2

3

12

13

7

8

9

10

11

12

13

14

1

2

3

4

5

6

15

16

17

18

6

7

8

9

10

11

12

13

14

1

2

3

4

5

18

17

16

15

5

6

7

8

9

10

11

12

13

14

1

2

3

4

16

15

18

17

9

10

11

12

13

14

1

2

3

4

5

6

7

8

17

18

15

16

 

Рис. 7

 

Второй латинский квадрат (решение № 1)

 

1

8

14

13

12

11

3

2

10

18

17

16

15

4

7

6

5

9

5

2

9

1

14

13

12

4

3

11

18

17

16

15

8

7

6

10

15

6

3

10

2

1

14

13

5

4

12

18

17

16

9

8

7

11

16

15

7

4

11

3

2

1

14

6

5

13

18

17

10

9

8

12

17

16

15

8

5

12

4

3

2

1

7

6

14

18

11

10

9

13

18

17

16

15

9

6

13

5

4

3

2

8

7

1

12

11

10

14

2

18

17

16

15

10

7

14

6

5

4

3

9

8

13

12

11

1

9

3

18

17

16

15

11

8

1

7

6

5

4

10

14

13

12

2

11

10

4

18

17

16

15

12

9

2

8

7

6

5

1

14

13

3

6

12

11

5

18

17

16

15

13

10

3

9

8

7

2

1

14

4

8

7

13

12

6

18

17

16

15

14

11

4

10

9

3

2

1

5

10

9

8

14

13

7

18

17

16

15

1

12

5

11

4

3

2

6

12

11

10

9

1

14

8

18

17

16

15

2

13

6

5

4

3

7

7

13

12

11

10

2

1

9

18

17

16

15

3

14

6

5

4

8

3

4

5

6

7

8

9

10

11

12

13

14

1

2

15

16

17

18

4

5

6

7

8

9

10

11

12

13

14

1

2

3

17

18

15

16

13

14

1

2

3

4

5

6

7

8

9

10

11

12

18

17

16

15

14

1

2

3

4

5

6

7

8

9

10

11

12

13

16

15

18

17

 

Рис. 8

 

Третий латинский квадрат (решение № 1)

 

15

17

14

7

10

8

5

16

13

3

6

4

12

18

2

11

9

1

18

15

17

1

8

11

9

6

16

14

4

7

5

13

3

12

10

2

14

18

15

17

2

9

12

10

7

16

1

5

8

6

4

13

11

3

7

1

18

15

17

3

10

13

11

8

16

2

6

9

5

14

12

4

10

8

2

18

15

17

4

11

14

12

9

16

3

7

6

1

13

5

8

11

9

3

18

15

17

5

12

1

13

10

16

4

7

2

14

6

5

9

12

10

4

18

15

17

6

13

2

14

11

16

8

3

1

7

16

6

10

13

11

5

18

15

17

7

14

3

1

12

9

4

2

8

13

16

7

11

14

12

6

18

15

17

8

1

4

2

10

5

3

9

3

14

16

8

12

1

13

7

18

15

17

9

2

5

11

6

4

10

6

4

1

16

9

13

2

14

8

18

15

17

10

3

12

7

5

11

4

7

5

2

16

10

14

3

1

9

18

15

17

11

13

8

6

12

12

5

8

6

3

16

11

1

4

2

10

18

15

17

14

9

7

13

17

13

6

9

7

4

16

12

2

5

3

11

18

15

1

10

8

14

2

3

4

5

6

7

8

9

10

11

12

13

14

1

15

16

17

18

11

12

13

14

1

2

3

4

5

6

7

8

9

10

16

15

18

17

9

10

11

12

13

14

1

2

3

4

5

6

7

8

17

18

15

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

18

17

16

15

 

Рис. 9

 

Понятно, что очень легко запрограммировать получение всех 24 вариантов КРМ, а по КРМ и построение групп MOLS.

Заметьте, что из данной группы MOLS можно получать неизоморфные группы и другим способом: варьируя латинские подквадраты 4х4.

Напомню, что именно на основе этой группы MOLS я получила 2880 неизоморфных пар ортогональных диагональных латинских квадратов (ОДЛК) (см. статью http://www.natalimak1.narod.ru/diagon.htm ).

 

 

Перехожу к группе MOLS 26-го порядка. Эта группа также построена по книге “Handbook of Combinatorial Designs”.

На рис. 10 изображена квази-разностная матрица, построенная из матрицы, приведённой в книге.

 

x1

1

2

4

7

5

x2

1

7

12

11

20

x3

1

8

21

15

6

x4

1

9

19

2

13

x5

1

15

11

6

3

1

2

4

7

5

x1

1

7

12

11

20

x2

1

8

21

15

6

x3

1

9

19

2

13

x4

1

15

11

6

3

x5

2

4

7

5

x1

1

7

12

11

20

x2

1

8

21

15

6

x3

1

9

19

2

13

x4

1

15

11

6

3

x5

1

4

7

5

x1

1

2

12

11

20

x2

1

7

21

15

6

x3

1

8

19

2

13

x4

1

9

11

6

3

x5

1

15

7

5

x1

1

2

4

11

20

x2

1

7

12

15

6

x3

1

8

21

2

13

x4

1

9

19

6

3

x5

1

15

11

5

x1

1

2

4

7

20

x2

1

7

12

11

6

x3

1

8

21

15

13

x4

1

9

19

2

3

x5

1

15

11

6

 

Рис. 10

 

Здесь символьные элементы x1, x2, x3, x4, x5 принимают значения 22, 23, 24, 25, 26  (или 22, 23, 24, 25, 0) в любой комбинации.

                        Построение группы MOLS по данной КРМ смотрите в статье http://www.natalimak1.narod.ru/mols26_38.htm

Теперь хочу применить к этой группе MOLS тот же самый приём варьирования секции КРМ. Сначала преобразую КРМ к виду, удобному для применения этого приёма (рис. 11):

 

x1

x2

x3

x4

x5

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

x1

x2

x3

x4

x5

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

2

7

8

9

15

18

3

17

10

20

1

4

6

2

16

5

12

21

19

x2

15

x4

x3

8

11

7

14

13

x5

x1

9

4

12

21

19

11

19

9

3

18

13

1

7

4

x1

x4

14

11

15

2

12

5

21

8

20

6

x3

x5

10

17

16

x2

7

11

15

2

6

21

14

16

7

9

1

5

x1

19

4

x2

20

6

13

18

x4

8

15

x3

3

2

12

x5

10

17

11

5

20

6

13

3

3

13

10

11

4

1

x1

21

20

12

16

x2

x3

x4

2

14

18

7

15

x5

9

5

8

6

19

17

 

Рис. 11

 

В этом примере надо варьировать восемь различных групп, каждая из которых состоит из 5 чисел. Я перечислю эти группы:

 

2,    7,    8,    9,  15

3,  10,  17,  18,  20

4,  11,  12,  19,  21

3,   9,   13,  18,  19

2,   6,     7,  11,  15

7,   9,   14,  16,  21

3,   5,     6,  13,  20

3,   4,   10,  11,  13

 

Совершенно понятно, что сразу можно применить все соответственные перестановки. Я составила программу для таких перестановок и получила 14400 решений. Это тоже вполне понятно: каждая группа из пяти чисел в третьей строке КРМ имеет 120 вариантов. Группы чисел в остальных строках КРМ располагаются соответственно группам чисел в третьей строке КРМ. Вот один пример КРМ с соответственными перестановками (рис. 12):

 

x1

x2

x3

x4

x5

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

x1

x2

x3

x4

x5

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

15

9

8

7

2

17

10

20

18

3

1

4

6

2

16

5

12

21

19

x2

15

x4

x3

8

11

7

14

13

x5

x1

9

11

19

21

12

4

3

18

13

19

9

1

7

4

x1

x4

14

11

15

2

12

5

21

8

20

6

x3

x5

10

17

16

x2

6

2

15

11

7

16

7

9

21

14

1

5

x1

19

4

x2

20

6

13

18

x4

8

15

x3

3

2

12

x5

10

17

11

3

13

6

20

5

10

11

4

3

13

1

x1

21

20

12

16

x2

x3

x4

2

14

18

7

15

x5

9

5

8

6

19

17

 

Рис. 12

 

Совершенно очевидно, что соответственные перестановки равносильны перестановке столбцов в выделенной секции КРМ. Разумеется, столбцы переставляются не во всей секции, а только в группе из первых пяти столбцов и в следующей группе из пяти столбцов.

Сложнее в этом примере найти не соответственные перестановки. Мне удалось найти только одну такую перестановку, да и то не для всей КРМ, а только для первых четырёх строк. Таким образом, я получила 14400 новых вариантов неизоморфных пар ОЛК. На рис. 13 показана КРМ с не соответственной перестановкой.

 

x1