Reordering of columns and rows in a cosine similarity matrix

Question

I have the following 7-by-7 matrix of cosine similarity measures:

Cosine-Matrix={{1, .91, 1, .78, .22, -.18, .22}, {.91, 1, .91, .46, -.18, -.57, -.18}, {1, .91, 1, .78, .22, -.18, .22}, {.78, .46, .78, 1, .78, .46, .78 }, {0.22, .18, .22, .78, 1, .91, 1}, {-.18, -.57, -.18, .46, .91, 1, .91}, {.22, -.18, .22, .78, 1, 0.91, 1}};

Through a reordering process this matrix can be transformed to the following:

 Reordered-Cosine-Matrix={{1, 1, .91, .78, .22, .22, -.18}, {1, 1, .91, .78, .22, .22, -.18}, {.91, .91, 1, .46, -.18, -.18, -.57}, {.78, .78, .46, 1, .78, .78, .46}, {.22, .22, -.18, .78, 1, 1, .91}, {.22, .22, -.18, .78, 1, 1, .91}, {-.18, -.18, -.57, .46, .91, .91, 1}}

This new matrix has the property that it is symmetric with diagonal entries equal to one and whose entries to the right of each one are decreasing from left to right.

A MATLAB function, which performs the reordering and which was provided by the authors of the article where I found the above matrices, is below. I'm having a hard time translating it to Mathematica.

In the code below "a" is the input cosine-similarity matrix; "z" is the reordered matrix)

function z = reorderM(a)

[s,dummy] = size(a); %number of rows in a = number of nodes

A = a; % create new variable A = a to reorder according to index I produced

for i = 1:s

b = a(:, 1:2) % Extract first two columns of a, index column and ist node column

[dummy1, index] = sortrows(b, -2) % Sort 1st node in descending order

c = a(index, :) % re-sorted rows according to index

c = [c(:, 1) c(:, index+1)] % re-sorted columns according to index r

I(i:s, 1) = c(:, 1) % record index in terms of node ids

a = c % put a = new reordered c

a(1, :)=[]; % remove first row (sorted node)

a(:, 2)=[]; % remove first (second) column (sorted node)

c = 0; b = 0; index=0;

end

% Use index I to reorder the rows and columns of A
z = A(I, :)

z = [z(:, 1) z(:, I+1)]

z = [0 z(:, 1)'; z]

Answer 1

The size of your matrix lends itself to a brute-force search for a symmetrizing rearrangement.

For instance, first generate all the row-rearranged matrices of your original matrix mat, then select the symmetric ones among the results:

Cases[{#, mat[[#]]} & /@ Permutations[Range[7]], {perm_, _?SymmetricMatrixQ} :> perm]

(* Out: {{3, 2, 1, 4, 5, 6, 7}, {3, 2, 1, 4, 7, 6, 5}} *)

It is also easy to verify that reordering columns leads to the same conclusion:

Cases[{#, mat[[All, #]]} & /@ Permutations[Range[7]], {perm_, _?SymmetricMatrixQ} :> perm]

(* Out: {{3, 2, 1, 4, 5, 6, 7}, {3, 2, 1, 4, 7, 6, 5}} *)

On the other hand, there is no way to reorder both rows and columns using the same permutation scheme and get a symmetric matrix:

Cases[{#, mat[[#, #]]} & /@ Permutations[Range[7]], {perm_, _?SymmetricMatrixQ} :> perm]

(* Out: {} *)

---

It can also be verified by inspection that none of the symmetric matrices obtained from your mat actually have the non-decreasing-to-the-right of the diagonal property that you sought:

Cases[{#, mat[[#]]} & /@ Permutations[Range[7]], {_, m_?SymmetricMatrixQ} :> m];
MatrixForm /@ %

Cases[{#, mat[[All, #]]} & /@ Permutations[Range[7]], {_, m_?SymmetricMatrixQ} :> m];
MatrixForm /@ %