Jacques HadamardUn teorema fundamental del álgebra lineal afirma que toda matriz simétrica real \( A \) puede ser diagonalizada. Es decir, para toda matriz de este tipo existe una matriz real no singular \( Q \) tal que
\[ Q^{-1} A Q = \begin{pmatrix} \lambda_1 & & 0 \\ & \ddots & \\ 0 & & \lambda_n \end{pmatrix} \]
está en forma diagonal. Los \( \lambda_i \) (reales) son los valores propios de \( A \), y las columnas de \( Q \) forman una base de vectores propios. Usaremos este resultado en varios capítulos más adelante.
Además, se puede elegir la matriz \( Q \) como una matriz ortogonal, lo cual significa que \( Q^T = Q^{-1} \), o equivalentemente, que las columnas de \( Q \) forman una base ortonormal con respecto al producto interno usual.
Moviendo \( Q \) y \( Q^T \) al otro lado, también se puede expresar el teorema como una representación de \( A \) como una combinación lineal de matrices \( P_i \) que corresponden a proyecciones sobre los espacios propios \( C_{\lambda_i} \):
\[ A = \lambda_1 P_1 + \cdots + \lambda_t P_t, \quad I_n = P_1 + \cdots + P_t, \]
con \( P_i P_j = \delta_{ij} P_i \) para todo \( i \) y \( j \). En esta forma, el teorema se conoce habitualmente como el teorema espectral.
Las demostraciones estándar del teorema se hacen por inducción sobre el orden de \( A \) (con algunos cuidados en presencia de valores propios múltiples), construyen la base de vectores propios paso a paso, y utilizan el hecho de que el polinomio característico se factoriza linealmente sobre el cuerpo \( \mathbb{C} \) de los números complejos.
© Springer-Verlag GmbH Germany, parte de Springer Nature 2018
M. Aigner, G. M. Ziegler, Proofs from THE BOOK,
https://doi.org/10.1007/978-3-662-57265-8_7
La siguiente demostración, debida a Herb Wilf, lo hace de un solo golpe y es verdaderamente inspiradora. Es muy diferente a las pruebas usuales: no recurre directamente a los valores propios, sino que emplea argumentos elegantes de compacidad de una forma sorprendente.
Comenzamos con algunos hechos preliminares. Sea \( O(n) \subseteq \mathbb{R}^{n \times n} \) el conjunto de matrices ortogonales reales de orden \( n \). Dado que
\[ (PQ)^{-1} = Q^{-1}P^{-1} = Q^T P^T = (PQ)^T \]
para \( P, Q \in O(n) \), vemos que el conjunto \( O(n) \) es un grupo. Si consideramos cualquier matriz en \( \mathbb{R}^{n \times n} \) como un vector en \( \mathbb{R}^{n^2} \), encontramos que \( O(n) \) es un conjunto compacto. De hecho, las columnas de una matriz ortogonal \( Q = (q_{ij}) \) son vectores unitarios, por lo que \( |q_{ij}| \leq 1 \) para todo \( i \) y \( j \), así que \( O(n) \) está acotado. Además, el conjunto \( O(n) \) se define como subconjunto de \( \mathbb{R}^{n^2} \) por las ecuaciones:
\[ x_{i1}x_{j1} + x_{i2}x_{j2} + \cdots + x_{in}x_{jn} = \delta_{ij} \quad \text{para } 1 \leq i,j \leq n, \]
por lo tanto, es cerrado, y así compacto.
Teorema de Heine-Borel:
Todo subconjunto cerrado y acotado de un espacio vectorial \( \mathbb{R}^k \) es compacto.
Para cualquier matriz cuadrada real \( A \), sea \[ \text{Od}(A) = \sum_{i \ne j} a_{ij}^2 \] la suma de los cuadrados de las entradas fuera de la diagonal. Supongamos que podemos probar el siguiente lema:
Lema. Si \( A \) es una matriz simétrica real que no es diagonal, es decir, \( \text{Od}(A) > 0 \), entonces existe \( U \in O(n) \) tal que \( \text{Od}(U^T A U) < \text{Od}(A) \).
Dado el lema, el teorema se deduce en tres pasos simples. Sea \( A \) una matriz simétrica real \( n \times n \).
En efecto, si \( \text{Od}(D) > 0 \), entonces aplicando el lema encontramos \( U \in O(n) \) con \( \text{Od}(U^T D U) < \text{Od}(D) \). Pero
\[ U^T D U = U^T Q^T A Q U = (QU)^T A (QU) \]
pertenece a \( f_A(O(n)) \) (recordemos que \( O(n) \) es un grupo), con un valor de \( \text{Od} \) menor que el de \( D \): contradicción, y por ende \( D \) es diagonal.
Solo queda probar el lema, y para ello se utiliza un argumento muy ingenioso atribuido a Carl Gustav Jacob Jacobi. Supongamos que \( a_{rs} \ne 0 \) para algún \( r \ne s \). Entonces afirmamos que existe una matriz \( U \) que coincide con la identidad excepto en la submatriz \( 2 \times 2 \) correspondiente a \( r, s \), donde:
\[ u_{rr} = \cos \theta, \quad u_{rs} = \sin \theta, \quad u_{sr} = -\sin \theta, \quad u_{ss} = \cos \theta, \]
para algún valor (real) de \( \theta \).
Claramente, \( U \) es ortogonal para cualquier valor de \( \vartheta \). Ahora calculemos la entrada \( (k, \ell) \) de \( U^T A U \). Tenemos:
\[ b_{k\ell} = \sum_{i,j} u_{ik} a_{ij} u_{j\ell} \]
Para \( k, \ell \notin \{r, s\} \), obtenemos que \( b_{k\ell} = a_{k\ell} \). Además, tenemos:
\[ \begin{aligned} b_{kr} &= \sum_{i=1}^n u_{ik} \sum_{j=1}^n a_{ij} u_{jr} \\ &= \sum_{\ell=1}^n u_{k\ell} (a_{\ell r} \cos \vartheta - a_{\ell s} \sin \vartheta) \\ &= a_{kr} \cos \vartheta - a_{ks} \sin \vartheta \quad \text{(para \( k \ne r, s \))}. \end{aligned} \]
De manera similar, se obtiene:
\[ b_{ks} = a_{kr} \sin \vartheta + a_{ks} \cos \vartheta \quad \text{(para \( k \ne r, s \))}. \]
De ello se deduce que:
\[ \begin{aligned} b_{kr}^2 + b_{ks}^2 &= a_{kr}^2 \cos^2 \vartheta - 2a_{kr}a_{ks} \cos \vartheta \sin \vartheta + a_{ks}^2 \sin^2 \vartheta \\ &\quad + a_{kr}^2 \sin^2 \vartheta + 2a_{kr}a_{ks} \sin \vartheta \cos \vartheta + a_{ks}^2 \cos^2 \vartheta \\ &= a_{kr}^2 + a_{ks}^2. \end{aligned} \]
Y por simetría:
\[ b_{rk}^2 + b_{sk}^2 = a_{rk}^2 + a_{sk}^2 \quad \text{(para \( k \ne r, s \))}. \]
Concluimos que la función \( \text{Od} \), que suma los cuadrados de los valores fuera de la diagonal, coincide para \( A \) y \( U^T A U \) excepto en las entradas \( (r, s) \) y \( (s, r) \), para cualquier \( \vartheta \). Para concluir la prueba, ahora mostramos que se puede elegir \( \vartheta_0 \) de manera que \( b_{rs} = 0 \), lo que dará como resultado:
\[ \text{Od}(U^T A U) = \text{Od}(A) - 2 a_{rs}^2 < \text{Od}(A), \]
como se requería.
"Diagonalizando mediante una rotación y eliminando elementos fuera de la diagonal"
Usando (1) obtenemos:
\[ b_{rs} = (a_{rr} - a_{ss}) \sin \vartheta \cos \vartheta + a_{rs} (\cos^2 \vartheta - \sin^2 \vartheta). \]
Para \( \vartheta = 0 \), esto se vuelve \( a_{rs} \), mientras que para \( \vartheta = \frac{\pi}{2} \) se convierte en \( -a_{rs} \). Por el teorema del valor intermedio, existe algún \( \vartheta_0 \) entre 0 y \( \frac{\pi}{2} \) tal que \( b_{rs} = 0 \), y con eso terminamos.
Esto fue muy elegante, y queremos aplicar de inmediato el teorema a un problema famoso (y no resuelto).
Problema del determinante de Hadamard
¿Qué tan grande puede ser \( \det A \) sobre el conjunto de todas las matrices reales \( n \times n \)
\( A = (a_{ij}) \) con \( |a_{ij}| \leq 1 \) para todo \( i \) y \( j \)?
Como el determinante es una función continua en las \( a_{ij} \) (consideradas como variables), y las matrices forman un conjunto compacto en \( \mathbb{R}^{n^2} \), este máximo debe existir. Además, el máximo se alcanza para alguna matriz cuyos elementos sean todos \( +1 \) o \( -1 \), porque \( \det A \) es lineal en cada entrada \( a_{ij} \) (si mantenemos fijos los demás). Así que podemos comenzar con cualquier matriz \( A \) y cambiar una entrada cada vez a \( \pm 1 \), en cada paso sin disminuir el determinante, hasta llegar a una matriz de solo \( \pm 1 \).
Aquí está el truco: en lugar de \( A \), consideramos la matriz \( B = A^T A = (b_{ij}) \). Es decir, si \( c_j = (a_{1j}, a_{2j}, \ldots, a_{nj})^T \) denota la columna \( j \)-ésima de \( A \), entonces \( b_{ij} = \langle c_i, c_j \rangle \), el producto interno de \( c_i \) y \( c_j \). En particular:
\[ b_{ii} = \langle c_i, c_i \rangle = n \quad \text{para todo } i, \]
y
\[ \text{traza } B = \sum_{i=1}^n b_{ii} = n^2. \tag{2} \]
Lo cual será útil en un momento.
Ahora podemos comenzar a trabajar. Primero, de \( B = A^T A \) obtenemos que \( |\det A| = \sqrt{\det B} \). Como multiplicar una columna de \( A \) por \( -1 \) convierte \( \det A \) en \( -\det A \), vemos que el problema de maximizar \( \det A \) es el mismo que maximizar \( \det B \). Además, podemos asumir que \( A \) es no singular, y por lo tanto \( B \) también lo es.
Dado que \( B = A^T A \) es simétrica, el teorema espectral nos dice que existe alguna matriz \( Q \in O(n) \) tal que:
\[ Q^T B Q = Q^T A^T A Q = (A Q)^T (A Q) = \begin{pmatrix} \lambda_1 & & 0 \\ & \ddots & \\ 0 & & \lambda_n \end{pmatrix}. \tag{3} \]
Jacques Hadamard
donde los \( \lambda_i \) son los valores propios de \( B \). Ahora, si \( d_j \) denota el vector columna \( j \)-ésimo de \( AQ \) (que es no nulo, ya que \( A \) es no singular), entonces
\[ \lambda_j = \langle d_j, d_j \rangle = \sum_{i=1}^n d_{ij}^2 > 0. \]
Así que \( \lambda_1, \ldots, \lambda_n \) son números reales positivos, y
\[ \det B = \lambda_1 \cdots \lambda_n, \quad \text{traza } B = \sum_{i=1}^n \lambda_i. \]
Cuando aparece un producto y una suma de números reales positivos, siempre es buena idea usar la desigualdad aritmético-geométrica (véase el Capítulo 20). En este caso, usando (2), obtenemos:
\[ \det B = \lambda_1 \cdots \lambda_n \leq \left( \frac{\sum_{i=1}^n \lambda_i}{n} \right)^n = \left( \frac{\text{traza } B}{n} \right)^n = n^n. \tag{4} \]
y así se obtiene la cota superior de Hadamard:
\[ |\det A| \leq n^{n/2}. \tag{5} \]
¿Cuándo se alcanza la igualdad en (5), o lo que es igual, en (4)? Fácil: si y solo si la media geométrica de los \( \lambda_i \) es igual a la media aritmética, o sea, si y solo si \( \lambda_1 = \cdots = \lambda_n = \lambda \). Entonces la traza \( B = n \lambda = n^2 \), y por tanto \( \lambda = n \), así que todos los \( \lambda_i = n \). Al mirar (3), esto significa que \( Q^T B Q = n I_n \), donde \( I_n \) es la matriz identidad \( n \times n \). Ahora recordemos que \( Q^T = Q^{-1} \), y multiplicando a izquierda y derecha por \( Q \) y \( Q^{-1} \), obtenemos:
\[ B = n I_n. \]
Volviendo a la matriz \( A \), esto significa que:
\[ |\det A| = n^{n/2} \iff \langle c_i, c_j \rangle = 0 \quad \text{para } i \ne j. \tag{6} \]
Las matrices con entradas \( \pm 1 \) que alcanzan la igualdad en (5) se llaman matrices de Hadamard. Así que una matriz \( n \times n \) con entradas \( \pm 1 \) es una matriz de Hadamard si y solo si:
\[ A^T A = A A^T = n I_n. \]
Esto conduce a otro problema difícil aún no resuelto:
¿Para qué valores de \( n \) existe una matriz de Hadamard de tamaño \( n \times n \)?
Un argumento breve muestra que si \( n > 2 \), entonces debe ser múltiplo de 4. De hecho, supongamos que \( A \) es una matriz de Hadamard \( n \times n \), \( n \geq 2 \), cuyas filas son los vectores \( r_1, \ldots, r_n \). Claramente, multiplicar cualquier fila o columna por \( -1 \) produce otra matriz de Hadamard. Por tanto, podemos suponer que la primera fila consiste solo en 1's. Dado que \( \langle r_1, r_i \rangle = 0 \) para \( i \ne 1 \), todas las demás filas deben contener igual número de 1's y −1's.
Cada fila debe contener \( \frac{n}{2} \) unos y \( \frac{n}{2} \) menos unos; en particular, \( n \) debe ser par. Supongamos ahora que \( n > 2 \) y consideremos las filas \( r_2 \) y \( r_3 \), y denotemos por \( a, b, c, d \) los números de columnas que tienen:
Entonces de \( \langle r_2, r_3 \rangle = 0 \), obtenemos que:
\[ a + b = c + d, \quad a + c = b + d = \frac{n}{2}, \]
lo cual implica que \( b = c, a = d \). Pero de \( \langle r_2, r_3 \rangle = 0 \), también tenemos \( a + d = b + c \), lo que da \( 2a = 2b \), por lo tanto \( a = b = c = d = \frac{n}{4} \). Así, el número de columnas con cada una de las combinaciones es \( \frac{n}{4} \), y por tanto \( n \) es múltiplo de 4.
¿Existe una matriz de Hadamard para todo \( n = 4a \)? Nadie lo sabe. Se conoce la existencia hasta el récord actual de \( n = 664 \), y para ciertas series infinitas como las potencias de 2 (ver el recuadro). Pero la respuesta general aún parece fuera de alcance.
Las matrices de Hadamard existen para todo \( n = 2^m \)
Consideremos un conjunto \( X \) con \( m \) elementos y enumeremos sus \( 2^m \) subconjuntos como \( C_1, \ldots, C_{2^m} \). La matriz \( A = (a_{ij}) \) se define por:\[ a_{ij} = (-1)^{|C_i \cap C_j|} \]
Queremos verificar que \( \langle r_i, r_j \rangle = 0 \) para \( i \ne j \). Desde la definición:\[ \langle r_i, r_j \rangle = \sum (-1)^{|C_i \cap C_k| + |C_j \cap C_k|}. \]
Ahora, como \( C_i \ne C_j \), existe un elemento \( a \in X \) tal que \( a \in C_i \setminus C_j \) o viceversa. Supongamos \( a \in C_i \setminus C_j \). La mitad de los subconjuntos contienen a \( a \), y la otra mitad no. Al agrupar por si \( C_k \) contiene o no a \( a \), los términos correspondientes tienen paridad distinta, y se cancelan. Así que la suma total es 0.
Para \( n = 4a \), ahora hemos reducido el problema original a la existencia de matrices de Hadamard. ¿Qué tan grande puede ser \( \det A \) cuando \( n \) no es múltiplo de 4? Este también es un problema difícil, pero quizás podamos encontrar una buena cota inferior para el máximo. Aquí hay un método que con frecuencia resulta exitoso, y que también funciona en este caso.
Veamos todas las \( 2^{n^2} \) matrices \( n \times n \) con entradas \( \pm 1 \), y consideremos algunos promedios del determinante. El promedio aritmético
\[ \frac{1}{2^{n^2}} \sum \det A \]
es 0 (claro), por lo que no sirve. Pero si consideramos el promedio cuadrático, obtenemos:
\[ D_n := \sqrt{ \frac{1}{2^{n^2}} \sum (\det A)^2 }. \]
Entonces todo mejora un poco. Claramente:
\[ \max_A \det A \geq D_n, \]
lo cual nos da una cota inferior para el máximo.
Este impresionante cálculo de \( D_n^2 \) probablemente apareció por primera vez en un artículo de George Szekeres y Paul Turán. Lo aprendimos primero de una hermosa demostración de Herb Wilf, quien lo oyó de Mark Kac. En palabras de Kac: "Escribe \((\det A)^2\) de forma adecuada, intercambia las sumas, y todo se simplifica." Así que eso es lo que vamos a hacer.
A partir de la definición del determinante obtenemos:
\[ D_n^2 = \frac{1}{2^{n^2}} \sum_A \left( \sum_\pi \text{sign}(\pi) \, a_{1\pi(1)} a_{2\pi(2)} \cdots a_{n\pi(n)} \right)^2 \]
\[ = \frac{1}{2^{n^2}} \sum_A \sum_\sigma \sum_\tau (\text{sign} \, \sigma)(\text{sign} \, \tau) \, a_{1\sigma(1)} a_{1\tau(1)} \cdots a_{n\sigma(n)} a_{n\tau(n)}, \]
donde \( \sigma \) y \( \tau \) recorren todas las permutaciones de \( \{1, \ldots, n\} \).
Intercambiando las sumas obtenemos:
\[ D_n^2 = \frac{1}{2^{n^2}} \sum_{\sigma, \tau} (\text{sign} \, \sigma)(\text{sign} \, \tau) \left( \sum_A a_{1\sigma(1)} a_{1\tau(1)} \cdots a_{n\sigma(n)} a_{n\tau(n)} \right). \]
Esto no parece muy prometedor, pero veamos un par fijo \( (\sigma, \tau) \). La suma interior es en realidad una suma sobre \( n^2 \) variables, una por cada \( a_{ij} \):
\[ \sum_{a_{11} = \pm 1} \cdots \sum_{a_{nn} = \pm 1} a_{1\sigma(1)} a_{1\tau(1)} \cdots a_{n\sigma(n)} a_{n\tau(n)}. \tag{7} \]
Supongamos que existe algún \( i \) tal que \( \sigma(i) \ne \tau(i) \). Entonces cada sumando contiene \( a_{ik} \), y por tanto el producto incluye un factor con suma nula (por simetría entre \( +1 \) y \( -1 \)). Así que toda la suma es 0, salvo cuando \( \sigma = \tau \).
Cuando \( \sigma = \tau \), el producto interno es 1 y el término es \( (\text{sign} \, \sigma)^2 = 1 \). Por tanto, la suma en (7) es:
\[ \sum_{a_{11} = \pm 1} \cdots \sum_{a_{nn} = \pm 1} 1 = 2^{n^2}. \]
Y concluyendo, obtenemos:
\[ D_n^2 = \frac{1}{2^{n^2}} \sum_\sigma 2^{n^2} = n!, \]
y con ello el siguiente resultado:
Es una característica típica del uso de promedios que, aunque aprendemos que existe tal matriz, no tengamos ninguna idea de cómo construirla de forma eficiente. Pero sorprendentemente, la cota es bastante buena. Invocando la fórmula de Stirling (vista en la página 13), tenemos:
\[ \sqrt{n!} \sim (2\pi n)^{1/4} \left( \frac{n}{e} \right)^{n/2}, \]
y esto no está nada mal en comparación con la cota superior \( n^{n/2} \).
Usando el promedio bicuadrático, Szekeres y Turán obtuvieron incluso una mejor cota inferior:
\[ \frac{1}{4} \sqrt{\frac{n!}{n}}, \]
pero el crecimiento exacto del máximo a medida que \( n \to \infty \) sigue sin conocerse.