Rearranging a matrix to get the minimum diagonal

[Dows]

Dear all,

I have the following problem: I have a symmetric (non sparse) matrix, and I want to find the permutation of columns and rows that lead to have the smaller numbers in the diagonal.

Anyone has a clue on how to solve efficiently this kind of problems?

Thanks!

 

[Dickfore]

if you change rows and the corresponding columns, the same elements remain on the diagonal, don't they?

 

[Dows]

One can change rows and columns independently.

 

[Dickfore]

Define "smallest elements"!

 

[AlephZero]

Define "smallest elements"!

It doesn't really matter what property the OP means, provided there is some way to identify the elements you want to put on the diagonal.

This has no solution in general. For example suppose you have a 4x4 matrix and the 4 smallest elements are in the the top left 2x2 submatrix. Any row or column interchange leaves exactly 2 rows and 2 columns containing the smallest values, so you can never separate them onto the diagonal elements of 4 separate rows.

So I conjecture there is no solution unless there is exactly one smallest element in each row and each column, in which case the solution is simple - just permute either the rows or the columns to put the smallest elements on the diagonal. This will destroy the symmetry of the matrix, but the OP said interchanging rows and columns independently was allowed.

 

[Dows]

I tried to explain a smaller problem saying that the matrix is symmetric but maybe it's not helping too much.

So, my specific problem is:
- I have a distance matrix of two sets of elements. The two sets can have different number of elements, so the matrix is only square and symmetric when you are comparing a set with itself.

- I want to stablish a relation of similarity (pairings) between the elements in both sets, so I want to find the permutation of rows and columns that leads to have the smaller distances in the diagonal (minimum).

 

[Dickfore]

My question is this: Which one of these sets is "smaller":
{1, 4, 6}, or {2, 3, 6}