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
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:
Dos matrices {1,−1}, R 1 y R 2 , se consideran equivalentes si R 1 se puede convertir en R 2 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.
Ejemplo:
En este ejemplo, la matriz original tiene determinante −16 y su imagen tiene determinante 2 = −16·(−2) −3 .
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
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
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.
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 ,
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
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 2 + x 2 = 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
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
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
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 2 ±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.
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1eade0d03bf672057eb930ffd1b2f9c24a5838c6)
![{\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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17277562156d707223b4307da7dd9f04c808a2fb)