Матрица Адамара

Концепция математики

Гилберт Стрэнг демонстрирует гипотезу Адамара в Массачусетском технологическом институте в 2005 году, используя конструкцию Сильвестра.

В математике матрица Адамара , названная в честь французского математика Жака Адамара , представляет собой квадратную матрицу , элементы которой равны +1 или -1 и строки которой взаимно ортогональны . С геометрической точки зрения это означает, что каждая пара строк в матрице Адамара представляет два перпендикулярных вектора , а с комбинаторной точки зрения это означает, что каждая пара строк имеет совпадающие записи ровно в половине своих столбцов и несовпадающие записи в остальных столбцах. Следствием этого определения является то, что соответствующие свойства справедливы как для столбцов, так и для строк.

n -мерный параллелоэдр , натянутый строками матрицы Адамара размера n  ×  n, имеет максимально возможный n -мерный объем среди параллелоэдров , натянутых на вектора, элементы которых ограничены по абсолютной величине единицей. Эквивалентно, матрица Адамара имеет максимальный определитель среди матриц с записи с абсолютным значением, меньшим или равным 1, и поэтому являются экстремальным решением проблемы максимального определителя Адамара .

Определенные матрицы Адамара можно почти напрямую использовать в качестве кода исправления ошибок с использованием кода Адамара (обобщенного в кодах Рида-Мюллера ), а также использовать их в сбалансированной повторной репликации (BRR), используемой статистиками для оценки дисперсии средства оценки параметров . .

Характеристики

Пусть H — матрица Адамара порядка n . Транспонирование H тесно связано с его инверсией . Фактически:

${\displaystyle HH^{\textsf {T}}=nI_{n}}$

где I _n — единичная матрица размера n  ×  n , а HT ^— транспонированная H . Чтобы убедиться в этом, обратите внимание, что все строки H являются ортогональными векторами над полем действительных чисел и каждая из них имеет длину. Деление H на эту длину дает ортогональную матрицу , транспонирование которой, таким образом, является ее обратной. Умножение на длину еще раз дает равенство, указанное выше. Как результат, ${\displaystyle {\sqrt {n}}\,.}$

${\displaystyle \operatorname {det} (H)=\pm \,n^{n/2},}$

где det( H ) — определитель H .

Предположим, что M — комплексная матрица порядка n , элементы которой ограничены | М _дж  | ≤ 1, для каждого i , j между 1 и n . Тогда оценка определителя Адамара утверждает, что

${\displaystyle |\operatorname {det} (M)|\leq n^{n/2}.}$

Равенство в этой оценке достигается для вещественной матрицы M тогда и только тогда, когда M — матрица Адамара.

Порядок матрицы Адамара должен быть 1, 2 или кратен 4. ^[1]

Строительство Сильвестра

Примеры матриц Адамара были впервые построены Джеймсом Джозефом Сильвестром в 1867 году. Пусть H — матрица Адамара порядка n . Тогда разбитая матрица

${\displaystyle {\begin{bmatrix}H&H\\H&-H\end{bmatrix}}}$

является матрицей Адамара порядка 2 n . Это наблюдение можно применять неоднократно и приводит к следующей последовательности матриц, также называемых матрицами Уолша .

${\displaystyle {\begin{aligned}H_{1}&={\begin{bmatrix}1\end{bmatrix}},\\H_{2}&={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},\\H_{4}&={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}},\end{aligned}}}$

и

${\displaystyle H_{2^{k}}={\begin{bmatrix}H_{2^{k-1}}&H_{2^{k-1}}\\H_{2^{k-1}}&-H_{2^{k-1}}\end{bmatrix}}=H_{2}\otimes H_{2^{k-1}},}$

для , где обозначает произведение Кронекера . ${\displaystyle 2\leq k\in N}$ ${\displaystyle \otimes }$

Таким образом Сильвестр построил матрицы Адамара порядка 2 ^k для каждого неотрицательного целого числа k . ^[2]

Матрицы Сильвестра обладают рядом особых свойств. Они симметричны и при k  ≥ 1 (2 ^k  > 1) имеют нулевой след . Все элементы в первом столбце и первой строке положительны. Элементы во всех остальных строках и столбцах поровну разделены на положительные и отрицательные . Матрицы Сильвестра тесно связаны с функциями Уолша .

Альтернативное строительство

Если мы отобразим элементы матрицы Адамара с помощью группового гомоморфизма , мы сможем описать альтернативную конструкцию матрицы Адамара Сильвестра. Сначала рассмотрим матрицу , столбцы которой состоят из всех n -битных чисел, расположенных в порядке возрастания. Мы можем определить рекурсивно с помощью ${\displaystyle (\{1,-1\},\times )\mapsto (\{0,1\}),\oplus \}}$ ${\displaystyle F_{n}}$ ${\displaystyle n\times 2^{n}}$ ${\displaystyle F_{n}}$

${\displaystyle {\begin{aligned}F_{1}&={\begin{bmatrix}0&1\end{bmatrix}}\\F_{n}&={\begin{bmatrix}0_{1\times 2^{n-1}}&1_{1\times 2^{n-1}}\\F_{n-1}&F_{n-1}\end{bmatrix}}.\end{aligned}}}$

По индукции можно показать , что образ матрицы Адамара при указанном выше гомоморфизме имеет вид

${\displaystyle H_{2^{n}}=F_{n}^{\textsf {T}}F_{n}.}$

Эта конструкция демонстрирует , что строки матрицы Адамара можно рассматривать как линейный по длине код с исправлением ошибок ранга n и минимального расстояния с порождающей матрицей ${\displaystyle H_{2^{n}}}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n-1}}$ ${\displaystyle F_{n}.}$

Этот код также называют кодом Уолша . Код Адамара , напротив, строится из матрицы Адамара с помощью несколько иной процедуры. ${\displaystyle H_{2^{n}}}$

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

Нерешенная задача по математике :

Существует ли матрица Адамара порядка 4 k для каждого натурального числа k ?

(еще нерешенные задачи по математике)

Самый важный открытый вопрос в теории матриц Адамара — вопрос существования. В частности, гипотеза Адамара предполагает, что матрица Адамара порядка 4 k существует для каждого положительного целого числа k . Гипотеза Адамара также приписывалась Пейли, хотя до работы Пейли она неявно рассматривалась другими. ^[3]

Обобщение конструкции Сильвестра доказывает, что если и являются матрицами Адамара порядков n и m соответственно, то является матрицей Адамара порядка nm . Этот результат используется для создания матриц Адамара более высокого порядка, если известны матрицы меньшего порядка. ${\displaystyle H_{n}}$ ${\displaystyle H_{m}}$ ${\displaystyle H_{n}\otimes H_{m}}$

Конструкция Сильвестра 1867 года дает матрицы Адамара порядка 1, 2, 4, 8, 16, 32 и т. д. Матрицы Адамара порядков 12 и 20 были впоследствии построены Адамаром (в 1893 году). ^[4] В 1933 году Рэймонд Пейли открыл конструкцию Пэли , которая дает матрицу Адамара порядка q + 1, когда q — любая степень простого числа , конгруэнтную 3 по модулю 4, и которая дает матрицу Адамара порядка 2 ( q + 1) когда q является простой степенью, которая равна 1 по модулю 4. ^[5] Его метод использует конечные поля .

Наименьший порядок, который невозможно построить комбинацией методов Сильвестра и Пэли, равен 92. Матрица Адамара этого порядка была найдена с помощью компьютера Баумертом, Голомбом и Холлом в 1962 году в Лаборатории реактивного движения . ^[6] Они использовали конструкцию Уильямсона , [ ^7] которая принесла много дополнительных заказов. Сейчас известны многие другие методы построения матриц Адамара.

В 2005 году Хади Харагани и Бехруз Тайфе-Резаи опубликовали свою конструкцию матрицы Адамара порядка 428. ^[8] В результате наименьший порядок, для которого в настоящее время не известна матрица Адамара, равен 668.

К 2014 году существовало 12 чисел, кратных 4 меньше 2000, для которых не была известна матрица Адамара этого порядка. ^[9] Это: 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. ^{[ 10]}

Матрицы Адамара также однозначно восстанавливаемы в следующем смысле: если в матрице порядка Адамара есть случайно удаленные элементы, то с подавляющей вероятностью можно идеально восстановить исходную матрицу из поврежденной. Алгоритм восстановления имеет те же вычислительные затраты, что и обращение матрицы. ^[11] ${\displaystyle H}$ ${\displaystyle n}$ ${\displaystyle O(n^{2}/\log n)}$ ${\displaystyle H}$

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

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

Перекос матрицы Адамара

Матрица Адамара H является косой , если косая матрица Адамара остается косой матрицей Адамара после умножения любой строки и соответствующего ей столбца на -1. Это позволяет, например, нормализовать косую матрицу Адамара так, чтобы все элементы в первой строке были равны 1. ${\displaystyle H^{\textsf {T}}+H=2I.}$

Рид и Браун в 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. ^[12]

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

Регулярные матрицы Адамара — это действительные матрицы Адамара, суммы строк и столбцов которых равны. Необходимым условием существования регулярной матрицы Адамара размера n  ×  n является то, что n — квадратное число . Циркулянтная матрица явно регулярна, и поэтому циркулянтная матрица Адамара должна быть квадратного порядка. Более того, если бы существовала циркулянтная матрица Адамара размера n  ×  n с n > 1, то n обязательно должно было бы иметь вид 4 u ² с u нечетным. ^{[13] [14]}

Циркулянтные матрицы Адамара

Гипотеза о циркулянтной матрице Адамара, однако, утверждает, что, кроме известных примеров 1 × 1 и 4 × 4, таких матриц не существует. Это было проверено для всех значений u меньше 10 ⁴ , кроме 26 . ^[15]

Обобщения

Одним из основных обобщений является весовая матрица . Матрица взвешивания — это квадратная матрица, в которой элементы также могут быть нулевыми и которая для некоторого w удовлетворяет своему весу. Весовая матрица, вес которой равен ее порядку, является матрицей Адамара. ^[16] ${\displaystyle WW^{\textsf {T}}=wI}$

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

Практическое применение

• Olivia MFSK – цифровой радиолюбительский протокол, предназначенный для работы в сложных (низкое соотношение сигнал/шум плюс многолучевое распространение) условиях на коротковолновых диапазонах.
• Сбалансированная повторная репликация (BRR) — метод, используемый статистиками для оценки дисперсии статистической оценки .
• Спектрометрия с кодированной апертурой – прибор для измерения спектра света . Элемент маски, используемый в спектрометрах с кодированной апертурой, часто представляет собой вариант матрицы Адамара.
• Сети задержки с обратной связью - цифровые устройства реверберации, которые используют матрицы Адамара для смешивания значений выборки.
• Планирование экспериментов Плакетта–Бермана для исследования зависимости некоторой измеряемой величины от ряда независимых переменных .
• Надежные конструкции параметров для исследования влияния фактора шума на отклики
• Сжатое зондирование для обработки сигналов и недоопределенных линейных систем (обратные задачи)
• Квантовые ворота Адамара для квантовых вычислений и преобразование Адамара для квантовых алгоритмов.

Смотрите также

• Комбинаторный дизайн
• Преобразование Адамара
• Матрица Квинконкса
• Матрица Уолша
• Матрица взвешивания
• Квантовый логический вентиль

Примечания

1. «Матрицы и схемы Адамара» (PDF) . Калифорнийский университет в Денвере . Проверено 11 февраля 2023 г.
2. Джей Джей Сильвестр. Мысли об обратных ортогональных матрицах, одновременной последовательности знаков и мозаичных тротуарах двух или более цветов с применением к правилу Ньютона, орнаментальной плитке и теории чисел. Философский журнал , 34: 461–475, 1867 г.
3. Хедаят, А.; Уоллис, WD (1978). «Матрицы Адамара и их приложения». Анналы статистики . 6 (6): 1184–1238. дои : 10.1214/aos/1176344370 . JSTOR  2958712. MR  0523759..
4. Адамар, Дж. (1893). «Решение вопроса об относительных определяющих факторах». Бюллетень математических наук . 17 : 240–246.
5. Пейли, REAC (1933). «Об ортогональных матрицах». Журнал математики и физики . 12 (1–4): 311–320. дои : 10.1002/sapm1933121311.
6. Баумерт, Л.; Голомб, Юго-Запад; Холл, М. младший (1962). «Открытие матрицы Адамара порядка 92». Бюллетень Американского математического общества . 68 (3): 237–238. дои : 10.1090/S0002-9904-1962-10761-7 . МР  0148686.
7. Уильямсон, Дж. (1944). «Определительная теорема Адамара и сумма четырех квадратов». Математический журнал Дьюка . 11 (1): 65–81. дои : 10.1215/S0012-7094-44-01108-7. МР  0009590.
8. Харагани, Х.; Тайфе-Резаи, Б. (2005). «Матрица Адамара порядка 428». Журнал комбинаторных проектов . 13 (6): 435–440. дои : 10.1002/jcd.20043. S2CID  17206302.
9. Джокович, Драгомир Ž; Голубицкий Олег; Коциреас, Илиас С. (2014). «Некоторые новые порядки матриц Адамара и Скью-Адамара». Журнал комбинаторных проектов . 22 (6): 270–277. arXiv : 1301.3671 . дои : 10.1002/jcd.21358. S2CID  26598685.
10. Ванлесс, IM (2005). «Перманенты матриц знаковых». Линейная и полилинейная алгебра . 53 (6): 427–433. дои : 10.1080/03081080500093990. S2CID  121547091.
11. Клайн, Дж. (2019). «Геометрический поиск матриц Адамара». Теоретическая информатика . 778 : 33–46. дои : 10.1016/j.tcs.2019.01.025 . S2CID  126730552.
12. Рид, КБ; Браун, Эзра (1972). «Дважды регулярные турниры эквивалентны перекосу матрицы Адамара». Журнал комбинаторной теории, серия А. 12 (3): 332–338. дои : 10.1016/0097-3165(72)90098-2 .
13. Турин, Р.Дж. (1965). «Суммы символов и наборы разностей». Тихоокеанский математический журнал . 15 (1): 319–346. дои : 10.2140/pjm.1965.15.319 . МР  0179098.
14. Турин, Р.Дж. (1969). «Последовательности с малой корреляцией». В Манне, HB (ред.). Коды исправления ошибок . Нью-Йорк: Уайли. стр. 195–228.
15. Шмидт, Б. (1999). «Циклотомические целые числа и конечная геометрия». Журнал Американского математического общества . 12 (4): 929–952. дои : 10.1090/S0894-0347-99-00298-2 . hdl : 10356/92085 . JSTOR  2646093.
16. Герамита, Энтони В.; Пуллман, Норман Дж.; Уоллис, Дженнифер С. (1974). «Семейства весовых матриц». Бюллетень Австралийского математического общества . 10 (1). Издательство Кембриджского университета (CUP): 119–122. дои : 10.1017/s0004972700040703. ISSN  0004-9727. S2CID  122560830.

дальнейшее чтение

• Баумерт, Л.Д.; Холл, Маршалл (1965). «Матрицы Адамара типа Вильямсона». Математика. Комп . 19 (91): 442–447. дои : 10.1090/S0025-5718-1965-0179093-2 . МР  0179093.
• Георгиу, С.; Кукувинос, К.; Себерри, Дж. (2003). «Матрицы Адамара, ортогональные конструкции и алгоритмы построения». Designs 2002: Дальнейшая вычислительная и конструктивная теория проектирования . Бостон: Клювер. стр. 133–205. ISBN 978-1-4020-7599-5.
• Гетальс, Дж. М.; Зайдель, Джей-Джей (1970). «Скошенная матрица Адамара порядка 36». Дж. Аустрал. Математика. Соц . 11 (3): 343–344. дои : 10.1017/S144678870000673X. S2CID  14193297.
• Кимура, Хироши (1989). «Новая матрица Адамара 24-го порядка». Графы и комбинаторика . 5 (1): 235–242. дои : 10.1007/BF01788676. S2CID  39169723.
• Настроение, Александр Михайлович (1964). «О проблеме взвешивания Хотеллинга». Анналы математической статистики . 17 (4): 432–446. дои : 10.1214/aoms/1177730883 .
• Рид, КБ; Браун, Э. (1972). «Дважды регулярные турниры эквивалентны перекосу матрицы Адамара». Дж. Комбин. Теория Сер. А.​ 12 (3): 332–338. дои : 10.1016/0097-3165(72)90098-2 .
• Себерри Уоллис, Дженнифер (1976). «О существовании матриц Адамара». Дж. Комб. Теория А. 21 (2): 188–195. дои : 10.1016/0097-3165(76)90062-5 .
• Себерри, Дженнифер (1980). «Конструкция обобщенных матриц Адамара». Дж. Статист. План. Сделайте вывод . 4 (4): 365–368. дои : 10.1016/0378-3758(80)90021-X.
• Себерри, Дж.; Высоцкий, Б.; Высоцкий, Т. (2005). «О некоторых приложениях матриц Адамара». Метрика . 62 (2–3): 221–239. doi : 10.1007/s00184-005-0415-y. S2CID  40646.
• Спенс, Эдвард (1995). «Классификация матриц Адамара 24 и 28 порядка». Дискретная математика . 140 (1–3): 185–242. дои : 10.1016/0012-365X(93)E0169-5 .
• Ярлагадда, РК; Херши, Дж. Э. (1997). Анализ и синтез матрицы Адамара . Бостон: Клювер. ISBN 978-0-7923-9826-4.

Внешние ссылки

• Раскачать матрицы Адамара всех порядков до 100, включая все типы с порядком до 28;
• «Матрица Адамара».в ОЭИС
• НЯА Слоан . «Библиотека матриц Адамара».
• Онлайн-утилита для получения всех заказов до 1000, кроме 668, 716, 876 и 892.
• R-Пакет для генерации матриц Адамара с использованием R
• Лаборатория реактивного движения: В 1961 году математики из Лаборатории реактивного движения НАСА и Калифорнийского технологического института работали вместе над построением матрицы Адамара, содержащей 92 строки и столбца.