re: Structure of the matrix inverse

Hi Edmond,

You're right, the transitive closure theorem 
requires the diagonal elements to be nonzero.
(And even then assumes the absence of coincidental 
numeric cancellation, of course).

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.

Cheers,

- John

=============================================================
    John R. Gilbert
    Department of Computer Science
    University of California
    Santa Barbara, CA  93106-5110
    office: Phelps 3220
    phone:  805-893-7512
    fax:    805-893-8553
    dept:   805-893-4321
    cell:   805-448-6438
    email:  [email protected]
    url:    http://www.cs.ucsb.edu/~gilbert
=============================================================

Edmond Chow said:

Hello everyone,

Given a square matrix, the transitive closure of its directed graph
gives the structure of the inverse of the matrix.

This does not seem to work for matrices that have one or more zeros
on the diagonal.  For example, the following two are inverses:

a =
     0     0     0     0     1
     1     0     0     0     0
     0     1     0     0     0
     0     0     1     0     0
     0     0     0     1     0

>> inv(a)
ans =
     0     1     0     0     0
     0     0     1     0     0
     0     0     0     1     0
     0     0     0     0     1
     1     0     0     0     0

Is there a graph description of how to determine the structure of
the inverse in these cases?  I suspect a bipartite graph representation
might be useful, since it can encode whether or not a diagonal
entry exists.

This has application to constructing sparse null-space bases.
Any help would be appreciated.

Thanks!
Edmond




_______________________________________________
Csc mailing list
Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
http://list.odu.edu/listinfo/csc