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... :-)