Н. Макарова

 

 

ГРУППЫ ВЗАИМНО ОРТОГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ

 

Mutually Orthogonal Latin Squares (MOLS)

 

Часть III

 

Данная страница является продолжением страницы

http://www.natalimak1.narog.ru/grolk1.htm

 

 

В журнале “Discrete Mathematics 140 (1995) 291 - 294” есть статья (автор M. Wojtas), в которой даётся ссылка [1] на статью (автор A. E. Brouwer). В этой статье в 1979 году было опубликовано количество взаимно ортогональных латинских квадратов для порядков до 10000 включительно. После этого данная таблица значений много раз изменялась по мере того, как математики находили новые ортогональные латинские квадраты.

В предыдущей части настоящей статьи приведён фрагмент современной таблицы, найденной мной в Интернете. Эта таблица содержит максимальные количества взаимно ортогональных латинских квадратов для порядков от 2 до 499.

На указанной выше странице показаны группы взаимно ортогональных латинских квадратов для порядков от 3 до 20 включительно, разумеется, те, которые мне известны.

Здесь будет рассказано о группах MOLS для порядков от 21 до 30.

Покажу фрагмент указанной выше таблицы значений для данной группы порядков (рис. 1):

 

n

21

22

23

24

25

26

27

28

29

30

Q(n)

5

3

22

5

24

4

26

5

28

4

 

Рис. 1

 

Начну с порядка 21. Как видно из таблицы, максимальное количество MOLS данного порядка равно 5. Мне эта группа неизвестна.

Для данного порядка работает метод составных квадратов. Этим методом можно построить пару ОЛК.

Кроме того, я могу получить пару ОЛК 21-го порядка путём разложения на два ортогональных латинских квадрата какого-нибудь идеального магического квадрата данного порядка, построенного методом качелей, аналогично тому, как это было сделано для квадратов 15-го порядка.

Установлена определённая связь между методом качелей и методом латинских квадратов, что позволяет легко строить пару ОЛК для тех магических квадратов, которые строятся методом качелей. В статье http://www.natalimak1.narod.ru/kachlat.htm показано построение пары ОЛК 21-го порядка на основании этой связи двух методов. На рис. 2 вы видите первый латинский квадрат из этой пары (скопирован из указанной статьи).

 

14

1

15

18

20

0

2

5

19

6

4

3

7

11

8

10

12

9

13

17

16

3

7

11

8

10

12

9

13

17

16

14

1

15

18

20

0

2

5

19

6

4

1

15

18

20

0

2

5

19

6

4

3

7

11

8

10

12

9

13

17

16

14

7

11

8

10

12

9

13

17

16

14

1

15

18

20

0

2

5

19

6

4

3

15

18

20

0

2

5

19

6

4

3

7

11

8

10

12

9

13

17

16

14

1

11

8

10

12

9

13

17

16

14

1

15

18

20

0

2

5

19

6

4

3

7

18

20

0

2

5

19

6

4

3

7

11

8

10

12

9

13

17

16

14

1

15

8

10

12

9

13

17

16

14

1

15

18

20

0

2

5

19

6

4

3

7

11

20

0

2

5

19

6

4

3

7

11

8

10

12

9

13

17

16

14

1

15

18

10

12

9

13

17

16

14

1

15

18

20

0

2

5

19

6

4

3

7

11

8

0

2

5

19

6

4

3

7

11

8

10

12

9

13

17

16

14

1

15

18

20

12

9

13

17

16

14

1

15

18

20

0

2

5

19

6

4

3

7

11

8

10

2

5

19

6

4

3

7

11

8

10

12

9

13

17

16

14

1

15

18

20

0

9

13

17

16

14

1

15

18

20

0

2

5

19

6

4

3

7

11

8

10

12

5

19

6

4

3

7

11

8

10

12

9

13

17

16

14

1

15

18

20

0

2

13

17

16

14

1

15

18

20

0

2

5

19

6

4

3

7

11

8

10

12

9

19

6

4

3

7

11

8

10

12

9

13

17

16

14

1

15

18

20

0

2

5

17

16

14

1

15

18

20

0

2

5

19

6

4

3

7

11

8

10

12

9

13

6

4

3

7

11

8

10

12

9

13

17

16

14

1

15

18

20

0

2

5

19

16

14

1

15

18

20

0

2

5

19

6

4

3

7

11

8

10

12

9

13

17

4

3

7

11

8

10

12

9

13

17

16

14

1

15

18

20

0

2

5

19

6

 

Рис. 2

 

Второй латинский квадрат в этой паре ОЛК получается из первого отражением относительно горизонтальной оси симметрии, точно так же, как в случае с ортогональными латинскими квадратами 15-го порядка. Однако не исключено, что и здесь возможно другое построение второго латинского квадрата ортогонального первому, как это было совсем недавно установлено для квадратов 15-го порядка. Возможно, я ещё вернусь к этому вопросу.

 

Для порядка 22 легко построить пары ОЛК по известному алгоритму для серии порядков n = 10(mod 12). Этот алгоритм известен очень давно (см., например, книгу Д. Райзера “Комбинаторная математика”).

Группу из трёх MOLS 22-го порядка мне удалось найти в статье “Three mutually orthogonal idempotent Latin squares of orders 22 and 26” (R.J.R. Abel и другие). Эти квадраты были показаны мной в цикле статей “Новые аспекты метода латинских квадратов”. Кстати, судя по названию статьи, в ней говорится и о взаимно ортогональных квадратах 26-го порядка, однако эти квадраты не приводятся, возможно, рассказывается, как они строятся. Я не разбиралась в тексте статьи, а взяла из статьи готовые латинские квадраты 22-го порядка.

 

Для порядка 23 всё очень просто, так как этот порядок является простым числом. Группа MOLS данного порядка содержит 22 латинских квадрата. Все квадраты группы легко построить вручную. Можно сделать это и в пакете математических программ Maple [надо использовать команду MOLS(23,1,22)].

 

Порядок 24 относится к группе порядков, для которых работает метод составных квадратов, поэтому легко составить пару ОЛК данного порядка. Кроме того, я разработала алгоритм составления пары ОЛК для порядков серии n = 6k, k>1.  Порядок 24 относится к данной серии порядков.

В  статье http://www.natalimak1.narod.ru/aspekty6.htm показано построение пары ОЛК 24-го порядка с помощью этого алгоритма (см. рис. 23 - 24 в указанной статье). Не буду дублировать эту пару ОЛК.

Как видно из таблицы на рис. 1, Q(24) = 5, значит, найдена группа из пяти взаимно ортогональных латинских квадратов порядка 24. Мне неизвестна эта группа. О построении этой группы рассказывается в журнале “Discrete Mathematics 140 (1995) 291 - 294”, но я не разобралась в этом построении.

 

Порядок 25 очень хорош. Во-первых, для этого порядка работает метод составных квадратов. Во-вторых, этот порядок является степенью простого числа 5. Значит, для этого порядка группа MOLS полная и состоит из 24 квадратов. Эту группу можно построить в пакете Maple, применив команду MOLS(5,2,24). Наконец, порядок 25 нечётный и не кратен 3, поэтому латинские квадраты для данного порядка составляются так же, как для порядков, являющихся простым числом: с помощью циклического сдвига строк с постоянным шагом. При этом в первой строке каждого латинского квадрата группы стоит тождественная перестановка чисел 0, 1, 2, … 24. Покажу первые три квадрата группы (рис. 3 – 5) и последний квадрат (рис. 6). В квадрате № 3 раскраской показан циклический сдвиг строк.

 

Квадрат № 1

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

 

Рис. 3

 

Квадрат № 2

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

 

Рис. 4

 

Квадрат № 3

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

 

Рис. 5

 

Квадрат № 24

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

13

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

12

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

11

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

10

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

9

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

8

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

7

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

6

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

5

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

4

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

3

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

2

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

0

 

Рис. 6

 

В группе только два не диагональных латинских квадрата – квадрат № 1 и квадрат № 24. Все остальные квадраты диагональные.

 

Группа MOLS 26-го порядка, состоящая из четырёх квадратов, мне неизвестна. Для данного порядка у меня нет даже пары ОЛК. Этот порядок входит в серию порядков n = 2(mod 6), для которой я не знаю алгоритм составления пар ОЛК. К этой же серии порядков относятся порядки 14 и 20. Для порядка 20 я могу составить пары ОЛК методом составных квадратов, а вот порядок 14 тоже пока не имеет у меня даже пары ОЛК. Вся данная серия порядков – белое пятно.

 

Порядок 27 является степенью простого числа 3. Группа MOLS данного порядка полная и состоит из 26 латинских квадратов. Группу можно составить в пакете Maple, применив команду MOLS(3,3,26). Приведу здесь первые четыре квадрата из группы, полученной в Maple (рис. 7 – 10). Интересно отметить, что первые два квадрата группы составлены методом составных квадратов.

 

Квадрат № 1

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

1

2

0

4

5

3

7

8

6

10

11

9

13

14

12

16

17

15

19

20

18

22

23

21

25

26

24

2

0

1

5

3

4

8

6