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 sean válidas tanto para columnas como para filas. El paralelootopo n- dimensionaldividido por las filas de una matriz de Hadamard n × n tiene el volumen n- dimensional máximo posible entre los paraleótopos divididos por vectores cuyas entradas están limitadas en valor absoluto por 1. De manera equivalente, una matriz de Hadamard tiene un determinante máximo entre matrices con entradas de valor absoluto menos que 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 códigos Reed-Muller ), y también se usan en la replicación repetida balanceada (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 echo:
donde I n es el n × n matriz identidad 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 una longitud. Dividir H por esta longitud da una matriz ortogonal cuya transposición es, por tanto, su inversa. Multiplicar por la longitud nuevamente da la igualdad anterior. Como resultado,
donde det ( H ) es el determinante de H .
Suponga que M es una matriz compleja de orden n , cuyas entradas están limitadas por | M ij | ≤ 1, para cada i , j entre 1 y n . Entonces la cota determinante de Hadamard establece que
La igualdad en este límite se logra para una matriz real M si y solo 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
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
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 .
y
por , dónde denota el producto Kronecker .
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 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. Primero considera 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
Se puede demostrar por inducción que la imagen de la matriz de Hadamard bajo el homomorfismo anterior está dada por
Esta construcción demuestra que las filas de la matriz de Hadamard se puede ver como una longitud código lineal de corrección de errores de rango n , y distancia mínima con matriz generadora
Este código también se conoce como código Walsh . El código de Hadamard , por el contrario, se construye a partir de la matriz de Hadamard por un procedimiento ligeramente diferente.
Conjetura de Hadamard
La cuestión abierta más importante en la teoría de las matrices de Hadamard es la de la existencia. 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, a continuación,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 más pequeñas.
La construcción de Sylvester de 1867 produce matrices de Hadamard de orden 1, 2, 4, 8, 16, 32, etc. Las matrices de Hadamard de órdenes 12 y 20 fueron posteriormente construidas por Hadamard (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 usa campos 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. Una matriz de Hadamard de este orden fue encontrada usando una computadora por Baumert , Golomb y Hall en 1962 en JPL . [6] Usaron una construcción, debida a Williamson , [7] que ha dado lugar a muchos pedidos adicionales. Ahora 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 Hadamard de orden 428. [8] Como resultado, el orden más pequeño para el que no se conoce actualmente ninguna matriz Hadamard es 668.
A partir de 2008[actualizar], hay 13 múltiplos de 4 menores o iguales que 2000 para los cuales no se conoce una matriz de Hadamard de ese orden. [9] Son: 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 y 1964.
Equivalencia de matrices de Hadamard
Dos matrices de Hadamard se consideran equivalentes si una se puede obtener de la otra negando filas o columnas, o intercambiando filas o columnas. Hasta la equivalencia, hay 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 inequivalentes para los órdenes 32, 36 y 40. Utilizando una noción más burda de equivalencia que también permite la transposición , hay 4 matrices inequivalentes de orden 16, 3 de orden 20, 36 de orden 24 y 294 de orden 28. [ 10]
Casos especiales
Se han investigado muchos casos especiales de matrices de Hadamard en la literatura matemática.
Inclinar matrices de Hadamard
Una matriz de Hadamard H es sesgada siUna matriz de Hadamard sesgada sigue siendo una matriz de Hadamard sesgada después de la multiplicación de cualquier fila y su columna correspondiente por -1. Esto hace posible, por ejemplo, normalizar una matriz de Hadamard sesgada para que todos los elementos de la primera fila sean iguales a 1.
Reid y Brown en 1972 demostraron que existe un torneo doblemente regular de orden n si y solo si existe una matriz de Hadamard sesgada de orden n + 1. En un torneo matemático de orden n , cada uno de n jugadores juega un partido contra cada uno de los los otros jugadores, cada partido resulta en una victoria para uno de los jugadores y una pérdida 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 da como resultado 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 frente a ( n −3) / 2 otros jugadores, el número de pares de jugadores ( i , j ) tales que j pierde tanto para i como para 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 juntos derrotan el mismo número de jugadores comunes oponentes. Por lo 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 que la fila i , la columna j contiene 1 si i = j o i derrota a j y −1 si j derrota a i . Esta correspondencia inversa produce un torneo doblemente regular a partir de una matriz Hadamard sesgada, asumiendo que la matriz Hadamard sesgada está normalizada de modo que todos los elementos de la primera fila sean iguales a 1. [11]
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 n × n es que n sea un cuadrado perfecto. Una matriz circulante es manifiestamente regular y, por lo tanto, una matriz Hadamard circulante tendría que ser de orden cuadrado perfecto. Además, si existiera una matriz de Hadamard circulante n × n con n > 1 entonces n tendría que ser necesariamente de la forma 4 u 2 con u impar. [12] [13]
Matrices circulantes de Hadamard
Sin embargo, la conjetura circulante de la matriz 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 de 10 4 . [14]
Generalizaciones
Una generalización básica es la matriz de ponderación , una matriz cuadrada en la que las entradas también pueden ser cero y que satisfacepara algunos w, su peso. Una matriz de pesaje con su peso igual a su orden es una matriz de Hadamard.
Otra generalización define una matriz de Hadamard complejo a ser una matriz en la que las entradas son números complejos de unidad de módulo y que satisface HH * = n I n donde H * es la transpuesta conjugada de H . Las matrices complejas de Hadamard surgen en el estudio de á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 q- ésima raíz de la unidad . Algunos autores han utilizado el término matriz compleja de Hadamard 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 equilibrada (BRR): 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 luz. El elemento de máscara utilizado en los espectrómetros de apertura codificada es a menudo 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 en una serie de variables independientes.
- Diseños de parámetros robustos para investigar los impactos del factor de ruido en las respuestas
- Detección comprimida para procesamiento de señales y sistemas lineales indeterminados (problemas inversos)
- Puerta cuántica de Hadamard para computación cuántica y la transformada de Hadamard para algoritmos cuánticos.
Ver también
- Diseño combinatorio
- Transformada de Hadamard
- Matriz de quincunx
- Matriz de Walsh
Notas
- ^ http://math.ucdenver.edu/~wcherowi/courses/m6406/hadamard.pdf
- ^ JJ Sylvester. Reflexiones sobre matrices ortogonales inversas, sucesiones de signos simultáneos y pavimentos teselados en dos o más colores, con aplicaciones a la regla de Newton, el trabajo de baldosas ornamentales y la teoría de los números. Revista filosófica , 34: 461–475, 1867
- ^ Hedayat, A .; Wallis, WD (1978). "Matrices de Hadamard y sus aplicaciones" . Annals of Statistics . 6 (6): 1184-1238. doi : 10.1214 / aos / 1176344370 . JSTOR 2958712 . Señor 0523759 ..
- ^ Hadamard, J. (1893). "Resolución de una cuestión relativa a los determinantes". Bulletin des Sciences Mathématiques . 17 : 240–246.
- ^ Paley, REAC (1933). "Sobre matrices ortogonales". Revista de Matemáticas y Física . 12 (1–4): 311–320. doi : 10.1002 / sapm1933121311 .
- ^ Baumert, L .; Golomb, SW; Hall, M., Jr. (1962). "Descubrimiento de una matriz de Hadamard de la orden 92" . Boletín de la American Mathematical Society . 68 (3): 237–238. doi : 10.1090 / S0002-9904-1962-10761-7 . Señor 0148686 .
- ^ Williamson, J. (1944). "Teorema determinante de Hadamard y la suma de cuatro cuadrados". Diario de matemáticas de Duke . 11 (1): 65–81. doi : 10.1215 / S0012-7094-44-01108-7 . Señor 0009590 .
- ^ 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 .
- ^ Đoković, Dragomir Ž (2008). "Existen matrices de Hadamard de orden 764". Combinatorica . 28 (4): 487–489. arXiv : matemáticas / 0703312 . doi : 10.1007 / s00493-008-2384-z . S2CID 123055271 .
- ^ Wanless, MI (2005). "Permanentes de matrices de firmados". Álgebra lineal y multilineal . 53 (6): 427–433. doi : 10.1080 / 03081080500093990 . S2CID 121547091 .
- ^ Reid, KB; Brown, 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 .
- ^ Turyn, RJ (1965). "Sumas de caracteres y conjuntos de diferencias" . Pacific Journal of Mathematics . 15 (1): 319–346. doi : 10.2140 / pjm.1965.15.319 . Señor 0179098 .
- ^ 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.
- ^ 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 . JSTOR 2646093 .
Otras lecturas
- Baumert, LD; Hall, 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". Diseños 2002: Más teoría del diseño computacional y constructivo . 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. Matemáticas. Soc . 11 (3): 343–344. doi : 10.1017 / S144678870000673X .
- Kimura, Hiroshi (1989). "Nueva matriz de Hadamard de orden 24". Gráficos y Combinatoria . 5 (1): 235–242. doi : 10.1007 / BF01788676 . S2CID 39169723 .
- Estado de ánimo, Alexander M. (1964). "Sobre el problema de pesaje 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 equivalen a sesgar las matrices de Hadamard" . J. Combin. Teoría Ser. Una . 12 (3): 332–338. doi : 10.1016 / 0097-3165 (72) 90098-2 .
- Seberry Wallis, Jennifer (1976). "Sobre la existencia de matrices de Hadamard" . J. Combinat. Una teoría . 21 (2): 188-195. doi : 10.1016 / 0097-3165 (76) 90062-5 .
- Seberry, Jennifer (1980). "Una construcción para matrices hadamard generalizadas" . J. Statist. 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 matrices 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 la matriz de Hadamard . Boston: Kluwer. ISBN 978-0-7923-9826-4.
enlaces externos
- Inclinar matrices Hadamard de todos los pedidos hasta 100, incluidos todos los tipos con pedidos hasta 28;
- "Matriz de Hadamard" .en 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.
- 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 contiene 92 filas y columnas.