Maximizing Determinant in 3x3 Matrix with 0/1 Entries

[neden]

I was wondering what would be the largest possible value for a determinant, for a 3 by 3 matrix whose entries can only be 0 or 1.
My solution is the following:

1 0 1
1 1 0
0 1 1

With a determinant of 2. Can anyone go any higher, or better yet is there an algebraic algorithm to determine that?

 

[Simon_Tyler]

I think that you're right. By brute force, I found that the max determinant of 3x3 matrices with elements in {0,1} is 2. There are three matrices with the max determinant
$$\left\{\left(<br /> \begin{array}{ccc}<br /> 0 & 1 & 1 \\<br /> 1 & 0 & 1 \\<br /> 1 & 1 & 0<br /> \end{array}<br /> \right),\left(<br /> \begin{array}{ccc}<br /> 1 & 0 & 1 \\<br /> 1 & 1 & 0 \\<br /> 0 & 1 & 1<br /> \end{array}<br /> \right),\left(<br /> \begin{array}{ccc}<br /> 1 & 1 & 0 \\<br /> 0 & 1 & 1 \\<br /> 1 & 0 & 1<br /> \end{array}<br /> \right)\right\}$$
The last two are just transpositions of each other.

There are similar results with 2x2 matrices which have max determinant = 1:
$$\left\{\left(<br /> \begin{array}{cc}<br /> 1 & 0 \\<br /> 0 & 1<br /> \end{array}<br /> \right),\left(<br /> \begin{array}{cc}<br /> 1 & 0 \\<br /> 1 & 1<br /> \end{array}<br /> \right),\left(<br /> \begin{array}{cc}<br /> 1 & 1 \\<br /> 0 & 1<br /> \end{array}<br /> \right)\right\}$$

For 4x4 matrices there are 60 matrices with the max determinant of 3. But only 5 non-similar matrices.
For higher dimensions, the brute force approach is not so good!

In arbitrary dimensions you can always construct the NxN matrix with elements
$$A_{ij} = 1 - \delta_{i,j-1}$$ where the indices are evaluated mod N. For the N=3 case, this yields the matrix you considered and for arbitrary N, this matrix has determinant det(A) = N-1.

You could also construct the matrix $$B_{ij} = 1 - \delta_{i,j}$$. This has determinant det(B) = -(-1)^N(N-1). Which is positive for odd dimensions.

These matrices can be thought of as the adjacency matrices of (non-weighted) directional graphs with self-loops.
I attached a picture of the graphs for the matrices A for N=3,4,5,6.
The matrix B corresponds to the http://en.wikipedia.org/wiki/Complete_graph" (undirected) graphs.

Anyway...
the case of 3x3 matrices that you were interested in is amenable to brute force and can be completely solved. The easiest way to generate all such matrices is to use the binary representation of all numbers from 0 to $$2^{n^2}-1$$.
Sorry I couldn't think of a decent proof - these types of problems are not my forte.

 

[neden]

Thank you for the brief explanation, kind sir.

I also found this formula called Hadamard's Maximum Determinant Problem.
|detA|<=((n+1)^((n+1)/2))/(2^n)

where n is the matrix length, in this case 3.
The answer comes up to 2.

 

[Simon_Tyler]

http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html" -- I'll have to try to remember that. Have you looked at any of the references for the (0,1)-matrix formula and its proof? Is it a difficult thing to prove?