Determinante máximo de una matriz llena de $\pm 1$

Question

¿Existe un algoritmo para determinar cuál es el máximo determinante que se puede obtener simplemente poniendo $1$ o $-1$ en una matriz cuadrada?

Por ejemplo, en un $3\times3$ matriz:

$$ \begin{bmatrix}1 && -1 && 1\\ 1 && 1 && -1 \\ -1 && -1 && 1\end{bmatrix} $$

¿O hay que ir a forzar todas las posibilidades?

Answer 1

La desigualdad de Hadarmard $$ |\det(A)|^{2} \le \prod_{j=1}^{n}\sum_{k=1}^{n} |a_{jk}|^{2} $$ aplicado al caso $a_{jk} = \pm 1$ produce $|\det(A)| \le n^{n/2}$ . En el $3\times3$ caso, esto da $\sqrt{27} \approx 5.19$ . Si $$ A = \begin{pmatrix} 1 & -1 & -1 \\ 1 & 1 & 1 \\ -1 & -1 & 1 \end{pmatrix} $$ entonces $\det(A) = 4$ por lo que esta desigualdad no es una terrible sobreestimación. Sin embargo, no ayuda si necesitas el valor exacto.