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

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

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

Свойства [ править ]

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

{\ Displaystyle ЧЧ ^ {\textf {T}} = нИ_ {п}}

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

\operatorname {det} (H)=\pm n^{\frac {n}{2}},

где Det ( Н ) является определяющим из Н .

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

|\operatorname {det} (M)|\leq n^{\frac {n}{2}}.

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

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

Конструкция Сильвестра [ править ]

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

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

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

{\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}}

и

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}},

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

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

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

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

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

{\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}}

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

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

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

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

Гипотеза Адамара [ править ]

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

Обобщение конструкции Сильвестра доказывает, что если и являются матрицами Адамара порядков n и m соответственно, то является матрицей Адамара порядка nm . Этот результат используется для получения матриц Адамара более высокого порядка, если известны матрицы меньшего порядка. $H_{n}$ $H_{m}$ $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] Они использовали конструкцию, из - за Williamson , ^[7] , что вкусил много дополнительных заказов. Сейчас известны многие другие методы построения матриц Адамара.

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

По состоянию на 2008 год ^[update]существует 13 кратных 4, меньших или равных 2000, для которых неизвестна матрица Адамара этого порядка. ^[9] Это: 668, 716, 892, 1004, 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]}

Особые случаи [ править ]

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

Косые матрицы Адамара [ править ]

Матрица Адамара H является косой, если косая матрица Адамара остается косой матрицей Адамара после умножения любой строки и соответствующего ей столбца на -1. Это позволяет, например, нормализовать скошенную матрицу Адамара так, чтобы все элементы в первой строке равнялись 1. $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. ^[11]

Регулярные матрицы Адамара [ править ]

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

Циркулянтные матрицы Адамара [ править ]

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

Обобщения [ править ]

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

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

Практическое применение [ править ]

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

См. Также [ править ]

Преобразование Адамара
Комбинаторный дизайн
Матрица Уолша
Матрица Quincunx

Заметки [ править ]

^ http://math.ucdenver.edu/~wcherowi/courses/m6406/hadamard.pdf
^ JJ Сильвестр. Мысли об обратных ортогональных матрицах, одновременной последовательности знаков и мозаичных тротуарах в двух или более цветах, с приложениями к правилу Ньютона, декоративной плитке и теории чисел. Философский журнал , 34: 461–475, 1867 г.
^ Hedayat, A .; Уоллис, WD (1978). «Матрицы Адамара и их приложения» . Анналы статистики . 6 (6): 1184–1238. DOI : 10.1214 / AOS / 1176344370 . JSTOR 2958712 . Руководство по ремонту 0523759 ..
^ Адамар, Дж. (1893). "Решение вопроса об относительных детерминантах". Бюллетень математических наук . 17 : 240–246.
^ Палей, REAC (1933). «Об ортогональных матрицах». Журнал математики и физики . 12 (1–4): 311–320. DOI : 10.1002 / sapm1933121311 .
^ Baumert, L .; Голомб, ЮЗ; Холл, М., младший (1962). «Открытие матрицы Адамара порядка 92» . Бюллетень Американского математического общества . 68 (3): 237–238. DOI : 10.1090 / S0002-9904-1962-10761-7 . Руководство по ремонту 0148686 .
^ Уильямсон, Дж. (1944). «Детерминантная теорема Адамара и сумма четырех квадратов». Математический журнал герцога . 11 (1): 65–81. DOI : 10.1215 / S0012-7094-44-01108-7 . MR 0009590 .
^ Kharaghani, H .; Тайфэ-Резайе, Б. (2005). «Матрица Адамара порядка 428». Журнал комбинаторных дизайнов . 13 (6): 435–440. DOI : 10.1002 / jcd.20043 .
^ Oković, Dragomir Ž (2008). «Матрицы Адамара порядка 764 существуют». Combinatorica . 28 (4): 487–489. arXiv : math / 0703312 . DOI : 10.1007 / s00493-008-2384-z .
^ Wanless, IM (2005). «Перманенты матриц знаковых». Линейная и полилинейная алгебра . 53 (6): 427–433. DOI : 10.1080 / 03081080500093990 .
^ Рид, КБ; Браун, Эзра (1972). «Дважды регулярные турниры эквивалентны косым матрицам Хадамара». Журнал комбинаторной теории, Серия А . 12 (3): 332–338. DOI : 10.1016 / 0097-3165 (72) 90098-2 .
^ Turyn, RJ (1965). «Суммы символов и разностные наборы» . Тихоокеанский математический журнал . 15 (1): 319–346. DOI : 10,2140 / pjm.1965.15.319 . Руководство по ремонту 0179098 .
^ Turyn, RJ (1969). «Последовательности с малой корреляцией». В Mann, HB (ред.). Коды исправления ошибок . Нью-Йорк: Вили. С. 195–228.
^ Шмидт, Б. (1999). «Циклотомические целые числа и конечная геометрия» . Журнал Американского математического общества . 12 (4): 929–952. DOI : 10.1090 / S0894-0347-99-00298-2 . JSTOR 2646093 .

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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

[1] ttp://math.ucdenver.edu/~wcherowi/courses/m6406/hadamard.pdf

[2] JJ Сильвестр. Мысли об обратных ортогональных матрицах, одновременной последовательности знаков и мозаичных тротуарах в двух или более цветах, с приложениями к правилу Ньютона, декоративной плитке и теории чисел. Философский журнал , 34: 461–475, 1867 г.

[3] Hedayat, A .; Уоллис, WD (1978). «Матрицы Адамара и их приложения» . Анналы статистики . 6 (6): 1184–1238. DOI : 10.1214 / AOS / 1176344370 . JSTOR 2958712 . Руководство по ремонту 0523759 ..

[4] Адамар, Дж. (1893). "Решение вопроса об относительных детерминантах". Бюллетень математических наук . 17 : 240–246.

[5] Палей, REAC (1933). «Об ортогональных матрицах». Журнал математики и физики . 12 (1–4): 311–320. DOI : 10.1002 / sapm1933121311 .

[6] Baumert, L .; Голомб, ЮЗ; Холл, М., младший (1962). «Открытие матрицы Адамара порядка 92» . Бюллетень Американского математического общества . 68 (3): 237–238. DOI : 10.1090 / S0002-9904-1962-10761-7 . Руководство по ремонту 0148686 .

[7] Уильямсон, Дж. (1944). «Детерминантная теорема Адамара и сумма четырех квадратов». Математический журнал герцога . 11 (1): 65–81. DOI : 10.1215 / S0012-7094-44-01108-7 . MR 0009590 .

[8] Kharaghani, H .; Тайфэ-Резайе, Б. (2005). «Матрица Адамара порядка 428». Журнал комбинаторных дизайнов . 13 (6): 435–440. DOI : 10.1002 / jcd.20043 .

[dokovic-9] Oković, Dragomir Ž (2008). «Матрицы Адамара порядка 764 существуют». Combinatorica . 28 (4): 487–489. arXiv : math / 0703312 . DOI : 10.1007 / s00493-008-2384-z .

[10] Wanless, IM (2005). «Перманенты матриц знаковых». Линейная и полилинейная алгебра . 53 (6): 427–433. DOI : 10.1080 / 03081080500093990 .

[11] Рид, КБ; Браун, Эзра (1972). «Дважды регулярные турниры эквивалентны косым матрицам Хадамара». Журнал комбинаторной теории, Серия А . 12 (3): 332–338. DOI : 10.1016 / 0097-3165 (72) 90098-2 .

[12] Turyn, RJ (1965). «Суммы символов и разностные наборы» . Тихоокеанский математический журнал . 15 (1): 319–346. DOI : 10,2140 / pjm.1965.15.319 . Руководство по ремонту 0179098 .

[13] Turyn, RJ (1969). «Последовательности с малой корреляцией». В Mann, HB (ред.). Коды исправления ошибок . Нью-Йорк: Вили. С. 195–228.

[14] Шмидт, Б. (1999). «Циклотомические целые числа и конечная геометрия» . Журнал Американского математического общества . 12 (4): 929–952. DOI : 10.1090 / S0894-0347-99-00298-2 . JSTOR 2646093 .

[1]