Sorting a symmetric matrix alphanumerically

Question

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.

Answer 1

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

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

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.

Answer 2

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