Matriz de Hadamard

Concepto de matemáticas

Gilbert Strang demuestra la conjetura de Hadamard en el MIT en 2005, utilizando la construcción de Sylvester.

En matemáticas , una matriz de Hadamard , llamada así por el matemático francés Jacques Hadamard , es una matriz cuadrada cuyas entradas son +1 o −1 y cuyas filas son mutuamente ortogonales . En términos geométricos , esto significa que cada par de filas en una matriz de Hadamard representa dos vectores perpendiculares , mientras que en términos combinatorios , significa que cada par de filas tiene entradas coincidentes en exactamente la mitad de sus columnas y entradas no coincidentes en las columnas restantes. Es una consecuencia de esta definición que las propiedades correspondientes se mantienen tanto para las columnas como para las filas.

El paralelotopo n -dimensional abarcado por las filas de una matriz de Hadamard n  ×  n tiene el máximo volumen n -dimensional posible entre los paralelotopos abarcados por vectores cuyas entradas están acotadas en valor absoluto por 1. De manera equivalente, una matriz de Hadamard tiene determinante máximo entre matrices con entradas de valor absoluto menores o iguales a 1 y, por lo tanto, es una solución extrema del problema del determinante máximo de Hadamard .

Ciertas matrices de Hadamard se pueden utilizar casi directamente como un código de corrección de errores utilizando un código de Hadamard (generalizado en los códigos Reed-Muller ), y también se utilizan en la replicación repetida equilibrada (BRR), utilizada por los estadísticos para estimar la varianza de un estimador de parámetros .

Propiedades

Sea H una matriz de Hadamard de orden n . La transpuesta de H está estrechamente relacionada con su inversa . De hecho:

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

donde I _n es la matriz identidad n  ×  n y H ^T es la transpuesta de H . Para ver que esto es cierto, observe que las filas de H son todos vectores ortogonales sobre el campo de números reales y cada uno tiene longitud Dividiendo H por esta longitud da una matriz ortogonal cuya transpuesta es, por lo tanto, su inversa. Multiplicando por la longitud nuevamente da la igualdad anterior. Como resultado, ${\displaystyle {\sqrt {n}}\,.}$

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

donde det( H ) es el determinante de H .

Supóngase que M es una matriz compleja de orden n , cuyos elementos están acotados por | M _ij  | ≤ 1, para cada i , j entre 1 y n . Entonces el límite determinante de Hadamard establece que

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

La igualdad en este límite se alcanza para una matriz real M si y sólo si M es una matriz de Hadamard.

El orden de una matriz de Hadamard debe ser 1, 2 o un múltiplo de 4. ^[1]

La construcción de Sylvester

Los primeros ejemplos de matrices de Hadamard fueron construidos por James Joseph Sylvester en 1867. Sea H una matriz de Hadamard de orden n . Entonces la matriz particionada

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

es una matriz de Hadamard de orden 2 n . Esta observación puede aplicarse repetidamente y conduce a la siguiente secuencia de matrices, también llamadas matrices de Walsh .

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

y

${\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 , donde denota el producto de Kronecker . ${\displaystyle 2\leq k\in N}$ ${\displaystyle \otimes }$

De esta manera, Sylvester construyó matrices de Hadamard de orden 2 ^k para cada entero no negativo k . ^[2]

Las matrices de Sylvester tienen varias propiedades especiales. Son simétricas y, cuando k  ≥ 1 (2 ^k  > 1), tienen traza cero. Los elementos de la primera columna y la primera fila son todos positivos. Los elementos de todas las demás filas y columnas se dividen equitativamente entre positivos y negativos . Las matrices de Sylvester están estrechamente relacionadas con las funciones de Walsh .

Construcción alternativa

Si mapeamos los elementos de la matriz de Hadamard usando el homomorfismo de grupo , podemos describir una construcción alternativa de la matriz de Hadamard de Sylvester. Primero consideremos la matriz , la matriz cuyas columnas consisten en todos los números de n bits dispuestos en orden de conteo ascendente. Podemos definir recursivamente por ${\displaystyle (\{1,-1\},\times )\mapsto (\{0,1\}),\oplus \}}$ ${\displaystyle F_{n}}$ ${\displaystyle n\times 2^{n}}$ ${\displaystyle F_{n}}$

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

Se puede demostrar por inducción que la imagen de la matriz de Hadamard bajo el homomorfismo anterior está dada por

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

Esta construcción demuestra que las filas de la matriz de Hadamard se pueden ver como un código de corrección de errores lineal de longitud de rango n y una distancia mínima con la matriz generadora ${\displaystyle H_{2^{n}}}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n-1}}$ ${\displaystyle F_{n}.}$

Este código también se conoce como código Walsh . El código Hadamard , por el contrario, se construye a partir de la matriz Hadamard mediante un procedimiento ligeramente diferente. ${\displaystyle H_{2^{n}}}$

Conjetura de Hadamard

Problema sin resolver en matemáticas :

¿Existe una matriz de Hadamard de orden 4 k para cada entero positivo k ?

(más problemas sin resolver en matemáticas)

La cuestión abierta más importante en la teoría de las matrices de Hadamard es la de su existencia. En concreto, la conjetura de Hadamard propone que existe una matriz de Hadamard de orden 4 k para cada entero positivo k . La conjetura de Hadamard también se ha atribuido a Paley, aunque otros la habían considerado de forma implícita antes del trabajo de Paley. ^[3]

Una generalización de la construcción de Sylvester demuestra que si y son matrices de Hadamard de órdenes n y m respectivamente, entonces es una matriz de Hadamard de orden nm . Este resultado se utiliza para producir matrices de Hadamard de orden superior una vez que se conocen las de órdenes menores. ${\displaystyle H_{n}}$ ${\displaystyle H_{m}}$ ${\displaystyle H_{n}\otimes H_{m}}$

La construcción de Sylvester de 1867 produce matrices de Hadamard de orden 1, 2, 4, 8, 16, 32, etc. Posteriormente, Hadamard construyó matrices de Hadamard de órdenes 12 y 20 (en 1893). ^[4] En 1933, Raymond Paley descubrió la construcción de Paley , que produce una matriz de Hadamard de orden q + 1 cuando q es cualquier potencia prima congruente con 3 módulo 4 y que produce una matriz de Hadamard de orden 2( q + 1) cuando q es una potencia prima congruente con 1 módulo 4. ^[5] Su método utiliza cuerpos finitos .

El orden más pequeño que no se puede construir mediante una combinación de los métodos de Sylvester y Paley es 92. Baumert, Golomb y Hall encontraron una matriz de Hadamard de este orden usando una computadora en 1962 en el JPL . ^[6] Usaron una construcción, debido a Williamson , ^[7] que ha producido muchos órdenes adicionales. Actualmente se conocen muchos otros métodos para construir matrices de Hadamard.

En 2005, Hadi Kharaghani y Behruz Tayfeh-Rezaie publicaron su construcción de una matriz de Hadamard de orden 428. ^[8] Como resultado, el orden más pequeño para el que actualmente no se conoce ninguna matriz de Hadamard es 668.

En 2014, había 12 múltiplos de 4 menores que 2000 para los que no se conocía ninguna matriz de Hadamard de ese orden. ^[9] Son: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 y 1964.

Equivalencia y unicidad

Dos matrices de Hadamard se consideran equivalentes si una puede obtenerse de la otra negando filas o columnas, o intercambiando filas o columnas. Hasta la equivalencia, existe una única matriz de Hadamard de órdenes 1, 2, 4, 8 y 12. Hay 5 matrices no equivalentes de orden 16, 3 de orden 20, 60 de orden 24 y 487 de orden 28. Se conocen millones de matrices no equivalentes para órdenes 32, 36 y 40. Utilizando una noción más burda de equivalencia que también permite la transposición , hay 4 matrices no equivalentes de orden 16, 3 de orden 20, 36 de orden 24 y 294 de orden 28. ^[10]

Las matrices de Hadamard también son recuperables de manera única, en el sentido siguiente: si una matriz de Hadamard de orden tiene entradas eliminadas aleatoriamente, entonces, con una probabilidad abrumadora, se puede recuperar perfectamente la matriz original a partir de la dañada. El algoritmo de recuperación tiene el mismo costo computacional que la inversión de matrices. ^[11] ${\displaystyle H}$ ${\displaystyle n}$ ${\displaystyle O(n^{2}/\log n)}$ ${\displaystyle H}$

Casos especiales

Se han investigado muchos casos especiales de matrices de Hadamard en la literatura matemática.

Matrices de Hadamard sesgadas

Una matriz de Hadamard H es asimétrica si Una matriz de Hadamard asimétrica sigue siendo una matriz de Hadamard asimétrica después de multiplicar cualquier fila y su columna correspondiente por −1. Esto permite, por ejemplo, normalizar una matriz de Hadamard asimétrica de modo que todos los elementos de la primera fila sean iguales a 1. ${\displaystyle H^{\textsf {T}}+H=2I.}$

Reid y Brown en 1972 demostraron que existe un torneo doblemente regular de orden n si y solo si existe una matriz Hadamard sesgada de orden n  + 1. En un torneo matemático de orden n , cada uno de los n jugadores juega un partido contra cada uno de los otros jugadores, y cada partido resulta en una victoria para uno de los jugadores y una derrota para el otro. Un torneo es regular si cada jugador gana el mismo número de partidos. Un torneo regular es doblemente regular si el número de oponentes derrotados por ambos de dos jugadores distintos es el mismo para todas las parejas de jugadores distintos. Dado que cada uno de los n ( n − 1)/2 partidos jugados resulta en una victoria para uno de los jugadores, cada jugador gana ( n − 1)/2 partidos (y pierde el mismo número). Dado que cada uno de los ( n − 1)/2 jugadores derrotados por un jugador dado también pierde ante ( n − 3)/2 otros jugadores, el número de pares de jugadores ( i , j  ) tales que j pierde tanto ante i como ante el jugador dado es ( n − 1)( n − 3)/4. Se debería obtener el mismo resultado si los pares se cuentan de forma diferente: el jugador dado y cualquiera de los n − 1 otros jugadores juntos derrotan al mismo número de oponentes comunes. Por tanto, este número común de oponentes derrotados debe ser ( n − 3)/4. Se obtiene una matriz de Hadamard sesgada introduciendo un jugador adicional que derrota a todos los jugadores originales y luego formando una matriz con filas y columnas etiquetadas por jugadores de acuerdo con la regla de que la fila i , columna j contiene 1 si i  =  j o i derrota a j y −1 si j derrota a i . Esta correspondencia a la inversa produce un torneo doblemente regular a partir de una matriz de Hadamard sesgada, suponiendo que la matriz de Hadamard sesgada está normalizada de modo que todos los elementos de la primera fila sean iguales a 1. ^[12]

Matrices regulares de Hadamard

Las matrices de Hadamard regulares son matrices de Hadamard reales cuyas sumas de filas y columnas son todas iguales. Una condición necesaria para la existencia de una matriz de Hadamard regular de n  ×  n es que n sea un número cuadrado . Una matriz circulante es manifiestamente regular y, por lo tanto, una matriz de Hadamard circulante tendría que ser de orden cuadrado. Además, si existiera una matriz de Hadamard circulante de n  ×  n con n > 1, entonces n tendría que ser necesariamente de la forma 4 u ² con u impar. ^{[13] [14]}

Matrices circulantes de Hadamard

Sin embargo, la conjetura de la matriz circulante de Hadamard afirma que, aparte de los ejemplos conocidos de 1 × 1 y 4 × 4, no existen matrices de ese tipo. Esto se verificó para todos los valores de u menores de 10 ⁴ , excepto 26 . ^[15]

Generalizaciones

Una generalización básica es una matriz de ponderación . Una matriz de ponderación es una matriz cuadrada en la que las entradas también pueden ser cero y que satisface, para algún w, su peso. Una matriz de ponderación con su peso igual a su orden es una matriz de Hadamard. ^[16] ${\displaystyle WW^{\textsf {T}}=wI}$

Otra generalización define una matriz de Hadamard compleja como una matriz en la que las entradas son números complejos de módulo unitario y que satisface HH ^* = n I _n donde H ^* es la transpuesta conjugada de H. Las matrices de Hadamard complejas surgen en el estudio de las álgebras de operadores y la teoría de la computación cuántica . Las matrices de Hadamard de tipo Butson son matrices de Hadamard complejas en las que las entradas se toman como raíces q ^-ésimas de la unidad . El término matriz de Hadamard compleja ha sido utilizado por algunos autores para referirse específicamente al caso q = 4.

Aplicaciones prácticas

• Olivia MFSK : un protocolo digital de radioaficionado diseñado para funcionar en condiciones difíciles (baja relación señal/ruido más propagación por trayectos múltiples) en bandas de onda corta.
• Replicación repetida balanceada (BRR): una técnica utilizada por los estadísticos para estimar la varianza de un estimador estadístico .
• Espectrometría de apertura codificada : instrumento para medir el espectro de la luz . El elemento de máscara utilizado en los espectrómetros de apertura codificada suele ser una variante de una matriz de Hadamard.
• Redes de retardo de retroalimentación: dispositivos de reverberación digital que utilizan matrices de Hadamard para combinar valores de muestra
• Diseño de experimentos de Plackett-Burman para investigar la dependencia de alguna cantidad medida de un número de variables independientes .
• Diseños de parámetros robustos para investigar los impactos del factor ruido en las respuestas
• Detección comprimida para procesamiento de señales y sistemas lineales subdeterminados (problemas inversos)
• Puerta de Hadamard cuántica para computación cuántica y transformada de Hadamard para algoritmos cuánticos.

Véase también

• Diseño combinatorio
• Transformación de Hadamard
• Matriz quincuncial
• Matriz de Walsh
• Matriz de ponderación
• Puerta lógica cuántica

Notas

1. "Matrices y diseños de Hadamard" (PDF) . UC Denver . Consultado el 11 de febrero de 2023 .
2. JJ Sylvester. Reflexiones sobre matrices ortogonales inversas, sucesiones de signos simultáneas y pavimentos teselados de dos o más colores, con aplicaciones a la regla de Newton, la cerámica ornamental y la teoría de números. Philosophical Magazine , 34:461–475, 1867
3. Hedayat, A.; Wallis, WD (1978). "Matrices de Hadamard y sus aplicaciones". Anales de Estadística . 6 (6): 1184–1238. doi : 10.1214/aos/1176344370 . JSTOR  2958712. MR  0523759..
4. Hadamard, J. (1893). "Résolution d'une question relativa aux determinantes". Boletín de Ciencias Matemáticas . 17 : 240–246.
5. Paley, REAC (1933). "Sobre matrices ortogonales". Revista de Matemáticas y Física . 12 (1–4): 311–320. doi :10.1002/sapm1933121311.
6. Baumert, L.; Golomb, SW; Hall, M. Jr. (1962). "Descubrimiento de una matriz de Hadamard de orden 92". Boletín de la Sociedad Matemática Americana . 68 (3): 237–238. doi : 10.1090/S0002-9904-1962-10761-7 . MR  0148686.
7. Williamson, J. (1944). "Teorema del determinante de Hadamard y la suma de cuatro cuadrados". Duke Mathematical Journal . 11 (1): 65–81. doi :10.1215/S0012-7094-44-01108-7. MR  0009590.
8. Kharaghani, H.; Tayfeh-Rezaie, B. (2005). "Una matriz de Hadamard de orden 428". Revista de diseños combinatorios . 13 (6): 435–440. doi :10.1002/jcd.20043. S2CID  17206302.
9. Đoković, Dragomir Ž; Golubitsky, Oleg; Kotsireas, Ilias S. (2014). "Algunos nuevos órdenes de matrices Hadamard y Skew-Hadamard". Revista de diseños combinatorios . 22 (6): 270–277. arXiv : 1301.3671 . doi :10.1002/jcd.21358. S2CID  26598685.
10. Wanless, IM (2005). "Permanentes de matrices de unos con signo". Álgebra lineal y multilineal . 53 (6): 427–433. doi :10.1080/03081080500093990. S2CID  121547091.
11. Kline, J. (2019). "Búsqueda geométrica de matrices de Hadamard". Ciencias de la computación teórica . 778 : 33–46. doi : 10.1016/j.tcs.2019.01.025 . S2CID  126730552.
12. Reid, KB; Brown, Ezra (1972). "Los torneos doblemente regulares son equivalentes a matrices Hadamard sesgadas". Journal of Combinatorial Theory, Serie A . 12 (3): 332–338. doi : 10.1016/0097-3165(72)90098-2 .
13. Turyn, RJ (1965). "Sumas de caracteres y conjuntos de diferencias". Revista del Pacífico de Matemáticas . 15 (1): 319–346. doi : 10.2140/pjm.1965.15.319 . MR  0179098.
14. Turyn, RJ (1969). "Secuencias con pequeña correlación". En Mann, HB (ed.). Códigos de corrección de errores . Nueva York: Wiley. págs. 195–228.
15. Schmidt, B. (1999). "Números enteros ciclotómicos y geometría finita". Revista de la Sociedad Americana de Matemáticas . 12 (4): 929–952. doi : 10.1090/S0894-0347-99-00298-2 . hdl : 10356/92085 . JSTOR  2646093.
16. Geramita, Anthony V.; Pullman, Norman J.; Wallis, Jennifer S. (1974). "Familias de matrices de pesaje". Boletín de la Sociedad Matemática Australiana . 10 (1). Cambridge University Press (CUP): 119–122. doi :10.1017/s0004972700040703. ISSN  0004-9727. S2CID  122560830.

Lectura adicional

• Baumert, LD; Hall, Marshall (1965). "Matrices de Hadamard del tipo Williamson". Math. Comp . 19 (91): 442–447. doi : 10.1090/S0025-5718-1965-0179093-2 . MR  0179093.
• Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). "Matrices de Hadamard, diseños ortogonales y algoritmos de construcción". Designs 2002: Further computational and constructive design theory (Diseños 2002: teoría de diseño computacional y constructivo adicional ). Boston: Kluwer. págs. 133–205. ISBN. 978-1-4020-7599-5.
• Goethals, JM; Seidel, JJ (1970). "Una matriz de Hadamard sesgada de orden 36". J. Austral. Math. Soc . 11 (3): 343–344. doi :10.1017/S144678870000673X. S2CID  14193297.
• Kimura, Hiroshi (1989). "Nueva matriz de Hadamard de orden 24". Graphs and Combinatorics . 5 (1): 235–242. doi :10.1007/BF01788676. S2CID  39169723.
• Mood, Alexander M. (1964). "Sobre el problema de ponderación de Hotelling". Anales de estadística matemática . 17 (4): 432–446. doi : 10.1214/aoms/1177730883 .
• Reid, KB; Brown, E. (1972). "Los torneos doblemente regulares son equivalentes a matrices de Hadamard sesgadas". J. Combin. Theory Ser. A . 12 (3): 332–338. doi : 10.1016/0097-3165(72)90098-2 .
• Seberry Wallis, Jennifer (1976). "Sobre la existencia de matrices de Hadamard". J. Comb. Theory A . 21 (2): 188–195. doi : 10.1016/0097-3165(76)90062-5 .
• Seberry, Jennifer (1980). "Una construcción para matrices de Hadamard generalizadas". J. Statist. Plann. Infer . 4 (4): 365–368. doi :10.1016/0378-3758(80)90021-X.
• Seberry, J.; Wysocki, B.; Wysocki, T. (2005). "Sobre algunas aplicaciones de las matrices de Hadamard". Metrika . 62 (2–3): 221–239. doi :10.1007/s00184-005-0415-y. S2CID  40646.
• Spence, Edward (1995). "Clasificación de matrices Hadamard de orden 24 y 28". Matemáticas discretas . 140 (1–3): 185–242. doi : 10.1016/0012-365X(93)E0169-5 .
• Yarlagadda, RK; Hershey, JE (1997). Análisis y síntesis de matrices de Hadamard . Boston: Kluwer. ISBN 978-0-7923-9826-4.

Enlaces externos

• Matrices de Hadamard sesgadas de todos los órdenes hasta 100, incluyendo cualquier tipo con orden hasta 28;
• "Matriz de Hadamard".en la OEIS
• NJA Sloane . "Biblioteca de matrices de Hadamard".
• Utilidad en línea para obtener todos los pedidos hasta 1000, excepto 668, 716, 876 y 892.
• Paquete R para generar matrices de Hadamard usando R
• JPL: En 1961, matemáticos del Laboratorio de Propulsión a Chorro de la NASA y Caltech trabajaron juntos para construir una Matriz Hadamard que contenía 92 filas y columnas.