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í en honor al 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. Una consecuencia de esta definición es que las propiedades correspondientes se aplican tanto a las columnas como a las filas.

El n -paralelotopo 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 un determinante máximo entre matrices con entradas de valor absoluto menor o igual a 1 y por lo tanto es una solución extrema del problema determinante máximo de Hadamard .

Ciertas matrices de Hadamard se pueden usar casi directamente como un código de corrección de errores usando un código de Hadamard (generalizado en los códigos de Reed-Muller ), y también se usan 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 In _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 todas vectores ortogonales sobre el campo de números reales y cada una tiene longitud. Dividir H por esta longitud da una matriz ortogonal cuya transpuesta es, por tanto, su inversa. Multiplicar 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 .

Supongamos que M es una matriz compleja de orden n , cuyas entradas están acotadas por | Mij  ​​|_​ ≤ 1, para cada i , j entre 1 y n . Entonces la cota determinante de Hadamard establece que

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

La igualdad en este límite se logra 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 múltiplo de 4. ^[1]

La construcción de Sylvester.

En realidad , James Joseph Sylvester construyó por primera vez ejemplos de matrices de Hadamard 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 se puede aplicar 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}},}$

for , 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étricos y, cuando k  ≥ 1 (2 ^k  > 1), tienen traza cero. Los elementos de la primera columna y de la primera fila son todos positivos. Los elementos de todas las demás filas y columnas se dividen uniformemente 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. Consideremos primero la matriz , la matriz cuyas columnas constan de 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 pueden verse como un código de corrección de errores lineal de longitud de rango n y 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 no resuelto 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 la existencia. Específicamente, 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 consideraron implícitamente antes del trabajo de Paley. ^[3]

Una generalización de la construcción de Sylvester demuestra que si y son matrices de Hadamard de orden 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 orden menor. ${\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 que es congruente con 3 módulo 4 y que produce una matriz de Hadamard de orden 2 ( q + 1) cuando q es una potencia prima que es congruente con 1 módulo 4. ^[5] Su método utiliza campos finitos .

El orden más pequeño que no puede construirse 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 utilizando una computadora en 1962 en el JPL . ^[6] Utilizaron una construcción, debida a Williamson , ^[7] que ha generado muchos pedidos 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 cual no se conoce actualmente ninguna matriz de Hadamard es 668.

En 2014, había 12 múltiplos de 4 menores que 2000 para los cuales 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 matriz de Hadamard única 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. Millones de Se conocen matrices no equivalentes de orden 32, 36 y 40. Usando una noción más aproximada 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 forma única, en el siguiente sentido: si una matriz de orden de Hadamard tiene entradas eliminadas aleatoriamente, entonces, con una probabilidad abrumadora, se puede recuperar perfectamente la matriz original de la dañada. El algoritmo de recuperación tiene el mismo coste computacional que la inversión de matrices. ^[11] ${\displaystyle H}$ ${\displaystyle n}$ ${\displaystyle O(n^{2}/\log n)}$ ${\displaystyle H}$

Casos especiales

En la literatura matemática se han investigado muchos casos especiales de matrices de Hadamard.

Sesgar matrices de Hadamard

Una matriz de Hadamard H es asimétrica si Una matriz de Hadamard sesgada sigue siendo una matriz de Hadamard sesgada después de multiplicar cualquier fila y su columna correspondiente por −1. Esto hace posible, por ejemplo, normalizar una matriz sesgada de Hadamard para 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 sólo si existe una matriz sesgada de Hadamard 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, cada partido resultando 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 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 determinado también pierde contra ( n − 3)/2 otros jugadores, el número de parejas de jugadores ( i , j  ) tales que j pierde tanto contra i como contra el jugador dado es ( n − 1)( n − 3)/4. Se debe obtener el mismo resultado si las parejas se cuentan de manera diferente: el jugador dado y cualquiera de los n − 1 otros jugadores derrotan juntos al mismo número de oponentes comunes. Por tanto, este número común de oponentes derrotados debe ser ( n − 3)/4. Una matriz sesgada de Hadamard se obtiene introduciendo un jugador adicional que derrota a todos los jugadores originales y luego formando una matriz con filas y columnas etiquetadas por los jugadores de acuerdo con la regla de que la fila i , la columna j contiene 1 si i  =  j o i derrota a j. y −1 si j vence a i . Esta correspondencia a la inversa produce un torneo doblemente regular a partir de una matriz sesgada de Hadamard, suponiendo que la matriz sesgada de Hadamard 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 tanto, una matriz circulante de Hadamard tendría que ser de orden cuadrático. Además, si existiera una matriz de Hadamard circulante de n  ×  n con n > 1, entonces n necesariamente tendría que ser 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 tales matrices. Esto se verificó para todos menos 26 valores de u menores que 10 ⁴ . ^[15]

Generalizaciones

Una generalización básica es una matriz de ponderación . Una matriz de pesaje 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 pesaje con su peso igual a su orden es una matriz de Hadamard. ^[dieciséis] ${\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 In _donde H * ^es la transpuesta conjugada de H. Las matrices complejas de Hadamard 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 consideran raíces q ^-ésimas de la unidad . El término matriz compleja de Hadamard ha sido utilizado por algunos autores para referirse específicamente al caso q = 4.

Aplicaciones prácticas

• Olivia MFSK : un protocolo digital para radioaficionados 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 equilibrada (BRR): una técnica utilizada por los estadísticos para estimar la varianza de un estimador estadístico .
• Espectrometría de apertura codificada : un 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 digitales 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 varias variables independientes .
• Diseños de parámetros sólidos para investigar los impactos del factor de ruido en las respuestas.
• Sensación comprimida para procesamiento de señales y sistemas lineales indeterminados (problemas inversos)
• Puerta cuántica de Hadamard para computación cuántica y transformada de Hadamard para algoritmos cuánticos.

Ver también

• Diseño combinatorio
• Transformada de Hadamard
• matriz quincunce
• matriz de Walsh
• matriz de pesaje
• Puerta lógica cuántica

Notas

1. "Matrices y diseños de Hadamard" (PDF) . Universidad de California en Denver . Consultado el 11 de febrero de 2023 .
2. JJ Silvestre. Reflexiones sobre matrices ortogonales inversas, sucesiones de signos simultáneas y pavimentos teselado en dos o más colores, con aplicaciones a la regla de Newton, azulejos ornamentales y teoría de números. Revista filosófica , 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. SEÑOR  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, suroeste; Hall, M. Jr. (1962). "Descubrimiento de una matriz Hadamard de orden 92". Boletín de la Sociedad Matemática Estadounidense . 68 (3): 237–238. doi : 10.1090/S0002-9904-1962-10761-7 . SEÑOR  0148686.
7. Williamson, J. (1944). "El teorema determinante de Hadamard y la suma de cuatro cuadrados". Revista de Matemáticas de Duke . 11 (1): 65–81. doi :10.1215/S0012-7094-44-01108-7. SEÑOR  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 firmados". Á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". Informática Teórica . 778 : 33–46. doi : 10.1016/j.tcs.2019.01.025 . S2CID  126730552.
12. Reid, KB; Marrón, Ezra (1972). "Los torneos doblemente regulares equivalen a sesgar matrices hadamard". Revista de teoría combinatoria, 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 Pacífico de Matemáticas . 15 (1): 319–346. doi : 10.2140/pjm.1965.15.319 . SEÑOR  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). "Enteros ciclotómicos y geometría finita". Revista de la Sociedad Matemática Estadounidense . 12 (4): 929–952. doi : 10.1090/S0894-0347-99-00298-2 . hdl : 10356/92085 . JSTOR  2646093.
16. Geramita, Antonio V.; Pullman, Norman J.; Wallis, Jennifer S. (1974). "Familias de matrices de pesaje". Boletín de la Sociedad Australiana de Matemáticas . 10 (1). Prensa de la Universidad de Cambridge (CUP): 119–122. doi :10.1017/s0004972700040703. ISSN  0004-9727. S2CID  122560830.

Otras lecturas

• Baumert, LD; Salón, Marshall (1965). "Matrices de Hadamard del tipo Williamson". Matemáticas. comp . 19 (91): 442–447. doi : 10.1090/S0025-5718-1965-0179093-2 . SEÑOR  0179093.
• Georgiou, S.; Koukouvinos, C.; Seberry, J. (2003). "Matrices de Hadamard, diseños ortogonales y algoritmos de construcción". Designs 2002: Más teoría del diseño constructivo y computacional . Boston: Kluwer. págs. 133-205. ISBN 978-1-4020-7599-5.
• Goethals, JM; Seidel, JJ (1970). "Una matriz sesgada de Hadamard de orden 36". J.Austral. Matemáticas. Soc . 11 (3): 343–344. doi :10.1017/S144678870000673X. S2CID  14193297.
• Kimura, Hiroshi (1989). "Nueva matriz de Hadamard de orden 24". Gráficas y Combinatoria . 5 (1): 235–242. doi :10.1007/BF01788676. S2CID  39169723.
• Estado de ánimo, Alexander M. (1964). "Sobre el problema del pesaje de Hotelling". Anales de estadística matemática . 17 (4): 432–446. doi : 10.1214/aoms/1177730883 .
• Reid, KB; Marrón, E. (1972). "Los torneos doblemente regulares equivalen a sesgar las matrices de Hadamard". J. Combinar. Teoría 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. peine. Teoría A. 21 (2): 188-195. doi : 10.1016/0097-3165(76)90062-5 .
• Seberry, Jennifer (1980). "Una construcción para matrices hadamard generalizadas". J. Estatista. Planificar. Inferir . 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". Métrica . 62 (2–3): 221–239. doi :10.1007/s00184-005-0415-y. S2CID  40646.
• Spence, Eduardo (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 la matriz de Hadamard . Boston: Kluwer. ISBN 978-0-7923-9826-4.

enlaces externos

• Sesgar matrices de Hadamard de todos los órdenes hasta 100, incluidos todos los tipos con orden hasta 28;
• "Matriz de Hadamard".en OEIS
• NJA Sloane . "Biblioteca de matrices de Hadamard".
• Utilidad online para obtener todos los pedidos hasta 1000, excepto 668, 716, 876 y 892.
• Paquete R para generar matrices 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.