Matrices and inverse Matrices in Python

Question

For a project that I am doing, I decompose a graph that I created using NetworkX into an adjacency matrix using the NetworkX adj_matrix() function. However, one of the problems that I have come across is that every single graph that I decompose gives me the following error when I try to find the inverse of the matrix.

str: Traceback (most recent call last):
  File "C:\eclipse\plugins\org.python.pydev.debug_1.4.7.2843\pysrc\pydevd_resolver.py", line 179, in _getPyDictionary
    attr = getattr(var, n)
  File "C:\Python26\lib\site-packages\numpy\core\defmatrix.py", line 519, in getI
    return asmatrix(func(self))
  File "C:\Python26\lib\site-packages\numpy\linalg\linalg.py", line 355, in inv
    return wrap(solve(a, identity(a.shape[0], dtype=a.dtype)))
  File "C:\Python26\lib\site-packages\numpy\linalg\linalg.py", line 254, in solve
    raise LinAlgError, 'Singular matrix'
LinAlgError: Singular matrix

I tried generating adjacency matrices from 5 different graphs and all of them produced the same error when I tried to find the inverse of the adjacency matrix. The question that I pose is whether there is any way to go from NetworkX graph to matrix. What is my best course of action from here? I realize there are other questions pertaining to matrix inverses, but mine is somewhat limited by the fact that I need the graph adjacency matrix.

Answer 1

Adjacency matrices are not always invertible. There are papers on this subject; I'm not sure whether there is any simple characterization of the corresponding graphs. A pragmatic approach would be to catch the LinAlgError exception in your code (try… except…), and warn when the adjacency matrix is not invertible (and keep performing your calculations otherwise).

Answer 2

I don't know exactly how networkx produces the adjacency matrix, but there is absolutely no reason for it to be inversible. For example, consider the complete graph (all nodes are connected to every each other), its adacency matrix is full of ones, and the matrix has obviously 0 as an eigenvalue (as soon as the number of nodes is >= 2 of course...). Or the graph with N Nodes and no edges, its adjacency matrix is 0...

What do you want to do ? I never had to consider the inverse of the adjacency matrix, but very often the inverse of I - x A for some (small) value of x. Its inverse is

(I - x A) ^(-1) = I + xA + x^2 A2 + ...

which is inversible for some value of x (in fact, as soon as |x| < max( |1/y| for y in eigenvalues of A) I think)... this is because you consider the number of paths in your graph, but putting some decay in it, so it is summable (Pagerank anyone ?)

Answer 3

are you asking for a method to generate graphs whose adjacency matrices are non-singular? it is no fault of networkx's or numpy's that the graphs you generated have adjacency matrices that do not have inverses.