Permutation on matrix to fill main diagonal with non-zero values

Question

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.

Answer 1

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.