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

Матрица Адамара H {displaystyle H} — это квадратная матрица размера n×n, составленная из чисел 1 и −1, столбцы которой ортогональны, так что справедливо соотношение

H n ⋅ H n T = n ⋅ E n , {displaystyle H_{n}cdot H_{n}^{T}=ncdot E_{n},}

где E n {displaystyle E_{n}} — это единичная матрица размера n. Матрицы Адамара применяются в различных областях, включая комбинаторику, численный анализ, обработку сигналов.

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

Свойства

На множестве матриц Адамара размера n × n {displaystyle n imes n} действует группа преобразований G {displaystyle G} , порождённая инверсиями строк и столбцов (умножением на −1), а также перестановками строк и столбцов.

Две матрицы Адамара H 1 {displaystyle H_{1}} и H 2 {displaystyle H_{2}} называются эквивалентными, если существует элемент g ∈ G {displaystyle gin G} такой, что H 2 = g H 1 {displaystyle H_{2}=gH_{1}} . Таким образом, все матрицы Адамара заданного размера разбиваются на классы эквивалентности.

Теорема 1. Существует алгоритм перечисления нормализованных матриц Адамара.

Теорема 2. Для порядков 1, 2, 4, 8, 12, 16, 20, 24 существует соответственно 1, 1, 1, 1, 2, 118, 6520, 43966313 (последовательность A147774 в OEIS) эквивалентных классов нормализованных матриц Адамара по отношению эквивалентности перестановок строк и столбцов.

Определение. Автотопией матрицы Адамара H называется элемент g ∈ G {displaystyle gin G} такой, что g ( H ) = H {displaystyle g(H)=H} .

Теорема 3. Существует алгоритм вычисления группы автотопий матрицы Адамара.

Теорема 4. Существует алгоритм проверки эквивалентности двух матриц Адамара, находящий нужный элемент g ∈ G {displaystyle gin G} .

Теорема 5. Существуют полиномиально вычислимые функции на матрицах Адамара, инвариантные относительно действия группы G {displaystyle G} , и позволяющие в определённых случаях различать неэквивалентные матрицы Адамара.

Теорема 6. Существует алгоритм, перечисляющий только по одной матрице из каждого эквивалентного класса, для всех матриц заданного размера (в стадии разработки).

Примеры

H 0 = + 1 , {displaystyle H_{0}=+1,} H 1 = 1 2 ( 1 1 1 − 1 ) {displaystyle H_{1}={frac {1}{sqrt {2}}}{egin{pmatrix}{egin{array}{rr}1&11&-1end{array}}end{pmatrix}}} , H 2 = 1 2 ( 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ) {displaystyle H_{2}={frac {1}{2}}{egin{pmatrix}{egin{array}{rrrr}1&1&1&11&-1&1&-11&1&-1&-11&-1&-1&1end{array}}end{pmatrix}}} , [ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ] = [ 1 1 1 − 1 ] ⊗ [ 1 1 1 − 1 ] {displaystyle {egin{bmatrix}1&1&1&11&-1&1&-11&1&-1&-11&-1&-1&1end{bmatrix}}={egin{bmatrix}1&11&-1end{bmatrix}}otimes {egin{bmatrix}1&11&-1end{bmatrix}}} , H 2 k + 1 = [ H 2 k H 2 k H 2 k − H 2 k ] = H 2 ⊗ H 2 k , {displaystyle quad H_{2^{k+1}}={egin{bmatrix}H_{2^{k}}&H_{2^{k}}H_{2^{k}}&-H_{2^{k}}end{bmatrix}}=H_{2}otimes H_{2^{k}},} ,

где   k ∈ N {displaystyle kin N} , а ⊗ {displaystyle otimes } означает произведение Кронекера.

Использование матриц Адамара

• Иногда используются в рентгеновских телескопах с пространственным кодированием апертуры.
• Используются при кодировании информации (коды, исправляющие ошибки, ECC).