Lic. Carlos Enrique Loria Beeche
Curso personal de matrices de Hadamard · Lección 1
Una matriz formada solamente por unos y menos unos puede esconder una estructura de equilibrio perfecto. Su definición cabe en pocas líneas, pero conduce a una conjetura matemática que continúa abierta después de más de un siglo.
Comprender qué es una matriz de Hadamard, interpretar geométricamente la ortogonalidad de sus filas, verificar manualmente un ejemplo de orden 4 y demostrar por qué, salvo los casos de órdenes 1 y 2, su orden debe ser múltiplo de 4.
1. Una definición sorprendentemente sencilla
Una matriz de Hadamard es una matriz cuadrada cuyas entradas pertenecen exclusivamente al conjunto \(\{-1,+1\}\) y cuyas filas son mutuamente ortogonales.
Una matriz \(H\) de orden \(n\) es una matriz de Hadamard cuando todas sus entradas son \(+1\) o \(-1\) y satisface:
donde \(H^{\mathsf T}\) es la matriz transpuesta de \(H\) e \(I_n\) es la matriz identidad de orden \(n\).
La igualdad anterior resume dos propiedades:
- El producto escalar de cada fila consigo misma es \(n\), porque contiene \(n\) entradas cuyos cuadrados son iguales a 1.
- El producto escalar de dos filas diferentes es 0.
2. ¿Qué significa que dos filas sean ortogonales?
En geometría estamos acostumbrados a decir que dos líneas son perpendiculares. En álgebra lineal, dos vectores son ortogonales cuando su producto escalar es igual a cero.
Consideremos los vectores:
Su producto escalar es:
Por tanto, \(u\) y \(v\) son ortogonales.
Cuando dos vectores contienen solamente \(+1\) y \(-1\), cada posición donde tienen el mismo signo aporta \(+1\) al producto escalar y cada posición donde tienen signos diferentes aporta \(-1\).
Para que el resultado sea cero, deben coincidir exactamente en la mitad de las posiciones y diferir en la otra mitad.
3. Una matriz de Hadamard de orden 4
El primer ejemplo suficientemente grande para mostrar toda la estructura es la siguiente matriz:
Cada fila contiene cuatro entradas. Por eso, el producto escalar de cualquier fila consigo misma es:
Probemos ahora las filas segunda y tercera:
Lo mismo ocurre con cualquier pareja de filas diferentes. Por tanto:
No es necesario calcular inicialmente todo el producto matricial. Basta comprobar que cada fila tiene longitud cuadrada 4 y que los seis pares de filas diferentes tienen producto escalar igual a cero.
4. Normalizar una matriz
Multiplicar una fila o una columna completa por \(-1\) no destruye la ortogonalidad. Tampoco la destruye intercambiar filas o columnas.
Estas operaciones permiten transformar cualquier matriz de Hadamard en una matriz equivalente cuya primera fila y primera columna contienen solamente \(+1\).
Una matriz de Hadamard se denomina normalizada cuando todas las entradas de su primera fila y de su primera columna son iguales a \(+1\).
La normalización no cambia la existencia de la matriz. Simplemente selecciona una representación especialmente conveniente entre muchas matrices equivalentes.
5. ¿Por qué el orden debe ser múltiplo de 4?
Podemos demostrar esta condición utilizando solamente productos escalares y un argumento de conteo.
Si existe una matriz de Hadamard de orden \(n>2\), entonces:
Supongamos que \(H\) es una matriz de Hadamard normalizada. Su primera fila contiene únicamente unos:
Para que la segunda fila sea ortogonal a la primera, debe contener la misma cantidad de \(+1\) y de \(-1\). En consecuencia, \(n\) debe ser par.
Después de permutar columnas, podemos escribir la segunda fila así:
Consideremos ahora una tercera fila \(r_3\). Sea \(a\) la cantidad de entradas \(+1\) de \(r_3\) situadas en la primera mitad de las columnas, y sea \(b\) la cantidad de entradas \(+1\) situadas en la segunda mitad.
Como \(r_3\) debe ser ortogonal a la primera fila, contiene exactamente \(n/2\) entradas positivas:
Como también debe ser ortogonal a la segunda fila, las contribuciones de ambas mitades deben equilibrarse. Esto obliga a que:
Combinando ambas igualdades obtenemos:
Como \(a\) es un número entero, \(n/4\) también debe ser entero. Por tanto, \(n\) es divisible por 4.
Hemos demostrado una condición necesaria: si una matriz de Hadamard de orden mayor que 2 existe, su orden debe ser múltiplo de 4.
No hemos demostrado la afirmación inversa. Saber que un número es múltiplo de 4 no nos proporciona automáticamente una matriz de Hadamard de ese orden.
6. La conjetura de Hadamard
Los órdenes 1 y 2 poseen matrices de Hadamard. Para órdenes mayores, acabamos de demostrar que solo debemos considerar múltiplos de 4. La pregunta inversa es el corazón del problema:
Para todo entero positivo \(m\), existe una matriz de Hadamard de orden:
La afirmación es fácil de comprender, pero todavía no se conoce una demostración general.
Se han desarrollado numerosas construcciones que producen matrices para familias infinitas de órdenes. También se han resuelto muchos órdenes individuales mediante teoría, programación y búsquedas computacionales. Sin embargo, esos éxitos no constituyen todavía una demostración para todos los múltiplos de 4.
7. Una interpretación mediante distancias
Podemos convertir cada fila de signos en una palabra binaria mediante la correspondencia:
Dos filas diferentes de una matriz de Hadamard coinciden en \(n/2\) posiciones y difieren en las otras \(n/2\). Por tanto, las palabras binarias correspondientes están a distancia de Hamming:
Las \(n\) filas originales producen palabras binarias que están mutuamente a distancia \(n/2\). Si agregamos también sus complementos, la distancia mínima continúa siendo \(n/2\), pero una palabra y su propio complemento están a distancia \(n\).
Por esa razón, al incluir todos los complementos no debemos afirmar que absolutamente todas las parejas permanecen a la misma distancia.
8. El determinante máximo
La identidad fundamental también permite calcular el valor absoluto del determinante de una matriz de Hadamard.
Tomando determinantes en:
obtenemos:
Como \(\det(H^{\mathsf T})=\det(H)\), resulta:
Este es precisamente el máximo permitido por la desigualdad de Hadamard para una matriz de orden \(n\) cuyas entradas tienen valor absoluto menor o igual que 1.
9. Una primera comprobación por computadora
El siguiente programa en Python verifica que la matriz \(H_4\) tiene entradas válidas y que todos los productos escalares cumplen las condiciones necesarias.
H = [
[1, 1, 1, 1],
[1, -1, 1, -1],
[1, 1, -1, -1],
[1, -1, -1, 1],
]
n = len(H)
assert all(len(fila) == n for fila in H)
assert all(valor in (-1, 1) for fila in H for valor in fila)
for i in range(n):
for j in range(n):
producto = sum(H[i][k] * H[j][k] for k in range(n))
esperado = n if i == j else 0
assert producto == esperado
print("H es una matriz de Hadamard de orden", n)El resultado esperado es:
H es una matriz de Hadamard de orden 4Comprobar que una matriz conocida satisface \(HH^{\mathsf T}=nI_n\) es una tarea relativamente sencilla. Encontrar una matriz para un orden desconocido puede requerir explorar un espacio combinatorio inmenso.
Esta diferencia entre descubrimiento y verificación será uno de los temas centrales de las próximas lecciones.
10. Ejercicios para comprobar la comprensión
Compruebe manualmente los productos escalares de todos los pares de filas diferentes de \(H_4\).
Multiplique la tercera columna de \(H_4\) por \(-1\). Verifique que la matriz resultante continúa siendo una matriz de Hadamard.
Explique por qué el argumento de divisibilidad entre 4 necesita una tercera fila y, por tanto, no se aplica al caso especial \(n=2\).
La condición \(n\equiv0\pmod4\) es necesaria. Explique por qué la demostración presentada no permite concluir que sea suficiente.
11. Lo que debemos haber comprendido
- Una matriz de Hadamard tiene entradas exclusivamente iguales a \(+1\) o \(-1\).
- Sus filas y columnas son mutuamente ortogonales.
- Su identidad fundamental es \(HH^{\mathsf T}=nI_n\).
- Para \(n>2\), su orden debe ser múltiplo de 4.
- Esa condición necesaria no demuestra la conjetura de Hadamard.
- Una matriz propuesta puede verificarse con relativa facilidad, aunque descubrirla sea extraordinariamente difícil.
12. Preguntas para mis profesores
- ¿Consideran adecuada esta explicación de la condición \(n\equiv0\pmod4\) para un estudiante de álgebra lineal?
- ¿Qué concepto debería incorporarse antes de introducir secuencias de Turyn y construcciones Goethals–Seidel?
- ¿Qué distinción entre encontrar y verificar una matriz fue especialmente importante en los programas que ustedes utilizaron?
- ¿Qué ejemplo pequeño recomendarían como puente entre esta primera lección y las búsquedas computacionales?
13. Fuentes y alcance
- Jacques Hadamard, “Résolution d’une question relative aux déterminants”, Bulletin des Sciences Mathématiques, volumen 17, 1893, páginas 240–246.
- Raymond E. A. C. Paley, “On Orthogonal Matrices”, Journal of Mathematics and Physics, volumen 12, 1933, páginas 311–320.
- Eduardo Piza, “Búsqueda de matrices de Hadamard a través de secuencias de Turyn”, Revista de Matemática: Teoría y Aplicaciones, volumen 18, número 2, 2011, páginas 193–214.
Esta lección es una exposición pedagógica. No presenta resultados matemáticos originales. Su propósito es reconstruir progresivamente mi comprensión del problema y preparar el estudio posterior de las construcciones y búsquedas computacionales.
¿Qué hace el programa?
Aunque esta lógica podría escribirse igualmente en Fortran, Pascal, C, C++ o C#, utilizaremos Python por su sintaxis compacta. Antes de ejecutar el programa, conviene comprender qué hace cada una de sus partes.
Representación de la matriz
En Python, la matriz se representa mediante una lista de listas. Cada lista interior corresponde a una fila:
H = [
[1, 1, 1, 1],
[1, -1, 1, -1],
[1, 1, -1, -1],
[1, -1, -1, 1],
]
Como ocurre en C, C++ y C#, los índices comienzan en cero.
Por ejemplo, H[0] representa la primera fila,
mientras que H[1][3] representa el
elemento situado en la segunda fila y la cuarta columna.
Determinación del orden
n = len(H)
La función len devuelve la cantidad de elementos de
una lista. Como H contiene cuatro filas, la variable
n toma el valor 4.
Comprobación de los datos
assert all(len(fila) == n for fila in H) assert all(valor in (-1, 1) for fila in H for valor in fila)
En Python, una instrucción assert establece una condición
que necesariamente debe cumplirse. Si la condición es verdadera, el
programa continúa normalmente. Si es falsa, la ejecución se detiene
y Python produce un error llamado AssertionError.
La primera instrucción comprueba que todas las filas tengan exactamente
n elementos; es decir, que la matriz sea cuadrada.
La segunda recorre todas las entradas y comprueba que cada una sea
1 o −1.
La función all devuelve verdadero solamente cuando
todas las condiciones examinadas son verdaderas.
Por tanto:
all(len(fila) == n for fila in H)
puede leerse como: «para cada fila de H, compruebe
que su longitud sea igual a n».
Producto escalar entre las filas
for i in range(n):
for j in range(n):
La función range(n) genera los índices desde
0 hasta n - 1. El índice i
identifica una fila y el índice j identifica otra.
Para cada valor de i, el segundo ciclo hace que
j recorra nuevamente todas las filas. De esta manera,
el programa calcula el producto escalar correspondiente a cada pareja
de filas, incluyendo el producto de cada fila consigo misma.
En la siguiente instrucción, el índice k recorre las
columnas. En cada posición se multiplican los elementos correspondientes
de las filas i y j. Finalmente, la función
sum suma todos esos productos:
producto = sum(H[i][k] * H[j][k] for k in range(n))
Por ejemplo, cuando i = 0 y j = 1,
se calcula el producto escalar de la primera fila con la segunda:
Como el resultado es cero, esas dos filas son ortogonales.
En cambio, cuando i y j tienen el mismo
valor, se calcula el producto escalar de una fila consigo misma.
Por ejemplo, para la primera fila:
Por eso, el resultado esperado depende de si los índices
i y j son iguales o diferentes:
esperado = n if i == j else 0
Esta es la forma compacta de escribir una decisión en Python.
Si i == j, el valor esperado es n.
Si los índices son diferentes, el valor esperado es cero.
Verificación de la propiedad de Hadamard
assert producto == esperado
Esta última afirmación exige que cada producto escalar coincida con
el valor esperado. Si dos filas distintas no producen cero, o si una
fila consigo misma no produce n, Python detiene la ejecución.
Si todas las verificaciones se cumplen, el programa concluye que las filas son mutuamente ortogonales y muestra el mensaje:
H es una matriz de Hadamard de orden 4En otras palabras, el programa verifica computacionalmente reminders:
Ejecute usted mismo la comprobación
Pulse Ejecutar Python para comprobar que esta matriz satisface \(HH^{\mathsf T}=4I_4\). También puede cambiar algún signo y observar qué sucede.
Python está listo para ejecutarse.
Soluciones de los ejercicios
A continuación presentamos las soluciones de los ejercicios propuestos. Cada solución permanece oculta y puede consultarse haciendo clic sobre el título correspondiente. Esta disposición es intencional: queremos evitar revelar anticipadamente la respuesta y privar al lector del gusto de descubrirla por sí mismo.
Es algo parecido a tener a mano las soluciones de un crucigrama: resultan muy útiles para comprobar nuestro trabajo o recibir una pequeña ayuda cuando nos hemos detenido, pero consultarlas demasiado pronto puede arruinar buena parte de la diversión. Le recomendamos intentar primero cada ejercicio y abrir la solución solamente cuando desee verificar su razonamiento o necesite una orientación.
Ejercicio 1: productos escalares entre filas
Enunciado
Compruebe manualmente los productos escalares de todos los pares de filas diferentes de H4.
¿Qué significa este enunciado?
La matriz H4 tiene cuatro filas. El ejercicio pide tomar esas filas de dos en dos y calcular el producto escalar de cada pareja.
Denotaremos las cuatro filas como r1, r2, r3 y r4:
El producto escalar de dos filas se obtiene multiplicando los elementos que ocupan la misma posición y sumando los resultados. En general:
¿Cuántos productos debemos calcular?
Como el ejercicio se refiere a filas diferentes, no incluimos productos de una fila consigo misma, como r1 · r1.
Tampoco es necesario repetir las parejas en el orden inverso, porque el producto escalar es simétrico:
Por tanto, con cuatro filas existen seis parejas diferentes:
¿Qué debemos demostrar?
Para que las filas sean mutuamente ortogonales, el producto escalar de cada pareja de filas diferentes debe ser cero. Por tanto, debemos obtener cero en los seis cálculos.
Desarrollo de los cálculos
Conclusión
Los seis productos escalares son iguales a cero. Por consiguiente, cada fila de H4 es ortogonal a las otras tres. Esto confirma manualmente una de las propiedades esenciales que debe satisfacer una matriz de Hadamard.
Ejercicio 2: cambio de signo de una columna
Enunciado
Multiplique la tercera columna de H4 por −1. Verifique que la matriz resultante continúa siendo una matriz de Hadamard.
¿Qué significa este enunciado?
Multiplicar la tercera columna por −1 significa cambiar el signo de todos los elementos de esa columna. Cada 1 se convierte en −1 y cada −1 se convierte en 1.
No se multiplica toda la matriz por −1 y tampoco se modifica un único elemento. La operación afecta exclusivamente a los cuatro elementos que forman la tercera columna.
La tercera columna original es:
Después de multiplicarla por −1 obtenemos:
Construcción de la nueva matriz
Las demás columnas permanecen sin modificación. Denotaremos la matriz resultante por H′4:
¿Qué debemos verificar?
Para demostrar que H′4 continúa siendo una matriz de Hadamard, debemos comprobar dos propiedades:
- Todas sus entradas deben seguir siendo 1 o −1.
- El producto escalar de cada pareja de filas diferentes debe seguir siendo cero.
La primera propiedad se cumple inmediatamente: cambiar el signo de un 1 o de un −1 produce nuevamente un elemento perteneciente al conjunto formado por 1 y −1.
Verificación de la ortogonalidad
Denotemos las filas de la nueva matriz como r′1, r′2, r′3 y r′4. Calculamos los seis productos escalares:
¿Por qué se conserva la ortogonalidad?
Existe una explicación general que evita repetir todos los cálculos. En el producto escalar de dos filas, los elementos correspondientes de la tercera columna se multiplican entre sí. Después del cambio de signo, ambos factores quedan multiplicados por −1:
Los dos signos negativos se cancelan. Por tanto, la contribución de la tercera columna al producto escalar no cambia. Como las otras columnas tampoco fueron modificadas, todos los productos escalares conservan su valor original.
Conclusión
La matriz resultante contiene solamente entradas iguales a 1 o −1, y el producto escalar de cada pareja de filas diferentes es cero. Por consiguiente, H′4 continúa siendo una matriz de Hadamard.
Este ejercicio ilustra una propiedad general: multiplicar una fila o una columna completa de una matriz de Hadamard por −1 produce otra matriz de Hadamard.
Ejercicio 3: por qué se necesita una tercera fila
Enunciado
Explique por qué el argumento de divisibilidad entre 4 necesita una tercera fila y, por tanto, no se aplica al caso especial n = 2.
¿Qué significa este enunciado?
La demostración estudiada establece que, si existe una matriz de Hadamard de orden n mayor que 2, entonces n debe ser divisible entre 4.
El ejercicio pide identificar en qué momento de esa demostración se necesita una tercera fila y explicar por qué ese paso no puede realizarse en una matriz de orden 2.
La primera fila demuestra que el orden es par
Podemos normalizar una matriz de Hadamard multiplicando columnas por −1 cuando sea necesario, de manera que su primera fila quede formada únicamente por unos:
Para que la segunda fila sea ortogonal a la primera, su producto escalar con ella debe ser cero. Como la primera fila contiene solamente unos, esto exige que la segunda fila tenga la misma cantidad de unos y de menos unos.
Este primer razonamiento permite concluir que n es par, pero todavía no demuestra que sea divisible entre 4.
Organización de la segunda fila
Podemos permutar las columnas sin alterar la propiedad de Hadamard. Por tanto, podemos ordenar la segunda fila de manera que sus primeros n/2 elementos sean unos y sus restantes n/2 elementos sean menos unos:
La línea vertical separa dos bloques, cada uno con n/2 posiciones.
¿Dónde se necesita la tercera fila?
Para continuar la demostración necesitamos una tercera fila, que llamaremos r3. Esta fila debe ser ortogonal tanto a r1 como a r2.
Sea a la cantidad de unos de r3 situados en el primer bloque, y sea b la cantidad de unos situados en el segundo bloque.
Como r3 debe ser ortogonal a la primera fila, tiene que contener en total n/2 unos. Por tanto:
La ortogonalidad con la segunda fila obliga a que la distribución de unos en ambos bloques esté equilibrada. De esta segunda condición se obtiene:
Al combinar las dos igualdades tenemos:
y, por consiguiente:
Como a y b cuentan elementos de una fila, necesariamente son números enteros. Por ello, n/4 debe ser entero y n debe ser divisible entre 4.
¿Qué sucede cuando el orden es 2?
Una matriz de orden 2 tiene únicamente dos filas. Por tanto, después de utilizar la primera y la segunda fila para demostrar que el orden es par, no existe una tercera fila sobre la cual puedan imponerse simultáneamente las dos condiciones de ortogonalidad anteriores.
El paso que produce la cantidad n/4 no puede realizarse. Por eso el argumento de divisibilidad entre 4 no se aplica al caso n = 2.
De hecho, existe la siguiente matriz de Hadamard de orden 2:
Sus dos filas son ortogonales porque:
Conclusión
Las primeras dos filas permiten demostrar solamente que n es par. Para concluir que n es divisible entre 4 se necesita una tercera fila que sea ortogonal a las dos primeras.
Como una matriz de orden 2 no posee una tercera fila, ese paso no está disponible. Por eso los posibles órdenes de una matriz de Hadamard son 1, 2 o múltiplos de 4.
Ejercicio 4: condición necesaria y condición suficiente
Enunciado
La condición n ≡ 0 (mod 4) es necesaria. Explique por qué la demostración presentada no permite concluir que sea suficiente.
¿Qué significa este enunciado?
El ejercicio pide distinguir entre una condición necesaria y una condición suficiente.
Una condición necesaria es una propiedad que obligatoriamente debe cumplirse para que algo pueda existir. Sin embargo, cumplir esa propiedad no garantiza por sí solo que el objeto buscado efectivamente exista.
Una condición suficiente, en cambio, es una propiedad cuyo cumplimiento garantiza el resultado.
¿Qué demuestra el argumento?
La demostración presentada parte de la suposición de que existe una matriz de Hadamard de orden n, con n mayor que 2. A partir de la ortogonalidad de sus filas, concluye que n debe ser divisible entre 4.
En forma lógica, la demostración establece:
Podemos representarlo mediante esta implicación:
Esto permite descartar como posibles órdenes todos los números mayores que 2 que no sean divisibles entre 4.
¿Qué no demuestra el argumento?
La demostración no construye una matriz de Hadamard para cada múltiplo de 4. Tampoco proporciona un procedimiento que garantice que dicha matriz pueda construirse en todos esos órdenes.
Por tanto, no demuestra la implicación inversa:
En general, demostrar una implicación no permite invertir automáticamente su dirección. Por ejemplo:
Esta afirmación es verdadera. Sin embargo, no podemos invertirla y afirmar que todo rectángulo sea un cuadrado.
Del mismo modo, saber que todo orden admisible mayor que 2 debe ser múltiplo de 4 no permite concluir automáticamente que cada múltiplo de 4 sea el orden de alguna matriz de Hadamard.
Necesaria no significa suficiente
La divisibilidad entre 4 funciona como un primer filtro. Si n no es divisible entre 4 y es mayor que 2, sabemos que no puede existir una matriz de Hadamard de ese orden.
Pero si n sí es divisible entre 4, solamente podemos afirmar que el orden no ha sido descartado por esa condición. Todavía es necesario construir una matriz de ese orden o demostrar por algún otro método que existe.
Relación con la conjetura de Hadamard
La afirmación de que la condición también es suficiente es precisamente la conjetura de Hadamard:
Se conocen matrices de Hadamard para numerosos órdenes múltiplos de 4, pero una colección de construcciones particulares, por extensa que sea, no constituye una demostración válida para todos los enteros positivos.
Conclusión
La demostración presentada establece que ser múltiplo de 4 es una condición necesaria para todo orden mayor que 2. No demuestra que esa condición sea suficiente, porque no construye ni garantiza la existencia de una matriz de Hadamard para cada múltiplo de 4.
Probar esa suficiencia en completa generalidad equivaldría a demostrar la conjetura de Hadamard.