Maximising determinant problem

Question

The problem is to maximize the determinant of a $3 \times 3$ matrix with elements from $1$ to $9$.
Is there a method to do this without resorting to brute force?

Answer 1

HINT:

The product of eigenvalues are the determinant. The trace is the sum of eigenvalues. It may be reasonable to believe that a large eigenvalue sum increases the chance of a large eigenvalue product. If that is the case then 9,8,7 would be good candidates for diagonal elements. Then some symmetry argument could possibly be used for the remaining 6 positions.

This would reduce from having to try $9! = 362880$ to $6! = 720$ matrices.

SPOILER WARNING:

Using Matlab or Octave, we can with a short but obscure brute force script (don't worry it took maybe 5-10 seconds on my machine ) :

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_)

Find that the matrix

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

Has a determinant $412$ which supposedly is the largest of the bunch. Of course as someone mentioned in the comments any combination of row or column permutations would give the same value so the important thing is that 7,8,9 don't share any row or column as we then could permute them into the diagonal.

Answer 2

Swapping rows and columns leaves the absolute value of the determinant unchanged, so we can assume that the middle cell contains 1. Then, since the absolute value of the determinant is unaffected by taking transposes (and swapping the top & bottom rows or the left and right columns), we can assume that the 2 occurs in either a corner of the middle of the top row.

This leaves $2 \cdot 7! = 10,080$ possibilities to check, which is an improvement on $9!=362,880$.

After fixing the 1,2, one could notice that there are only 4 essentially different places to put the 3, hence we only need to check $2 \cdot 4 \cdot 6! = 5,760$ possibilities.

Brute force (computing all 9! possibilities), always a favourite of mine, works too:

# 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

This prints 412.0 after 8 seconds on my old X201 tablet.

Answer 3

The question asks for alternatives to brute force, but just to illustrate the difficulties of using brute force, here is python code for brute forcing it:

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)

Took my machine 3 seconds for a 3x3 matrix. Seems like would take several years for a 4x4 matrix...
Although with a bit of thought you could shorten the process.
There are 36 matrices with a determinant of 412 and 36 with a determinant of -412.

All of the matrices with det 412 have 7,8,9 in separate cols and separate rows, as someone else mentioned.