Sort matrix elements around the diagonal

Question

I am looking for an algorithm that can sort the rows of a matrix so that the elements will cumulate around the diagonal. I will have a square matrix (around 80 rows/ columns) containing only the values 0 and 1. There are algorithms that sort the rows in a way that most of the elements with the value 1 are below the diagonal. I need an algorithm that sort to minimize the mean distance of the elements to the diagonal. Like so: from:

0 1 0
1 0 1
1 1 0

to:

1 1 0
0 1 0
1 0 1

Since I am not familiar with this topic I hope that someone can help me. I am not looking for a complete solution. The name of such algorithm if it exists or a pseudo code would be sufficient.

Thanks a lot!

SaiBot SaiBot · Accepted Answer · 2018-10-10T09:24:16

There is probably a more efficient way, but you could treat this problem as an assignment problem (trying to assign each row to a diagonal element).

This can be done in three steps:

1) Create a new matrix M where each entry M(i,j) contains the cost of assigning row i of your input matrix to the diagonal element j. For your example this matrix will be the following (average distance to the diagonal element):

1   0   1
1   1   1
1  0.5 1.5

Example: M(0,0) = 1 is the average distance when assigning row 0 of the input matrix (0 1 0) to the diagonal element positioned at 0.

2) Run an algorithm to find the best assignment (e.g., hungarian algorithm). This will give you an optimal 1:1 matching between rows and columns minimizing the sum of cost in the matrix.

The result will be the elements (0,1), (1,2) and (2,0)

3) Rearrange your input matrix using this knowledge. So

row 0 -> row 1
row 1 -> row 2
row 2 -> row 0

Sort matrix elements around the diagonal

1 Answers