Латинский квадрат

Лати́нский квадра́т — таблица n × n, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу). Ниже приводятся два примера:

${\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}$ ${\begin{bmatrix}A&B&C\\B&C&A\\C&A&B\\\end{bmatrix}}$

Латинские квадраты существуют для любого n.

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

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

Ортогональные латинские квадраты

Два латинских квадрата называются ортогональными, если различны все пары символов (a,b), где a — символ в некоторой клетке первого латинского квадрата, а b — символ в той же клетке второго латинского квадрата. Пример пары ортогональных латинских квадратов:

${\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}\quad \quad {\begin{bmatrix}1&2&3\\3&1&2\\2&3&1\\\end{bmatrix}}$

Легко видеть, что в соответствующем квадрате из пар все пары различны:

${\begin{bmatrix}11&22&33\\23&31&12\\32&13&21\\\end{bmatrix}}$

Ортогональные латинские квадраты существуют для любого порядка n кроме 2 и 6. Для n являющихся степенью простого числа есть набор n-1 попарно ортогональных латинских квадратов. Такой набор можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n.

Если в каждой диагонали латинского квадрата все элементы различны, такой латинский квадрат называется диагональным. Пары ортогональных диагональных латинских квадратов существуют для всех порядков, кроме 2, 3 и 6. Пример пары диагональных ортогональных латинских квадратов 5-го порядка:

${\begin{bmatrix}1&2&3&4&5\\5&3&4&1&2\\4&5&2&3&1\\2&4&1&5&3\\3&1&5&2&4\\\end{bmatrix}}\quad \quad {\begin{bmatrix}1&2&3&4&5\\4&5&2&3&1\\5&3&4&1&2\\3&1&5&2&4\\2&4&1&5&3\\\end{bmatrix}}$

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

Использование латинских квадратов для планирования экспериментов

Предположим, что нужно провести несколько экспериментов, зависящих от 3 параметров 1≤a,b,c≤n, так чтобы для каждой пары параметров были опробованы все n² вариантов. Тогда нужно взять любой латинский квадрат порядка n и провести n² экспериментов с параметрами a = номер строки, b = номер столбца, c = значение в клетке латинского квадрата.

Задача о заполнении латинского квадрата

Пусть дана таблица n × n, в которой некоторые ячейки пусты, а в некоторых стоят числа от 1 до n. Задача о заполнении латинского квадрата формулируется так: существует ли способ вписать числа в пустые ячейки так, чтобы полученная таблица стала латинским квадратом? Задача о заполнении латинского квадрата NP-полна. Однако, если заполнены несколько верхних строк, то квадрат всегда можно дополнить до латинского.

Ссылки

• http://www.natalimak1.narod.ru/aspekty5.htm Построение пар диагональных ОЛК методом составных квадратов
• http://www.natalimak1.narod.ru/aspekty7.htm Ортогональные латинские квадраты десятого порядка
• http://www.natalimak1.narod.ru/olk.htm Построение пар ортогональных латинских квадратов методом составных квадратов
• http://www.natalimak1.narod.ru/grolk.htm Группы взаимно ортогональных латинских квадратов
• http://www.natalimak1.narod.ru/arry.htm Построение взаимно ортогональных латинских квадратов из ортогонального массива
• http://www.natalimak1.narod.ru/mols12.htm Построение группы MOLS двенадцатого порядка
• http://www.natalimak1.narod.ru/mols14.htm Построение групп MOLS четырнадцатого порядка
• http://www.natalimak1.narod.ru/quazi.htm Подробно о квази-разностной матрице
• http://www.natalimak1.narod.ru/metod.htm Метод построения пар ортогональных латинских квадратов порядка 6k + 4
• http://dxdy.ru/topic15897.html Латинские квадраты
• http://www.mi.ras.ru/spm/pdf/011.pdf Леонард Эйлер и современная математика

См. также

• Судоку
• Магический квадрат
• Ортогональный массив