Problema del determinante maximizador

Question

El problema es maximizar el determinante de un $3 \times 3$ con elementos de $1$ a $9$ .
¿Hay algún método para hacerlo sin recurrir a la fuerza bruta?

Answer 1

SUGERENCIA:

El producto de los valores propios es el determinante. La traza es la suma de los valores propios. Puede ser razonable creer que una gran suma de valores propios aumenta la posibilidad de un gran producto de valores propios. Si ese es el caso, entonces 9,8,7 serían buenos candidatos para los elementos diagonales. Entonces algún argumento de simetría podría utilizarse para las 6 posiciones restantes.

Esto reduciría de tener que intentar $9! = 362880$ a $6! = 720$ matrices.

ADVERTENCIA DE SPOILER:

Usando Matlab u Octave, podemos con un corto pero oscuro script de fuerza bruta (no se preocupen que tomó tal vez 5-10 segundos en mi máquina ) :

b = reshape(permute(perms(1:9),[3,2,1]),[3,3,362880]);

s=-1; for o_=1:size(b,3); if det(b(:,:,o_))>s; i_=o_; end; s = max(s,det(b(:,:,o_)); end;

b(:,:,i_)

Encuentra que la matriz

$$\left[\begin{array}{rrr}7&1&5\\6&8&3\\2&4&9\end{array}\right]$$

Tiene un determinante $412$ que supuestamente es el más grande del grupo. Por supuesto, como alguien mencionó en los comentarios, cualquier combinación de permutaciones de filas o columnas daría el mismo valor, así que lo importante es que 7,8,9 no compartan ninguna fila o columna, ya que entonces podríamos permutarlas en la diagonal.

Answer 2

El intercambio de filas y columnas deja el valor absoluto del determinante sin cambios, por lo que podemos asumir que la celda del medio contiene 1. Entonces, ya que el valor absoluto del determinante no se ve afectado por la toma de transposiciones (y el intercambio de las filas superior e inferior o las columnas izquierda y derecha), podemos suponer que el 2 se encuentra en una esquina de la mitad de la fila superior.

Esto deja $2 \cdot 7! = 10,080$ posibilidades de comprobar, que es un mejora respecto a $9!=362,880$ .

Después de arreglar el 1,2, uno podría notar que sólo hay 4 esencialmente lugares diferentes para poner el 3, por lo que sólo tenemos que comprobar $2 \cdot 4 \cdot 6! = 5,760$ posibilidades.

La fuerza bruta (calculando las 9 posibilidades), siempre una de mis favoritas, también funciona:

# python 2.7.6
import numpy
import itertools

sup = 0
for p in itertools.permutations(range(1,10)):
    m = [ p[0:3], p[3:6], p[6:10] ]
    d = abs(numpy.linalg.det(m))
    if d > sup:
        sup = d

print sup

Esto imprime 412.0 después de 8 segundos en mi vieja tableta X201.

Answer 3

La pregunta pide alternativas a la fuerza bruta, pero sólo para ilustrar las dificultades de usar la fuerza bruta, aquí está el código python para forzarla:

import numpy as np
import itertools
import time

MATRIX_SIZE = 3            #3 for a 3x3 matrix, etc

best_matrices = []
highest_det = 0

start_time = time.process_time()

def report():
    print(round(time.process_time() - start_time,4) ,"\t", 
        iteration, "/", num_permutations, round(100*iteration/ num_permutations,2), "%   \t", 
        permutation, "\tdet=",det,"(prev best det",highest_det,")")

num_permutations = np.math.factorial(MATRIX_SIZE**2)
iteration = 0
for permutation in itertools.permutations(range(1, MATRIX_SIZE*MATRIX_SIZE+1)):
    iteration += 1
    matrix = np.array(permutation).reshape((MATRIX_SIZE, MATRIX_SIZE))
    det = round((np.linalg.det(matrix)) )
    if det > highest_det:
        report()
        highest_det = det
        best_matrices = [permutation]
    elif det==highest_det:
        report()
        best_matrices.append(permutation)

total_time = time.process_time() - start_time 

#print("List of the matrices with the highest determinant:\n", *best_matrices, sep='\n')
print(len(best_matrices), "matrices found")
print("which all have determinant", highest_det)
print("\ntime taken:", total_time)

Mi máquina tardó 3 segundos para una matriz de 3x3. Parece que tomaría varios años para una matriz de 4x4...
Aunque con un poco de reflexión se podría acortar el proceso.
Hay 36 matrices con un determinante de 412 y 36 con un determinante de -412.

Todas las matrices con det 412 tienen 7,8,9 en cols separadas y filas separadas, como alguien más mencionó.