Латинские квадраты. Название «латинский квадрат» берёт начало от Леонарда Эйлера, который использовал латинские буквы вместо цифр в таблице.

Определение. Латинским квадратом порядка n называют квадратную матрицу размером nxn, элементы которой принадлежат множеству M = {1, 2, ..., n}, причем каждое число из M встречается ровно один раз в каждой строке и в каждом столбце.

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

Занимаясь греко-латинскими квадратами Эйлер доказал, что квадратов второго порядка не существует, зато были найдены квадраты 3, 4, и 5 порядков. Квадрата 6 порядка обнаружить не удалось, но доказать, что их не существует, Эйлеру не удалось. Но им была высказана гипотеза, что не существует квадрата порядка N, если N — чётное число, не делящееся на 4 (то есть 6, 10, 14 и т. д.).

В 1901 гипотеза была подтверждена для N=6 математиком Гастоном Терри. Это было сделано перебором всех возможных вариантов квадрата. А в 1959 году гипотеза была опровергнута Э. Т. Паркером, Р. К. Боусом и С. С. Шрикхердом, обнаружившими греко-латинский квадрат порядка 10.


00 47 18 76 29 93 85 34 61 52 
86 11 57 28 70 39 94 45 02 63 
95 80 22 67 38 71 49 56 13 04 
59 96 81 33 07 48 72 60 24 15 
73 96 90 82 44 17 58 01 35 26 
68 74 09 91 83 55 27 12 46 30 
37 08 75 19 92 84 66 23 50 41 
14 25 36 40 51 62 03 77 88 99 
21 32 43 54 65 06 10 89 97 78 
42 53 64 05 16 20 31 98 79 87

После были обнаружены квадраты 14, 18 и т. д. порядков.


A=['a' 'b' 'c'; 'b' 'c' 'a'; 'c' 'a' 'b'], 
B=['a' 'b' 'c'; 'c' 'a' 'b'; 'b' 'c' 'a'], 
C={A+B}, C=?,

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

M-матрицы. M-матрицы - ортогональные матрицы, максимум абсолютного значения элементов которых минимален на классе ортогональных матриц. Величина максимума называется m-нормой ортогональной матрицы. К M-матрицам относятся, в частности, матрицы Адамара и C-матрицы Белевича четных порядков, теория которых заслуживает отдельного внимания.

Аналитическое построение M-матриц нечетного порядка. Матрицы третьего и пятого порядков - нетрадиционный латинский и магический квадрат в том смысле, что суммы абсолютных значений элементов по строкам и строкам равны между собой и существует (n-1)/2 "диагоналей" по n элементов. Матрица третьего порядка имеет вид

A =
a b b
b ±a ±b
b ±b ±a

Условие ортогональности диктует ab±ab±bb=0 или 2a-b=0 при b≠0 знак при a положительный (а при b - отрицательный), откуда b=2a. В данном случае 2, не есть продукт оптимизации, получена постулированием.

M-матрица 5-го порядка такова

A =
2 6 6 6 3
3 2 6 -6 -6
6 -3 -2 6 -6
6 -6 3 -2 6
6 6 -6 -3 2


A=[2 6 6 6 3;3 2 6 -6 -6;6 -3 -2 6 -6;6 -6 3 -2 6;6 6 -6 -3 2], 
Q={A'*A}, mesh(Q), S=sum(A), S=?

Суммы элементов, кстати, убывают!

Сравним с классическим латинским квадратом пятого порядка, полученным циклическим сдвигом столбца

A =
1 5 4 3 2
2 1 5 4 3
3 2 1 5 4
4 3 2 1 5
5 4 3 2 1

Замечательно тут то, что первый явно аппроксимируется вторым при замене 1 на a, 2 на b и {3,4,5} на с.

A =
a c c c b
b ±a ±c ±c ±c
c ±b ±a ±c ±c
c ±c ±b ±a ±c
c ±c ±c ±b ±a

Еще. По суммам элементов наиболее неуравновешен первый столбец или строка. Последние столбцы ли строки - напротив, выведены почти в 0. Поэтому там игра знаков при c.

Условие ортогональности (ранее хватило одного уравнения) - поэлементное умножение строчек с суммированием дает 0, для первых двух (более мотивировано было бы - первого и последнего, но и этого пока хватило)

ba±ac±cc±cc±cb=0 или ba±ac±cb=0

пусть ±cc±cc уйдет в 0 (как самое большое), cb компенсируется суммой ba+ac=cb, так как a - малое число. Правило знаков почти поймано, для поиска соотношений достаточно еще одного уравнения, скрестим первое с третьим

ca±bc±ac±cc±cb=0 или ±b±c±b=0

предположив, что ca±ac=0, т.е. минус, откуда с=2b, т.к. c>b, и тогда первое уравнение дает b=3a/2.

с=2b, b=3a/2

и есть точное решение этой задачи.



Rambler's Top100