For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.

learn more… | top users | synonyms

0
votes
1answer
27 views

Spectrum of k-partite graph

For a given undirected graph, it is known that the signless Laplacian $Q=D+W$ is positive semidefinite, where $W$ is the adjacency matrix and $D$ is the degree matrix. In particular, the smallest ...
0
votes
1answer
27 views

graphs with smallest eigenvalue at least -1

Let $G$ be an undirected simple graph and let $A$ be its adjacency matrix. It is easy to see that $A$ is neither positive semidefinite nor negative semidefinite. I would like to know if there are ...
0
votes
1answer
16 views

What Laplacian should we use for spectral clustering?

The second eigenvector of the normalized Laplacian $I-D^{-1}W$ or the symmetric normalized Laplacian $I-D^{-1/2}WD^{-1/2}$ can be used to approximate a minmizer of the normalized cut problem. Which ...
2
votes
0answers
7 views

Can a graph be recovered from its Bonacich centrality vector?

Let $A$ be the adjacency matrix of a directed graph with $n$ vertices and spectral radius $\lambda$. Let $I$ be the $n \times n$ identity matrix and let $e \in \mathbb{R}^n$ be the vector of 1's. For ...
1
vote
0answers
26 views

Spectral radius of perturbed bipartite graphs

I am looking into how perturbation(s) on a bipartite graph affect its spectrum (specifically its spectral radius or largest eigenvalue). Actually I'm not exactly looking into bipartite but the ...
0
votes
0answers
17 views

Sparsifying a weighted complete graph

Sparsifying a graph $G=(V,E)$ using effective resistance method [as described in http://arxiv.org/abs/0803.0929 ], requires the existence of a Laplacian solver which can be used to calculate the ...
3
votes
1answer
29 views

How to perturb an adjacecny matrix in order to have the highest increase in spectral radius?

Let's suppose I have a generic directed graph $G$ and it's adjacency matrix $A$. I can add an arc wherever I want in the graph. (i.e. perturb the matrix A changing a single 0 into a 1). Where should ...
2
votes
0answers
201 views

Is each edge interpreted like a $2$-cycle?

Let $a_k$ a an eigenvalue of the adjacency matrix $A$ of a planar cubic graph with $n$ vertices. For the returning paths without backtracking we get the generating function of ...
1
vote
1answer
268 views

All Ihara $\zeta$ functions for planar $k$-regular graphs with a given set of faces are equivalent

This sounds like a simple piece of math (which got a long story over time, thanks for reading!) and the consequence seems surprising. At least to me. Here it is: It boils down to comparing two ...
0
votes
0answers
8 views

How to prove the relation between the directed Laplacian and the number of strongly connected components?

Let be a weighted digraph G (without loops) and its Laplacian L. How to prove that the multiplicity of the zero eigenvalue associated to L is equal the number of strongly connected components of G?
0
votes
1answer
20 views

Are cospectral/non-cospectral non-isomorphic graphs similar?

Suppose you have two adjacency matrices $A$ and $B$ of cospectral but non-isomorphic graphs. Is there a matrix $Q$ such that $$A=Q^{-1}BQ$$ holds? Note if $A$ and $B$ are not cospectral we cannot ...
2
votes
1answer
5k views

Plotting a one-sided amplitude spectrum

I have a continuous signal $x(t)$ such that $$x(t)=12\cos(6\pi t)+6\cos(24\pi t)+3\cos(30 \pi t)$$ and is asked to sketch a $1$-sided Amplitude Spectrum of the signal $x(t)$ if sampled above the ...
1
vote
0answers
45 views

Semigroup of matrices and expander Cayley graphs

I am interested in proving or disproving that certain Cayley graphs are expander. Let $S$ be the multiplicative semigroup of matrices generated by $A = \left( \begin{array}{cc} a & b \\ 0 & ...
4
votes
0answers
28 views

What does the spectrum of the adjacency matrix of a graph tell you? [duplicate]

I am trying to search for an answer to the following question and I cannot find a straightforward answer. What does the spectrum of the adjacency matrix (set of eigenvalues and their multiplicities) ...
3
votes
1answer
47 views

Trace of hadamard product of adjacency matrices based on eigenvalues

Let $A$ be the adjacency matrix of the simple graph $G_n$. Is there any formula for $\text{trace}(A^3 \circ A^2)$ based on eigenvalues of $A$?
4
votes
0answers
28 views

Multiplicity of 0 eigenvalue of directed graph Laplacian matrix

I am looking for a result (if it exists) for directed graphs relating the multiplicity of 0 eigenvalues of the directed Laplacian matrix. Consider a directed graph ...
0
votes
0answers
10 views

Minimum Degree of Maximally Eigencentral Vertices

In Grassi et al. (2007), they state the following theorem: Let $G(V,E)$ be a connected graph and $A$ its adjacency matrix, with spectral radius $\rho$ and principal eigenvector $x$. Let us ...
0
votes
0answers
26 views

Eigenvalues of graphs

Given an undirected, unweighted graph $G$, let $A_G$ denote the graph's adjacency matrix. I want to understand in what cases there exists negative eigenvalue for $A_G$, for example, any claim of the ...
3
votes
0answers
44 views

sum of the modulus eigenvalues of a matrix A >= B.

Kindly help me to prove/disprove the following statement. Let $A$ be a symmetric matrix of order $n \times n$ with all the diagonal entry equal to $0$, and other non-diagonal entry equal to $k$ ...
0
votes
0answers
5 views

Interpretation of Left Dominant Eigenvector centrality on empty graph

What is the correct interpretation of the centrality measure "left dominant eigenvector" in the case when the matrix is empty? We know that the eigenvalues are all 1, and the eigenvectors are the ...
5
votes
0answers
106 views

Theoretical link between the graph diffusion/heat kernel and spectral clustering

The graph diffusion kernel of a graph is the exponential of its Laplacian $\exp(-\beta L)$ (or a similar expression depending on how you define the kernel). If you have labels on some vertices, you ...
1
vote
0answers
22 views

Probability having a path of length less than a fixed number

A graph $G(V, E)$ is given. For a random pair of nodes $e_1, e_2 \in V$, what is the chance/probability of having a path of size less than $k$ (a fixed number) between $e_1$ and $e_2$ (let's assume ...
2
votes
4answers
192 views

Graphs interpreted as adjacency matrices

Consider a real symmetric matrix. Such a matrix can be considered as an adjacency matrix of a graph, and in fact may be identified with the graph itself. Now consider the equivalence class of the ...
0
votes
0answers
12 views

Spectral properties of certain weighted adjacency matrices

I would like to know if anyone has ever studied the spectral properties of the weighted adjacency matrix of a digraph where if $w(u,v)$ is the weight of edge $(u,v)$, then $w(v,u) = w(u,v)^{-1}$. ...
1
vote
1answer
40 views

Eigenvalues of the sum of Laplacian matrix and the all ones matrix

Given an undirected graph and its Laplacian is $L$. I need to find the eigenvalues of the sum: $L + \mathbf{11^T}$ (where $\mathbf{1}$ is the all-ones vector, which means that $\mathbf{11^T}$ is a ...
1
vote
0answers
57 views

Finding all eigenvalues of the adjacency matrix of a simple graph

I want to find all eigenvalues of the adjacency matrix of the following graph(Graph spectrum), where $G$ and $H$ are complete graphs with $n$ and $m$ vertices, respectively, for positive integers $n,m ...
1
vote
1answer
38 views

Which cubic graphs have an eigenvalue of $\sqrt{6}$?

Which cubic graphs have an eigenvalue of $\sqrt{6}$? Can these graphs be constructed? The question is related to this one...
13
votes
4answers
625 views

On the invertibility of adjacency matrix

Which are the sufficient and necessary conditions for an undirected graph with no self edges (i.e. no loop of length 1) to have an invertible adjacency matrix? I recall that in this case the ...
1
vote
3answers
35 views

Are isomorphic graphs also isospectral?

Two graphs are isomorphic if they just have a different labeling for their vertices i.e. if $A$ and $B$ are their adjacency matrices, then, for some permutation matrix $P$, $PAP^T = B$. Two graphs ...
0
votes
1answer
13 views

Value of the Eigenfunction at a point

I'm reading "Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation" http://www.cs.jhu.edu/~misha/Fall07/Papers/Rustamov07.pdf At a certain point the author states "where ...
1
vote
3answers
34 views

The eigenvalues of $A=E-I$, where $E$ is a square matrix made up entirely of $1$'s and where $I$ is the appropriate identity matrix.

Let $A=E-I$, where $E$ is a square matrix made up entirely of $1$'s and where $I$ is the appropriate identity matrix. The following regarding $A$ is stated in my notes, but I am not sure how to show ...
0
votes
0answers
25 views

How can I prove the assertion for a Graph G?

Let G be a graph and A be the adjacency matrix of G. Let $ \delta(G)$ be the minimum degree of G and $\lambda_{min} $ be the least eigen value of A. Show that $\lambda_{min} \leq \delta(G)$.
5
votes
1answer
137 views

Which graphs do have invertible adjacency matrices?

I would like to know if there is any class of graphs for which the adjacency matrices are invertible. At this moment I am aware of only the class of graphs $n K_2$ which is the disjoint union of $n$ ...
1
vote
0answers
36 views

Graph having bounded degree

A graph is said to have bounded degree if there exists $N \in \mathbb{N}$ such that, for every $x \in V$, one has $\sum\limits_{y \in V} A_{x,y} \le N$. Show that, in this case, for any $f \in ...
5
votes
1answer
125 views

Bounding 2nd-smallest eigenvalue of the Laplacian of the binary tree

I am reading on my own the notes of this lecture series from 2012: http://www.cs.yale.edu/homes/spielman/561/2012/lect04-12.pdf. In section 4.7.2 (page 8) it's mentioned that we can prove a lower ...
0
votes
0answers
47 views

Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian

The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)? To make the question as self-contained as ...
3
votes
0answers
36 views

Possible lower Bound of radius of a graph

First of all I would like to ask people to forgive me because the question that I am about to ask is based on results of a study that I was involved in this year. The project was about designing ...
2
votes
1answer
42 views

Ball in a $k$-regular tree

Let $X$ be a finite k-regular graph. Fix a vertex $x_0$ and, for $r <\frac{g(X)}{2}$, consider the ball centered at $x_0$ and of radius r in X. Show that it is isometric to any ball with the same ...
1
vote
1answer
30 views

Do you need to know a lot of (regular?) graph theory to get into spectral graph theory?

Do you need to know a lot of (regular?) graph theory to get into spectral graph theory? What are the prerequisites?
0
votes
0answers
25 views

Perron vector of the distance matrix of a tree

Increasing properties of perron vector of distance matrix from the vertex corresponding to which row sum is minimum
0
votes
0answers
33 views

Number of connected components in a graph.

$\newcommand{\R}{\mathbb R}$ Let $G=(V,E,W:E\mapsto\R)$ be an undirected weighted graph with node set $V=(v_1,\dots,v_n)$, edge set $E\subseteq V\times V$ and weights over the edges $W_{ij}$. The ...
1
vote
1answer
68 views

eigenvalues of cycle graph and its complement graph

I am trying to find the eigenvalue of cycle graph and its complement. How to simplify.Suppose $\omega^{1}+\omega^{n-1}=2\cos (2\pi/n) $, then, $\omega^{\frac{n-1}{2}}+\omega^{\frac{n+1}{2}}=\ ?$ Is ...
1
vote
1answer
24 views

Creating a Hermitian matrix that is also positive semi-definite

Given some measurements on empirical data (in the form of a multigraph with two weighted edges between every pair of vertices), I would like to place the measurements in a Hermitian matrix that also ...
1
vote
0answers
37 views

A question about minimizing the $\lambda_{max}$ over a set of diagonal perturbations

Say I have an off-diagonal symmetric $0,1,-1$ entry matrix $B$ and a set of $2k$ diagonal matrices, $D_{11}, D_{12}, D_{21}, D_{22},..,D_{k1},D_{k2}$. (if it helps you can assume that $(1)$ all the ...
0
votes
1answer
29 views

Optimal partitioning of a planar graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
0
votes
0answers
20 views

Spectrum of the circulant graph

How to prove that the eigenvalue of cycle $C_n=\lambda_r=2 cos(2\pi r/n)$?where $r=0,1,...n-1$, which is proved for the circulant matrix with first row $(v_0=0,v_1=1,v_2=0, ...v_{n-2}=0,v_{n-1}=1)$, ...
1
vote
0answers
68 views

Eigenvectors of graph laplacian

Let $L$ be the laplacian matrix of a graph $G$, i.e. $L = D - A$, where $D$ is the degree matrix, and $A$ the adjacency matrix. Let $v_i$ be an eigenvector of $L$. Let $x,y$ be two vertices of the ...
2
votes
0answers
25 views

Integral roots of a circulant matrix

When does the circulant matrix have only integral roots? For example: adjacency matrix for $K_n$ has all the roots integral which is circulant, but in case of Cycle on $n>3$ it is circulant but it ...
4
votes
2answers
78 views

Determinant of $ n \times n$ matrix and its characteristic polynomial.

Suppose, $M_4, M_5,..M_n$ is as follows then determinant and characteristic polynomial of $M_n$. $M_4=\left( \begin{array}{cccc} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 ...
0
votes
0answers
54 views

Who are the mathematicians in US who are working on expander graphs right now?

I am familiar with only the "big" names doing this research like Gharan, Nikhil Srivastava, Dan Spielman, Jean Bourgain, Luca Trevisan, Elina Fuchs, Peter Sarnak , Amin Saberi and Terence Tao. I would ...