Введение

Математическая концепция

В математике матрица Хадамара, названная в честь французского математика Жака Хадамара, представляет собой квадратную матрицу, элементы которой равны либо +1, либо −1, и строки которой взаимно ортогональны. Геометрически это означает, что каждая пара строк в матрице Хадамара представляет собой два перпендикулярных вектора, а комбинаторно – что каждая пара строк имеет совпадающие элементы ровно в половине столбцов и различающиеся элементы в остальных столбцах. Из этого определения следует, что аналогичные свойства выполняются и для столбцов, и для строк. n-мерный параллелепипед, образованный строками n × n матрицы Хадамара, имеет максимально возможный n-мерный объем среди параллелепипедов, образованных векторами, абсолютные значения элементов которых ограничены единицей. Эквивалентно, матрица Хадамара имеет максимальный определитель среди матриц, элементы которых по абсолютной величине не превосходят 1, и, следовательно, является экстремальным решением задачи Хадамара о максимальном определителе. Некоторые матрицы Хадамара могут быть почти напрямую использованы в качестве кода коррекции ошибок, используя код Хадамара (обобщенный в кодах Рида — Мюллера), а также применяются в сбалансированном повторном воспроизведении (BRR), используемом статистиками для оценки дисперсии оценщика параметра.

Гипотеза Хадамарда

Самый важный открытый вопрос в теории матриц Адамара — вопрос о существовании. В частности, гипотеза Адамара утверждает, что матрица Адамара порядка 4k существует для каждого положительного целого числа k. Гипотеза Адамара также приписывается Пейли, хотя она рассматривалась неявно другими исследователями до работы Пейли. Обобщение конструкции Сильвестра доказывает, что если и — матрицы Адамара порядков n и m соответственно, то — матрица Адамара порядка nm. Этот результат используется для получения матриц Адамара более высокого порядка, как только известны матрицы меньшего порядка. Конструкция Сильвестра 1867 года позволяет получать матрицы Адамара порядков 1, 2, 4, 8, 16, 32 и т. д. Матрицы Адамара порядков 12 и 20 были впоследствии построены самим Адамаром (в 1893 году). В 1933 году Рэймонд Пейли открыл конструкцию Пейли, которая позволяет построить матрицу Адамара порядка q + 1, когда q — любое простое число в степени, сравнимое с 3 по модулю 4, и матрицу Адамара порядка 2(q + 1), когда q — простое число в степени, сравнимое с 1 по модулю 4. Его метод использует конечные поля. Наименьший порядок, который нельзя построить с помощью комбинации методов Сильвестра и Пейли, равен 92. Матрица Адамара этого порядка была найдена с помощью компьютера Баумертом, Голомбом и Холлом в 1962 году в JPL. Они использовали конструкцию, предложенную Уильямсоном, которая позволила получить множество других порядков. В настоящее время известно много других методов построения матриц Адамара. В 2005 году Хади Харагани и Бехруз Тайфех Резаи опубликовали свою конструкцию матрицы Адамара порядка 428. В результате, наименьший порядок, для которого в настоящее время не известна матрица Адамара, составляет 668. По состоянию на 2014 год существует 12 чисел, кратных 4 и меньших 2000, для которых не известна матрица Адамара соответствующего порядка. Это: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 и 1964.

Эквивалентность и уникальность

Две матрицы Хадамара считаются эквивалентными, если одну из них можно получить из другой путем изменения знака строк или столбцов, либо перестановкой строк или столбцов. С точностью до эквивалентности существует единственная матрица Хадамара порядков 1, 2, 4, 8 и 12. Существует 5 неэквивалентных матриц порядка 16, 3 порядка 20, 60 порядка 24 и 487 порядка 28. Миллионы неэквивалентных матриц известны для порядков 32, 36 и 40. При использовании более широкого понятия эквивалентности, допускающего также транспонирование, существует 4 неэквивалентных матрицы порядка 16, 3 порядка 20, 36 порядка 24 и 294 порядка 28. Матрицы Хадамара также могут быть однозначно восстановлены в следующем смысле: если в матрице Хадамара порядка n случайно удалены некоторые элементы, то с очень высокой вероятностью можно точно восстановить исходную матрицу по поврежденной. Сложность алгоритма восстановления сопоставима со сложностью инверсии матрицы.

Особые случаи

В математической литературе исследовано множество частных случаев матриц Адамара.

Матрицы Хадамарда

Матрица Хадамара H называется скошенной, если скошенная матрица Хадамара остается скошенной после умножения любой строки и соответствующего столбца на −1. Это позволяет, например, нормализовать скошенную матрицу Хадамара так, чтобы все элементы в первой строке были равны 1. Рид и Браун в 1972 году показали, что существует двукратно регулярный турнир порядка n тогда и только тогда, когда существует скошенная матрица Хадамара порядка n + 1. В математическом турнире порядка n каждый из n игроков играет по одному матчу с каждым из остальных игроков, и каждый матч заканчивается победой одного игрока и поражением другого. Турнир считается регулярным, если каждый игрок выигрывает одинаковое количество матчей. Регулярный турнир является двукратно регулярным, если число соперников, побежденных двумя различными игроками, одинаково для всех пар различных игроков. Поскольку каждый из n(n − 1)/2 сыгранных матчей заканчивается победой одного из игроков, каждый игрок выигрывает (n − 1)/2 матчей (и проигрывает столько же). Поскольку каждый из (n − 1)/2 игроков, проигравших данному игроку, также проигрывает (n − 3)/2 другим игрокам, число пар игроков (i, j), таких что j проигрывает и i, и данному игроку, равно (n − 1)(n − 3)/4. Тот же результат должен быть получен, если пары подсчитывать иначе: данный игрок и любой из n − 1 других игроков вместе побеждают одинаковое число общих противников. Следовательно, это общее число побежденных противников должно быть равно (n − 3)/4. Скошенная матрица Хадамара получается путем добавления дополнительного игрока, который побеждает всех исходных игроков, а затем формированием матрицы со строками и столбцами, обозначенными игроками, в соответствии с правилом, что элемент в строке i и столбце j равен 1, если i = j или i побеждает j, и −1, если j побеждает i. Это обратное соответствие позволяет построить двукратно регулярный турнир из скошенной матрицы Хадамара, при условии, что скошенная матрица Хадамара нормализована так, что все элементы первой строки равны 1.

Регулярные матрицы Хадамарда

Регулярные матрицы Хадамара — это вещественные матрицы Хадамара, у которых суммы строк и столбцов равны между собой. Необходимым условием существования регулярной матрицы Хадамара размера n × n является то, что n является полным квадратом. Циркулянтная матрица по определению регулярна, поэтому циркулянтная матрица Хадамара должна иметь квадратный порядок. Более того, если бы существовала циркулянтная матрица Хадамара размера n × n при n > 1, то n обязательно должно быть вида 4u², где u — нечётное число.

Матрицы Хадамарда

Однако гипотеза о циркулянтных матрицах Адамара утверждает, что, за исключением известных примеров 1 × 1 и 4 × 4, таких матриц не существует. Это было проверено для всех значений u меньше 104, кроме 26.

Обобщения

Одно из основных обобщений — весовая матрица. Весовая матрица — это квадратная матрица, элементы которой могут быть равны нулю и которая удовлетворяет условию для некоторого w, называемого её весом. Весовая матрица, вес которой равен её порядку, является матрицей Хадамара. Другое обобщение определяет комплексную матрицу Хадамара как матрицу, элементы которой — комплексные числа с единичным модулем, и которая удовлетворяет H H* = n In, где H* — сопряжённая транспонированная матрица H. Комплексные матрицы Хадамара возникают при изучении операторных алгебр и теории квантовых вычислений. Матрицы Хадамара типа Бутсона — это комплексные матрицы Хадамара, элементы которых являются q-ми корнями из единицы. Термин «комплексная матрица Хадамара» некоторыми авторами использовался для обозначения конкретно случая, когда q = 4.