0
votes
0answers
17 views

The lower bound of Cheeger Inequality as the degree goes to infinity

Consider an undirected graph $G(V,E)$ with adjacency matrix $A$ and define the graph Laplacian as \begin{equation} L = D - A \end{equation} where $D$ is a diagonal matrix such that $D(i,i) = d_i$. ...
2
votes
1answer
38 views

the solution of matrix polynomials

In order to get the eigenvalues of \begin{equation} P=\left[ \begin{array}{cc} 0_{n\times n} & I_{n\times n} \\ -A & -B% \end{array} \right], \end{equation} where $A$ and $B$ are both $n\times ...
2
votes
0answers
32 views

interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...
0
votes
1answer
23 views

Lower bound on the minimum eigenvalue of sum of two matrices

Assume that $A$ is a symmetric positive definite matrix and $B$ is a symmetric (can potentially negative entries). Is the following bound correct? $$\lambda_{min}(A+B)\geq ...
4
votes
0answers
129 views

spectral radius (adjacency matrix) of a partitioned graph

Is the following bound on the largest eigenvalue of a partitioned graph known? It seems like it should be but I am not able to find a reference to it. Given a graph $G=(V,E)$ whose vertices are ...
0
votes
0answers
34 views

Controlling the spectral radius of a matrix product

Given a binary $n \times m$ matrix $B$, I want to find a real $m \times m$ diagonal matrix $D$ that minimizes the spectral radius of $BDB^T$, subject to the constraints: $Tr(D) = 0$. $\|D\|_{F1} = ...
1
vote
2answers
70 views

Upper bound on the difference between two elements of an eigenvector

Let $W$ be the non-negative, symmetric adjacency/affinity matrix for some connected graph. If $W_{ij}$ is large, then vertex $i$ and vertex $j$ have a heavily weighted edge between them. If $W_{ij} = ...
1
vote
2answers
105 views

Adjacency, Laplacian and Maximum Degree

I am relevantly new to http://math.stackexchange.com/ and this will be my first question, although I have been lurking around for some time now! So, pardon me if I am missing any posting etiquette ...
1
vote
0answers
133 views

Is there a simple interpretation of the eigenvectors of a graph (visualizable?)?

I want to understand eigenvectors obtain from graphs (adjacency matrices) in an analogous way as they are interpreted from principal component analysis of a set of images, which is easy:Eigenfaces ...
3
votes
2answers
1k views

Lowest Eigenvalue of a positive semi-definite matrix

I am reading a paper on spectral graph theory. Let us say we have an adjacency matrix W and a degree matrix D. We construct a Laplacian matrix, L defined as: L = D - W The paper claims that L is ...
1
vote
1answer
133 views

Tighter bound on a spectrum of a matrix obtained by partial diagonal shift

A matrix $V\in\mathbb{R}^{n\times n}$ is a full symmetric matrix with negative off-diagonal elements summing (in absolute value) to diagonal elements. Suppose that $V$ has all entries, and let ...
7
votes
3answers
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?
19
votes
1answer
3k 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 ...
11
votes
5answers
2k views

Spectrum of adjacency matrix of complete graph

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

Relationship Between Eigenvalue and Degree

I have a question regarding Rayleigh quotient. It's well known that maximal eigenvalue can be found by $$\lambda_{\max}(M)=\max_{x\neq 0}\frac{x^{T}Mx}{x^{T}x}.$$ Using this how to prove that ...
7
votes
1answer
349 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 ...
7
votes
1answer
164 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 ...
12
votes
1answer
414 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 ...
2
votes
0answers
425 views

Is there any relation between the principal eigenvalue of sub matrix and the original matrix?

I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix. In fact I am facing a problem which is to select $n$ rows and $n$ columns from the ...
2
votes
1answer
166 views

Kinks in the eigenvalue spectrum of short range lattices

Take a periodic one-dimensional lattice of size $N$ with $2k$ nearest neighborers. That is, vertex $i$ is connected to $i+1,i+2,...,i+k$ and $i-1,i-2,...i-k$ (with the understanding that the indices ...