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

3
votes
0answers
49 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
9 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 ...
1
vote
0answers
28 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 ...
5
votes
0answers
118 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
1answer
57 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
79 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 ...
0
votes
0answers
15 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
41 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...
1
vote
3answers
41 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
15 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
35 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
161 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$ ...
0
votes
0answers
109 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
39 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 ...
1
vote
0answers
37 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 ...
1
vote
1answer
34 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
29 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
50 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 ...
2
votes
1answer
52 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
26 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
1answer
72 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
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
20 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 ...
5
votes
1answer
131 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
1answer
30 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
22 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
80 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
27 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
80 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
56 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 ...
1
vote
0answers
35 views

What is the adjacency matrix of a squared (or k^th power) d-regular graph

If $A$ is the adjacency matrix of a $d$-regular graph, then I suppose $A'$(the adjacency matrix of the squared graph) should be $A^2 + A - dI$ (to remove self-loops). What about higher powers? How do ...
5
votes
0answers
64 views

Lower bound for spectral gap for graph on $n$ vertices

Let $G = (V,E)$ be a graph on the vertex set $V$ with edges $E$. Let $A$ be the adjacency matrix for $G$ (so $A_{ij} = 1$ if vertices $v_i$ and $v_j$ are connected by an edge), and $D$ be the ...
3
votes
1answer
145 views

Construction of a Strongly Regular Graph which has regular Neighbourhood graphs in all iteration.

Notation and Definition: $G$ is a Strongly Regular Graph (not complete or a cycle) and is denoted by $\mathrm{SRG}(n,r, \lambda, \mu)$ if it has the following properties: Every two adjacent ...
1
vote
1answer
97 views

Computing eigenvalue of the adjacency matrix of a path

Let $A\in \{0,1\}^{n \times n}$ be the adjacency matrix of a path of length $n$, i.e. having ones on the two off-diagonals, and zeros elsewhere. How does one compute the eigenvalues of this? I know ...
3
votes
0answers
86 views

Eigenvalue of Block matrix: Adjacency of complete bipartite Graph

Let $A\in \{0,1\}^{mn \times mn}$ be the adjacency matrix of a complete bipartite graph with $m$ and $n$ vertices each, i.e. let $A$ be the matrix consisting of two blocks $A_1\in \{0,1\}^{m \times ...
2
votes
2answers
99 views

Confusion between spectral radius of matrix and spectral radius of the operator

The adjacency matrix $A(G)$ of an infinite undirected graph $G$ is considered as a bounded self-adjoint linear operator $A$ on the Hilbert Space $l^2(G)$ (last section of ...
-2
votes
1answer
87 views

Characteristic polynomial of a block matrix

Let $A$ be an $n\times n$ symmetric matrix whose diagonal are is covered by zero blocks (square, but not of a fixed size) and all other entries are $1$ (one). How can I find its Characteristic ...
1
vote
0answers
48 views

Highest eigenvalues/vectors of graph laplacian

In page 8 of the paper Laplacian Eigenmaps for dimensionality reduction and Data Representation it reads: Standard methods show that the solution is provided by the matrix of eigenvectors ...
1
vote
0answers
17 views

Size of intersection of balls on non-ameanable graphs

Let $G$ be a vertex-transitive non-ameanable graph and let $B(x,n)$ be the ball of radius $n$ centered on the vertex $x$. I am interested in estimates on the cardinality of the following set, ...
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 ...
0
votes
1answer
35 views

Relation between edge expansion of graph and sparsity

I was going through the lectures of Graph Partitioning and Expanders - Stanford Online. In lecture 1, near the end of page 5, I came across this inequality for regular graphs: $$\phi(S) \leq h(S) \leq ...
0
votes
0answers
16 views

The image of a a vector in the edge space when multiplied by it's incidence matrix.

Consider a graph $G=(V,E)$ and it's incidence matrix $M$. Let $\textbf{x}$ be the characteristic vector for a standard basis vector in $\mathcal{E}$ (a vector corresponding to the one element edges ...
3
votes
0answers
39 views

What do we know about inverses of matrices which are “like” Laplacians of graphs?

Consider the Laplacian $L$ of a bipartite graph. Is there any generic understanding we have about what $1/(z-L)$ looks like? [say $z > \lambda_\max(L)$)] You can consider variations of $L$ like ...
0
votes
0answers
5 views

PageRank metaphor as suspended unlimited capacity pools

What do you think about my metaphor of the centrality measure PageRank? PageRank is an algorithm for evaluating node centrality: it's a function $f:G \to R^n$ where $n$ is the number of nodes in the ...
3
votes
0answers
29 views

How networks with high largest eigenvalues are more robust?

In the literature, it sometimes indicates that network with high value of largest eigenvalue (either adjacency matrix or its Laplacian counterpart) are more robust. Robustness here is relevant to ...
0
votes
1answer
33 views

Construction of graph Laplacian

I have a weighted undirected graph, and all the edge-weights are non-negative. According to the definition of the graph Laplacian matrix, $L=D-W$. In literature, I found that $D$ is known as degree ...
2
votes
0answers
51 views

When do a Regular graph has an odd eigenvalue?

Merely looking at adjacency matrix of a regular graph, without explicit calculation, can we decide that graph will have an odd eigenvalue or not? If regularity is odd, we are sure that it will be an ...
1
vote
1answer
51 views

spectrum of complete p-partite graphs

I need to determine the spectrum of the complete p-partite graph ( in which each partite set has m vertices) using the complement. How can i show this? I know the spectrum of the adjacency matrix of ...
2
votes
0answers
63 views

Interpretations of a weighted adjacency matrix's eigenvectors and eigenvalues?

Suppose that I have weighted undirected graph $G$, and the corresponding adjacency matrix which is a symmetric matrix $A$. Suppose that the edge between node $i$ and $j$ has weight $w_{ij}$, then $$ ...