Somewhat related to Sort matrix by columns and rows without changing them, but more general.

I'd like to sort a square matrix (a 3 by 3 in my case, but surely the general solution will treat any), say, M = {{i, b, c}, {d, e, f}, {g, h, a}}, into lexicographic form without changing Abs[Det[M]], so all row, column and diagonal swaps are allowed. In the example the wanted result would be {{a, c, f}, {h, b, e}, {g, i, d}}. Obviously I can't split the sorting into row, column and diagonal sorts separately. (The latter CAN be split off but this would still require in my own dumb algorithm: write down the 36 permuted orderings explicitly and pick the first.)

Surely you have a more intelligent (and completely unintelligible, for a n00b like me :-) sorting algorithm? (Like, sorting the list on all levels simultaneously? Only I don't know how yet. Guess it needs a lot of ampersands and octothorpes :-) BTW, I need it to sort a (formal) 9j symbol list and eliminate equivalent duplicates.

  • 2
    $\begingroup$ Can you help me understand the diagonal aspect of this? $\endgroup$
    – Mr.Wizard
    Mar 27, 2013 at 17:31
  • $\begingroup$ Sounds interesting, but I fail to get how the expected result is lexicographically ordered: h > g (rows are not ordered according to lex) and h > b (columns are not ordered...). $\endgroup$ Mar 27, 2013 at 17:40
  • $\begingroup$ @István I didn't check but I assumed that it is ordered to the extent possible within the Det restriction. I have yet to think of a good way to approach such a problem so I don't have an output to compare. $\endgroup$
    – Mr.Wizard
    Mar 27, 2013 at 17:44
  • $\begingroup$ @Mr.W yes, I was thinking about this though some confirmation from Hauke would be useful before delving deep. Surely then we need a metric on how well a matrix is ordered. $\endgroup$ Mar 27, 2013 at 17:46
  • 2
    $\begingroup$ You need to accept that the solution is not, in general, unique. One solution, quite obviously, is to effect a lexicographic sort of the rows. After you do that, exactly what criterion do you propose to apply to determine whether the job is done? (I see a partial order on matrices here but not a total order.) $\endgroup$
    – whuber
    Mar 27, 2013 at 18:19

2 Answers 2


According to the comments, here is a non-elegant, non-exhaustive but direct approach: sort by rows, transpose, sort by columns, transpose, and iterate the process until result does not change anymore.

m = {{a, c, f}, {h, b, e}, {g, i, d}};

(new = FixedPoint[Transpose@Sort@Transpose@Sort@# &, m]) // MatrixForm

enter image description here

The new determinant indicates that an odd number of swaps took place:

Det@m === (Det@new*-1)

I am a little confused. The solution listed is not in lexicographic order (compare with answer of @IstvanZachar.

Perhaps counter to the spirit of the question using the brute computation:

EDIT I edited this code due to an omission.

 an[u_] := Module[{n, perm, p, tp, ptp}, n = Length[u];
   perm = 
    Flatten[Outer[List, Permutations@Range[n], Permutations@Range[n], 
      1], 1];
   p = Map[u[[#[[1]], #[[2]]]] &, perm];
   tp = Transpose /@ p;
   ptp = Union[p, tp];
   SortBy[Select[ptp, Sort[#] == # &], #[[1]] &]
M = {{i, b, c}, {d, e, f}, {g, h, a}};

an[M] yields lexigraphically ordered matrices preserving Abs(Det(M).

MatrixForm /@ an[M]


enter image description here

Note the first matrix is the same as @IstvanZachar.

The determinants satisfy the constraint:

det = Det[M]
Simplify@(Det[#]/det & /@ an[M])


{1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, -1}

The difference in determinants cf @IstvanZachar relates to a different starting matrix (already subject to operation cf question).


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.