# Sorting a matrix alphanumerically

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.

• Can you help me understand the diagonal aspect of this? Commented Mar 27, 2013 at 17:31
• 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...). Commented Mar 27, 2013 at 17:40
• @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. Commented Mar 27, 2013 at 17:44
• @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. Commented Mar 27, 2013 at 17:46
• 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.) Commented Mar 27, 2013 at 18:19

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


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

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

True


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]


yields:

Note the first matrix is the same as @IstvanZachar.

The determinants satisfy the constraint:

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


yields:

{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).