Н. Макарова

 

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

 

Mutually Orthogonal Latin squares (MOLS)

 

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

Как всегда, всех в первую очередь интересует вопрос: а зачем это нужно? Каково практическое применение ортогональных латинских квадратов. На одном форуме и был задан такой вопрос, когда я написала об ортогональных латинских квадратах. Пришлось отвечать на вопрос. Взяла цитату из одной статьи. Приведу её здесь, потому что моих читателей тоже наверняка интересует этот вопрос.

 

Это цитата из статьи по ссылке: http://www.mi.ras.ru/spm/pdf/011.pdf

 

“В XVIII веке, когда Эйлер ввёл понятие греко-латинских (ортогональных) квадратов, они были просто новыми чисто математическими объектами. В дальнейшем латинские и особенно ортогональные латинские квадраты нашли применения в различных областях (см., например, [13]).

В комбинаторике полные системы ортогональных латинских квадратов соответствуют конечным аффинным и проективным плоскостям. Латинские квадраты используются при построении квадратов Рума (турниров игры в бридж). В конце XIX века Кэли показал, что таблица умножения элементов конечной группы является латинским квадратом. В 30-х годах ХХ века возникло понятии квазигруппы, в которой таблицей умножения может быть любой латинский квадрат.

Системы попарно ортогональных латинских квадратов используются при построении сеточных методов интегрирования в вычислительной математике.

В 30-х годах ХХ века Р. Фишер [11], [12] предложил использовать латинские (и ортогональные латинские) квадраты для планирования сельскохозяйственных экспериментов”.

 

Я уже рассказала немного об ортогональных латинских квадратах в статье “Новые аспекты метода латинских квадратов” (статья написана в нескольких частях). Теперь хочу рассказать о группах ортогональных латинских квадратов. Кратко эта тема упоминалась в указанной статье.

 

Напомню, что группа из m латинских квадратов порядка n называется группой (или системой) взаимно  (или попарно) ортогональных квадратов, если любые два квадрата этой группы ортогональны. Известно, что для любого порядка n существует не больше чем n-1 взаимно ортогональных квадратов (см., например, М. Гарднер, “Математические досуги”, М.: Мир, 1972). Далее доказано, что для любого порядка n, являющегося простым числом или степенью простого числа, существует ровно n-1 взаимно ортогональных квадратов. Такая группа, состоящая из n-1 попарно ортогональных латинских квадратов, называется полной. Обозначим Q(n) максимальное количество взаимно ортогональных квадратов порядка n, которые удалось найти общими усилиями математиков. Поскольку для порядков 2 и 6 вообще не существует ортогональных латинских квадратов, будем считать Q(2) = Q(6) = 1. Так написано в таблице, фрагмент которой приводится ниже. Эту таблицу я нашла по следующей ссылке:

 

http://djvu.504.com1.ru:8019/WWW/10ce1596c3b6ce5e1c9b29593c2e2226.pdf

 

В таблице приводятся значения Q(n) для n от 2 до 499. Я приведу небольшой фрагмент этой таблицы (рис. 1).

 

 

Рис. 1

 

По этой же ссылке приведены группы взаимно ортогональных латинских квадратов порядков 3, 4 и 10. Для порядка 3 приведена такая группа, состоящая из двух ортогональных латинских квадратов (рис. 2):

 

 

Рис. 2

 

На рис. 3 вы видите группу из трёх взаимно ортогональных латинских квадратов 4-го порядка.

 

 

Рис. 3

 

Понятно, что из трёх квадратов группы можно составить три пары ортогональных латинских квадратов (далее буду использовать для термина “ортогональные латинские квадраты” аббревиатуру ОЛК).

 

Группу взаимно ортогональных латинских квадратов 5-го порядка взяла из указанной выше книги М. Гарднера. Эта группа показана на рис. 4.

 

 

Рис. 4

 

Примечание: в книге латинские квадраты записаны в традиционном виде, то есть заполнены числами от 0 до 4. Я представила квадраты в нетрадиционном виде, как в двух предыдущих группах.

 

Из четырёх квадратов этой группы можно составить шесть пар ОЛК 5-го порядка.

Обратите внимание: во всех приведённых группах квадраты получаются друг из друга перестановкой строк.

Группы взаимно ортогональных латинских квадратов для порядков, являющихся простым числом или степенью простого числа, можно строить в пакете математических программ Maple. На рис. 5 вы видите группу из шести взаимно ортогональных латинских квадратов порядка 7 (здесь квадраты даются в традиционном виде), построенную в Maple.

 

 

 

Рис. 5

 

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

Далее показываю группу из семи взаимно ортогональных латинских квадратов 8-го порядка (рис. 6), построенную в Maple.

 

 

 

 

Рис. 6

 

В этой группе только один латинский квадрат не диагональный. Из семи квадратов данной группы можно составить 21 пару ОЛК. Здесь пары ОЛК могут быть смешанными или состоять только из диагональных квадратов, так как не диагональный квадрат всего один.

И, наконец, ещё одна группа, построенная в Maple, – группа из восьми квадратов 9-го порядка (рис. 7).

 

 

 

 

Рис. 7

 

В этой группе два латинских квадрата не диагональные, остальные шесть диагональные. Из восьми квадратов группы можно составить 28 пар ОЛК. Эти пары могут состоять из диагональных квадратов, из не диагональных квадратов и быть смешанными.

Интересно ещё раз обратить внимание на то, что во всех приведённых группах взаимно ортогональных латинских квадратов квадраты получаются друг из друга перестановкой строк. Например, посмотрите на последнюю группу квадратов (рис. 7). В первой строке всех квадратов группы стоит тождественная перестановка чисел. А все следующие строки переставляются, при этом каждая строка занимает во всех квадратах восемь разных позиций.

 

Думаю, что для всех порядков группа взаимно ортогональных латинских квадратов, составленная в Maple, не единственная. В статье “Handbook of Combinatorial Design” нашла подтверждение для порядка 9. В этой статье приведено несколько групп взаимно ортогональных латинских квадратов 9-го порядка. Вот одна из них:

 

    123456789    123456789    123456789    123456789    123456789    123456789    123456789    123456789

    231564897    456789123    645978312    897231564    312645978    564897231    789123456    978312645

    312645978    789123456    897231564    645978312    231564897    978312645    456789123    564897231

    456789123    312645978    978312645    564897231    789123456    645978312    231564897    897231564

    564897231    645978312    231564897    312645978    978312645    789123456    897231564    456789123

    645978312    978312645    456789123    789123456    897231564    231564897    564897231    312645978

    789123456    231564897    564897231    978312645    456789123    897231564    312645978    645978312

    897231564    564897231    789123456    456789123    645978312    312645978    978312645    231564897

    978312645    897231564    312645978    231564897    564897231    456789123    645978312    789123456

 

Примечание: латинские квадраты записаны в нетрадиционной форме, то есть с помощью чисел 1, 2, 3 … 9. Я не стала их переводить в традиционную форму записи.

 

Интересно отметить, что в этой группе тоже два не диагональных латинских квадрата, при этом не диагональные квадраты в точности совпадают с не диагональными квадратами приведённой выше группы, построенной в Maple. А все диагональные квадраты другие.

Можно продолжить построение групп взаимно ортогональных латинских квадратов порядков, являющихся простым числом или степенью простого числа, в Maple.

Можно даже попытаться составлять такие пары ОЛК и без Maple. Я, например, сделала это для пары ОЛК порядка 16. Составила пару диагональных ОЛК 16-го порядка по аналогии с парами ОЛК 8-го порядка из группы, приведённой на рис. 6.

Теперь рассказываю о группах взаимно ортогональных квадратов 10-го порядка. В таблице на рис. 1 вы видите, что Q(10) = 2. Это значит, что максимальное количество взаимно ортогональных латинских квадратов, которое удалось найти, равно 2. То есть известны только пары ОЛК 10-го порядка и не удалось найти трёх взаимно ортогональных латинских квадратов 10-го порядка. Хорошая задача для читателей! Представьте: задача решается со времён Эйлера, который вообще считал, что пар ОЛК 10-го порядка не существует. Однако Эйлер ошибся, такие пары были найдены. А вот дальше пар дело не продвинулось.

Покажу здесь три пары диагональных ОЛК 10-го порядка, которые были найдены только в 1992 году. Эти пары опубликованы в статье “Completion of the Spectrum of Orthogonal Diagonal Latin Squares” (J. W. Brown и другие). Смотрите эти пары на рис. 8 – 10.

 

 

Рис. 8

 

 

Рис. 9

 

 

Рис. 10

 

Заметьте, что латинские квадраты в этих парах не получаются друг из друга перестановкой строк, как во всех приведённых выше группах взаимно ортогональных латинских квадратов. Однако мне удалось найти в Интернете одну пару ОЛК 10-го порядка, в которой квадраты получаются друг из друга перестановкой строк. Вы найдёте эту пару ОЛК в статье “Orthogonal Latin Squares of Order 10. Ортогональные латинские квадраты десятого порядка” (http://www.natalimak1.narod.ru/aspekty7.htm ). Правда, в этой паре ОЛК квадраты не диагональные. В указанной статье приведены также другие пары не диагональных ОЛК 10-го порядка.

Группу взаимно ортогональных латинских квадратов 11-го и 13-го порядков предлагаю составить читателям. Это простые числа и поэтому группы взаимно ортогональных латинских квадратов для данных порядков полные и состоят соответственно из 10 и 12 квадратов (см. в таблице на рис. 1: Q(11) = 10, Q(13) = 12).

Теперь рассмотрим порядок 12. В таблице написано, что Q(12) = 5. Значит, удалось составить группу из 5 взаимно ортогональных латинских квадратов 12-го порядка. Мне эта группа неизвестна. Я составила пару ОЛК 12-го порядка, которую показываю на рис. 11.

 

 

Рис. 11

 

Подробно построение этой пары ОЛК описано в статье http://www.natalimak1.narod.ru/aspekty6.htm

 

Кроме того, я составила пару ОЛК 12-го порядка методом составных квадратов. Покажу и эту пару (рис. 12):

 

 

Рис. 12

 

Подробно метод составных квадратов описан в статье http://www.natalimak1.narod.ru/olk.htm

 

Для порядка 15 мне тоже неизвестна группа из четырёх взаимно ортогональных латинских квадратов. Пары ОЛК для данного порядка мне удалось составить двумя способами. Первый способ: разложение известного идеального квадрата, построенного методом качелей, на два ортогональных латинских квадрата. Вы видите эту пару ОЛК на рис. 13 – 14.

 

 

Рис. 13

 

 

Рис. 14

 

Интересно отметить, что в этом примере второй латинский квадрат получается из первого отражением относительно горизонтальной оси симметрии. Таким приёмом строятся пары ОЛК во многих случаях. Иногда второй латинский квадрат в паре ОЛК получается из первого поворотом на 90 градусов (по или против ч. с.). Ещё возможно получить ортогональный квадрат отражением относительно главной диагонали (такой пример приведён в одной из частей статьи “Новые аспекты метода латинских квадратов”).

Второй способ составления пары ОЛК 15-го порядка – метод составных квадратов. Покажу и эту пару ОЛК (рис. 15 - 16):

 

 

Рис. 15

 

 

Рис. 16

 

Группу из 15 взаимно ортогональных латинских квадратов 16-го порядка, как уже знают читатели, умеет составлять Maple. Поскольку у меня нет этого пакета, я составила одну пару диагональных ОЛК 16-го порядка по аналогии с ОЛК 8-го порядка. Для построения магического квадрата мне хватило одной пары ОЛК. Вот эта пара:

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15            0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13            3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12

4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11            6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9

6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9            5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10           

8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7            12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3                      

10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5            15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0                      

12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3            10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5

14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1            9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6

9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6            7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8           

11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4            4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11

13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2            1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0            2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13

1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14            11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4

3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12            8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7

5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10            13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2

7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8            14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1

 

Предлагаю читателям составить другие латинские квадраты этой группы. Осталось составить 13 квадратов.

Для порядков 17 и 19 всё должно быть очень просто – эти порядка являются простыми числами.

Группа из трёх взаимно ортогональных латинских квадратов 18-го порядка мне тоже неизвестна. Пару ОЛК данного порядка мне удалось составить. Смотрите схему составления этой пары ОЛК в статье http://www.natalimak1.narod.ru/aspekty6.htm

 

На рис. 17 - 18 вы видите составленную мной пару ОЛК 18-го порядка.

 

 

Рис. 17

 

 

Рис. 18

 

Как видно из таблицы на рис. 1, Q(20) = 4. Эта группа взаимно ортогональных латинских квадратов мне неизвестна. Я составила только пару ОЛК 20-го порядка методом составных квадратов. Эта пара ОЛК показана на рис. 19 - 20. Латинские квадраты в этой паре диагональные.

 

 

Рис. 19

  

 

Рис. 20

 

Заключение

 

В рассмотренной группе порядков от 3 до 20 (исключая порядок 6) только для n = 14 мне пока не удалось составить даже пару ОЛК. Для других порядков мне неизвестны следующие группы взаимно ортогональных латинских квадратов:

 

·        группа из пяти MOLS 12-го порядка;

·        группа из трёх MOLS 14-го порядка;

·        группа из четырёх MOLS 15-го порядка;

·        группа из трёх MOLS 18-го порядка;

·        группа из четырёх MOLS 20-го порядка.

 

Примечание: аббревиатура MOLS означает Mutually Orthogonal Latin squares – взаимно ортогональные латинские квадраты; данная аббревиатура часто используется в англоязычных статьях.

 

Если читателям что-нибудь известно об этих группах MOLS, сообщите мне, пожалуйста. Ликвидируем сообща белые пятна!

 

Напомню читателям, что есть статья о составлении группы из трёх MOLS 14-го порядка: “Three Mutually Orthogonal Latin Squares of Order 14” (D. T. Todorov). Но я никак не могу разобраться в этой статье. Эта статья находится здесь:

http://www.natalimak1.narod.ru/mk/mols14.pdf

 

Далее, есть статья того же автора “Four Mutually Orthogonal Latin Squares of Order 20”. Понятно, что в этой статье описывается составление группы из четырёх взаимно ортогональных латинских квадратов 20-го порядка. Эту статью я даже не пыталась понять. Надо сначала разобраться с порядком 14. Думаю, что для порядка 20 всё аналогично. Итак, если разобраться в этих двух статьях, сразу можно ликвидировать два белых пятна в моих исследованиях.

 

В заключение отмечу, что самым “капризным” порядком оказался порядок 10. Посмотрите в таблицу на рис. 1, Q(10) = 2. Значит, найдены только пары MOLS 10-го порядка. Неужели не существует трёх взаимно ортогональных латинских квадратов данного порядка? Интересный вопрос!

Ещё интересен такой вопрос: являются ли все указанные значения Q(n) в таблице на рис. 1 действительно максимальными? Нельзя ли, найти, например, группу из шести MOLS 12-го порядка, или группу из четырёх MOLS 14-го порядка.

 

ДОБАВЛЕНИЕ (4 февраля 2009 г.)

 

На форуме dxdy.ru в теме “Магические квадраты” выложен очень интересный цикл статей “Анатомия магических квадратов” из журнала “Recreational Mathematics” (спешите скачать!). Цикл статей относится к 1938 - 1945 гг.

В этом цикле статей (стр. 206) я нашла замечательную пару ортогональных латинских квадратов 15-го порядка, из которой строятся два идеальных магических квадрата данного порядка. Кстати, наконец-то развеян созданный в Интернете миф о том, что первый в мире идеальный магический квадрат 15-го порядка был построен Г. Александровым в 2007 году.

 

Сначала приведу копию иллюстрации из журнала (рис. 21).

 

 

Рис. 21

 

Примечание: не удалось скопировать рисунок полностью, но вы сейчас увидите эти квадраты в моём изображении.

 

Интересно отметить, что перед латинскими квадратами дана схема, согласно которой строятся квадраты.

А теперь покажу эти латинские квадраты полностью (рис. 22 – 23).

 

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

 

 

Рис. 22

 

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

 

 

Рис. 23

 

Вот такие интересные ортогональные латинские квадраты! В статье говорится, что магический квадрат из данной пары квадратов А и В (так они обозначены в статье) можно построить двумя способами: А + 15В или 15А + В. Это и понятно, читатели уже знают, что в методе латинских квадратов первый и второй латинские квадраты можно менять местами в формуле для построения магического квадрата. Очевидно, что оба магических квадрата, построенных из данной пары ортогональных латинских квадратов, идеальные. Покажу один из этих квадратов (рис. 24):

 

 

Рис. 24

 

Далее интересен такой момент. Выше приведена пара ОЛК 15-го порядка, полученная мной путём разложения готового идеального магического квадрата 15-го порядка, построенного методом качелей (см. рис. 13 - 14). В этой паре ОЛК второй латинский квадрат получается из первого отражением относительно горизонтальной оси симметрии. Очевидно, что в паре ОЛК из журнала второй латинский квадрат не получается из первого таким способом. Однако если построить латинский квадрат из первого латинского квадрата с рис. 22 путём отражения относительно горизонтальной оси симметрии, то получится латинский квадрат ортогональный этому квадрату. Таким образом, мы имеем ещё одну пару ОЛК и можем построить ещё два идеальных магических квадрата 15-го порядка.

 

Но и это ещё не всё! Приведённая мной пара ОЛК и пара ОЛК из журнала изоморфны, то есть одна пара превращается в другую трансформацией тождественной перестановки чисел, вот такой:

 

0  1   2    3   4    5  6  7   8   9  10  11  12  13  14

       9  1  0   12  10  8  3  7  11  6   4    2   14   13   5

 

С помощью данной трансформации тождественной перестановки чисел я получила вторую пару ОЛК из своей пары, то есть построила другой латинский квадрат ортогональный первому латинскому квадрату и построенный по тому же принципу, как второй латинский квадрат в паре ОЛК из журнала. На рис. 25 вы видите этот латинский квадрат.

 

 

Рис. 25

 

Таким образом, мы имеем новую пару ОЛК 15-го порядка (квадрат с рис. 13 и квадрат с рис. 25) и можем построить ещё два идеальных магических квадрата.

Очевидно, что во всех идеальных магических квадратах, построенных из приведённых пар ОЛК, начальная цепочка имеет форму “ход конём”.

 

Далее в указанном цикле статей приводится ещё одна пара ортогональных латинских квадратов 15-го порядка (стр. 207), но уже обобщённых, а не классических. Построенные из этой пары ОЛК магические квадраты тоже идеальные, причём начальная цепочка в этих квадратах имеет совсем другую форму. То есть это совершенно новый вид идеальных магических квадратов 15-го порядка, который не получен ни Александровым, ни мной.

Есть в этих статьях и пары ОЛК 9-го порядка, из которых тоже строятся идеальные магические квадраты.

 

Продолжение читайте здесь:

 

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

 

 

19 - 21 января – 4 февраля 2009 г.

г. Саратов

 

       Пишите мне!

Приглашаю всех на форум!

На главную страницу