Re: re: Structure of the matrix inverse

On Saturday, Apr 12, 2003, at 05:19 Asia/Jerusalem, John Gilbert wrote:
>
> If A has an inverse, then there exists a (row)
> permutation P such that P*A has nonzero diagonal;
> you can use the transitive closure of P*A to
> predict the structure of inv(A) = inv(P*A)*P.
>

Probably obvious:

You find P using a maximum matching algorithm on the
bipartite graph that represents A (as Edmond suspected). If the
maximum matching is perfect (all rows are matched), you get P,
otherwise, no such P exists.

Alex Pothen has a Fortran 77 code for finding maximum matchings
in bipartite graphs, which John and I have used.

Sivan