# Anyone knows a transformation that can lump non-zero values in a matrix together?

Suppose you have a matrix that contains a lot zeros (like spare matrix). Is there any known transformation that can gather non-zero values (e.g. into a corner of the matrix)?I am not sure but I think such transformation is very likely to be non-linear.

There is a naïve transformation can be used as an example of the intention (however it does not well achieve the above objective). You can count the number of zeros of each row and rearrange rows by those counts in an ascending order. This can be done by multiplying a corresponding permutation matrix on the left. Then you can count the number of zeros of each column and do the same thing -- rearrange the columns by those counts in an ascending order.

After rearrangement of both rows and columns, a sparse matrix would approximate a diagonal block matrix, as shown below, with blue color meaning 0.

However, I am asking if there is any transformation that can lump most non-zero values into approximately one block, rather than a diagonal block.

It would be greatly appreciated if someone could help provide some hint or reference.

• What would you expect for the $3\times 3$ identity matrix if such transformation exists? – Jack Dec 7 '16 at 19:39
• @Jack Thanks for your comment. A good result can be like $\left( {\begin{array}{*{20}{c}} 1&1&0 \\ 1&0&0 \\ 0&0&0 \end{array}} \right)$. It is best that there should also be a way to reverse the transformation. The transformation and its reverse can be approximate. – Ralph B. Dec 7 '16 at 21:20

Given an $n\times n$ matrix $(a_{ij})$, one can write it as a $1\times n^2$ vector: $$a=(a_{11},a_{21},a_{12},a_{31},a_{22},a_{13},\cdots,a_{nn}).$$ Then you can use a combination of permutations to put everything nonzero to the "left" of this vector and then pull it back to the matrix form.