Н. Макарова

 

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

 

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