Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
2  
Can you help me understand the diagonal aspect of this? –  Mr.Wizard Mar 27 '13 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...). –  István Zachar Mar 27 '13 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. –  Mr.Wizard Mar 27 '13 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. –  István Zachar Mar 27 '13 at 17:46
1  
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.) –  whuber Mar 27 '13 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)
True
share|improve this answer

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:

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])

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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