Properties of adjacency matrix of graph with cycle

asja · Dec 14, 2009

Let A be the adjacency matrix of some graph G. I am aware that A^n
counts paths of length n between vertices of G, and that for graphs
without cycles and non-singular A, (I-A)^-1 counts the total number of
paths between vertices of G (correct me if any of this is wrong).This
is a very limited class of graph however and I was wondering whether
there is any useful information at all that can be obtained from the
matrix (I-A)^-1 when A is non-singular and G contains a cycle (from
the entries, determinant, etc.)? To take this further, what about if
the matrix is singular? Is there any information that can be extracted
other than counting paths of length n for each n?
Thanks for any information.

haruspex · Jul 9, 2022

asja said:

for graphs
without cycles and non-singular A, (I-A)^-1 counts the total number of
paths between vertices of G

Why do we need A non-singular? We certainly need I-A non-singular. E.g. for a null graph A is singular but (I-A)^-1-I correctly gives zero paths for each pair.
And presumably this is for directed graphs without cycles; otherwise it seems it is going to count bouncing back and forth between two adjacent vertices as an infinite number of paths of even length.
I would think I-A is non-singular if and only if it is a directed graph without cycles. E.g. for a simple directed triangle on three vertices:
##\begin{pmatrix} 1&-1&0\\0&1&-1\\-1&0&1\end{pmatrix}##
is indeed singular, and likewise for K₂:
##\begin{pmatrix} 1&-1\\-1&1\end{pmatrix}##

Office_Shredder · Jul 10, 2022

A hacks thing you can do, is instead of writing 1, write ##1-\epsilon## in the adjacency matrix
Then each entry of ##A^n## is ##k(1-\epsilon)^n## where ##k## is the number of paths of length ##n##. As long as the number of paths doesn't grow exponentially in n this sum should converge. Even if it does grow exponentially, you can just pick ##\epsilon## close to 1. It feels like the output of this might be useful for certain types of analysis, I'm not sure.

haruspex · Jul 10, 2022

Office_Shredder said:

A hacks thing you can do, is instead of writing 1, write ##1-\epsilon## in the adjacency matrix
Then each entry of ##A^n## is ##k(1-\epsilon)^n## where ##k## is the number of paths of length ##n##. As long as the number of paths doesn't grow exponentially in n this sum should converge. Even if it does grow exponentially, you can just pick ##\epsilon## close to 1. It feels like the output of this might be useful for certain types of analysis, I'm not sure.

I just tried that for K₂. It produces
##(I-A)^{-1}=\frac 1{\epsilon(2-\epsilon)}\begin{pmatrix} 1&\epsilon-1\\\epsilon-1&1\end{pmatrix}##
The off diagonal terms are negative. Can’t think of any useful interpretation.

Properties of adjacency matrix of graph with cycle

What is an adjacency matrix?

How is an adjacency matrix used to represent a graph with a cycle?

What are the properties of an adjacency matrix of a graph with a cycle?

Can an adjacency matrix of a graph with a cycle have all 0s?

How can the adjacency matrix of a graph with a cycle be used in practical applications?

Similar threads

Hot Threads

Recent Insights