Questions tagged [adjacency-matrices]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
20 views

upper band for the eigenvalue-distance from an eigenvalue regarding its eigenvector extension, in the adjacency matrix of a local graph?

Background: Suppose we have a system in which an electron can hop locally on this lattice. Here locally means that the electron can hop up to a short distance. We can make an energy spectrum that ...
0 votes
0 answers
55 views

Show that two matrices are strongly shift equivalent

The following question is from Introduction to dynamical systems, written by Michael Brin and Garrett Stuclk. Given two non-negative integer square matrices $A, B$, we say $A, B$ are elementarily ...
0 votes
0 answers
81 views

Does the following hermitian matrix represent the adjacency matrix of the Rubik's cube?

The Rubik's cube can be generated with quarter-turn clockwise/counterclockwise twists of each of the front, back, left, right, up, and down faces: $$\langle F_1,B_1,L_1,R_1,U_1,D_1,F_3,B_3,L_3,R_3,U_3,...
  • 1,615
2 votes
1 answer
276 views

Solution to the sum of k-step path lengths between node pairs in directed weighted graphs

In a non weighted graph, the adjacency matrix ($A$) raised to the power $k$ will return the number of k-step paths between nodes $i$ and $j$ at the entry $a_{ij}$. Is there an equivalent for weighted ...
2 votes
0 answers
44 views

Formulas to determine the value of graph energy with addition or deletion of edges

If $G$ is a graph, then the graph energy of $G$ denoted by $E(G)$ is defined as the sum of absolute values of eigenvalues of the adjacency matrix of $G$. It is known that $E(G)\geq E(G-v)$, where $ ...
  • 203
4 votes
0 answers
309 views

Computing adjacency matrix eigenvalues by counting closed walks

Let $G$ be a finite undirected graph. A closed walk in $G$ is a walk from any vertex of $G$ to itself. It is relatively straightforward to show that the total number of closed walks of length $k$ in $...
  • 19.8k
24 votes
6 answers
1k views

Factorization of the characteristic polynomial of the adjacency matrix of a graph

Let $G$ be a regular graph of valence $d$ with finitely many vertices, let $A_G$ be its adjacency matrix, and let $$P_G(X)=\det(X-A_G)\in\mathbb{Z}[X]$$ be the adjacency polynomial of $G$, i.e., the ...
10 votes
1 answer
1k views

Eigenvalues of the complement of a graph

Let $A$ and $\widetilde A$ be the adjacency matrices of a graph $G$ and of its complement, respectively. Is there any relation between the eigenvalues of $A + \widetilde A$ and the eigenvalues of $A$ ...
  • 1,179
4 votes
1 answer
141 views

Digraphs with unique walk of length $k$ between any two vertices

Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices. Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $...
3 votes
1 answer
134 views

Traces and closed walks that do not close before their time

Let $A$ be the adjacency matrix of a graph. Then, as is well-known and trivial to show, $\mathrm{Tr} A^k$ equals the number of closed walks of length $k$. Is there a similar way to express (a) the ...
  • 17.9k
1 vote
1 answer
483 views

Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]

If so, could you provide examples and specify the conditions under which this occurs? Thank you in advance
2 votes
1 answer
238 views

Leading eigenvector value problem as an optimisation problem for asymmetric matrices

As noted in 1806.05647, given a symmetric matrix $A$, the leading eigenvector value problem (LEVP) $$Av = \lambda v,$$ where $A = A^T \in \mathbb{R}^{n \times n}$, $\lambda$ is the largest ...
0 votes
1 answer
656 views

Significance of the Eigenvalues of the adjacency matrix of a weighted di-graph

I'm currently running a simulation on a bunch of randomly generated points, each with two randomly selected 'partners' from the set of points. In the simulation the points try to move such that they ...
  • 3
2 votes
2 answers
211 views

Adjacency matrix of total graph

Is there a nice way of relating the adjacency, incidence , Laplacian matrices and other matrices associated to a graph of a total graph with its original graph, or, say, at least relating that of the ...
  • 1,765
5 votes
1 answer
360 views

Determining the primitive order of a binary matrix

Let ${\bf A}_n$ be an $2n \times 2n$ matrix that is defined as follows $$ {\bf A}_n=\left( \begin{array}{c} 0&0&\cdots&0&0&0&0&1&1\\ 0&0&\cdots&0&0&...
  • 315
2 votes
1 answer
255 views

When does a row standardized adjacency matrix have a real spectrum?

A colleague in spatial statistics was looking at a map with about 600 regions. For the application she's considering, the induced adjacency matrix had some undesirable properties (where two regions ...
  • 4,441
3 votes
1 answer
688 views

Finding an adjacency matrix whose cube's diagonal is equal to a given vector

How can I find all binary matrices $A$ such that $A^3$ is a non-negative, integer square matrix and $$\mbox{diag}\left(A^3\right)=b$$ for some given vector $b$? Is there a way to characterize all ...
  • 451
10 votes
1 answer
528 views

is it possible to have two non-isomorphic non-regular graphs with the same adjacent spectrum and the same laplacian spectrum?

For two regular graphs $G$ and $H$, it is possible for them to share the same adjacent spectrum and the same laplacian spectrum. While, on the other hand, is it possible to have two non-regular graphs ...
  • 103
1 vote
0 answers
104 views

Primitivity of $AA^\top$

Let $A\in\mathbb{R}^{n\times n}$ be a non-negative and irreducible matrix. Consider $B:=AA^\top$. It can be proved (I can post a proof if needed) that the following condition is necessary and ...
  • 2,662
2 votes
0 answers
144 views

Which functions preserve the connectivity of graphs/components?

I am somewhat stuck working on an issue and would really love some guidance. I will state the problem, my current state and what led to it in case the solution lies beyond where I was looking The ...
  • 21
1 vote
2 answers
153 views

Is there a name for this operation on graphs - e.g. duplication, Kronecker product of graphs?

I am revising a paper where one of the operations performed on a undirected graph with no loops, is to take each vertex, and split it into two vertices, and take each edge and replace it with 4 edges: ...
  • 129
-3 votes
1 answer
319 views

adjacency matrix of random geometric graphs [closed]

Consider a graph with N nodes. All nodes are distributed as a Poisson point process with density of λ in a L*L area. There is an edge between two nodes if and only if the distance between them is less ...
  • 35
1 vote
1 answer
226 views

power bounded adjacency matrices

A bounded linear operator $T$ on a Banach space $X$ is called power bounded if $\|T^k\|\le M$ for some $M>0$ and all $k\in \mathbb N$. A classical result of Lorch says that if $X$ is reflexive, ...