2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice idea, I'll try it and then I'll validate your answer. $\endgroup$ – Demurgos May 31 '16 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.