1
$\begingroup$

When the positive integers 1 to 9, inclusive, are used exactly once as elements of a 3 x 3 matrix, what is the largest possible value of the determinant of the matrix?

$\endgroup$

3 Answers 3

2
$\begingroup$
per = Permutations[Range[1, 9]];
all = (Det[{{#1, #2, #3}, {#4, #5, #6}, {#7, #8, #9}}] &) @@@ per;

now:

maxdet = Max[all]
(*412*)

positions of these matrices are:

  pos = Flatten@Position[all, maxdet];
    (*{14176, 18520, 27624, 31968, 55210, 64000, 68658, 77448, 100690,
    105034, 114138, 118482, 125216, 131000, 151265, 157001, 164810,
    176240, 186665, 198047, 210050, 215834, 227711, 233447, 244519,
    250303, 262185, 267921, 284113, 295543, 297585, 308967, 329353,
    335137, 338631, 344367}*)

these matrices are:

    maxm = per[[pos]];

Det[{{#1, #2, #3}, {#4, #5, #6}, {#7, #8, #9}}] & @@@ maxm

(*{412, 412, 412, 412, 412, 412, 412, 412, 412, 412, 412, 412, 412,
412, 412, 412, 412, 412, 412, 412, 412, 412, 412, 412, 412, 412, 412,
412, 412, 412, 412, 412, 412, 412, 412, 412}*)
$\endgroup$
1
$\begingroup$

Algohi is right, but I'm going to give a bit faster version of this.

We can assume 1 is the first entry of the matrix.

We can also assume that the first row and first column are in ascending order.

That gives us this construction for the first row:

ROWONE = {};
For[b = 2, b <= 8, b++,
  For[c = b + 1, c <= 9, c++,
    ROWONE = Append[ROWONE, {1, b, c}]
    ];
  ];

And likewise to construct the first column:

PARTIAL = {};
For[j = 1, j <= Length[ROWONE], j++,
  rowone = ROWONE[[j]];
  ints = Complement[Range[9], rowone];
  For[b = 1, b <= 5, b++,
   For[c = b + 1, c <= 6, c++,
     PARTIAL = Append[PARTIAL, {rowone, ints[[b]], ints[[c]]}];
     ];
   ];
  ];

And finally to construct them all:

MATRICES = {};
For[j = 1, j <= Length[PARTIAL], j++,
  rowone = PARTIAL[[j, 1]];
  b = PARTIAL[[j, 2]];
  c = PARTIAL[[j, 3]];
  ints = Complement[Range[9], Union[rowone, {b, c}]];
  PERM = Permutations[ints];
  For[i = 1, i <= Length[PERM], i++,
   perm = PERM[[i]];
   MATRICES = 
    Append[MATRICES, {rowone, {b, perm[[1]], perm[[2]]}, {c, 
       perm[[3]], perm[[4]]}}];
   ];
  ];

That gives us our list, so:

DET = Det /@ MATRICES;
Max[DET]
(* Output: 349 *)

Now, you might have an "oh s___" moment, but don't worry. Our assumptions about permuting the rows and columns involve permuting the matrix -- permutation matrices have sign 1 or -1. We just compensate for that by:

Min[DET]
(* Output: -412 *)

There are two matrices with this determinant, in our scheme at least, which are:

MatrixForm /@ MATRICES[[Map[#[[1]] &, Position[DET, -412]]]]

(*Output something like:
 1 4 8
 5 9 3
 7 2 6
 and the transpose of this*)

This leads me to conclude we should have also assumed that b was less than the second entry of the first row.. we could to that too, but I'll leave that as an exercise. It's actually a very quick-fix. (Hindsight is 20/20.)

Just to make the point, to get from fresh kernel to the answer of 412, it takes Algohi's method 6.75s (for me, anyway) while my method takes 0.67s (for me), with an improvement all the way down to 0.26s when transpositions are cut out (as noted in the previous paragraph). His search is over $9!$ matrices, while mine is only over $7!$ of them.

It's also nice because this gives us a great understanding of what all the maximum/minimum determinant matrices are -- permutations and transpositions of that one above.

You can use our matrix, which I have named Matt, to take a look at what this determinant 412 really is -- how it comes from my favorite definition of the determinant, the permutation definition (see Wikipedia). I have permuted two rows of Matt so that his determinant is positive.

Matt = {{7, 2, 6}, {5, 9, 3}, {1, 4, 8}};
perm = Permutations[Range[3]];
neg = Select[perm, Count[Table[#[[i]] != i, {i, 1, 3}], True] == 2 &];
pos = Complement[perm, neg];

That just splits up the six permutations into even (positively counted) and odd (negatively). We can run it through our friend Matt to see:

pos = Table[Matt[[i, pos[[j, i]]]], {j, 1, 3}, {i, 1, 3}]
neg = Table[Matt[[i, neg[[j, i]]]], {j, 1, 3}, {i, 1, 3}]

(*Output:
 {{7, 9, 8}, {2, 3, 1}, {6, 5, 4}}
 {{7, 3, 4}, {2, 5, 8}, {6, 9, 1}}
 *)

pos = Map[Times @@ # &, pos]
neg = Map[Times @@ # &, neg]

(*Output:
 {504, 6, 120}
 {84, 80, 54}
 *)

pos = Plus @@ pos
neg = Plus @@ neg
pos - neg

(*Output:
 630
 218
 412
 *)

You can see that the even permutations, the ones that count positively in the determinant, will give you 630, but interestingly enough, that comes from $504+6+120$, since the permutation $213$ gives us entries $\{2,3,1\}$ in Matt. However, that's actually a good thing. If you just wanted to maximize the sum of three disjoint products of 1 through 9, you would definitely split it up as: $$9\cdot 8\cdot 7 + 6 \cdot 5\cdot 4 + 3\cdot 2\cdot 1=630.$$ Having those three positive terms of the permutation is best-possible. The worst-possible (i.e. smallest) sum is what we want for the negatively counted permutations. That sum is:$$1\cdot 8\cdot 9 + 2\cdot 5\cdot 7 + 3\cdot 4\cdot 6=214,$$ and it is at least somewhat interesting that although it is not possible to simultaneously achieve pos=630 and neg=214, our best determinant is very close, with neg=218.

I assume it is obvious why the positive terms are as large as possible, but we can check the negatives (and why not do both) with:

perm = Map[Partition[#, 3] &, Permutations[Range[9]]];
f[p_] := Plus @@ Map[Times @@ # &, p]
DATA = Map[f, perm];
max = Max[DATA]
min = Min[DATA]

You can even confirm these are unique:

pos=Position[DATA, max];
DeleteDuplicates[Map[Sort, Table[perm[[pos[[i, 1]]]], {i, 1, Length[pos]}], 2]]
pos=Position[DATA, min];
DeleteDuplicates[Map[Sort, Table[perm[[pos[[i, 1]]]], {i, 1, Length[pos]}], 2]]

(*Output:
 {{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}}
 {{{1, 8, 9}, {2, 5, 7}, {3, 4, 6}}}
*)

Inspired by the fact that we like $9\cdot 8\cdot 7 + 6\cdot 5 \cdot 4 + 3\cdot 2\cdot 1$ so much, we could even construct a matrix where we think of the main diagonal as $\{9,8,7\}$ as fixed and assume that the other two diagonals are $\{6,5,4\}$ and $\{3,2,1\}$ and try to reconstruct the matrix that way:

perm654 = Permutations[{6, 5, 4}];
perm321 = Permutations[{3, 2, 1}];
DetMatt[p_, q_] := Det[
  {{9, perm654[[p, 1]], perm321[[q, 1]]},
   {perm321[[q, 2]], 8, perm654[[p, 2]]},
   {perm654[[p, 3]], perm321[[q, 3]], 7}}]
Table[DetMatt[p, q], {p, 1, 6}, {q, 1, 6}]
(*Output:
 {{405, 402, 395, 389, 382, 379}, {390, 396, 388, 400, 392, 398},
 {410, 391, 407, 369, 385, 366}, {380, 379, 393, 391, 405, 404},
 {400, 374, 412, 360, 398, 372}, {385, 368, 405, 371, 408, 391}}

Notice these are all quite large, because pos is quite large and neg varies but can't be too big (the two biggest terms are already in pos). Our 412 appears in there of course. We can make sure this is our friend Matt by:

Table[DetMatt[p, q], {p, 1, 6}, {q, 1, 6}];
{{p, q}} = Position[%, 412];
{{9, perm654[[p, 1]], perm321[[q, 1]]},
 {perm321[[q, 2]], 8, perm654[[p, 2]]},
 {perm654[[p, 3]], perm321[[q, 3]], 7}}
(*Output something like:
 9 4 2
 3 8 6
 5 1 7
*)

That is Matt, although he is disguised by a transposition and permutation.

If you tried that with the hope that you would use neg=214 instead of neg=218, you would have a similar outcome. I'll let the main diagonal be $\{1,8,9\}$ with permutations of $\{2,5,7\}$ and $\{3,4,6\}$ throughout:

perm257 = Permutations[{2, 5, 7}];
perm346 = Permutations[{3, 4, 6}];
DetMatt[p_, q_] := Det[
  {{9, perm257[[p, 1]], perm346[[q, 1]]},
   {perm346[[q, 2]], 8, perm257[[p, 2]]},
   {perm257[[p, 3]], perm346[[q, 3]], 1}}]
Table[DetMatt[p, q], {p, 1, 6}, {q, 1, 6}];
Min[%]
(*Output: -330 *)

Notice it isn't even close to our 412 figure. If we use the antidiagonals from the correct matrix, which are (see above) $\{\{7, 3, 4\}, \{2, 5, 8\}, \{6, 9, 1\}\}$ we do recover -412 as we expect:

perm258 = Permutations[{2, 5, 8}];
perm347 = Permutations[{3, 4, 7}];
DetMatt[p_, q_] := Det[
  {{9, perm258[[p, 1]], perm347[[q, 1]]},
   {perm347[[q, 2]], 6, perm258[[p, 2]]},
   {perm258[[p, 3]], perm347[[q, 3]], 1}}]
Table[DetMatt[p, q], {p, 1, 6}, {q, 1, 6}];
Min[%]
(*Output: -412 *)

The difference is that the roles of 6, 7, and 8 have been changed.

$\endgroup$
0
$\begingroup$

Permutations[Range[1, 9]] // Map[Partition[#, 3] & /* Det] // Max

(* 412 .. try Histogram *)

Monte Carlo:

randomAngeMatrix := 
 PermutationReplace[Range[9], RandomPermutation[9]] // 
  Partition[#, 3] & 

angeMatrixPlot[m_] := 
 MatrixPlot[m - 5, Frame -> False, ImageSize -> 20]

angeMatrixData[m_] := <|"matrix" -> m, "icon" -> angeMatrixPlot[m], 
  "det" -> Det[m], 
  "sparkline" -> 
   ListPlot[Flatten[m], Frame -> False, Axes -> False, 
    ImageSize -> 20, Joined -> True]|>

Table[randomAngeMatrix // angeMatrixData, {1000}] // Dataset // Query[Max, "det"]

(* 400 in one run)

Exploratory:

Table[randomAngeMatrix // angeMatrixData, {100}] // Dataset // 
    Query[GroupBy[Quotient[Abs[#det], 10] &] /* KeySort, 
     All, {"sparkline", "icon", "det"} /* Values /* Column] // 
   Normal // Normal // Column

enter image description here

Grouping by Determinant intervals of 10 doesn't reveal patterns in sparklines. Spectral methods could reveal additional structure.


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.