# Reordering of columns and rows in a cosine similarity matrix

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]

• I am a bit confused: some of the rows in your matrix do not contain a $1$, so how can there be ones on the diagonal after simple rearrangements? Also, the reordering you propose does not seem to make your matrix symmetric: if mat is your matrix, none of the possible reorderings generates a symmetrical matrix. (the following all return false: reorder rows: SymmetricMatrixQ@mat[[{1, 3, 2, 4, 5, 7, 6}]], columns: SymmetricMatrixQ@mat[[All, {1, 3, 2, 4, 5, 7, 6}]], and both: SymmetricMatrixQ@mat[[{1, 3, 2, 4, 5, 7, 6}, {1, 3, 2, 4, 5, 7, 6}]]). – MarcoB Feb 6 '17 at 0:05
• @MarcoB: I apologize for not being more clear. Copying from the research article where found: CosineMatrix={{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,.91,1}} ReorderedCosineMatrix={{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}} – fishbacp Feb 6 '17 at 21:03
• The authors of the research article gave this snippet of pseudocode, which I don't quite see how to translate to Mathematica: "function REORDER-MATRIX (Cosine-Matrix) returns Reordered Cosine Matrix X A = Cosine-Matrix [r, c] = size(Cosine-Matrix) loop for i = 1 to c index = sortrows-descending(Cosine-Matrix, i) reorder rows and columns of Cosine-Matrix based on index INDEX = update (index) remove row and column i from Cosine-Matrix end A = reorder rows and columns of A based on INDEX return A" – fishbacp Feb 6 '17 at 21:04
• Please add the new matrices and the pseudocode in your original question. You can edit the question at any time using the "edit" link at the bottom left of the question itself. Make sure that you format the code / data for readability. Perhaps you could add a link to the article from which this came as well. – MarcoB Feb 6 '17 at 21:06
• Thanks--I think giving you the article link would be more helpful: SVD Article The part relevant to what I'm hoping to do is described as a "matrix reordering algorithm" as discussed in the second paragraph of p. 046114-7. I've computed the unordered matrix of cosine values and wish to obtain the re-ordered on in Figure 3d. Thanks again for your patience. – fishbacp Feb 6 '17 at 21:18

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 /@ %