El problema de determinantes máximos de Hadamard , llamado así por Jacques Hadamard , pide 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 un {0 , 1} matriz de tamaño n −1. El problema fue planteado por Hadamard en el artículo de 1893 [1] en el que presentó su famosa cota determinante y sigue sin resolverse para matrices de tamaño general. La cota de Hadamard implica que {1, −1} -matrices de tamaño ntienen 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 mostró que el límite solo es alcanzable cuando n es igual a 1, 2 o un múltiplo de 4. Más tarde, Scarpis y Paley y, posteriormente, muchos otros autores construyeron ejemplos adicionales. Estas matrices ahora se conocen como matrices de Hadamard . Han recibido un estudio intensivo.
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 ajustó el límite de Hadamard para n impar, y Williamson, quien encontró los mayores determinantes para n = 3, 5, 6 y 7. Algunos resultados importantes incluyen
- límites más estrechos, 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 pocas 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 or 1 o 2 específicos (mod 4),
- una serie de matrices que no alcanzan los límites para n ≡ 1 o 3 específicos (mod 4), pero que, mediante un cálculo exhaustivo, se ha demostrado que tienen un determinante máximo.
El diseño de experimentos en estadística hace uso de {1, −1} matrices X (no necesariamente cuadradas) para las cuales la matriz de información X T X tiene un determinante máximo. (La notación X T denota la transposición de X ). Estas matrices se conocen como diseños D-óptimos . [3] Si X es una matriz cuadrada , se conoce como un diseño D-óptimo saturado.
Matrices de Hadamard
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 cual 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í. Juntas, 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 se han estudiado bien, pero no se sabe si existe una matriz de Hadamard n × n para cada n que es un múltiplo positivo de 4. El n más pequeño para el que no se sabe que existe una matriz de Hadamard n × n es 668.
Equivalencia y normalización de matrices {1, −1}
Cualquiera de las siguientes operaciones, cuando se realiza en una matriz R {1, −1} , 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 1 y R 2 , se consideran equivalentes si R 1 puede convertirse en R 2 mediante alguna secuencia de las operaciones anteriores. Los determinantes de las matrices equivalentes son iguales, excepto posiblemente por un cambio de signo, y a menudo es conveniente estandarizar R mediante negaciones y permutaciones de filas y columnas. Una matriz {1, −1} se normaliza 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 contiene 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.
Conexión de los problemas de determinantes máximos para matrices {1, −1} y {0, 1}
Hay un mapa uno a uno del conjunto de matrices normalizadas n × n {1, −1} al conjunto de matrices ( n −1) × ( n -1) {0, 1} bajo las cuales la magnitud de el determinante se reduce por un factor de 2 1− n . Este mapa consta de los siguientes pasos.
- Reste la fila 1 de la matriz {1, −1} de las filas 2 a n . (Esto no cambia el determinante).
- 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 cofactor en la columna 1 de la matriz obtenida en el Paso 1.)
- Divida la submatriz por −2 para obtener una matriz {0, 1}. (Esto multiplica el determinante por (−2) 1− n .)
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 .
Límites superiores del determinante máximo
Matriz de Gram
Sea R una matriz de n por n {1, −1}. La matriz de Gram de R se define para ser la matriz G = RR T . De esta definición se sigue que G
- es una matriz entera,
- es simétrico ,
- es positivo-semidefinito ,
- tiene una diagonal constante cuyo valor es igual a n .
Negando filas de R o la aplicación de una permutación a ellos resulta en las mismas negaciones y ser permutación aplicada tanto a las filas y a las columnas correspondientes, de G . También podemos definir la matriz G '= R T R . La matriz G es la usual matriz de Gram de un conjunto de vectores, derivado del conjunto de filas de R , mientras que G 'es la matriz de Gram derivado del conjunto de columnas de R . Una matriz R para la cual G = G ′ es una matriz normal . Toda matriz de determinante máximo conocida es equivalente a una matriz normal, pero no se sabe si siempre es así.
Atado de Hadamard (para todos los n )
El límite de Hadamard se puede derivar observando que | det R | = (det G ) 1/2 ≤ (det nI ) 1/2 = n n / 2 , que es una consecuencia de la observación de que nI , donde I es la matriz identidad n por n , es la matriz única de determinante máximo entre matrices que satisfacen las propiedades 1–4. Que det R debe ser un múltiplo entero de 2 n −1 puede usarse 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 es no entero o 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 para dividir 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.
Barba está destinado a n impar
Cuando n es impar, la propiedad 1 de las matrices de Gram se puede fortalecer para
- G es una matriz de números enteros impares.
Esto permite derivar un límite superior [4] más agudo : | 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 el matriz todo-uno. Aquí ( n -1) I + J es la matriz de determinantes máximos que satisface la propiedad modificada 1 y las propiedades 2-4. Es único hasta la multiplicación de cualquier conjunto de filas y el correspondiente conjunto 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).
El Ehlich-Wojtas con destino a n ≡ 2 (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 an (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 el matriz cero. Esta forma óptima es única hasta la multiplicación de cualquier conjunto de filas y el correspondiente conjunto de columnas por -1 y la aplicación simultánea de una permutación a filas y columnas. Esto implica el 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 están permutadas de modo que tanto G = RR T como G ′ = R T R tienen la forma estándar y están adecuadamente normalizadas, entonces podemos escribir
donde W , X , Y y Z son ( n / 2) × ( n / 2) matrices con sumas constantes de filas y columnas w , x , y y z que satisfacen z = - w , y = x y w 2 + x 2 = 2 norte −2. Por lo tanto, el límite de Ehlich-Wojtas no es alcanzable a menos que 2 n -2 sea expresable como la suma de dos cuadrados.
Límite de Ehlich para n ≡ 3 (mod 4)
Cuando n es impar, al usar 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 asume esta normalización, entonces la propiedad 1 de G puede fortalecerse a
- G es una matriz con elementos enteros congruentes an (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 el límite puede afilarse en el último caso. Ehlich [7] mostró que cuando n ≡ 3 (mod 4), la propiedad reforzada 1 implica que la forma máxima-determinante de G se puede escribir como B - J donde J es la matriz todo-uno y B es una diagonal de bloque matriz cuyos bloques diagonal son de la forma ( n -3) I 4 J . Además, mostró que en la forma óptima, el número de bloques, s , depende de n como se muestra en la siguiente tabla, y que cada bloque tiene tamaño ro tamaño r + 1 donde
norte | s |
---|---|
3 | 3 |
7 | 5 |
11 | 5 o 6 |
15 - 59 | 6 |
≥ 63 | 7 |
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 de columnas correspondiente por -1 y 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 número entero solo para n = 112 t 2 ± 28 t +7 para algún número entero positivo t . Tamura [9] derivó restricciones adicionales sobre la alcanzabilidad de la cota usando 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 que la cota de Ehlich es concebible es 511.
Determinantes máximos hasta la talla 21
Los determinantes máximos de las matrices {1, −1} hasta el tamaño n = 21 se dan en la siguiente tabla. [10] El tamaño 22 es el estuche abierto más pequeño. En la tabla, D ( n ) representa el determinante máximo dividido por 2 n −1 . De manera equivalente, D ( n ) representa el determinante máximo de una matriz {0, 1} de tamaño n −1.
norte | D ( n ) | Notas |
---|---|---|
1 | 1 | Matriz de Hadamard |
2 | 1 | Matriz de Hadamard |
3 | 1 | Alcanza el límite de Ehlich |
4 | 2 | Matriz de Hadamard |
5 | 3 | Alcanza la unión de Barba; matriz circulante |
6 | 5 | Alcanza el límite de Ehlich-Wojtas |
7 | 9 | 98,20% de Ehlich encuadernado |
8 | 32 | Matriz de Hadamard |
9 | 56 | 84,89% de Barba encuadernado |
10 | 144 | Alcanza el límite de Ehlich-Wojtas |
11 | 320 | 94,49% de Ehlich unido; tres matrices no equivalentes |
12 | 1458 | Matriz de Hadamard |
13 | 3645 | Alcanza la unión de Barba; La matriz de determinantes máximos es {1, −1} matriz de incidencia del plano proyectivo de orden 3 |
14 | 9477 | Alcanza el límite de Ehlich-Wojtas |
15 | 25515 | 97,07% de Ehlich unido |
dieciséis | 131072 | Matriz de Hadamard; cinco matrices no equivalentes |
17 | 327680 | 87,04% de Barba encuadernado; tres matrices no equivalentes |
18 | 1114112 | Alcanza la unión de Ehlich-Wojtas; tres matrices no equivalentes |
19 | 3411968 | Alcanza el 97,50% de la unión de Ehlich; tres matrices no equivalentes |
20 | 19531250 | Matriz de Hadamard; tres matrices no equivalentes |
21 | 56640625 | 90,58% de Barba encuadernado; siete matrices no equivalentes |
Referencias
- ^ Hadamard, J. (1893), "Résolution d'une question relativas aux determinants", Bulletin des Sciences Mathématiques , 17 : 240–246
- ^ Sylvester, JJ (1867), "Reflexiones sobre matrices ortogonales inversas, sucesiones de signos simultáneos y pavimentos teselados en dos o más colores, con aplicaciones a la regla de Newton, el trabajo de baldosas ornamentales y la teoría de los números", Londres Edimburgo Dublín Phil. revista J. Sci. , 34 : 461–475
- ^ Galil, Z .; Kiefer, J. (1980), " D -diseños de pesaje óptimos", Ann. Stat. , 8 : 1293–1306, doi : 10.1214 / aos / 1176345202
- ^ Barba, Guido (1933), "Intorno al teorema di Hadamard sui determinanti a valore massimo", Giorn. Estera. Battaglini , 71 : 70–86.
- ^ Ehlich, Hartmut (1964), "Determinantenabschätzungen für binäre Matrizen", Matemáticas. Z. , 83 : 123–132, doi : 10.1007 / BF01111249.
- ^ Wojtas, M. (1964), "Sobre la desigualdad de Hadamard para los determinantes del orden no divisible por 4", Colloq. Matemáticas. , 12 : 73–83.
- ^ Ehlich, Hartmut (1964), "Determinantenabschätzungen für binäre Matrizen mit n ≡ 3 mod 4", Matemáticas. Z. , 84 : 438–447, doi : 10.1007 / BF01109911.
- ^ Cohn, JHE (2000), "Diseños casi óptimos D", Utilitas Math. , 57 : 121–128.
- ^ Tamura, Hiroki (2006), "Diseños óptimos D y diseños divisibles en grupo", Journal of Combinatorial Designs , 14 : 451–462, doi : 10.1002 / jcd.20103.
- ^ Sloane, N. J. A. (ed.). "Secuencia A003432 (problema de determinante máximo de Hadamard: determinante más grande de una (real) {0,1} -matriz de orden n.)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.