Tagged Questions

1
vote
0answers
18 views

Delocalization of eigenvectors in Expanding Graphs

Given an adjacency matrix A, can we say something about whether the eigenvectors corresponding to its highest(or second-highest) eigenvalues are delocalized ? By delocalization I mean that every ...
1
vote
0answers
23 views

finding the decomposition of Laplacian matrix with position of zero elements unchanged

I'd like to know whether it's possible to find the decomposition of a Lapalacian matrix $A$ $B^TB = A$ where $B$ has the same dimension with $A$ and the position of zero elements in $B$ is the same ...
9
votes
1answer
233 views

Why does this matrix have 3 nonzero distinct eigenvalues

Consider the $n \times n$ matrix $$A=\left[ \begin{array}{cccc} 0 & 1 & ... & 1 \\ 1 & 0 & & 0 \\ \vdots & & \ddots & \\ 1 & 0 & & 0% ...
1
vote
1answer
114 views

Parameter for Katz centrality of a graph

I am teaching a course using M.E.J. Newman's Networks. It covers several measures of vertex centrality. One of them is the Katz centrality. Let $G$ be a graph and let $A$ be its adjacency matrix. ...
5
votes
1answer
57 views

Is Eigenvector/eigenvalues of a sub graph similar to the main graph?

In Gephi I visualized a graph to calculate the eigenvalues,then I choose a portion of graph (e.g 6 vertex with their edges) and delete all others. I calculate the eigenvalues again and noticed that I ...
2
votes
0answers
35 views

maxcut and the minimal eigenvalue

For an adjacency matrix $A$ that represent a graph $G=\langle V,E\rangle$, I need to show that the maxcut is bounded by: $$ \mathrm{maxcut} \leq \frac{1}{2}|E| - \frac{|V| \lambda_{\min}(A)}{4}, $$ ...
0
votes
1answer
49 views

Question related to a proof about the multiplicity of some eigenvalues

I have a question related to Lemma 4.2 from this pdf (which is, btw quite a nice exposition of Hoffman Singleton work on the classifications of Moore graphs of diameter 2 and 3.) We are given a $n ...
2
votes
1answer
74 views

Possible relation between spectra bounds of two matrices

A Laplacian matrix $L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, \begin{equation} l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\ -w_{ij} & ...
4
votes
1answer
108 views

Eigenvalues of a special block matrix associated with strongly connected graph

Definition Let $G=(V,E,A)$ be a strongly connected directed graph, where $V=\{1,2,...,n\}$ denotes the vertex set, $E$ is the edge set, and $A$ is the associated adjacent matrix with $0-1$ weighting, ...
6
votes
3answers
663 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?
9
votes
5answers
874 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
0answers
132 views

Eigenvalues of regular graphs

Could someone give me a hint for exercise 2.iii of these lecture notes? The exercise asks to show that a $k$-regular undirected graph (without loops) whose adjacency matrix $A$ has eigenvalues ...
7
votes
1answer
183 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
134 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 ...
10
votes
1answer
226 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 ...
4
votes
2answers
173 views

Graphs with eigenvalues of large multiplicity

For a strongly regular graph, there are exactly 3 eigenvalues, all nonzero (I believe). One has multiplicity 1, which means the other two have pretty high multiplicities. There are tables that give ...
2
votes
1answer
122 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 ...
1
vote
1answer
227 views

eigen decomposition of an interesting matrix (general case)

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 ...
4
votes
1answer
298 views

eigen decomposition of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
4
votes
2answers
297 views

Knowledge about Graph Spectral Theory and correlation between a graph Weighted Adjacency matrix and its eigenvalues

I know that this question is some sort of bridge between Informatics and Mathematics, not knowing the best place where to post this question, I opted for this place because of the type of answer I ...