Matriz de Hadamard

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Gilbert Strang demuestra la conjetura 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 paralelotopo n-dimensional abarcado por las filas de una matriz de Hadamard n×n tiene el máximo n posible. Volumen i>-dimensional entre 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 de Hadamard'. El problema del determinante máximo de 39;

Ciertas matrices de Hadamard pueden usarse casi directamente como un código de corrección de errores utilizando un código Hadamard (generalizado en los códigos 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^{textosf {T}=nI_{n}

Donde I_n es n × n matriz de identidad y H^T es la transposición de H. Para ver que esto es cierto, note que las filas de H son todos los vectores ortogonales sobre el campo de números reales y cada uno tiene longitud ${displaystyle {sqrt {n}}$ . Dividir H a través de esta longitud da una matriz ortogonal cuya transposición es así su inverso. Multiplying by the length again gives the equality above. Como resultado,

{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 |M_ij | ≤ 1, para cada i, j entre 1 y n. Entonces la cota determinante de Hadamard establece que

{displaystyle Silenciooperatorname {det} (M) Previousleq n^{n/2}

La igualdad en esta cota 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.

Prueba
La prueba de la noexistencia de matrices Hadamard con dimensiones distintas de 1, 2, o múltiples de 4 sigue: Si ${displaystyle n confía1}$ , entonces hay al menos un producto de escalar de 2 filas que tiene que ser 0. El producto del cuero cabelludo es una suma de n valores cada uno de los cuales es 1 o -1, por lo tanto la suma es extraña nAsí que n Debe ser igual. Si ${displaystyle n=4m+2}$ con ${displaystyle mgeq 1}$ , y existe ${displaystyle ntimes n}$ Matriz de Hadamard ${displaystyle H=(h_{i,j})_{i,jin {0,1,...,n-1}}$ , entonces tiene la propiedad que para cualquier ${displaystyle kneq l}$ : ${displaystyle sum _{i=0}{n-1}h_{k,i}h_{l,i}=0}$ Ahora definimos la matriz ${displaystyle A=(a_{i,j})_{i,jin {0,1,...,n-1}}}$ por configuración ${displaystyle a_{i,j}=h_{0,j}h_{i,j}$ . Note que ${displaystyle A}$ tiene todos 1s en fila 0. Revisamos que la matriz ${displaystyle A}$ es también una matriz Hadamard: ${displaystyle sum ¿Por qué? ¿Por qué? ¿Por qué? ¿Qué?$ Fila 1 y fila 2, como todas las otras filas excepto la fila 0, debe tener ${fnMicroc} {n}{2}}$ entradas de 1 y ${fnMicroc} {n}{2}}$ entradas de -1 cada una. () Vamos ${displaystyle alpha }$ denota el número de 1s de fila 2 debajo de 1s en fila 1. Vamos ${displaystyle beta }$ denota el número de -1s de fila 2 bajo 1s en fila 1. Vamos ${displaystyle gamma }$ denota el número de 1s de fila 2 bajo -1s en la fila 1. Vamos ${displaystyle delta }$ denota el número de -1s de fila 2 debajo -1s en la fila 1. La fila 2 tiene que ser ortogonal a fila 1, por lo que el número de productos de las entradas de las filas resulta en 1, ${displaystyle alpha +delta }$ , tiene que coincidir con los que resultan en -1, ${displaystyle beta +gamma }$ . Debido a (), también tenemos ${displaystyle {frac {fn}}=alpha +gamma =beta +delta }$ , desde el cual podemos expresar ${displaystyle gamma ={frac {n}{2}-alpha }$ y ${displaystyle delta ={frac {n}{2}-beta}$ y sustituto: ${displaystyle alpha +delta =beta +gamma }$ ${displaystyle alpha +{frac {n}{2}-beta =beta +{frac {n}{2}-alpha }$ ${displaystyle alpha -beta =beta - Alpha.$ ${displaystyle alpha =beta }$ Pero tenemos como el número de 1s en fila 1 el número impar ${displaystyle {frac {fn}}=alpha #$ , contradicción.

Prueba

La prueba de la noexistencia de matrices Hadamard con dimensiones distintas de 1, 2, o múltiples de 4 sigue:

Si ${displaystyle n confía1}$ , entonces hay al menos un producto de escalar de 2 filas que tiene que ser 0. El producto del cuero cabelludo es una suma de n valores cada uno de los cuales es 1 o -1, por lo tanto la suma es extraña nAsí que n Debe ser igual.

Si ${displaystyle n=4m+2}$ con ${displaystyle mgeq 1}$ , y existe ${displaystyle ntimes n}$ Matriz de Hadamard ${displaystyle H=(h_{i,j})_{i,jin {0,1,...,n-1}}$ , entonces tiene la propiedad que para cualquier ${displaystyle kneq l}$ :

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

Ahora definimos la matriz ${displaystyle A=(a_{i,j})_{i,jin {0,1,...,n-1}}}$ por configuración ${displaystyle a_{i,j}=h_{0,j}h_{i,j}$ . Note que ${displaystyle A}$ tiene todos 1s en fila 0. Revisamos que la matriz ${displaystyle A}$ es también una matriz Hadamard:

{displaystyle sum ¿Por qué? ¿Por qué? ¿Por qué? ¿Qué?

Fila 1 y fila 2, como todas las otras filas excepto la fila 0, debe tener ${fnMicroc} {n}{2}}$ entradas de 1 y ${fnMicroc} {n}{2}}$ entradas de -1 cada una. (*)

Vamos ${displaystyle alpha }$ denota el número de 1s de fila 2 debajo de 1s en fila 1. Vamos ${displaystyle beta }$ denota el número de -1s de fila 2 bajo 1s en fila 1. Vamos ${displaystyle gamma }$ denota el número de 1s de fila 2 bajo -1s en la fila 1. Vamos ${displaystyle delta }$ denota el número de -1s de fila 2 debajo -1s en la fila 1.

La fila 2 tiene que ser ortogonal a fila 1, por lo que el número de productos de las entradas de las filas resulta en 1, ${displaystyle alpha +delta }$ , tiene que coincidir con los que resultan en -1, ${displaystyle beta +gamma }$ . Debido a (*), también tenemos ${displaystyle {frac {fn}}=alpha +gamma =beta +delta }$ , desde el cual podemos expresar ${displaystyle gamma ={frac {n}{2}-alpha }$ y ${displaystyle delta ={frac {n}{2}-beta}$ y sustituto:

{displaystyle alpha +delta =beta +gamma }

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

{displaystyle alpha -beta =beta - Alpha.

{displaystyle alpha =beta }

Pero tenemos como el número de 1s en fila 1 el número impar ${displaystyle {frac {fn}}=alpha #$ , contradicción.

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 pacienteHH recur-Hend{bmatrix}}

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

{begin} {begin} {begin {bmatrix}1end{bmatrix}}},H_{2} limit={begin{bmatrix}1}1}1}1}11111 {cH_{4}}}}} {begin{1begin{1}

{displaystyle H_{2^{k}={begin{bmatrix}H_{2^{k-1} {2^{k-1}H_{2^{k-1} {k-1}} {2^{k-1} {2^{k-1}end{bmatrix}}=H_{2}otimes H_{2^{k-1}}}

para ${displaystyle 2leq kin N}$ , donde ${displaystyle otimes }$ denota el producto Kronecker.

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

Las matrices de Sylvester tienen una serie de 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 Hadamard usando el homomorfismo grupo ${displaystyle {1,-1,times }mapsto {0,1,oplus }$ , podemos describir una construcción alternativa de la matriz Hadamard de Sylvester. Primera consideración de la matriz ${displaystyle F_{n}$ , el ${displaystyle ntimes 2^{n}$ matriz cuyas columnas constan de todas n- números de bits dispuestos en orden ascendente. Podemos definir ${displaystyle F_{n}$ recursivamente por

{displaystyle {begin{aligned}F_{1} limit={begin{bmatrix}0 limit1end{bmatrix}}\F_{n} limit={begin{bmatrix}0_{1times 2^{n-1} {1_{1times 2^{n-1}\F_{n-1} {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 Hadamard ${displaystyle H_{2^{n}}$ se puede ver como una longitud ${displaystyle 2^{n}$ código lineal de corrección de errores n, y distancia mínima ${displaystyle 2^{n-1}$ con matriz generadora ${displaystyle F_{n}.$

Este código también se denomina código Walsh. El código Hadamard, por contraste, se construye a partir de la matriz Hadamard ${displaystyle H_{2^{n}}$ por un procedimiento ligeramente diferente.

Conjetura de Hadamard

Problema no resuelto en matemáticas:

¿Hay una matriz Hadamard del orden 4k para cada entero positivo k?

(Problemas más no resueltos en matemáticas)

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 4k 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.

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

La construcción de Sylvester en 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). 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. Su método utiliza 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. Baumert, Golomb y Hall encontraron una matriz de Hadamard de este orden usando una computadora en 1962 en JPL. Utilizaron una construcción, debida a Williamson, 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. Como resultado, el orden más pequeño para el cual no se conoce ninguna matriz de Hadamard actualmente es 668.

A partir de 2014, hay 12 múltiplos de 4 menores o iguales a 2000 para los cuales no se conoce ninguna matriz de Hadamard de ese orden. Ellos 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 se puede obtener 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 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.

Las matrices hadamard también son únicamente recuperables, en el siguiente sentido: Si una matriz Hadamard ${displaystyle H.$ de orden ${displaystyle n}$ tiene ${displaystyle O(n^{2}/log n)}$ entradas eliminadas al azar, entonces con abrumadora probabilidad, uno puede recuperar perfectamente la matriz original ${displaystyle H.$ del dañado. El algoritmo de recuperación tiene el mismo costo computacional que la inversión de matriz.

Casos especiales

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

Matrices sesgadas de Hadamard

Una matriz Hadamard H es Skew si ${displaystyle H^{textsf - Sí.$ Una matriz de Hadamard se mantiene como una matriz Hadamard de puño después de la multiplicación de cualquier fila y su columna correspondiente por −1. Esto hace posible, por ejemplo, normalizar una matriz Hadamard de corte para que todos los elementos en la primera fila sean iguales 1.

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 En un torneo matemático de orden n, cada uno de los n jugadores juega un partido contra cada uno de los demás 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 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 coincidencias (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 jugadores más, el número de parejas de jugadores (i, j) tal que j pierde tanto contra i como contra el jugador dado es (n −1) (n−3) / 4. Se debe obtener el mismo resultado si se cuentan las parejas de forma diferente: el jugador dado y cualquiera de los (n−1) otros jugadores derrotan juntos al mismo número de oponentes comunes. Por lo 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>i vence 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, asumiendo que la matriz sesgada de Hadamard está normalizada de modo que todos los elementos de la primera fila sean iguales a 1.

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 tanto, una matriz de Hadamard circulante tendría que ser de orden cuadrado perfecto. Además, si un Hadamard circulante n×n la matriz existía con n > 1 entonces n necesariamente tendría que ser de la forma 4u² con u impar.

Matrices de Hadamard circulantes

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⁴.

Generalizaciones

Una generalización básica es una matriz de pesaje. Una matriz de pesaje es una matriz cuadrada en la que las entradas también pueden ser cero y que satisfice ${displaystyle WW^{textsf {T}=wI}$ para algunos, su peso. Una matriz de pesaje con su peso igual a su orden es una matriz Hadamard.

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 H H^* = n I_n 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^ésima 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 trabajar en condiciones difíciles (bajo ratio de señal a ruido y propagación multipática) en bandas de onda corta.
Repetición equilibrada (BRR) – técnica utilizada por los estadísticos para estimar la varianza de un estimador estadístico.
Espectrometría de abertura codificada – un instrumento para medir el espectro de la luz. El elemento de máscara utilizado en espectrómetros de abertura codificada es a menudo una variante de una matriz Hadamard.
Redes de retraso de retroalimentación – Dispositivos de reverberación digital que utilizan matrices Hadamard para combinar valores de muestra
Plackett–Burman diseño de experimentos 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
Sensación comprimida para el procesamiento de señales y sistemas lineales subdeterminados (problemas inversos)
Puerta de Hadamard Quantum para la computación cuántica y la transformación Hadamard para algoritmos cuánticos.

Contenido relacionado

Más resultados...