Questions tagged [adjacency-matrix]

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal.

Filter by
Sorted by
Tagged with
1 vote
0 answers
14 views

Find crossing edges in a graph from adjacency matrix

Is there any way to find the crossing edges from the adjacency matrix of a given undirected graph $G=(V,E)$? For example in the following graph ( actually a tree in this specific example) $e_{3, 13}$ ...
user avatar
0 votes
0 answers
27 views

Powers of adjacent matrix and the path length

I'm really struggling with a question in linear algebra that is associated with graph theory but I honestly have no idea how I should go about it. Graph $G=(E,K)$ consists of a finite set of vertices ...
user avatar
  • 496
1 vote
0 answers
11 views

Check if adjacency tensor of hypergraph is irreducible

Consider an m-uniform, n-dimensional hypergraph. It's adjacency tensor is an $\overbrace{(n \times n \times ... \times n)}^{m}$ -dimensional tensor $T$. As shown in [1], to calculate the $(H)$-...
user avatar
  • 279
0 votes
0 answers
14 views

Applications of second largest eigenvalue in absolute value

I'm reading a paper where someone attempts to find the second largest eigenvalue in absolute value of the adjacency matrix of a distance-regular graph. That made me wonder: what is this specific ...
user avatar
0 votes
1 answer
288 views

Graph theory with trees and adjacency matrix [closed]

For $n \in \Bbb N$ we define the set $\Bbb Z_n = \{1, 2, \ldots , n - 1\}$ and on this set we define the modular product as follows: For $x, y, z \in \Bbb Z_n : (x\cdot y = z) ⇔ (x\cdot y \equiv z \...
user avatar
  • 1
0 votes
0 answers
104 views

Meaning of eigenvalues of an adjacency matrix

I know the eigen vector of a matrix transformation is the vector that turns it into a scalar transformation. But in the context of a adjacency matrix and in a graph, what does the eigen vector or ...
user avatar
1 vote
1 answer
42 views

Formula for counting the number of subgraphs in a given graph $G$

I want to find a formula for counting the number of subgraphs in a given graph $G$ with adjacency matrix $A$. The subgraph I want to count its number of occurences is of the structure above. So my ...
user avatar
  • 123
0 votes
1 answer
6 views

How can one efficiently group the nodes of a directed acyclic graph to make collective nodes?

The adjacency matrix $A$ of the transitive closure of a directed acyclic graph can have a `checkerboard' pattern like \begin{equation} A = \begin{pmatrix} 0 & ? & ? & ? & {\bf a} &...
user avatar
0 votes
0 answers
27 views

Is there anything special about the singular values of a zero-diagonal matrix?

The singular values and the related SVD are important and useful in many fields. When we study the adjacency matrix $A$ of a simple (weighted) graph, we have that $A$ is zero-diagonal and symmetric. ...
user avatar
  • 638
0 votes
0 answers
27 views

Adjacency Matrix after Conway Operations on Graphs

Given a cubic graph $G$, with $v$ vertices, $e$ edges and $f$ faces (embedded on an orientable surface with genus $g$, not sure if this is important). Let $A_G$ denote its adjacency matrix. Let's ...
user avatar
  • 17.8k
3 votes
0 answers
104 views

Visual analysis of adjacency matrices

Given a simple graph $G$ and its adjacency matrix $A$, one may naturally consider the following graph $A_G$: $V(A_G)=\{(i,j):i<j,a_{i,j}=1\}$ $E(A_G)=\{\{(i,j),(k,l)\}\in2^{V(A_G)}:(|i-k|=1\text{ ...
user avatar
  • 331
0 votes
0 answers
54 views

Relationship between square of adjacency matrix and Laplacian matrix

Consider a simple undirected graph with $n$ elements. Let $A$ be the adjacency matrix of the graph with elements $a_{ij}$. Let $L$ be the graph Laplacian with $L=D-A$ where $D$ is the degree matrix. ...
user avatar
  • 71
1 vote
0 answers
83 views

Number of k-cycles from an adjacency matrix of a graph

Let $G(V,E)$ be a finite undirected graph with an adjacency matrix $A$. As far as I know it holds that that $A^k_{ii}$ gives us the number of walks starting and ending at vertex $i$ and having length $...
user avatar
2 votes
3 answers
475 views

Why isn't this graph bipartite?

This is a very silly question but I can't seem to figure it out. Let $G$ be the graph with 6 nodes and 3 edges where 1 is connected to 4, 2 to 5 and 3 to 6. Le $ U = \{1,2,3\}$ and $V=\{4,5,6\}$. Then ...
user avatar
1 vote
0 answers
58 views

Eigenvector of a $1D$ Path/Grid Graph

Let $A$ be the $N\times N$ adjacency matrix of a 1D grid graph (also called path graph?) of size $N\times 1$. this can be seen as a discrete line of $N$ connected vertices: I know that the ...
user avatar
  • 43
1 vote
1 answer
48 views

Eigenvalues for block-tridiagonal adjacency matrix with "rays"

I'm looking for closed-form expressions of the eigenvalues of the following adjacency matrix: \begin{equation} M = \begin{pmatrix} A & B^T & 0\\ B & A & C^T\\ 0 & C & A \end{...
user avatar
  • 41
1 vote
0 answers
29 views

Sum of pairwise distance after applying normalized adjacency matrix to values

I have $N$ values defined on a graph with $N$ nodes called $x_i$ for node $i$. I define the pairwise distance between these values as follow: $D(x) = \frac{1}{2}\sum_{i,j}a_{ij}||x_i - x_j||_2 $ Now, ...
user avatar
0 votes
0 answers
25 views

Adjacency Matrix questions

Bit of a weird one and hopefully a simple thing I missed when reading my text but here goes. So I have been studying Adjacency Matrix and how to construct graphs and graphs to AMs. Now its all been ...
user avatar
  • 29
0 votes
0 answers
21 views

Adjacency Matrix of d-regular graph [duplicate]

"If 𝐴 is the adjacency matrix of a 𝑑-regular graph, then any row of 𝐴 contains exactly 𝑑 1’s. Thus, the vector 1𝑛=1,1,…,1 is an eigenvector of 𝐴 with eigenvalue 𝑑." How do we know ...
user avatar
1 vote
0 answers
46 views

Reordering vertices of a graph to make the adjacency matrix a block matrix with band-shaped blocks

Let $G = (V, E)$ be a sparse oriented graph with $n$ vertices (i.e. no loops, no multi-edges, about 1-5% of all possible $n\cdot(n-1)/2$ edges are present). The value of $n$ is about $100$. Let $A$ be ...
user avatar
2 votes
2 answers
238 views

Spectral radius of a graph

I researched about the spectral radius and was confused. There are two definitions. The spectral radius of a finite graph is defined to be the spectral radius of its adjacency matrix. the spectral ...
user avatar
  • 361
1 vote
1 answer
454 views

Obtaining the degree matrix from the adjacency matrix

I was unable to find a mathematical operation for obtaining the degree matrix from the adjacency matrix of a given graph. For a graph $G = (V,E)$, let $A$ be the adjacency matrix of $G$ and let $D \in ...
user avatar
  • 153
1 vote
0 answers
40 views

Normalize an adjacency matrix twice

I am working on a graph clustering problem and i've seen that applying two consecutive normalizations on the adjacency matrix gives much better performance than when applying a single one. I first ...
user avatar
  • 55
2 votes
1 answer
64 views

What is the number of possible simple directed graphs of $n$ elements without 2-cycles and self-loops?

Let $A$ be the adjacency matrix of a graph with $n$ vertices. Let $a_{ij}$ denote the entry in the $i$-th row and $j$-th column. For a given $n$, how can we compute the number of possible networks, $f(...
user avatar
2 votes
0 answers
82 views

Interpretation of Symmetric Normalised Weighted Adjacency Matrix in GCN

Yann Dubois explained very well about the "Interpretation of Symmetric Normalised Graph Adjacency Matrix?". He defined that adjacency matrix  can be weighted. He also defined that D̂ is ...
user avatar
0 votes
1 answer
147 views

Sum of adjacency matrices in connected graph G

If G is connected graph, then show that there is no $0$ element in matrix $A+A^2+A^3+\cdots+A^{n-1}$ where A is adjacency matrix of G, and n number of vertices. If we are looking at element on ...
user avatar
  • 503
1 vote
1 answer
31 views

There are at most three walks of length 4 between any two distinct vertices of the graph G?

The following adjacency matrix given by A represents a graph called G: $$A = \left[ \begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ ...
user avatar
4 votes
2 answers
177 views

Upper bound on the largest eigenvalue of a simple graph

Let $X$ be a simple graph with $n$ vertices and $e$ edges and let $\lambda$ be an eigenvalue of $X$. Show that $$ |\lambda| \leq \sqrt\frac{2e(n-1)}{n}$$ which is equivalent to $$n\lambda^{2} \leq 2e(...
user avatar
  • 297
5 votes
1 answer
108 views

What is a non binary adjacency Matrix?

I am going through the implementation of a graph convolutional neural network. I came across a non-binary adjacency matrix in the case of a directed graph. The particular issue is discussed here in ...
user avatar
  • 53
1 vote
1 answer
64 views

Eigenvalue of d regular graph being 1

Let G be a (2d-1) regular graph, and $(X_1,X_2)$ be a partition of vertices of G s.t. if $v\in X_i$, then $|N(v) \cap X_i|=d$. Prove that one is an eigenvalue of the adjacency matrix of G. Since 𝐺 ...
user avatar
  • 1,715
2 votes
2 answers
88 views

How to find the determinant of a scaled adjacency matrix?

If $A$ is a $3 \times 3$ matrix and $\det(A) = -1$, what would $\det(\frac{1}{3} \operatorname{adj}(3A))$ be? I know that $\det(\operatorname{adj}(A)) = \det(A)^{n-1}$, so I guessed it would be $(27 \...
user avatar
1 vote
1 answer
61 views

Examples of graph problems that are $\Omega(n^2)$ when using adjacency matrix representation.

I recently learned about this very nice way to prove that given a simple undirected graph $G = (V, E)$, given as an adjacency matrix $A$, any algorithm deciding if $G$ is Hamiltonian is $\Omega(n^2)$. ...
user avatar
  • 571
0 votes
1 answer
77 views

Range of eigenvalue in a normalized adjacency matrix

Assuming that $G$ is a simple and undirected graph, no isolated node and let $A$ be the adjacency matrix of $G$. My question is that, what is the range for the eigenvalue of the following normalized ...
user avatar
  • 191
0 votes
1 answer
66 views

Let G be a graph with connected components, give adjacency matrix.

Let G be a graph with connected components $G_1,\: \ldots ,\: G_l$, and $V(G_1)=\{u_1^1,\: u_2^1,\: \ldots ,\: u_{n_1}^1\},\: V(G_l)=\{u_1^l,\: u_2^l,\: \ldots ,\: u_{n_l}^l\}$ their set of vertices, ...
user avatar
  • 282
2 votes
1 answer
71 views

Checking if two digraphs are isomorphic from their adjacency matrices

Wikipedia says that, given digraphs $ G_1 $ and $ G_2 $ whose adjacency matrices are $ A_1 $ and $ A_2 $ respectively, $ G_1 $ and $ G_2 $ are isomorphic if and only if there exists a permutation ...
user avatar
0 votes
2 answers
211 views

Largest eigenvalue of a simple graph

Let $\Gamma$ be a simple graph with $n$ vertices, $e$ edges and largest eigenvalue $\lambda_{max}$. Show that $\lambda_{max} = \frac{2e}{n}$ iff $\Gamma$ is regular. I've already shown the if part, ...
user avatar
  • 297
1 vote
2 answers
59 views

Prove if $\operatorname{adj}(A) = O$ then $\operatorname{rank}A \leq n-2$

Prove if $\operatorname{adj}(A) =0$, then $\operatorname{rank}A \leq n-2$ My initial idea is to setup an induction. Base case $A \in M_{2×2}$ which obviously implies that $A = [O]_{2×2} \rightarrow \...
user avatar
0 votes
1 answer
211 views

Number of labelled spanning trees in the following graph.

Hi, I have this question in one of my assignments. Normally I would use an adjacency matrix (a very big one) to solve these kinds of questions but the hint makes me believe the professor wants me to ...
user avatar
  • 69
0 votes
2 answers
260 views

Power of adjacency matrix

What does ij element of the k-th power of adjacency matrix for a directed graph, i.e. A^k represent: number of paths with exact k length or number of paths with length k or less than k from i to j?
user avatar
1 vote
0 answers
21 views

Check if there will be graph represented by incidence matrix, hamilton? Draw the graph.

My task is: "Check if there will be graph represented by incidence matrix and is it hamilton graph? Draw the graph." Matix image $$ \pmatrix{0&1&0&1&0&1&1&0\\ 1&...
user avatar
  • 11
2 votes
0 answers
62 views

Graphs with maximum and minimum Graph Energies

Given a graph $G$ with $n$ vertices, if its adjacency matrix $A$ has eigenvalues $\lambda_1 \geq \lambda_2 \geq . . . \geq \lambda_n$ then the energy is defined as: $$E(G) =\sum_{i=1}^{n} |\lambda_i|.$...
user avatar
  • 1,174
1 vote
1 answer
156 views

If $A$ is the adjacency matrix of a graph $G$, and $A^3$ has a $1$ on the diagonal, then $G$ has a triangle

If we have a graph $G$, and $A$ the adjacency matrix that represents $G$, how can we proof the diagonal of $A^3$ having a $1$ implies that there is a triangle in $G$? I try to use the theorem that $A$...
user avatar
1 vote
1 answer
24 views

Graph neighbourhood matrix in which each pair of rows has at least one common column full of ones

I am trying to understand a particular method of moments estimation algorithm. If you are interested in that, see this for more detailed description. Long story short, I am trying to understand what ...
user avatar
  • 1,379
1 vote
0 answers
147 views

trace of positive integer power of adjacency matrix

I have been trying to calculate cycles cycles in undirected graphs and I have read this article which has really helped but I'm still seeking a shorter way to calculate matrix power traces(it is ...
user avatar
  • 154
2 votes
1 answer
328 views

Having number of walks between two vertices how to calculate paths

I know that we can calculate number of walks with n length between two vertices of an undirected graph by calculating the nth power of the adjancy matrix but what if you want to avoid repetition in ...
user avatar
  • 154
0 votes
1 answer
64 views

Why do diagonal entries of odd potencies of adjacency matrices of forests sum up to zero?

I came across the statement that the trace (sum of diagonal entries) of an odd potency of an adjacency matrix of a forest is always zero. I have tried out a few options and it seems to be correct for ...
user avatar
  • 135
0 votes
1 answer
164 views

How is a matrix connected to a grid?

I have a hard time finding information about and understanding how a matrix (adjacency matrix) is connected to a grid used in numerical analysis. What would the nodes be and are the matrix weighted or ...
user avatar
1 vote
1 answer
1k views

What is the transitive closure of the following digraph?

What is the transitive closure of the following digraph ? To find reach-ability matrix and adjacency matrix. My approach: The adjacency matrix is \begin{bmatrix} 0 &1 &0 &0 \\ 0 & 0&...
user avatar
  • 9,597
1 vote
1 answer
139 views

Degree Matrix of Fully connected graph

https://www.kaggle.com/vipulgandhi/spectral-clustering-detailed-explanation In this blog post about spectral clustering it states that we can just use the Gaussian Kernel directly. "Generally we ...
user avatar
0 votes
1 answer
111 views

Spectrum of a labelled complete graph $K_n$

Suppose, $K_n$ is a complete simple graph with each edge label $k$. Then its adjacency matrix $A(K_n)$ has all the entries zero along the diagonal, and each non-diagonal entries are $k$. What are ...
user avatar
  • 1,174

1
2 3 4 5