Maximizing Determinant in 3x3 Matrix with 0/1 Entries

In summary, the largest possible value for a determinant of a 3x3 matrix with entries of 0 or 1 is 2. This was found through a brute force approach, and there are three matrices that have this maximum determinant. Similar results were found for 2x2 matrices with a max determinant of 1 and 4x4 matrices with 60 matrices having a max determinant of 3. In general, for arbitrary dimensions, the determinant can be determined using the adjacency matrices of directional graphs with self-loops. Another formula, known as Hadamard's Maximum Determinant Problem, gives a maximum value of 2 for 3x3 matrices. There are references available for the (0,1)-matrix formula
  • #1
neden
18
0
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?
 
Physics news on Phys.org
  • #2
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
[tex]\left\{\left(
\begin{array}{ccc}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{array}
\right),\left(
\begin{array}{ccc}
1 & 0 & 1 \\
1 & 1 & 0 \\
0 & 1 & 1
\end{array}
\right),\left(
\begin{array}{ccc}
1 & 1 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1
\end{array}
\right)\right\}[/tex]
The last two are just transpositions of each other.

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

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
[tex]A_{ij} = 1 - \delta_{i,j-1}[/tex] 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 [tex]B_{ij} = 1 - \delta_{i,j}[/tex]. 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" [Broken] (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 [tex]2^{n^2}-1[/tex].
Sorry I couldn't think of a decent proof - these types of problems are not my forte.
 

Attachments

  • graphs.png
    graphs.png
    9.5 KB · Views: 503
Last edited by a moderator:
  • #3
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.
 
  • #4
http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html" [Broken] -- 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?
 
Last edited by a moderator:
  • #5


I would say that your solution is correct. The maximum determinant for a 3x3 matrix with 0/1 entries is indeed 2. This can be proven using algebraic methods, specifically by using the Laplace expansion formula for calculating determinants. However, there is no general algorithm for finding the maximum determinant for a given size of matrix with specific entries. It would depend on the specific values and patterns of the entries in the matrix. In this case, your solution is optimal and cannot be improved upon.
 

What is a 3 by 3 matrix puzzle?

A 3 by 3 matrix puzzle is a type of math puzzle that involves arranging nine numbers in a 3 by 3 grid such that each row, column, and diagonal adds up to the same sum.

How do you solve a 3 by 3 matrix puzzle?

To solve a 3 by 3 matrix puzzle, you must first determine the sum that each row, column, and diagonal should add up to. Then, you can use trial and error or logic to fill in the empty spaces with numbers that will add up to those sums.

Are there any strategies for solving a 3 by 3 matrix puzzle?

Yes, there are several strategies for solving a 3 by 3 matrix puzzle. These include looking for patterns, using the process of elimination, and starting with the corners and working your way towards the center.

Can a 3 by 3 matrix puzzle have multiple solutions?

No, a 3 by 3 matrix puzzle should only have one unique solution. If you end up with multiple solutions, then you have made a mistake in your calculations or placement of numbers.

What is the significance of a 3 by 3 matrix puzzle in mathematics?

3 by 3 matrix puzzles are a popular type of mathematical puzzle that can help improve problem-solving skills and logical thinking. They can also be used to explore concepts such as symmetry and mathematical patterns.

Similar threads

  • Linear and Abstract Algebra
Replies
8
Views
771
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
Replies
3
Views
971
Replies
7
Views
782
  • Linear and Abstract Algebra
Replies
2
Views
930
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
735
  • Linear and Abstract Algebra
Replies
1
Views
977
  • Linear and Abstract Algebra
Replies
10
Views
925
Back
Top