3
$\begingroup$

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.

Unsorted term-term affinity matrix

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

  • 0
    I think the Matlab function is sortrows().2012-12-15
  • 0
    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.2012-12-15
  • 0
    @DávidKaya `sortrows` doesn't preserve the symmetry and doesn't sort the columns as well.2012-12-15
  • 0
    @joriki: The third part of my question suggests that I don't have a definition. However, I added more information to what I want.2012-12-15
  • 0
    @Unapiedra: It does now after you edited it; it didn't when I commented; the "What should be the definition of what I want?" part is new. Regarding your edit in the first paragraph: Those ideas only refer to non-zero elements; your selection of the *largest* non-diagonal element seemed to suggest that size matters.2012-12-15
  • 0
    "What should a good algorithm that does this look for? (When to stop, which row to swap, etc)."2012-12-15
  • 0
    I found out that what I want is matrix permutation.2012-12-16
  • 1
    Maybe this is useful [**Row-column permutation of sparse matrices**](http://csam.univ-ovidius.ro/~tudrescu/cursuri/vision/300.pdf). 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.2012-12-16
  • 0
    @Amzoti: Excellent paper. They call it block diagonal form and from this, I found this: http://mathoverflow.net/questions/68041/showing-block-diagonal-structure-of-matrix-by-reordering2012-12-16

1 Answers 1