Н.Макарова

 

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

 

Доказано, что существование t взаимно ортогональных латинских квадратов порядка n эквивалентно существованию ортогонального массива ОА(t+2,n) (см., например, книгу М. Холла “Комбинаторика”, М.: Мир, 1970). Под ортогональным массивом ОА(t+2,n) понимается матрица размером (t+2)хn², состоящая из элементов 0, 1, 2, … n-1, все строки которой взаимно ортогональны.  Взаимная ортогональность строк матрицы определяется следующим образом:

если a = (a₁, a₂, a₃, … a_n^2), b = (b₁, b₂, b₃, … b_n^2) любые две строки матрицы, то каждая пара (x,y) (x, y есть любые элементы из 0, 1, 2, … n-1) встречается ровно один раз среди пар (a_i,b_i).

 

Чтобы лучше понять определение ортогонального массива, приведу два конкретных примера.

Пример 1. Ортогональный массив ОА(4,3) для двух ортогональных латинских квадратов 3-го порядка (рис. 1).

 

 

Рис. 1

 

Пример 2. Ортогональный массив ОА(5,4) для трёх ортогональных латинских квадратов 4-го порядка (рис. 2).

 

 

Рис. 2

 

Если известен ортогональный массив, группу взаимно ортогональных латинских квадратов построить очень легко. Покажу это на примере ортогонального массива, изображённого на рис. 2. Первые две строки сверху в ортогональном массиве – это координаты. Теперь берём первый столбец ортогонального массива. Первое число в столбце (считая сверху) – координата x, второе число в столбце – координата y; далее идут числа, записанные в ячейке с такими координатами, в первом, втором и третьем латинском квадрате соответственно. Конкретно из первого столбца имеем: в ячейке с координатами (0,0) во всех трёх латинских квадратах запишется число 0. По последнему столбцу ортогонального массива имеем: в ячейку с координатами (3,3) в первом латинском квадрате запишется число 1, во втором латинском квадрате – число 2, в третьем латинском квадрате – число 0 [система координат (x,y) имеет положительную полуось x, направленную вправо, и положительную полуось y, направленную вниз]. На рис. 3 вы видите группу из трёх взаимно ортогональных латинских квадратов 4-го порядка, построенных по данному ортогональному массиву с рис. 2.

 

 

Рис. 3

 

Теперь, когда известно, как из ортогонального массива построить сами ортогональные латинские квадраты, мне удалось построить пары ОЛК 14-го и 26-го порядков, используя описанные в указанной выше книге Холла ортогональные массивы. Покажу эти пары ОЛК, очень интересный результат! Сначала подробно опишу построение ортогонального массива по книге Холла (стр. 279).

Для построения ортогонального массива ОА(4,14) берётся следующая матрица P₀ (рис. 4):

 

 

Рис. 4

 

 Далее строятся матрицы P₁, P₂, P₃ путём циклической перестановки строк в матрице P_0. Матрица A₀ = (P₀,P₁,P₂,P₃). Матрицы A_i (i = 1, 2, …, 10) получаются из матрицы A₀ прибавлением i по модулю 11 к каждому числу в A₀ (за исключением неизвестных x₁, x₂, x₃)_. Матрица A = (A₀, A₁, A₂,…,A₁₀). Матрица B есть ОА(4,3) относительно x₁, x₂, x₃. Наконец, матрица E есть матрица размером 4х11, i-ый столбец которой содержит на каждом месте i.

Искомый ортогональный массив ОА(4,14) = (E,A,B).

На этом Холл заканчивает построение ортогонального массива. Я продолжу подробнее. Сначала покажу матрицу Е. Это очень простая матрица (рис. 5):

 

 

Рис. 5

 

На рис. 6 вы видите ОА(4,3) относительно x₁, x₂, x₃, это матрица В.

 

 

Рис. 6

 

Осталось показать матрицы A_i, из которых образуется матрица А. Не буду показывать все матрицы  A_i, покажу только первые три матрицы (рис. 7–9) и последнюю матрицу (рис. 10). Все остальные матрицы строятся аналогично.

 

Матрица А₀

 

 

Рис. 7

 

Матрица А₁

 

 

Рис. 8

 

Матрица А₂

 

 

Рис. 9

 

Матрица А₁₀

 

 

Рис. 10

 

Всё готово для построения ОА(4,14). На рис. 11 вы видите фрагмент этого массива. Понятно, что эта матрица имеет размер 4х196.

 

 

Рис. 11

 

По готовому ортогональному массиву очень просто построить пару ОЛК 14-го порядка. Как это делается, показано в начале статьи. На рис. 12 показан первый латинский квадрат из этой пары ОЛК, а на рис. 13 – второй латинский квадрат.

 

 

Рис. 12

 

 

Рис. 13

 

Вам ничего не напоминает это построение? Это же очень похоже на алгоритм построения пары ОЛК 10-го порядка! Посмотрите: тоже есть латинский подквадрат 3-го порядка, есть переменные x₁, x₂, x₃.

Закономерности заполнения квадратов очевидны: заполнение в угловом квадрате 11х11 идёт по диагонали, числа записываются в порядке возрастания, после числа 10 пишется число 0. При достижении краёв квадрата диагональ продолжается с другого края квадрата (как если бы квадрат был свёрнут в трубочку по вертикальной или по горизонтальной оси).

Понятно, что переменные x₁, x₂, x₃ могут принимать значения 11, 12, 13 в любой комбинации. Значит, можно построить 6 подобных пар ОЛК. На рис. 14 – 15 показана одна из этих пар с такими значениями переменных: x₁ = 11, x₂ = 12, x₃ = 13.

 

 

Рис. 14

 

 

Рис. 15

 

Кроме того, можно варьировать латинские подквадраты 3-го порядка (на рис. 14-15 подквадраты выделены жёлтым цветом). Понятно, что эти подквадраты тоже должны быть ортогональны. Следует отметить, что варьирование латинских подквадратов 3-го порядка даёт существенно новые, неизоморфные пары ОЛК.

 

Итак, пара ОЛК 14-го порядка получена. Очевидно, что латинские квадраты в этой паре не диагональные (и суммы чисел в диагоналях не равны 91), поэтому пара не пригодна для построения магических квадратов. Надо её преобразовать. Первый латинский квадрат преобразовываю с помощью такой трансформации тождественной перестановки чисел:

 

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

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

 

Полученный в результате этого преобразования латинский квадрат изображён на рис. 16.

 

 

Рис. 16

 

Преобразовываю второй латинский квадрат с помощью такой трансформации тождественной перестановки чисел:

 

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

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

 

На рис. 17 вы видите преобразованный второй латинский квадрат.

 

 

Рис. 17

 

Теперь оба латинских квадрата являются нетрадиционными магическими квадратами с магической константой 91. Из этой пары можно построить два магических квадрата, меняя местами латинские квадраты. На рис. 18 показан один из этих магических квадратов. Это первый магический квадрат 14-го порядка, построенный методом латинских квадратов (из пары ортогональных классических латинских квадратов).

 

 

Рис. 18

 

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

 

Далее в книге Холла приведён пример построения ортогонального массива для пары ОЛК 26-го порядка. Исходная матрица для этого построения показана на рис. 19.

 

 

Рис. 19

 

Дальше всё делается совершенно аналогично построению ортогонального массива для латинских квадратов 14-го порядка. Чтобы построить пару ОЛК 26-го порядка, мне оказалось достаточно одной матрицы A₀. Показываю эту матрицу на рис. 20.

 

 

Рис. 20

 

Ортогональные латинские квадраты сразу даю для конкретных значений переменных: x₁ = 23, x₂ = 24, x₃ = 25. Готовые латинские квадраты из полученной пары ОЛК изображены на рис. 21-22.

 

Первый латинский квадрат 26-го порядка

 

 

Рис. 21

 

Второй латинский квадрат 26-го порядка