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

редактировать

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

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

Содержание

1 Свойства
2 Конструкция Сильвестра
- 2.1 Альтернативная конструкция
3 Гипотеза Адамара
4 Эквивалентность матриц Адамара
5 Особые случаи
- 5.1 Косые матрицы Адамара
- 5.2 Регулярные матрицы Адамара
- 5.3 Циркулянтные матрицы Адамара
6 Обобщения
7 Практические приложения
8 См. Также
9 Примечания
10 Дополнительная литература
11 Внешние ссылки

Свойства

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

HHT = n I n {\ displaystyle HH ^ {\textf {T}} = nI_ {n}}

{\ displaystyle HH ^ {\textf {T}} = nI_ {n}}

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

det ⁡ (H) = ± nn 2, {\ displaystyle \ operatorname {det} (H) = \ pm n ^ {\ frac {n} {2}},}

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

где det (H) - определитель матрицы H.

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

| det ⁡ (M) | ≤ п п 2. {\ displaystyle | \ operatorname {det} (M) | \ leq n ^ {\ frac {n} {2}}.}

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

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

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

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

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

[H H H - H] {\ displaystyle {\ begin {bmatrix} HH \\ H -H \ end {bmatrix}}}

{\ displaystyle {\ begin {bmatrix} HH \\ H -H \ end {bmatrix}}}

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

H 1 = [1], H 2 = [1 1 1 - 1], H 4 = [1 1 1 1 1 - 1 1 - 1 1 1 - 1 - 1 1 - 1 - 1 1], {\ displaystyle {\ begin {align} 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 {align}}}

{\ displaystyle {\ begin {align} 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 {выровнено}}}

H 2 k = [H 2 k - 1 H 2 k - 1 H 2 К - 1 - ЧАС 2 К - 1] = ЧАС 2 ⊗ ЧАС 2 К - 1, {\ 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 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 ≤ k ∈ N {\ displaystyle 2 \ leq k \ in N}$ $2 \ leq k \ in N$ , где $⊗ {\ displaystyle \ otimes}$ $\ otimes$ обозначает произведение Кронекера.

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

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

Альтернативная конструкция

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

F 1 = [0 1] F n = [0 1 × 2 n - 1 1 1 × 2 n - 1 F n - 1 F n - 1]. {\ displaystyle {\ begin {align} 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 {align}}}

{\ displaystyle {\ begin {align} 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 {выравнивается}}}

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

H 2 n = F n TF n. {\ displaystyle H_ {2 ^ {n}} = F_ {n} ^ {\textf {T}} F_ {n}.}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

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

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

См. Также

Примечания

Дополнительная литература

Baumert, LD; Холл, Маршалл (1965). «Матрицы Адамара типа Вильямсона». Математика. Комп. 19 (91): 442–447. doi : 10.1090 / S0025-5718-1965-0179093-2. MR 0179093.
Georgiou, S.; Кукувинос, С.; Себери, Дж. (2003). «Матрицы Адамара, ортогональные планы и алгоритмы построения». Проекты 2002: Дальнейшие исследования в области вычислительной и конструктивной теории проектирования. Бостон: Клувер. С. 133–205. ISBN 978-1-4020-7599-5.
Goethals, J.M.; Зайдель, Дж. Дж. (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 / aoms / 1177730883.
Reid, K.B.; Браун, Э. (1972). «Дважды регулярные турниры эквивалентны косым матрицам Адамара». J. Combin. Теория Сер. А. 12 (3): 332–338. doi : 10.1016 / 0097-3165 (72) 90098-2.
Seberry Wallis, Jennifer (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-y.
Спенс, Эдвард (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
N. Дж. А. Слоан. «Библиотека матриц Адамара».
Онлайновая утилита для получения всех заказов до 1000, кроме 668, 716, 876 и 892.
JPL: В 1961 году математики из Лаборатории реактивного движения НАСА и Калтех работали вместе, чтобы построить матрицу Адамара, содержащую 92 строки и столбца