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

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

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

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

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

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

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

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

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

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

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

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

Предположим, что M — комплексная матрица порядка n , элементы которой ограничены | M _ij  | ≤ 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 }$

Таким образом, Сильвестр построил матрицы Адамара порядка 2k ^для каждого неотрицательного целого числа 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}}}$

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

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

Существует ли матрица Адамара порядка 4k для каждого положительного целого числа 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 году в JPL . ^[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, таких матриц не существует. Это было проверено для всех, кроме 26 значений u , меньших 10 ⁴ . ^[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. JJ Sylvester. Размышления об обратных ортогональных матрицах, одновременных последовательностях знаков и мозаичных мостовых в два или более цветов, с приложениями к правилу Ньютона, орнаментальной плитке и теории чисел. Philosophical Magazine , 34:461–475, 1867
3. Хедаят, А.; Уоллис, У. Д. (1978). «Матрицы Адамара и их приложения». Annals of Statistics . 6 (6): 1184–1238. doi : 10.1214/aos/1176344370 . JSTOR  2958712. MR  0523759..
4. Адамар, Дж. (1893). «Решение вопроса относительно определяющих факторов». Бюллетень математических наук . 17 : 240–246.
5. Paley, REAC (1933). «Об ортогональных матрицах». Журнал математики и физики . 12 (1–4): 311–320. doi :10.1002/sapm1933121311.
6. Baumert, L.; Golomb, SW; Hall, M. Jr. (1962). «Открытие матрицы Адамара порядка 92». Бюллетень Американского математического общества . 68 (3): 237–238. doi : 10.1090/S0002-9904-1962-10761-7 . MR  0148686.
7. Уильямсон, Дж. (1944). «Теорема Адамара об определителе и сумма четырех квадратов». Duke Mathematical Journal . 11 (1): 65–81. doi :10.1215/S0012-7094-44-01108-7. MR  0009590.
8. Харагани, Х.; Тайфе-Резаи, Б. (2005). «Матрица Адамара порядка 428». Журнал комбинаторных конструкций . 13 (6): 435–440. doi :10.1002/jcd.20043. S2CID  17206302.
9. Джокович, Драгомир Ž; Голубицкий Олег; Коциреас, Илиас С. (2014). «Некоторые новые порядки матриц Адамара и Скью-Адамара». Журнал комбинаторных проектов . 22 (6): 270–277. arXiv : 1301.3671 . дои : 10.1002/jcd.21358. S2CID  26598685.
10. Wanless, IM (2005). «Перманенты матриц знаковых единиц». Линейная и полилинейная алгебра . 53 (6): 427–433. doi :10.1080/03081080500093990. S2CID  121547091.
11. Клайн, Дж. (2019). «Геометрический поиск матриц Адамара». Теоретическая информатика . 778 : 33–46. doi : 10.1016/j.tcs.2019.01.025 . S2CID  126730552.
12. Рид, КБ; Браун, Эзра (1972). «Дважды регулярные турниры эквивалентны косым матрицам Адамара». Журнал комбинаторной теории, Серия A. 12 ( 3): 332–338. doi : 10.1016/0097-3165(72)90098-2 .
13. Turyn, RJ (1965). «Суммы символов и разностные множества». Pacific Journal of Mathematics . 15 (1): 319–346. doi : 10.2140/pjm.1965.15.319 . MR  0179098.
14. Turyn, RJ (1969). «Последовательности с малой корреляцией». В Mann, HB (ред.). Коды исправления ошибок . Нью-Йорк: Wiley. С. 195–228.
15. Шмидт, Б. (1999). «Циклотомические целые числа и конечная геометрия». Журнал Американского математического общества . 12 (4): 929–952. doi : 10.1090/S0894-0347-99-00298-2 . hdl : 10356/92085 . JSTOR  2646093.
16. Geramita, Anthony V.; Pullman, Norman J.; Wallis, Jennifer S. (1974). «Семейства весовых матриц». Бюллетень Австралийского математического общества . 10 (1). Cambridge University Press (CUP): 119–122. doi :10.1017/s0004972700040703. ISSN  0004-9727. S2CID  122560830.

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

• Баумерт, Л. Д.; Холл, Маршалл (1965). «Матрицы Адамара типа Уильямсона». Math. Comp . 19 (91): 442–447. doi : 10.1090/S0025-5718-1965-0179093-2 . ​​MR  0179093.
• Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). «Матрицы Адамара, ортогональные конструкции и алгоритмы построения». Designs 2002: Дальнейшая вычислительная и конструктивная теория проектирования . Бостон: Kluwer. С. 133–205. ISBN 978-1-4020-7599-5.
• Goethals, JM; Seidel, JJ (1970). «Скошенная матрица Адамара порядка 36». J. Austral. Math. Soc . 11 (3): 343–344. doi :10.1017/S144678870000673X. S2CID  14193297.
• Кимура, Хироши (1989). «Новая матрица Адамара порядка 24». Графы и комбинаторика . 5 (1): 235–242. doi :10.1007/BF01788676. S2CID  39169723.
• Mood, Alexander M. (1964). «О задаче взвешивания Хотеллинга». Annals of Mathematical Statistics . 17 (4): 432–446. doi : 10.1214/aoms/1177730883 .
• Рид, КБ; Браун, Э. (1972). «Дважды регулярные турниры эквивалентны перекошенным матрицам Адамара». J. Combin. Theory Ser. A . 12 (3): 332–338. doi : 10.1016/0097-3165(72)90098-2 .
• Seberry Wallis, Jennifer (1976). «О существовании матриц Адамара». J. Comb. Theory A. 21 ( 2): 188–195. doi : 10.1016/0097-3165(76)90062-5 .
• Seberry, Jennifer (1980). «Конструкция для обобщенных матриц Адамара». J. Statist. Plann. Infer . 4 (4): 365–368. doi :10.1016/0378-3758(80)90021-X.
• Seberry, J.; Wysocki, B.; Wysocki, T. (2005). «О некоторых приложениях матриц Адамара». Metrika . 62 (2–3): 221–239. doi :10.1007/s00184-005-0415-y. S2CID  40646.
• Спенс, Эдвард (1995). "Классификация матриц Адамара порядка 24 и 28". Discrete Math . 140 (1–3): 185–242. doi : 10.1016/0012-365X(93)E0169-5 .
• Ярлагадда, РК; Херши, ДЖЕ (1997). Анализ и синтез матрицы Адамара . Бостон: Kluwer. ISBN 978-0-7923-9826-4.

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

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