1
$\begingroup$

NOT related to my related question! (Different problem source)

This time, I want to sort a symmetric matrix M, and it must stay symmetric (i.e. row and col sort is the same). WLOG the diagonal is 0 (no relevance). This means the following restraint: Assume that M is

{{0, 2, 3, 6}, {2, 0, 1, 4}, {3, 1, 0, 5}, {6, 4, 5, 0}}

then your allowed operations are any row swap (here 2 and 3)

{{0, 2, 3, 6}, {3, 1, 0, 5}, {2, 0, 1, 4}, {6, 4, 5, 0}}

and now you must accompany it with same col swap (also 2 and 3)

{{0, 3, 2, 6}, {3, 0, 1, 5}, {2, 1, 0, 4}, {6, 5, 4, 0}}

so M is symmetric again. You are done when M is smallest by alphanumeric comparison:

{{0, 1, 2, 4}, {1, 0, 3, 5}, {2, 3, 0, 6}, {4, 5, 6, 0}}

This of course means that the linked answer doesn't work anymore:

{{0, 2, 3, 6}, {2, 0, 1, 4}, {3, 1, 0, 5}, {6, 4, 5, 0}}

becomes a fixed point (where instead 1 shall go into the first row).

Neither does it work to just elide the diagonal, sort just by row and with the same permutation by col:

{{0, 1, 2, 4}, {1, 0, 3, 5}, {2, 3, 0, 1}, {4, 5, 1, 0}} 

is correctly sorted without the 0, but not the solution.

My working algorithm is generating all possible n! M and fish out the smallest. A much better almost working is in the comments.

$\endgroup$
6
  • $\begingroup$ What is the correct solution in this example and what are the constraints to sorting? $\endgroup$ Nov 15, 2022 at 14:47
  • $\begingroup$ How large is M likely to be and how will you know if you've reached an optimal solution? $\endgroup$ Nov 17, 2022 at 15:55
  • $\begingroup$ @IntroductionToProbability: M is very small as the main problem requires to bring O(n!) M's into normal form. n=8-10 at most. The correctness must be guaranteed by the algorithm itself!...But the problem just has become moot as I read the Wiki - if an effective sorting algorithm would exist, we just would have solved the graph isomorphy problem (read M as incidency matrix) - which is in NP-intermediate. $\endgroup$ Nov 18, 2022 at 10:27
  • $\begingroup$ Will your matrix contain strings? Your title says "alphanumerically" but your example contains only numbers. $\endgroup$
    – Edmund
    Mar 26, 2023 at 22:07
  • $\begingroup$ You seem to have a typo in your solution. Third row should be {2, 3, 0, 6}. The 2 and 3 are swapped around. $\endgroup$
    – Edmund
    Mar 26, 2023 at 22:22

2 Answers 2

2
$\begingroup$

You may use ResourceFunction["SymmetricSort"] and OrderingBy.

With

MatrixForm[matrix = {{0, 2, 3, 6}, {2, 0, 1, 4}, {3, 1, 0, 5}, {6, 4, 5, 0}}]

Mathematica graphics

and

SymmetricMatrixQ[matrix]
True

Then symmetrically ordering by matrix rows

symMatrixNSort[m_?SymmetricMatrixQ] :=
 ResourceFunction["SymmetricSort"][m, OrderingBy[m, Total]]

symMatrixNSort symmetrically orders the rows by their total.

MatrixForm[res = symMatrixNSort[matrix]]

Mathematica graphics

SymmetricMatrixQ[res]
True

Your title says "alphanumerically" but your example contains only numbers so I used Total as the order function. You can replace this with a function of your choice to handle your alphanumeric vectors.

Hope this helps.

$\endgroup$
2
  • 1
    $\begingroup$ (+1) Your resource function SymmetricSort is very nice, @Edmund. $\endgroup$ Mar 27, 2023 at 1:10
  • $\begingroup$ @Edmund: That's OK, in practice only numbers will show up. "Alphanumerically" for generality :-) $\endgroup$ Mar 27, 2023 at 8:40
1
$\begingroup$

Does this satisfy your constraints?

unsortedMatrix = {{0, 2, 3, 6}, {2, 0, 1, 4}, {3, 1, 0, 5}, {6, 4, 5, 0}};
unsortedMatrix // MatrixForm

\begin{pmatrix} 0 & 2 & 3 & 6 \\ 2 & 0 & 1 & 4 \\ 3 & 1 & 0 & 5 \\ 6 & 4 & 5 & 0 \\ \end{pmatrix}

unsortedVector = 
 Statistics`Library`UpperTriangularMatrixToVector[unsortedMatrix]

{2, 3, 6, 1, 4, 5}

sortedVector = Sort@unsortedVector

{1, 2, 3, 4, 5, 6}

sortedMatrix = 
  Statistics`Library`VectorToSymmetricMatrix[sortedVector,0,Length[unsortedMatrix]];
(* 1st argument: vector to make into matrix *)
(* 2nd argument: what to place on the diagonal *)
(* 3rd argument: n, where n-by-n is the desired matrix dimensions *)

sortedMatrix // MatrixForm

\begin{pmatrix} 0 & 1 & 2 & 3 \\ 1 & 0 & 4 & 5 \\ 2 & 4 & 0 & 6 \\ 3 & 5 & 6 & 0 \\ \end{pmatrix}

Note: makes use of undocumented functions from Statistics`Library

$\endgroup$
10
  • $\begingroup$ This is definitely correct (as a result), since the vectors stay in place, but how does it work exactly? And, even more relevant, does it work for the critical second example? $\endgroup$ Nov 16, 2022 at 12:00
  • $\begingroup$ If the second example is {{0, 1, 2, 4}, {1, 0, 3, 5}, {2, 3, 0, 1}, {4, 5, 1, 0}} then it sorts to {{0, 1, 1, 2}, {1, 0, 3, 4}, {1, 3, 0, 5}, {2, 4, 5, 0}}. I will edit my answer to make the algorithm clearer $\endgroup$ Nov 16, 2022 at 14:01
  • $\begingroup$ What do you mean by “the vectors stay in place” $\endgroup$ Nov 16, 2022 at 23:12
  • $\begingroup$ Bad wording...The numbers of the vector stay "together". Obviously, this can't work with just sorting all numbers of the matrix - it's just a lucky accident that (0123),(0145),(0246) and (0356) stay together after sorting. OK, I reword it: if a matrix contains the vector (a1,a2,...) before, it must also contain this vector after sorting (in any order of the vector elements). $\endgroup$ Nov 17, 2022 at 13:02
  • 1
    $\begingroup$ @IntroductionToProbability Your solution does not have the same eigenvalues as the starting matrix. The "staying together" means the rows can change position and the numbers in a row change position within the row. Numbers should not leave their row, only be rearranged within it. $\endgroup$
    – Edmund
    Mar 27, 2023 at 12:59

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.