thumb|Gilbert Strang explica a conjectura de Hadamard no MIT em 2005, usando a construção de Sylvester.
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 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:
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 Dividir H por este comprimento dá uma matriz ortogonal cuja transposta é, portanto, sua inversa:
Multiplicando pelo comprimento novamente dá a igualdade acima. Como resultado,
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
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 , 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 com , e existe uma matriz de Hadamard , então ela tem a propriedade de que para qualquer :
Agora definimos a matriz definindo . Note que tem todos 1s na linha 0. Verificamos que também é uma matriz de Hadamard:
A linha 1 e a linha 2, como todas as outras linhas exceto a linha 0, devem ter entradas de 1 e entradas de −1 cada. (*)
Seja o número de 1s da linha 2 abaixo de 1s na linha 1. Seja o número de −1s da linha 2 abaixo de 1s na linha 1. Seja o número de 1s da linha 2 abaixo de −1s na linha 1. Seja 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, , tem que corresponder àqueles resultando em −1, . Devido a (*), também temos , a partir do qual podemos expressar e e substituir:
Mas temos como o número de 1s na linha 1 o número ímpar , 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
é 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.
e
para , onde denota o produto de Kronecker.
Desta forma, Sylvester construiu matrizes de Hadamard de ordem 2k para todo inteiro não negativo k.J.J. Sylvester. Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers. Philosophical Magazine, 34:461–475, 1867
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.
thumb|320px|Matriz de Hadamard binária como um produto de matrizes. A matriz binária (branco 0, vermelho 1) é o resultado com operações em F2. Os números cinza mostram o resultado com operações em .
Construção alternativa Se mapearmos os elementos da matriz de Hadamard usando o homomorfismo de grupo , onde é o grupo aditivo do campo com dois elementos, podemos descrever uma construção alternativa da matriz de Hadamard de Sylvester. Primeiro considere a matriz , a matriz cujas colunas consistem em todos os números de n bits dispostos em ordem crescente de contagem. Podemos definir recursivamente por
Pode-se mostrar por indução que a imagem da matriz de Hadamard sob o homomorfismo acima é dada por
onde a aritmética matricial é feita sobre .
Esta construção demonstra que as linhas da matriz de Hadamard podem ser vistas como um código corretor de erros linear de comprimento , rank n, e distância mínima com matriz geradora
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 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 e são matrizes de Hadamard de ordens n e m respectivamente, então é 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 de ordem tem entradas aleatoriamente deletadas, então com grande probabilidade, pode-se recuperar perfeitamente a matriz original 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 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