Properties of adjacency matrix of graph with cycle

In summary, the adjacency matrix A of a graph G can be used to count paths of length n between vertices of G. For graphs without cycles and non-singular A, the matrix (I-A)^-1 can be used to count the total number of paths between vertices of G. However, this method is limited to a specific class of graphs. It is unclear if there is any other useful information that can be obtained from the matrix (I-A)^-1 when A is non-singular and G contains a cycle. Additionally, if the matrix is singular, the only information that can be extracted is the number of paths of length n for each n.
  • #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.
 
Physics news on Phys.org
  • #2
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 K2:
##\begin{pmatrix} 1&-1\\-1&1\end{pmatrix}##
 
  • #3
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
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 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.
 

What is an adjacency matrix?

An adjacency matrix is a square matrix that represents the connections between vertices in a graph. It contains information about which vertices are connected and how they are connected.

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

In an adjacency matrix, a cycle is represented by a diagonal line of 1s. This indicates that the vertices are connected in a cyclical manner, with no other vertices connected in between.

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

One property is that the matrix will have at least one row and column with all 1s, representing the cycle. Another property is that the matrix will have at least one pair of non-zero entries that form a closed loop, indicating the cycle. Additionally, the matrix will be symmetric since the graph is undirected.

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

No, an adjacency matrix of a graph with a cycle cannot have all 0s. This would indicate that there are no edges or connections between any of the vertices, which is not possible in a graph with a cycle.

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

An adjacency matrix of a graph with a cycle can be used to determine the shortest path between two vertices in the cycle. It can also be used to visualize and analyze the connectivity of a network or system, such as in transportation or social networks.

Similar threads

Replies
4
Views
1K
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
746
  • Engineering and Comp Sci Homework Help
Replies
4
Views
993
Replies
1
Views
1K
  • Differential Equations
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
Back
Top