Матрица Адамара - Hadamard matrix

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

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

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

Позволять ЧАС - матрица Адамара порядка п. Транспонирование ЧАС тесно связан со своим обратным. Фактически:

${ Displaystyle ЧЧ ^ { extf {T}} = нИ_ {п}}$

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

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

где det (ЧАС) это детерминант из ЧАС.

Предположим, что M сложная матрица порядка п, элементы которого ограничены |M_ij| ≤ 1, для каждого я, j от 1 до п. потом Детерминантная граница Адамара утверждает, что

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

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

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

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

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

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

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

${ 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}}, конец {выровнен}}}$

и

${ 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.^[1]

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

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

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

${ 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 H_ {2 ^ {n}} = F_ {n} ^ { extf {T}} F_ {n}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Рид и Браун в 1972 г. показали, что существует дважды регулярная турнир порядка п тогда и только тогда, когда существует косая матрица Адамара порядка п + 1. В математическом турнире порядка п, каждый из п игроки играют по одному матчу с каждым из других игроков, причем каждый матч приводит к победе одного из игроков и поражению другого. Турнир считается обычным, если каждый игрок выигрывает одинаковое количество матчей. Регулярный турнир является дважды регулярным, если количество оппонентов, побежденных обоими двумя разными игроками, одинаково для всех пар разных игроков. Поскольку каждый из п (п−1) / 2 сыгранных матча приводят к победе для одного из игроков, каждый игрок выигрывает (п−1) / 2 совпадений (и теряет такое же число). Поскольку каждый из (п−1) / 2 игрока, побежденные данным игроком, также проигрывают (п−3) / 2 других игрока, количество пар игроков (я, j) такие, что j проигрывает обоим я а данному игроку - (п−1) (п−3) / 4. Тот же результат должен быть получен, если пары считаются по-разному: данный игрок и любая из (п−1) другие игроки вместе побеждают такое же количество общих противников. Таким образом, это общее количество побежденных противников должно быть (п−3) / 4. Косая матрица Адамара получается путем введения дополнительного игрока, который побеждает всех исходных игроков, а затем формирования матрицы со строками и столбцами, помеченными игроками в соответствии с правилом, что строка я, столбец j содержит 1, если я = j или же я поражения j и −1, если j поражения я. Это обратное соответствие дает дважды регулярный турнир из скошенной матрицы Адамара, предполагая, что скошенная матрица Адамара нормализована так, что все элементы первой строки равны 1.^[10]

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

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

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

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

Обобщения

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

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

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

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

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

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

Примечания

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

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

внешняя ссылка

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