# Sorting Matrix to Block structure

I have a symmetric matrix and I want it to be as block-like as possible. I don't have a clear definition. I want the smallest number of groups of non zero elements or maybe the most non-zero elements as close as possible to the diagonal.

Example: $$X = \begin{pmatrix}1& 0 & .3& 0& .5& 0\\ 0& 1& 0& .2& 0& .4\\ .3 &0 &1& 0& .3& .1\\ 0 & .2 & 0 & 1 & 0 & .3\\ .5 & 0 & .3 & 0 & 1 & 0\\ 0 & .4 & .1 & .3 & 0 & 1\end{pmatrix}$$

Output: $$Y = \begin{pmatrix}1& .5 & .3& 0& 0& 0\\ .5 & 1 & .3 & 0 & 0 & 0\\ .3 & .3 & 1 & 0 & 0 & .1\\ 0 & 0 & 0 & 1 & .2 & .3\\ 0 & 0 & 0 & .2 & 1 & .4\\ 0 & 0 & .1 & .3 & .4 & 1\end{pmatrix}$$

I only had to swap column and row 2 with 5 to get this result. My algorithm was that I swapped rows and colums for the largest non-diagonal element (in the upper triangle) to a closer position to the diagonal.

• Is there a Matlab/Octave function that does this?
• What is this process called?
• What should a good algorithm that does this look for? (When to stop, which row to swap, etc). What should be the definition of what I want?

The domain my question is related to is that these is a term-term affinity matrix (from Information Retrieval). So if $a_{ij}$ is large then the terms $i$ and $j$ occur often in the same documents.

I want to sort the matrix such that the blocks (which broadly refer to topics) can be visualised. In the current state (see image) one can't see much.

EDIT: I found out that this is called matrix permutation.

-
I think the Matlab function is sortrows(). –  Noturab Dec 15 '12 at 18:15
The fact that you moved the largest non-diagonal element seems to imply that your notion of "as block-like as possible" involves the size of entries. If so, it's less than obvious how "as block-like as possible" is defined; you should provide a definition. –  joriki Dec 15 '12 at 18:15
@DávidKaya sortrows doesn't preserve the symmetry and doesn't sort the columns as well. –  Unapiedra Dec 15 '12 at 18:26
@joriki: The third part of my question suggests that I don't have a definition. However, I added more information to what I want. –  Unapiedra Dec 15 '12 at 18:37
Maybe this is useful Row-column permutation of sparse matrices. You can also search those two topics (permutation and sparse matrix methods). If you have Mathematica or Matlab, they have commands to do that and maybe linear algebra packages do too. Regards. –  Amzoti Dec 16 '12 at 0:12

Here is a link to a paper explaining matrix seriation and an R package. I don't know about Matlab or Octave packages, but try searching for the keyword "seriation" along with your favourite math package.

There are several algorithms, depending on what they measure and minimize. For example one algorithm rearranges the matrix to minimize stress. Stress of a particular matrix cell being the measure of how different it is from the adjacent cells. Depending on what particular measure you minimize you'll get slightly different results.

http://www.jstatsoft.org/v25/i03

Apologies if I'm incorrect, I'm also just trying to understand this. From the dozens of papers I've glanced through, the one I linked seems to be the clearest. And from the handful of keywords that cropped up "seriation" seems to be the most specific to this.

-