# Tagged Questions

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

3k views

### Motivation for spectral graph theory.

Why do we care about eigenvalues of graphs? Of course, any novel question in mathematics is interesting, but there is an entire discipline of mathematics devoted to studying these eigenvalues, so ...
6k views

### What do the eigenvectors of an adjacency matrix tell us?

The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality. What do the second, third, etc. eigenvectors tell us? Motivation: A standard information ...
366 views

### What is the intuition behind / How can we interpret the eigenvalues and eigenvectors of Euclidean Distance Matrices?

Given a set of points $x_1,x_2,\dots,x_m$ in the euclidean space $\mathbb{R}^n$, we can form a $m\times m$ Euclidean Distance Matrix $D$ where $D_{ij}={\|x_i-x_j\|}^2$. We know a little bit about ...
619 views

### What does the minimal eigenvalue of a graph say about the graph's connectivity?

I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this ...
874 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 ...
3k views

### Spectrum of adjacency matrix of complete graph

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$. ...
1k views

### Eigenstructure of discrete Laplacian on uniform grid

The discrete Laplacian of a graph is the matrix $L = D - A$ where $D$ is a diagonal matrix with $d_{ii}$ being the degree of $v_i$, and $A$ is the usual adjacency matrix. Is there anything known ...
1k views

### Significance of eigenvalue

When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?
227 views

### Two formulas for the minimal eigenvalue of a graph

Hello again everybody, I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm ...
272 views

### Applications of Cayley Graphs in Physics

I have been recently reading about Cayley graphs and character theory. It is evident that Cayley graphs are very useful tool in theoretical computer science. In physics, Cayley graphs seem do appear ...
180 views

### When a matrix has same eigenvalues of its column-swapped version?

What are the properties needed for a matrix $A$ to have $\mbox{Spec}(A)= \mbox{Spec}(A \cdot P)$, where P = \begin{pmatrix} 0 & \cdots & 0 & 1 \\ \vdots & \...
3k views

### Eigenvalues of a bipartite graph

Let $X$ be a connected graph with maximum eigenvalue $k$. Assume that $-k$ is also an eigenvalue. I wish to prove that $X$ is bipartite. Now if $\vec{x}=(x_1,\cdots ,x_n)$ is the eigenvector for $-k$...
691 views

### Spielman's proof of graph connectivity

I use Spielman's lectures on course Spectral Graph Theory I have few question regarding Lecture 2. The Laplacian, especially Lemma 2.3.1 (Graph connectivity). Please, help me to make it a little bit ...
539 views

197 views

### Constructing a directed graph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
740 views

### A finite graph G is $d$-regular if, and only if, its adjacency matrix has the eigenvalue $λ = d$

Show that a graph $G$ ﬁnite with $n$ vertices is $d$-regular if, and only if, the vector with all the coordinates equals to 1 is eigenvetor from eigenvalue $λ = d$ from the adjacency matrix $A$ ...
570 views

### Intuitive interpretation of the adjacency matrix as a linear operator.

Naturally we can describe graphs via tables of "yes there is an edge" or "no there is not" between each pair of vertices, so the definition of an adjacency matrix is easily understood. Thinking of ...
342 views

### Spectral graph theory and connected components of graphs

We know that multiplicity of least eigenvalue of laplacian matrix of graph gives us number of connected components in graph.What is intuition behind this theorem? How do we know that this works in ...
151 views

### Understanding and interpreting graph spectra

I'm not a mathematician, but a geographer trying to get a grasp on some network analysis I'm experimenting with. I have a few questions related to spectral graph theory that a mathematician could help ...
176 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$ ...
148 views

### Laplacians, Diagonal Perturbations

Setup: Consider a Laplacian (or Kirchoff) matrix $L = L^T \in \mathbb{R}^{n \times n}$ corresponding to a weighted, undirected and connected graph. That is, a matrix with $L_{ij} \leq 0$ for $i\neq j$ ...
120 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 ...
136 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 ...
72 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 ...
952 views

### Can I find the connected components of a graph using matrix operations on the graph's adjacency matrix?

If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
82 views

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 &... 1answer 578 views ### Does an$n\times n$adjacency matrix of a scale-free network graph have$n$distinct eigenvalues? Question updated Suppose that I have an$n\times n$adjacency matrix$\mathbf{A}$of a simple graph$G$where the entry$(i,j)$represent the number of edges between node$i$and$j$in$G$. Note ... 1answer 65 views ### Laplacian solvers for inversion of large matrices? I have a large matrix L of size 400,000$\times $400,000 . I'm using this L matrix in the following way. Lin = L$^{-1}$C = D - B * Lin * B'; B,D are of appropriate sizes. L matrix is ... 1answer 91 views ### Is this graph and its spectrum understood? Consider the graph whose vertices are labelled by the binary representation of the integers from$0$to$2^{d}-1$for some$d \in \mathbb{N}$. So its a graph with$2^d$vertices. An edge exists ... 2answers 133 views ### Is there anything special about a graph with the golden ratio in its spectrum? Given a simple connected graph$g$with adjacency matrix$\mathbf{A}$. Let the spectrum$\lambda_1 < \lambda_2 < \ldots < \lambda_N$be the eigenvalues of the equation$\mathbf{A} v=\lambda v$... 1answer 111 views ### Spectral radius of “almost” regular graph ?! The answer to this question could be trivial. The Graph Let$G$be graph formed of two$d$-regular connected components. That is,$G= H_1\cup H_2$, where$H_1$, and$H_2$are$d$-regular and ... 1answer 309 views ### characteristic polynomial of the adjacency matrix of a tree I have read that if$A$is the adjacency matrix of a tree$T$, then we have that $$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k}$$ where$N_k(T)$is the number ... 2answers 53 views ### Geometric intuition of graph Laplacian matrices I am reading about Laplacian matrices for the first time and struggling to gain intuition as to why they are so useful. Could anyone provide insight as to the geometric significance of the Laplacian ... 1answer 166 views ### What graph Laplacians commute I know that the graph Laplacian of a fully connected graph commutes with the Laplacian of any other graph. Is there any theorem stating something similar about some more general family of graphs? I'... 1answer 278 views ### Questions on fractional Laplacian graph spectra Both the signed ($D-A$) and unsigned ($D+A$) Laplacian are of interest in spectral graph theory, see eg Cvetkovic: Bibliography on the signless Laplacian eigenvalues: first one hundred references. ... 0answers 31 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) ... 0answers 39 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$\mathcal{G}=(\mathcal{V},\mathcal{...
Given a finite metric space $(X = \{ x_i \}_{i=1}^n,d)$, one can form the matrix $A$ of pairwise distances $a_{ij} = d(x_i, x_j)$. What does the eigenspectrum of this matrix say about the metric $d$? ...