Properties of adjacency matrix of graph with cycle

  • Thread starter asja
  • Start date
  • #1
asja
4
0
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.
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,734
8,148
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 K2:
##\begin{pmatrix} 1&-1\\-1&1\end{pmatrix}##
 
  • #3
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
2021 Award
5,331
1,279
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.
 
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
38,734
8,148
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 K2. 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.
 

Suggested for: Properties of adjacency matrix of graph with cycle

Replies
5
Views
1K
  • Last Post
Replies
9
Views
888
  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
13
Views
646
Replies
1
Views
1K
  • Last Post
Replies
7
Views
2K
Replies
4
Views
3K
  • Last Post
Replies
1
Views
184
Replies
36
Views
1K
Replies
7
Views
489
Top