I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled with non-zero values. My matrices represent a set of linear equations and there is no problem to use permutations between rows and columns of my matrix to get a zero-less diagonal.I do know that the matrix is non-singular so such a permutation must exist (otherwise the determinant would be null), however I searched on the internet and wasn't able to find anything relevant.Here is an example were 0 denotes an null value and 1 any non-zero value.I numerated the rows, the permutation only changes the rows:(row)    (matrix)        (matrix, blanks are zeros)original:01    1000011110000000    |1    1111       |02    0100010001110000    | 1   1   111    |03    0010001001001100    |  1   1  1  11  |04    0001000100101010    |   1   1  1 1 1 |05    0000100010010110    |    1   1  1 11 |06    0000000000001110    |            111 |07    0000000000110010    |          11  1 |08    0000000001010100    |         1 1 1  |09    0000000110000010    |       11     1 |10    0000001010000100    |      1 1    1  |11    0000010010010000    |     1  1  1    |12    0001100000000010    |   11         1 |13    0010100000000100    |  1 1        1  |14    0100100000010000    | 1  1      1    |15    1000100010000000    |1   1   1       |16    1000000000000001    |1              1|permutated:01    1000011110000000    |1    1111       |02    0100010001110000    | 1   1   111    |03    0010001001001100    |  1   1  1  11  |04    0001000100101010    |   1   1  1 1 1 |05    0000100010010110    |    1   1  1 11 |11    0000010010010000    |     1  1  1    |10    0000001010000100    |      1 1    1  |09    0000000110000010    |       11     1 |15    1000100010000000    |1   1   1       |08    0000000001010100    |         1 1 1  |07    0000000000110010    |          11  1 |14    0100100000010000    | 1  1      1    |06    0000000000001110    |            111 |13    0010100000000100    |  1 1        1  |12    0001100000000010    |   11         1 |16    1000000000000001    |1              1|Is there a smart way to perform those row/column permutations in order to get a main diagonal without zeros ? I am almost certain that there is a way to express this problem as a path-finding problem (visit all the columns once and only if the current line of a column is a non-zero value) but wasn't very successful.
Permutation on matrix to fill main diagonal with non-zero values
graph theory;matrices;linear algebra;permutations;sparse matrices
You can use bipartite matching for that.Nodes corresponding to rows in one set, nodes corresponding to columns in the other set. A row has an edge to every column in which it has a 1. If the maximum matching has size n, every row is matched up with a corresponding column and the matching gives the order. The index of the column that a row is matched up with will be its new position.