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

Смотрите также: матрица Уолша

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

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

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

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

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

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

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

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

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

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

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

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

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

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

показывать Доказательство

The proof of the nonexistence of Hadamard matrices with dimensions other than 1, 2, or a multiple of 4 follows: If $n>1$, then there is at least one scalar product of 2 rows which has to be 0. The scalar product is a sum of n values each of which is either 1 or −1, therefore the sum is odd for odd n, so n must be even. If $n=4m+2$ with $m\geq 1$, and there exists an $n\times n$ Hadamard matrix $H=(h_{i,j})_{i,j\in \{0,1,...,n-1\}}$, then it has the property that for any $k\neq l$: $\sum _{i=0}^{n-1}h_{k,i}h_{l,i}=0$ Now we define the matrix $A=(a_{i,j})_{i,j\in \{0,1,...,n-1\}}$ by setting $a_{i,j}=h_{0,j}h_{i,j}$.Note that $A$ has all 1s in row 0.We check that $A$ is also a Hadamard matrix: $\sum _{i=0}^{n-1}a_{k,i}a_{l,i}=\sum _{i=0}^{n-1}h_{0,j}h_{k,i}h_{0,j}h_{l,i}=\sum _{i=0}^{n-1}h_{0,j}^{2}h_{k,i}h_{l,i}=\sum _{i=0}^{n-1}h_{k,i}h_{l,i}=0.$ Row 1 and row 2, like all other rows except row 0, must have $n/2$ entries of 1 and $n/2$ entries of −1 each. (*) Let $\alpha$ denote the number of 1s of row 2 beneath 1s in row 1.Let $\beta$ denote the number of −1s of row 2 beneath 1s in row 1.Let $\gamma$ denote the number of 1s of row 2 beneath −1s in row 1.Let $\delta$ denote the number of −1s of row 2 beneath −1s in row 1. Row 2 has to be orthogonal to row 1, so the number of products of entries of the rows resulting in 1, $\alpha +\delta$, has to match those resulting in −1, $\beta +\gamma$.Due to (*), we also have $n/2=\alpha +\gamma =\beta +\delta$, from which we can express $\gamma =n/2-\alpha$ and $\delta =n/2-\beta$ and substitute: $\alpha +\delta =\beta +\gamma$ $\alpha +{\frac {n}{2}}-\beta =\beta +{\frac {n}{2}}-\alpha$ $\alpha -\beta =\beta -\alpha$ $\alpha =\beta$ But we have as the number of 1s in row 1 the odd number $n/2=\alpha +\beta$, contradiction.

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

Примеры матриц Адамара были впервые построены Джеймсом Джозефом Сильвестром в 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$ обозначает произведение Кронекера .

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

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

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

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

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

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

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

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

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

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

Обобщение конструкции Сильвестра доказывает, что если $H_{n}$ и $H_{m}$ являются матрицами Адамара порядков n и m соответственно, тогда $H_{n}\otimes H_{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 году в Лаборатории реактивного движения . Они использовали конструкцию Уильямсона , это принесло много дополнительных заказов. Сейчас известны многие другие методы построения матриц Адамара.

В 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.

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

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

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

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

Матрица Адамара H является косой , если $H^{\textsf {T}}+H=2I.$ Косая матрица Адамара остается косой матрицей Адамара после умножения любой строки и соответствующего ей столбца на -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 обязательно должно было бы иметь вид 4 u ² с тобой странно.

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

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

Обобщения

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

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

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

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

См. также

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

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

• Баумерт, Л.Д.; Холл, Маршалл (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. дои : 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 строки и столбца.