Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Rearranging a matrix to get the minimum diagonal

  1. Jan 26, 2012 #1
    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?

  2. jcsd
  3. Jan 26, 2012 #2
    if you change rows and the corresponding columns, the same elements remain on the diagonal, don't they?
  4. Jan 26, 2012 #3
    One can change rows and columns independently.
  5. Jan 26, 2012 #4
    Define "smallest elements"!
  6. Jan 26, 2012 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
  7. Jan 27, 2012 #6
    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).
  8. Jan 27, 2012 #7
    My question is this: Which one of these sets is "smaller":
    {1, 4, 6}, or {2, 3, 6}
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook