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.

Improve this question
$\endgroup$
6
  • $\begingroup$ What is the correct solution in this example and what are the constraints to sorting? $\endgroup$ Commented 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$ Commented 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$ Commented Nov 18, 2022 at 10:27
  • $\begingroup$ Will your matrix contain strings? Your title says "alphanumerically" but your example contains only numbers. $\endgroup$ Commented 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$ Commented Mar 26, 2023 at 22:22

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ (+1) Your resource function SymmetricSort is very nice, @Edmund. $\endgroup$ Commented Mar 27, 2023 at 1:10
  • $\begingroup$ @Edmund: That's OK, in practice only numbers will show up. "Alphanumerically" for generality :-) $\endgroup$ Commented 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

Improve this answer
$\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$ Commented 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$ Commented Nov 16, 2022 at 14:01
  • $\begingroup$ What do you mean by “the vectors stay in place” $\endgroup$ Commented 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$ Commented 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$ Commented Mar 27, 2023 at 12:59

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.