Matriz de Hadamard

Em matemática, uma matriz de Hadamard, nomeada em homenagem ao matemático francês Jacques Hadamard, é uma matriz quadrada cujas entradas são +1 ou −1 e cujas linhas são mutuamente ortogonais. Em termos geométricos, isso significa que cada par de linhas em uma matriz de Hadamard representa dois vetores perpendiculares, enquanto em termos combinatórios, significa que cada par de linhas tem entradas correspondentes em exatamente metade de suas colunas e entradas não correspondentes nas colunas restantes. É uma consequência desta definição que as propriedades correspondentes valem também para colunas. O paralelotopo n-dimensional gerado pelas linhas de uma matriz de Hadamard n × n tem o máximo n-dimensional volume possível entre paralelotopos gerados por vetores cujas entradas são limitadas em valor absoluto por 1. Equivalentemente, uma matriz de Hadamard tem determinante máximo entre matrizes com entradas de valor absoluto menor ou igual a 1 e, portanto, é uma solução extrema do problema do determinante máximo de Hadamard. Certas matrizes de Hadamard podem ser usadas quase diretamente como um código corretor de erros usando um código de Hadamard (generalizado em códigos de Reed-Muller), e também são usadas na replicação repetida balanceada (BRR), usada por estatísticos para estimar a variância de um estimador de parâmetro.

Propriedades Seja H uma matriz de Hadamard de ordem n. A transposta de H está intimamente relacionada à sua inversa. De fato:

= n

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

onde In é a matriz identidade n × n e HT é a transposta de H. Para ver que isso é verdade, note que as linhas de H são todas ortogonais sobre o corpo dos números reais e cada uma tem comprimento

{\displaystyle {\sqrt {n}}\,.}

Dividir H por este comprimento dá uma matriz ortogonal cuja transposta é, portanto, sua inversa:

− 1

{\displaystyle {\frac {1}{\sqrt {n}}}H^{\textsf {T}}={\sqrt {n}}H^{-1}}

Multiplicando pelo comprimento novamente dá a igualdade acima. Como resultado,

det ⁡ ( H ) = ±

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

onde det(H) é o determinante de H. Suponha que M é uma matriz complexa de ordem n, cujas entradas são limitadas por |Mij| ≤ 1, para cada i, j entre 1 e n. Então a desigualdade do determinante de Hadamard afirma que

det ⁡ ( M )

≤

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

A igualdade nesta desigualdade é atingida para uma matriz real M se e somente se M é uma matriz de Hadamard. A ordem de uma matriz de Hadamard deve ser 1, 2 ou um múltiplo de 4.

Prova A prova da inexistência de matrizes de Hadamard com dimensões diferentes de 1, 2 ou um múltiplo de 4 segue: Se

n > 1

{\displaystyle n>1}

, então há pelo menos um produto escalar de 2 linhas que tem que ser 0. O produto escalar é uma soma de n valores, cada um dos quais é 1 ou −1, portanto a soma é ímpar para n ímpar, então n deve ser par. Se

n = 4 m + 2

{\displaystyle n=4m+2}

com

m ≥ 1

{\displaystyle m\geq 1}

, e existe uma matriz de Hadamard

n × n

{\displaystyle n\times n}

H = (

i , j

)

i , j ∈ { 0 , 1 , . . . , n − 1 }

{\displaystyle H=(h_{i,j})_{i,j\in \{0,1,...,n-1\}}}

, então ela tem a propriedade de que para qualquer

k ≠ l

{\displaystyle k\neq l}

∑

i = 0

n − 1

k , i

l , i

= 0

{\displaystyle \sum _{i=0}^{n-1}h_{k,i}h_{l,i}=0}

Agora definimos a matriz

A = (

i , j

)

i , j ∈ { 0 , 1 , . . . , n − 1 }

{\displaystyle A=(a_{i,j})_{i,j\in \{0,1,...,n-1\}}}

definindo

i , j

0 , j

i , j

{\displaystyle a_{i,j}=h_{0,j}h_{i,j}}

. Note que

{\displaystyle A}

tem todos 1s na linha 0. Verificamos que

{\displaystyle A}

também é uma matriz de Hadamard:

∑

i = 0

n − 1

k , i

l , i

∑

i = 0

n − 1

0 , i

k , i

0 , i

l , i

∑

i = 0

n − 1

0 , i

k , i

l , i

∑

i = 0

n − 1

k , i

l , i

= 0.

{\displaystyle \sum _{i=0}^{n-1}a_{k,i}a_{l,i}=\sum _{i=0}^{n-1}h_{0,i}h_{k,i}h_{0,i}h_{l,i}=\sum _{i=0}^{n-1}h_{0,i}^{2}h_{k,i}h_{l,i}=\sum _{i=0}^{n-1}h_{k,i}h_{l,i}=0.}

A linha 1 e a linha 2, como todas as outras linhas exceto a linha 0, devem ter

{\displaystyle n/2}

entradas de 1 e

{\displaystyle n/2}

entradas de −1 cada. (*) Seja

{\displaystyle \alpha }

o número de 1s da linha 2 abaixo de 1s na linha 1. Seja

{\displaystyle \beta }

o número de −1s da linha 2 abaixo de 1s na linha 1. Seja

{\displaystyle \gamma }

o número de 1s da linha 2 abaixo de −1s na linha 1. Seja

{\displaystyle \delta }

o número de −1s da linha 2 abaixo de −1s na linha 1. A linha 2 tem que ser ortogonal à linha 1, então o número de produtos de entradas das linhas resultando em 1,

α + δ

{\displaystyle \alpha +\delta }

, tem que corresponder àqueles resultando em −1,

β + γ

{\displaystyle \beta +\gamma }

. Devido a (*), também temos

2 = α + γ = β + δ

{\displaystyle n/2=\alpha +\gamma =\beta +\delta }

, a partir do qual podemos expressar

γ = n

2 − α

{\displaystyle \gamma =n/2-\alpha }

δ = n

2 − β

{\displaystyle \delta =n/2-\beta }

e substituir:

α + δ = β + γ

{\displaystyle \alpha +\delta =\beta +\gamma }

α +

n 2

− β = β +

n 2

− α

{\displaystyle \alpha +{\frac {n}{2}}-\beta =\beta +{\frac {n}{2}}-\alpha }

α − β = β − α

{\displaystyle \alpha -\beta =\beta -\alpha }

α = β

{\displaystyle \alpha =\beta }

Mas temos como o número de 1s na linha 1 o número ímpar

2 = α + β

{\displaystyle n/2=\alpha +\beta }

, contradição.

Construção de Sylvester Exemplos de matrizes de Hadamard foram na verdade construídos pela primeira vez por James Joseph Sylvester em 1867. Seja H uma matriz de Hadamard de ordem n. Então a matriz particionada

[

− H

]

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

é uma matriz de Hadamard de ordem 2n. Esta observação pode ser aplicada repetidamente e leva à seguinte sequência de matrizes, também chamadas de matrizes de Walsh.

[

]

[

− 1

]

[

− 1

]

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

[

k − 1

−

k − 1

]

⊗

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

para

2 ≤ k ∈ N

{\displaystyle 2\leq k\in N}

, onde

⊗

{\displaystyle \otimes }

denota o produto de Kronecker. Desta forma, Sylvester construiu matrizes de Hadamard de ordem 2k para todo inteiro não negativo k. As matrizes de Sylvester têm várias propriedades especiais. Elas são simétricas e, quando k ≥ 1 (2k > 1), têm traço zero. Os elementos na primeira coluna e na primeira linha são todos positivos. Os elementos em todas as outras linhas e colunas são igualmente divididos entre positivos e negativos. As matrizes de Sylvester estão intimamente ligadas às funções de Walsh.

Construção alternativa Se mapearmos os elementos da matriz de Hadamard usando o homomorfismo de grupo

( { 1 , − 1 } , × ) → ( { 0 , 1 } ) , + )

{\displaystyle (\{1,-1\},\times )\rightarrow (\{0,1\}),+)}

, onde

( { 0 , 1 } ) , + )

{\displaystyle (\{0,1\}),+)}

é o grupo aditivo do campo

G F

( 2 )

{\displaystyle \mathrm {GF} (2)}

com dois elementos, podemos descrever uma construção alternativa da matriz de Hadamard de Sylvester. Primeiro considere a matriz

{\displaystyle F_{n}}

, a matriz

n ×

{\displaystyle n\times 2^{n}}

cujas colunas consistem em todos os números de n bits dispostos em ordem crescente de contagem. Podemos definir

{\displaystyle F_{n}}

recursivamente por

[

]

[

1 ×

n − 1

1 ×

n − 1

]

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

Pode-se mostrar por indução que a imagem da matriz de Hadamard sob o homomorfismo acima é dada por

↦

{\displaystyle H_{2^{n}}\mapsto F_{n}^{\textsf {T}}F_{n},}

onde a aritmética matricial é feita sobre

G F

( 2 )

{\displaystyle \mathrm {GF} (2)}

. Esta construção demonstra que as linhas da matriz de Hadamard

{\displaystyle H_{2^{n}}}

podem ser vistas como um código corretor de erros linear de comprimento

{\displaystyle 2^{n}}

, rank n, e distância mínima

n − 1

{\displaystyle 2^{n-1}}

com matriz geradora

{\displaystyle F_{n}.}

Este código também é referido como um código de Walsh. O código de Hadamard, por contraste, é construído a partir da matriz de Hadamard

{\displaystyle H_{2^{n}}}

por um procedimento ligeiramente diferente.

Conjectura de Hadamard

A questão em aberto mais importante na teoria das matrizes de Hadamard é uma de existência. Especificamente, a conjectura de Hadamard propõe que uma matriz de Hadamard de ordem 4k existe para todo inteiro positivo k. A conjectura de Hadamard também foi atribuída a Paley, embora tenha sido considerada implicitamente por outros antes do trabalho de Paley. Uma generalização da construção de Sylvester prova que se

{\displaystyle H_{n}}

{\displaystyle H_{m}}

são matrizes de Hadamard de ordens n e m respectivamente, então

⊗

{\displaystyle H_{n}\otimes H_{m}}

é uma matriz de Hadamard de ordem nm. Este resultado é usado para produzir matrizes de Hadamard de ordem superior uma vez que as de ordens menores são conhecidas. A construção de Sylvester de 1867 produz matrizes de Hadamard de ordem 1, 2, 4, 8, 16, 32, etc. Matrizes de Hadamard de ordens 12 e 20 foram posteriormente construídas por Hadamard (em 1893). Em 1933, Raymond Paley descobriu a construção de Paley, que produz uma matriz de Hadamard de ordem q + 1 quando q é qualquer potência de primo que é congruente a 3 módulo 4 e que produz uma matriz de Hadamard de ordem 2(q + 1) quando q é uma potência de primo que é congruente a 1 módulo 4. Seu método usa corpos finitos. A menor ordem que não pode ser construída por uma combinação dos métodos de Sylvester e Paley é 92. Uma matriz de Hadamard desta ordem foi encontrada usando um computador por Baumert, Golomb e Hall em 1962 no JPL. Eles usaram uma construção, devida a Williamson, que produziu muitas ordens adicionais. Muitos outros métodos para construir matrizes de Hadamard são agora conhecidos. Em 2005, Hadi Kharaghani e Behruz Tayfeh-Rezaie publicaram sua construção de uma matriz de Hadamard de ordem 428. Como resultado, a menor ordem para a qual nenhuma matriz de Hadamard é atualmente conhecida é 668. Em 2014, havia 12 múltiplos de 4 menores que 2000 para os quais nenhuma matriz de Hadamard daquela ordem era conhecida. São eles: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 e 1964.

Equivalência e unicidade Duas matrizes de Hadamard são consideradas equivalentes se uma pode ser obtida da outra negando linhas ou colunas, ou trocando linhas ou colunas. Até a equivalência, há uma única matriz de Hadamard de ordens 1, 2, 4, 8 e 12. Há 5 matrizes inequivalentes de ordem 16, 3 de ordem 20, 60 de ordem 24 e 487 de ordem 28. Milhões de matrizes inequivalentes são conhecidas para ordens 32, 36 e 40. Usando uma noção mais grosseira de equivalência que também permite transposição, há 4 matrizes inequivalentes de ordem 16, 3 de ordem 20, 36 de ordem 24 e 294 de ordem 28. Matrizes de Hadamard também são unicamente recuperáveis, no seguinte sentido: Se uma matriz de Hadamard

{\displaystyle H}

de ordem

{\displaystyle n}

tem

O (

log ⁡ n )

{\displaystyle O(n^{2}/\log n)}

entradas aleatoriamente deletadas, então com grande probabilidade, pode-se recuperar perfeitamente a matriz original

{\displaystyle H}

a partir da danificada. O algoritmo de recuperação tem o mesmo custo computacional que a inversão de matriz.

Casos especiais Muitos casos especiais de matrizes de Hadamard foram investigados na literatura matemática.

Matrizes de Hadamard enviesadas Uma matriz de Hadamard H é enviesada se

+ H = 2 I .

{\displaystyle H^{\textsf {T}}+H=2I.}

Uma matriz de Hadamard enviesada permanece uma matriz de Hadamard enviesada após a multiplicação de qualquer linha e sua coluna correspondente por −1. Isso torna possível, por exemplo, normalizar uma matriz de Hadamard enviesada de modo que todos os elementos na primeira linha sejam iguais a 1. Reid e Brown em 1972 mostraram que existe um torneio duplamente regular de ordem n se e somente se existe uma matriz de Hadamard enviesada de ordem n + 1. Em um torneio matemático de ordem n, cada um dos n jogadores joga uma partida contra cada um dos outros jogadores, cada partida resultando em uma vitória para um dos jogadores e uma derrota para o outro. Um torneio é regular se cada jogador vence o mesmo número de partidas. Um torneio regular é duplamente regular se o número de oponentes derrotados por ambos de dois jogadores distintos é o mesmo para todos os pares de jogadores distintos. Como cada uma das n(n − 1)/2 partidas disputadas resulta em uma vitória para um dos jogadores, cada jogador vence (n − 1)/2 partidas (e perde o mesmo número). Como cada um dos (n − 1)/2 jogadores derrotados por um dado jogador também perde para (n − 3)/2 outros jogadores, o número de pares de jogadores (i, j) tais que j perde tanto para i quanto para o jogador dado é (n − 1)(n − 3)/4. O mesmo resultado deve ser obtido se os pares forem contados de forma diferente: o jogador dado e qualquer um dos n − 1 outros jogadores juntos derrotam o mesmo número de oponentes comuns. Este número comum de oponentes derrotados deve, portanto, ser (n − 3)/4. Uma matriz de Hadamard enviesada é obtida introduzindo um jogador adicional que derrota todos os jogadores originais e então formando uma matriz com linhas e colunas rotuladas por jogadores de acordo com a regra de que a linha i, coluna j contém 1 se i = j ou i derrota j e −1 se j derrota i. Esta correspondência inversa produz um torneio duplamente regular a partir de uma matriz de Hadamard enviesada, assumindo que a matriz de Hadamard enviesada é normalizada de modo que todos os elementos da primeira linha sejam iguais a 1.

Matrizes de Hadamard regulares Matrizes de Hadamard regulares são matrizes de Hadamard reais cujas somas de linhas e colunas são todas iguais. Uma condição necessária para a existência de uma matriz de Hadamard regular n × n é que n seja um número quadrado. Uma matriz circulante é manifestamente regular e, portanto, uma matriz de Hadamard circulante teria que ser de ordem quadrada. Além disso, se existisse uma matriz de Hadamard circulante n × n com n > 1, então n necessariamente teria que ser da forma 4u2 com u ímpar.

Matrizes de Hadamard circulantes A conjectura da matriz de Hadamard circulante, no entanto, afirma que, além dos exemplos conhecidos de 1 × 1 e 4 × 4, tais matrizes não existem. Isso foi verificado para todos, exceto 26 valores de u menores que 104.

Generalizações Uma generalização básica é uma matriz de pesagem. Uma matriz de pesagem é uma matriz quadrada na qual as entradas também podem ser zero e que satisfaz

= w I

{\displaystyle WW^{\textsf {T}}=wI}

para algum w, seu peso. Uma matriz de pesagem com seu peso igual à sua ordem é uma matriz de Hadamard. Outra generalização define uma matriz de Hadamard complexa como uma matriz na qual as entradas são números complexos de módulo unitário e que satisfaz H H* = n In onde H* é a transposta conjugada de H. Matrizes de Hadamard complexas surgem no estudo de álgebras de operadores e na teoria da computação quântica. Matrizes de Hadamard do tipo Butson são matrizes de Hadamard complexas nas quais as entradas são tomadas como q-ésimas raízes da unidade. O termo matriz de Hadamard complexa tem sido usado por alguns autores para se referir especificamente ao caso q = 4. Matrizes do tipo Hadamard sobre corpos finitos também foram consideradas. Para um primo ímpar p, uma matriz do tipo Hadamard sobre

GF ⁡ ( p )

{\displaystyle \operatorname {GF} (p)}

é uma matriz n por n com entradas em

GF ⁡ ( p )

{\displaystyle \operatorname {GF} (p)}

satisfazendo

= n I

{\displaystyle HH^{\textsf {T}}=nI}

módulo p. Kodama e Kojima mostraram que, embora ordens ímpares sejam restritas a resíduos quadráticos módulo p, tais matrizes existem para toda ordem par n com

n ≢ 0

( mod

p )

{\displaystyle n\not \equiv 0{\pmod {p}}}

Aplicações práticas Olivia MFSK – um protocolo digital de rádio amador projetado para funcionar em condições difíceis (baixa relação sinal-ruído mais propagação por múltiplos caminhos) em bandas de ondas curtas. Replicação repetida balanceada (BRR) – uma técnica usada por estatísticos para estimar a variância de um estimador estatístico. Espectrometria de abertura codificada – um instrumento para medir o espectro da luz. O elemento de máscara usado em espectrômetros de abertura codificada é frequentemente uma variante de uma matriz de Hadamard. Redes de atraso com realimentação – Dispositivos digitais de reverberação que usam matrizes de Hadamard para combinar valores de amostra Projeto de Plackett-Burman de experimentos para investigar a dependência de alguma quantidade medida em várias variáveis independentes. Projetos de parâmetros robustos para investigar impactos de fatores de ruído nas respostas Sensoriamento compressivo para processamento de sinais e sistemas lineares subdeterminados (problemas inversos) Porta quântica de Hadamard para computação quântica e a transformada de Hadamard para algoritmos quânticos.

Ver também Projeto combinatório Transformada de Hadamard Matriz quincunce Matriz de Walsh Matriz de pesagem Porta lógica quântica Processamento de sinais algébrico – estrutura na qual a matriz de Hadamard surge como a tabela de caracteres do grupo abeliano elementar

{\displaystyle \mathbb {Z} _{2}^{n}}

Notas

Leitura adicional Baumert, L. D.; Hall, Marshall (1965). «Hadamard matrices of the Williamson type». Math. Comp. 19 (91): 442–447. MR 0179093. doi:10.1090/S0025-5718-1965-0179093-2 Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). «Hadamard matrices, orthogonal designs and construction algorithms». Designs 2002: Further computational and constructive design theory. Boston: Kluwer. pp. 133–205. ISBN 978-1-4020-7599-5 Goethals, J. M.; Seidel, J. J. (1970). «A skew Hadamard matrix of order 36». J. Austral. Math. Soc. 11 (3): 343–344. doi:10.1017/S144678870000673X Kimura, Hiroshi (1989). «New Hadamard matrix of order 24». Graphs and Combinatorics. 5 (1): 235–242. doi:10.1007/BF01788676 Mood, Alexander M. (1964). «On Hotelling's Weighing Problem». Annals of Mathematical Statistics. 17 (4): 432–446. doi:10.1214/aoms/1177730883 Reid, K. B.; Brown, E. (1972). «Doubly regular tournaments are equivalent to skew Hadamard matrices». J. Combin. Theory Ser. A. 12 (3): 332–338. doi:10.1016/0097-3165(72)90098-2 Seberry Wallis, Jennifer (1976). «On the existence of Hadamard matrices». J. Comb. Theory A. 21 (2): 188–195. doi:10.1016/0097-3165(76)90062-5 Seberry, Jennifer (1980). «A construction for generalized hadamard matrices». J. Statist. Plann. Infer. 4 (4): 365–368. doi:10.1016/0378-3758(80)90021-X Seberry, J.; Wysocki, B.; Wysocki, T. (2005). «On some applications of Hadamard matrices». Metrika. 62 (2–3): 221–239. doi:10.1007/s00184-005-0415-y Spence, Edward (1995). «Classification of hadamard matrices of order 24 and 28». Discrete Math. 140 (1–3): 185–242. doi:10.1016/0012-365X(93)E0169-5 Yarlagadda, R. K.; Hershey, J. E. (1997). Hadamard Matrix Analysis and Synthesis. Boston: Kluwer. ISBN 978-0-7923-9826-4

Ligações externas Matrizes de Hadamard enviesadas de todas as ordens até 100, incluindo cada tipo com ordem até 28; «Hadamard Matrix» no OEIS N. J. A. Sloane. «Library of Hadamard Matrices» Utilitário online para obter todas as ordens até 1000, exceto 668, 716, 876 e 892. Pacote-R para gerar Matrizes de Hadamard usando R JPL: Em 1961, matemáticos do Laboratório de Propulsão a Jato da NASA e do Caltech trabalharam juntos para construir uma Matriz de Hadamard contendo 92 linhas e colunas

Matriz de Hadamard

Mais conteúdos de Cultura

Vindicators 3: The Return of Worldender

Sanctuary (álbum de Evanescence)