Maximizar el valor de un determinante

Question

Dadas las entradas de una matriz, ¿cómo podemos optimizar su determinante?

Así, si las entradas de un $n\times n$ pertenecen al conjunto $\{a_1,a_2,\ldots ,a_p\}$ ¿Cómo se pueden organizar para maximizar o minimizar el determinante?

He visto un resultado relativo a $3 \times 3$ matrices, que dice que el determinante es máximo cuando todos los elementos diagonales son $\min\{a_i\}_{1\leq i\leq p}$ y todos los elementos no diagonales son $\max\{a_i\}_{1\leq i\leq p}$ . Y una vez que lo maximizamos, cambiando dos filas o dos columnas obtenemos el valor mínimo.

Además, no tengo ninguna pista para las matrices de orden superior. Cualquier ayuda será apreciada. Gracias de antemano.

Answer 1

Este problema contiene http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html que es difícil. Se trata de una interesante extensión de 1 parámetro (ver más abajo).

El número de matrices con entradas extraídas de $\{a_1, \ldots, a_p\}$ es finito, por lo que se alcanza el máximo. Supongamos que $A$ es una matriz que lo consigue. Afirmo que cada entrada en $A$ es $m=\min a_j$ o $M=\max a_j$ . De hecho, visto como una función de una sola entrada, el determinante es una función lineal afín, por lo que se maximiza haciendo que la entrada sea máxima (si la pendiente es positiva) o mínima (si la pendiente es negativa). (Otra forma de decir lo mismo es tomar una expansión de filas; esto muestra que la pendiente es (hasta el signo) el determinante menor complementario).

Ahora sólo pedimos el determinante máximo de una matriz con entradas $m, M$ .

El caso $m=M$ no es interesante, por lo que podemos suponer que una de ellas es distinta de cero y por reescalado reducir al caso de matrices con entradas $1, r$ . Si $r=0$ o $r=-1$ recuperamos los casos "clásicos".

Actualización: Yves Daoust tiene razón en que el determinante es divisible por $(x-1)^{(n-1)}$ . Lo demostramos de dos maneras:

1) Por el lema del determinante de la matriz,

$$\det\left(B + uv^T\right) = \det\left(B\right) + v^T\mathrm{adj}\left(B\right)u$$

aplicado a $u=v=[1, \ldots, 1]^T$ y $B=A-uv^T$ obtenemos

$$\det A= \det B+ (\text{sum of entries of }\mathrm{adj}\left(B\right) ).$$

Dado que todas las entradas de $B$ son $0$ o $x-1$ Así que $\det B$ es un múltiplo de $(x-1)^n$ y todas las entradas de $\mathrm{adj}\left(B\right) )$ son múltiplos de $(x-1)^{(n-1)}$ El resultado es el siguiente.

2) Como alternativa, argumentamos por inducción utilizando la fórmula de Jacobi:

$$\frac{d}{dx} \det A(x) = \operatorname{tr} \left (\operatorname{adj}(A(x)) \, \frac{dA(x)}{dx}\right ).$$

El caso base está vacío (o podemos tomar $n=2$ y comprobar). Ahora para el paso de inducción demostramos que $\frac{d}{dx} \det A(x)$ es divisible por $(x-1)^{(n-2)}$ y como $\det A(x)$ es divisible por $(x-1)$ debe ser divisible por $(x-1)^{(n-1)}$ . De hecho, $x=1$ es una raíz de $A(x)$ y su multiplicidad es una más que la multiplicidad de esta raíz para $\frac{d}{dx} \det A(x)$ .

Observe que $\operatorname{adj}(A(x))$ tiene entradas menores determinantes de $A(x)$ que son todas las matrices con entradas $1$ y $x$ de tamaño $n-1\times n-1$ por lo que por hipótesis de inducción son divisibles por $(x-1)^{(n-2)}$ La $\frac{dA(x)}{dx}$ es una matriz de 0s y 1s, por lo que tras la multiplicación obtenemos una matriz cuya entrada es divisible por $(x-1)^{(n-2)}$ por lo que también lo es su traza. Concluimos por la fórmula de Jacobi que la multiplicidad de $x=1$ como raíz de $\frac{d}{dx} \det A(x)$ es al menos $n-2$ por lo que su multiplicidad como raíz de $A(x)$ es al menos $n-1$ . QED.

De hecho, el cociente $\det A(x)/(x-1)^{(n-1)}$ es constante o lineal por razones de grado. Si supiéramos qué polinomio lineal puede ser, tendríamos una solución al problema de Hadamard. De hecho, en el problema de Hadamard para $\pm1$ matrices, podemos multiplicar algunas filas por -1 y hacer una columna de todos los 1s. Entonces (de nuevo por razones de grado) $\det A(x)/(x-1)^{(n-1)}$ es una constante. El problema de Hadamard para $\pm1$ equivale entonces a calcular esta constante; desgraciadamente eso mismo equivale a resolver el problema correspondiente para $0-1$ matrices, por lo que no parece que estemos haciendo ningún progreso real... Por ejemplo, haciendo todo esto para matrices Hadamard deberíamos obtener que la constante es $n^{n/2}/(-2)^{n-1}$ .

Answer 2

Conjeturas:

En $d$ espacio dimensional, los puntos con coordenadas tomadas del conjunto están contenidos en un hipercubo entre los límites $a_{\min}$ y $a_{\max}$ . El determinante es proporcional al volumen de la hiperpirámide formada por el origen y $d$ puntos de la red.

Si estoy en lo cierto (pero hay que confirmarlo), el mayor volumen se consigue eligiendo puntos de esquina. Sin pérdida de generalidad, podemos tomar los valores de $a_{\min},a_{\max}$ para ser $1,x$ (independientemente del orden).

En el caso 2D, los posibles determinantes son $x^2-1,x^2-x,x-1$ y $0$ (ignorando un signo global); tras la división por $x-1$ , estos son $x+1,x,1,0$ .

En el caso del 3D, las opciones son $x^3-3x+2,x^3-2x^2+x,x^3-x^2-x+1,\cdots$ . Después de la división por $(x-1)^2$ , estos son $x+2,x+1,x,\cdots$ .

Tras una rápida comprobación, parece que los valores en 4D son $x+3,x+2,x+1,x,\cdots$ veces $(x-1)^3$ que parece confirmar un patrón simple.

---

Actualización:

Después de ver esta información (problema del determinante máximo de Hadamard), parece que una solución general no tiene remedio:

http://www.indiana.edu/~maxdet/

Answer 3

También puedes intentar maximizar el determinante logarítmico, que es una función representable semidefinida (concretamente, representable mediante dos conos semidefinidos y un cono exponencial). Utilizando variables binarias para modelar la restricción de que cada entrada pertenece a un conjunto discreto se obtiene entonces un programa semidefinido mixto-integro, que puede resolverse con tamaños de problema mayores que los relacionados en las otras respuestas. Hay un solucionador de MISDP disponible aquí: http://www.opt.tu-darmstadt.de/scipsdp/ .

Más información: https://epubs.siam.org/doi/pdf/10.1137/S0895479896303430