Sorting a symmetric matrix alphanumerically

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


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

• What is the correct solution in this example and what are the constraints to sorting? Nov 15, 2022 at 14:47
• How large is M likely to be and how will you know if you've reached an optimal solution? Nov 17, 2022 at 15:55
• @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. Nov 18, 2022 at 10:27
• Will your matrix contain strings? Your title says "alphanumerically" but your example contains only numbers. Mar 26, 2023 at 22:07
• You seem to have a typo in your solution. Third row should be {2, 3, 0, 6}. The 2 and 3 are swapped around. Mar 26, 2023 at 22:22

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.

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

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 =
StatisticsLibraryUpperTriangularMatrixToVector[unsortedMatrix]


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

sortedVector = Sort@unsortedVector


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

sortedMatrix =
StatisticsLibraryVectorToSymmetricMatrix[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 StatisticsLibrary

• 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? Nov 16, 2022 at 12:00
• 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 Nov 16, 2022 at 14:01
• What do you mean by “the vectors stay in place” Nov 16, 2022 at 23:12
• 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). Nov 17, 2022 at 13:02
• @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. Mar 27, 2023 at 12:59