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.

enter image description here

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.

  • 1
    $\begingroup$ What would you expect for the $3\times 3$ identity matrix if such transformation exists? $\endgroup$ – Jack Dec 7 '16 at 19:39
  • $\begingroup$ @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. $\endgroup$ – Ralph B. Dec 7 '16 at 21:20

"Sparse matrix" is a loose term in numerical analysis and I don't think there is a definition for matrices containing "lots of zeros". One can talk about storage of such matrices and each way of storage can be viewed as a desired mapping.

One possible way maybe as follows.

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.