Finding Max Determinant of 6x6 matrix

[shiranian]

1. Construct 6x6, 5x5, 4x4 and 3x3 matrices that has the largest determinant possible using only 1 and -1

I have attempted to reduce this problem by applying determinant properties, here is an example of my work for a 3x3 matrix.

If we have 3x3 and fill it with 1's and -1's the total possible matrices are
512
However, property two says and row exchange or column exchange does not change the absolute values
Thus, there are
8*7*6 = 336
Property three says if we multiply a matrix its determinant stays the same (in this case by -1)
Thus there are
336/2 = 168
Property 5 says that two rows or columns that are equal (linear dep)
Since we already applied that no rows are the same with P2. Not sure..
Property 10 says the det of the transpose is equal to the original matrix
Thus
168/2 = 84


Where my true problem lies is not in only in simplifying the problem, but what to do afterwards? Once I have a reasonable number, how do I construct those matrices? Will I have to construct all 512 and then cut down...there must be a simple way to do this.


Thanks for the help.

 

[HallsofIvy]

Finding the determinant of an n by n matrix involves sums and differences of n! terms, each a product of n of the entries. If all entries in the matrix are 1s, then each of these terms is $\pm 1$. If we could arrange the sums and differences so that the "-" signs canceled we would have a total of n!. The determinant cannot be larger than that.

 

[willem2]

There's an upper bound for the determinant.
Suppose your matrix is a set of row vectors v_1..v_n (columns works too).
The determinant is the volume of the n-dimensional parallelepiped formed by the set: c_1*v_1 + c_2*v_2 + ... c_n *v_n with 0 <= c_i <= 1.
This volume is maximal if all the v_i are orthogonal.
Since the length of the v_i is $\sqrt {n}$ and there are n of them, the maximum volume, and therefore the maximum determinant is ${\sqrt {n}}^n = n^{\frac {n} {2}}$

Now it's not always possible to get the maximum determinant. If n is odd, you can't get 2 vectors that are orthogonal, and if n is divisible by 2 but not 4, you can't get 3 orthogonal vectors. (if n>2)


It appears that it's always possible to find the maximum determinant of n^(n/2) when n is divisible by four. This is called a Hadamard matrix

http://mathworld.wolfram.com/HadamardMatrix.html
It is an open conjecture, wether an Hadamard matrix existes for all multiples of 4.

If you would try a computer search if n is not a multiple of 4, you could limit yourself to a matrix whose rows are nearly orthogonal.

n = 3 is easy. The limit is 5.19..., but the determinant has to be an even number, because it's the sum of 6 odd numbers, so the maximum is 4, which you'll find with a few tries.