Problema del determinante máximo de Hadamard

El problema del determinante máximo de Hadamard , llamado así por Jacques Hadamard , pregunta por el determinante más grande de una matriz con elementos iguales a 1 o −1. La pregunta análoga para matrices con elementos iguales a 0 o 1 es equivalente ya que, como se mostrará a continuación, el determinante máximo de una matriz {1,−1} de tamaño n es 2 ^{n −1} veces el determinante máximo de una matriz {0,1} de tamaño n −1. El problema fue planteado por Hadamard en el artículo de 1893 ^[1] en el que presentó su famoso límite determinante y permanece sin resolver para matrices de tamaño general. El límite de Hadamard implica que las matrices {1, −1} de tamaño n tienen determinante como máximo n ^{n /2} . Hadamard observó que una construcción de Sylvester ^[2] produce ejemplos de matrices que alcanzan el límite cuando n es una potencia de 2, y produjo ejemplos propios de tamaños 12 y 20. También demostró que el límite solo se puede alcanzar cuando n es igual a 1, 2 o un múltiplo de 4. Scarpis y Paley construyeron ejemplos adicionales más tarde y, posteriormente, muchos otros autores. Dichas matrices se conocen ahora como matrices de Hadamard y han sido objeto de un estudio intensivo.

Los tamaños de matriz n para los cuales n  ≡ 1, 2 o 3 (mod 4) han recibido menos atención. Los primeros resultados se deben a Barba, quien estrechó el límite de Hadamard para n impar, y a Williamson, quien encontró los determinantes más grandes para n = 3, 5, 6 y 7. Algunos resultados importantes incluyen

• límites más estrictos, debido a Barba, Ehlich y Wojtas, para n  ≡ 1, 2 o 3 (mod 4), que, sin embargo, se sabe que no siempre son alcanzables,
• unas cuantas secuencias infinitas de matrices que alcanzan los límites para n  ≡ 1 o 2 (mod 4),
• un número de matrices que alcanzan los límites para n específico  ≡ 1 o 2 (mod 4),
• un número de matrices que no alcanzan los límites para n  ≡ 1 o 3 específico (mod 4), pero que se ha demostrado mediante cálculo exhaustivo que tienen determinante máximo.

El diseño de experimentos en estadística hace uso de matrices {1, −1} X (no necesariamente cuadradas) para las cuales la matriz de información X ^T X tiene determinante máximo. (La notación X ^T denota la transpuesta de X .) Tales matrices se conocen como diseños D-óptimos . ^[3] Si X es una matriz cuadrada , se conoce como un diseño D-óptimo saturado .

Dos filas cualesquiera de una matriz de Hadamard n × n son ortogonales . Para una matriz {1, −1}, significa que dos filas cualesquiera difieren exactamente en la mitad de las entradas, lo que es imposible cuando n es un número impar . Cuando n  ≡ 2 (mod 4), dos filas que son ortogonales a una tercera fila no pueden ser ortogonales entre sí. En conjunto, estas afirmaciones implican que una matriz de Hadamard n × n solo puede existir si n  = 1, 2 o un múltiplo de 4. Las matrices de Hadamard han sido bien estudiadas, pero no se sabe si existe una matriz de Hadamard n × n para cada n que sea un múltiplo positivo de 4. El n más pequeño para el que no se sabe que exista una matriz de Hadamard n × n es 668.

Cualquiera de las siguientes operaciones, cuando se realiza en una matriz {1, −1} R , cambia el determinante de R solo por un signo menos:

• Negación de una fila.
• Negación de una columna.
• Intercambio de dos filas.
• Intercambio de dos columnas.

Dos matrices {1,−1}, R ₁ y R ₂ , se consideran equivalentes si R ₁ se puede convertir en R ₂ mediante alguna secuencia de las operaciones anteriores. Los determinantes de matrices equivalentes son iguales, excepto posiblemente por un cambio de signo, y a menudo es conveniente estandarizar R por medio de negaciones y permutaciones de filas y columnas. Una matriz {1, −1} está normalizada si todos los elementos en su primera fila y columna son iguales a 1. Cuando el tamaño de una matriz es impar, a veces es útil usar una normalización diferente en la que cada fila y columna contenga un número par de elementos 1 y un número impar de elementos −1. Cualquiera de estas normalizaciones se puede lograr utilizando las dos primeras operaciones.

Existe una función biunívoca del conjunto de matrices normalizadas n × n {1, −1} al conjunto de matrices ( n −1)×( n -1) {0, 1} en la que la magnitud del determinante se reduce en un factor de 2 ^{1− n} . Esta función consta de los siguientes pasos.

1. Resta la fila 1 de la matriz {1, −1} de las filas 2 a n . (Esto no cambia el determinante).
2. Extraiga la submatriz ( n −1)×( n −1) que consta de las filas 2 a n y las columnas 2 a n . Esta matriz tiene los elementos 0 y −2. (El determinante de esta submatriz es el mismo que el de la matriz original, como se puede ver al realizar una expansión de cofactores en la columna 1 de la matriz obtenida en el Paso 1).
3. Divida la submatriz por −2 para obtener una matriz {0, 1}. (Esto multiplica el determinante por (−2) ^{1− n} ).

Ejemplo:

${\displaystyle {\begin{bmatrix}1&1&1&1\\1&-1&-1&1\\1&1&-1&-1\\1&-1&1&-1\end{bmatrix}}\rightarrow \left[{\begin{array}{c|ccc}1&1&1&1\\\hline 0&-2&-2&0\\0&0&-2&-2\\0&-2&0&-2\end{array}}\right]\rightarrow {\begin{bmatrix}-2&-2&0\\0&-2&-2\\-2&0&-2\end{bmatrix}}\rightarrow {\begin{bmatrix}1&1&0\\0&1&1\\1&0&1\end{bmatrix}}}$

En este ejemplo, la matriz original tiene determinante −16 y su imagen tiene determinante 2 = −16·(−2) ⁻³ .

Dado que el determinante de una matriz {0, 1} es un número entero, el determinante de una matriz n × n {1, −1} es un múltiplo entero de 2 ^{n −1} .

Sea R una matriz n por n {1, −1}. La matriz de Gram de R se define como la matriz G  =  RR ^T . De esta definición se deduce que G

1. es una matriz entera,
2. es simétrico ,
3. es positivo-semidefinido ,
4. tiene diagonal constante cuyo valor es igual a n .

Negar filas de R o aplicarles una permutación da como resultado que se apliquen las mismas negaciones y permutaciones tanto a las filas como a las columnas correspondientes de G . También podemos definir la matriz G ′= R ^T R . La matriz G es la matriz de Gram habitual de un conjunto de vectores, derivada del conjunto de filas de R , mientras que G ′ es la matriz de Gram derivada del conjunto de columnas de R . Una matriz R para la que G  =  G ′ es una matriz normal . Toda matriz con determinante máximo conocida es equivalente a una matriz normal, pero no se sabe si este es siempre el caso.

El límite de Hadamard se puede derivar observando que |det  R | = (det  G ) ^1/2  ≤ (det  nI ) ^1/2  =  n ^{n /2} , lo cual es una consecuencia de la observación de que nI , donde I es la matriz identidad n por n , es la única matriz de determinante máximo entre las matrices que satisfacen las propiedades 1-4. El hecho de que det  R debe ser un múltiplo entero de 2 ^{n −1} se puede utilizar para proporcionar otra demostración de que el límite de Hadamard no siempre es alcanzable. Cuando n es impar, el límite n ^{n /2} no es entero o es impar y, por lo tanto, es inalcanzable excepto cuando n  = 1. Cuando n  = 2 k con k impar, la potencia más alta de 2 que divide el límite de Hadamard es 2 ^k, que es menor que 2 ^{n −1} a menos que n  = 2. Por lo tanto, el límite de Hadamard es inalcanzable a menos que n  = 1, 2 o un múltiplo de 4.

Cuando n es impar, la propiedad 1 para las matrices de Gram se puede fortalecer a

1. G es una matriz de números enteros impares.

Esto permite derivar  un límite superior más nítido ^{[4] : ​​|det} R | = (det  G ) ^1/2  ≤ (det ( n -1) I + J ) ^1/2  = (2 n −1) ^1/2 ( n −1) ^{( n −1)/2} , donde J es la matriz todo-uno. Aquí ( n -1) I + J es la matriz de determinante máximo que satisface la propiedad modificada 1 y las propiedades 2-4. Es única hasta la multiplicación de cualquier conjunto de filas y el conjunto correspondiente de columnas por −1. El límite no es alcanzable a menos que 2 n −1 sea un cuadrado perfecto y, por lo tanto, nunca es alcanzable cuando n  ≡ 3 (mod 4).

Cuando n es par, el conjunto de filas de R se puede dividir en dos subconjuntos.

• Las filas de tipo par contienen un número par de elementos 1 y un número par de elementos −1.
• Las filas de tipo impar contienen un número impar de elementos 1 y un número impar de elementos −1.

El producto escalar de dos filas del mismo tipo es congruente con n (mod 4); el producto escalar de dos filas de tipo opuesto es congruente con n +2 (mod 4). Cuando n  ≡ 2 (mod 4), esto implica que, al permutar filas de R , podemos asumir la forma estándar ,

${\displaystyle G={\begin{bmatrix}A&B\\B^{\mathrm {T}}&D\end{bmatrix}},}$

donde A y D son matrices enteras simétricas cuyos elementos son congruentes con 2 (mod 4) y B es una matriz cuyos elementos son congruentes con 0 (mod 4). En 1964, Ehlich ^[5] y Wojtas ^[6] demostraron independientemente que en la matriz de determinantes máximos de esta forma, A y D son ambos de tamaño n /2 e iguales a ( n −2) I +2 J mientras que B es la matriz cero. Esta forma óptima es única hasta la multiplicación de cualquier conjunto de filas y el conjunto correspondiente de columnas por −1 y hasta la aplicación simultánea de una permutación a filas y columnas. Esto implica la cota det  R  ≤ (2 n −2)( n −2) ^{( n −2)/2} . Ehlich demostró que si R alcanza el límite, y si las filas y columnas de R se permutan de modo que tanto G  =  RR ^T como G ′ =  R ^T R tengan la forma estándar y estén adecuadamente normalizadas, entonces podemos escribir

${\displaystyle R={\begin{bmatrix}W&X\\Y&Z\end{bmatrix}}}$

donde W , X , Y y Z son matrices ( n /2)×( n /2) con sumas constantes de filas y columnas w , x , y y z que satisfacen z  = − w , y  =  x y w ² + x ²  = 2 n −2. Por lo tanto, el límite de Ehlich-Wojtas no se puede alcanzar a menos que 2 n −2 sea expresable como la suma de dos cuadrados.

Cuando n es impar, entonces, utilizando la libertad de multiplicar filas por −1, se puede imponer la condición de que cada fila de R contenga un número par de elementos 1 y un número impar de elementos −1. Se puede demostrar que, si se supone esta normalización, entonces la propiedad 1 de G puede reforzarse a

1. G es una matriz con elementos enteros congruentes con n (mod 4).

Cuando n  ≡ 1 (mod 4), la forma óptima de Barba satisface esta propiedad más fuerte, pero cuando n  ≡ 3 (mod 4), no lo hace. Esto significa que la cota se puede agudizar en el último caso. Ehlich ^[7] demostró que cuando n  ≡ 3 (mod 4), la propiedad reforzada 1 implica que la forma de determinante máximo de G se puede escribir como B − J donde J es la matriz todo-uno y B es una matriz diagonal de bloques cuyos bloques diagonales son de la forma ( n -3) I +4 J . Además, demostró que en la forma óptima, el número de bloques, s , depende de n como se muestra en la tabla siguiente, y que cada bloque tiene un tamaño r o un tamaño r+1 donde${\displaystyle r=\lpiso n/s\rpiso .}$

Excepto para n = 11, donde hay dos posibilidades, la forma óptima es única hasta la multiplicación de cualquier conjunto de filas y el conjunto correspondiente de columnas por −1 y hasta la aplicación simultánea de una permutación a filas y columnas. Esta forma óptima conduce al límite

${\displaystyle \det R\leq (n-3)^{(ns)/2}(n-3+4r)^{u/2}(n+1+4r)^{v/2}\left[1-{\frac {ur}{n-3+4r}}-{\frac {v(r+1)}{n+1+4r}}\right]^{1/2},}$

donde v  =  n − rs es el número de bloques de tamaño r +1 y u  = s − v es el número de bloques de tamaño r . Cohn ^[8] analizó el límite y determinó que, aparte de n  = 3, es un entero solo para n  = 112 t ² ±28 t +7 para algún entero positivo t . Tamura ^[9] derivó restricciones adicionales sobre la alcanzabilidad del límite utilizando el teorema de Hasse-Minkowski sobre la equivalencia racional de formas cuadráticas, y mostró que el n > 3 más pequeño  para el cual el límite de Ehlich es concebiblemente alcanzable es 511.

Los determinantes máximos de matrices {1, −1} hasta un tamaño n  = 21 se dan en la siguiente tabla. ^[10] El tamaño 22 es el caso abierto más pequeño. En la tabla, D ( n ) representa el determinante máximo dividido por 2 ^{n −1} . Equivalentemente, D ( n ) representa el determinante máximo de una matriz {0, 1} de tamaño n −1.