Getting most non-zero values near diagonal of matrix

[Nask]

When I have a matrix like this:

0 0 1 0
0 1 0 0
1 0 0 1
0 0 1 1
0 0 0 1

I can get most non zero values in the centre changing only the order of rows

1 0 0 1
0 1 0 0
0 0 1 0
0 0 1 1
0 0 0 1

Probably when I am allowed to change the order of columns and rows at the same time I will even get a better result, getting rid of the 1 in the top-right corner.

Is there an algorithm that can be used to optimise a n by m matrix, having most of its non zero values near its diagonal?

Background:
The columns are the different client orders, the rows the different articles. I like to divide the clients that require a simular set of articles in different groups. The real amount of clients is about 500, articles about 2500, so I need an algorithm that also works for larger matrices (calculation has to be made each day upfront).




Thanks,

Nasko

 

[Bill Simpson]

Perhaps Jordan Normal form?

http://en.wikipedia.org/wiki/Jordan_normal_form

 

[AlephZero]

The problem of how to find the absolutely "optimal" ordering for a large matrix, in a short enough time to be useful, is an unsolved problem.

There are many approximate methods that will produce "good" but not "perfect" orderings, ranging from quick single-pass methods to complex iterative algorithms. Search for matrix bandwith or profile reduction algorithms used in solving sparse linear equations.

Which method works best depends very much on the "shape" of the matrix. Often several different methods are tried, and the best result is used.

Note: the standard methods only work with square matrices. It is not quite clear what you mean by the "diagonal" of a rectangular matrix. But you should be able to use the basic ideas behind the methods to get what you want.

 

[Nask]

Thanks for both answers. Knowing the term bandwidth reduction helps a lot finding information on internet!


And for the diagonal of a non-square matix.. just the line from the top left to the bottem right... :-)

 

[blue_raver22]

I can suggest a few different approaches that can be used to optimize a matrix in the way you described.

1. Sorting by Diagonal Elements: One approach is to sort the rows and columns of the matrix based on the values of their diagonal elements. This will bring the largest values towards the center of the matrix, making the non-zero values more concentrated near the diagonal. This approach is simple and can be easily implemented for larger matrices.

2. Clustering: Another approach is to use clustering algorithms to group similar rows and columns together. This will help in identifying patterns and similarities in the data, and arranging them in a way that maximizes the non-zero values near the diagonal. This approach may require some initial data analysis and may be more complex to implement, but it can provide better results for larger matrices.

3. Matrix Factorization: Matrix factorization techniques, such as Singular Value Decomposition (SVD) or Non-negative Matrix Factorization (NMF), can also be used to optimize a matrix. These techniques break down a matrix into smaller matrices that represent its underlying structure. By rearranging these smaller matrices, the non-zero values can be concentrated near the diagonal. However, these techniques may not be suitable for larger matrices as they can be computationally intensive.

In conclusion, there are several methods that can be used to optimize a matrix and achieve a concentration of non-zero values near the diagonal. The choice of which approach to use will depend on the specific characteristics of your data and the level of complexity and computation that you are willing to invest. I hope this helps.