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

2
votes
1answer
56 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
93 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 ...
1
vote
1answer
106 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 ...
5
votes
1answer
189 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
5
votes
0answers
341 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
0
votes
1answer
67 views

Graph Laplacian - Spectral Clustering with Regularization

Assume a graph $G=(V,E)$ where the vertices $V$ are points in ${{R}^{D}}$ with $\left| V \right|=n$. The edges $E$ are represented by a $n\times n$ affinity matrix $W$. Consider the graph Laplacian ...
1
vote
0answers
54 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seem to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...
2
votes
0answers
58 views

Possible Eigenvalues of Graph

How would one prove (or disprove) that there is no such graph $G$ with $\lambda$ as an eigenvalue? I tried setting up a system of equations to see if it's possible for $-\frac{1}{2}$ to be an ...
1
vote
0answers
49 views

pierre simon laplace and his knowledge of the (Laplacian) matrices

so as we all know, there is a graph matrix called the Laplacian that is used in some eigenvalue/eigenvector/graph theory/spectral theory problems. i'm wondering if the name of this matrix is ...
1
vote
0answers
37 views

How to show that the spectral radius of a binary tree approaches exp(1) as the N tends to infinity?

How can I prove mathematically that the spectral radius of a binary tree approaches e as the number of nodes tends to infinity? I mean it is true that the increase in nodes number is exponential but ...
1
vote
0answers
57 views

Characterization of all matrices with unit spectral radius under constraint

Let $A \in \mathbb{R}^{n \times n}_{\geq 0}$ be a symmetric matrix with positive row sums $\mathbf{d} := A\mathbf{1} > 0$. I am interested in characterizing all those positive diagonal matrices $Z ...
4
votes
0answers
219 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
1answer
105 views

Compute eigenvalues of a regular graph.

I have a $(q^2+q)(q+1)$-regular graph. Is there some general method to compute the eigenvalues of the adjacency matrix of a $k$-regular graph explicitly? Or could we estimate its eigenvalues? Thank ...
0
votes
1answer
200 views

how do I compute the eigenvectors for spectral clustering from a singular value decomposition?

I am implementing spectral clustering following A tutorial on spectral clustering. After preparing the Laplacian matrix $L^{n \times n}$, I compute the Singular Value Decomposition $U \Sigma V^{*}$. ...
1
vote
2answers
882 views

Rank of adjacency matrix vs rank of graph Laplacian

What is the relation between rank of the adjacency matrix of a graph and rank of the corresponding graph Laplacian matrix?
0
votes
1answer
107 views

Are these equivalent representations (labelled graph and adjacency matrix)?

This is an example from Wikipedia's page on adjacency matrices, which from the site's format seems to be suggesting equivalence between the simple diagram below, left, and the abstractly represented ...
4
votes
0answers
128 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 ...
3
votes
0answers
62 views

Is the upper Cheeger Inequality tight?

The (upper) Cheeger Inequality says: Let $G$ be an unweighted, undirected, regular graph of degree $d$. Let $\lambda_2$ be the second eigenvalue of the Laplacian matrix of $G$, and let $\phi(G)$ ...
4
votes
0answers
180 views

What can we say about two graphs if they have similar adjacency matrices?

Suppose we have two (finite, simple, undirected) graphs, what can we say about these graphs if they have similar adjacency matrices? Observations to begin with: If $G_1$ and $G_2$ are isomorphic, ...
1
vote
1answer
146 views

cluster validation and determining number of clusters

I want to find number of cluster in the real world data set. So, I validate the spectral clustering by using some indexes as shown in figures below? But as you seen in figures the results are very ...
0
votes
0answers
165 views

Variance of the first return time of a simple random walk on an hypercube graph

I am trying to solve this problem.... I have a simple random walk on a $d$-cube (finite graph). At each vertex of the graph, the particle chooses one of $d$ edges equally likely. I need to calculate ...
1
vote
1answer
132 views

What does small eigenvalue gap imply for a graph?

Knowing a graph has good expansion has well-known implications. What can we say about graphs with $1-\lambda = O(\log n/n)$, where $1-\lambda$ is the difference between the two largest eigenvalues of ...
2
votes
1answer
116 views

Connection between the Tutte and characteristic polynomials?

Both the Tutte polynomial $T_G(x,y)$ and the characteristic polynomial $\phi_G(x)$ encode a great amount of structure of the input graph $G$. I've read somewhere that the Tutte polynomial has a kind ...
1
vote
0answers
99 views

Algebraic characterization of being $P_n$-free.

Is there an algebraic way to determine from the adjacency matrix $A$ of a simple graph $G$, whether $G$ contains an induced path of fixed length $n$? I am particularly interested in the case $n=6$. ...
1
vote
2answers
94 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} = ...
2
votes
0answers
81 views

when does a graph with normalized laplacian have a uniform degree distribution?

Consider the graph $G(A)$ with A as its adjacency matrix. Let $L$ be its Laplacian and $L_{sym} = D^{\frac{1}{2}}LD^{\frac{1}{2}}$ be the normalized Laplacian. Now let $A(L_{sym}) = I - L_{sym}$ ...
0
votes
1answer
43 views

For which spectrum is the following result for?

I don't know if I am the only one that feels this, but damn Spectral Graph Theory needs some notation change... Maybe it is because I am not so experienced in the field yet, but man every time I read ...
2
votes
0answers
282 views

Bounds on the maximum eigenvalue of the adjacency matrix of a graph.

I managed to proof the following result for the maximum eigenvalue: $ d_{avg}\leq \lambda_{max} \leq \Delta(G) $ where $d_{avg}$ is the average degree of the graph while $\Delta(G)$ is the maximum ...
4
votes
1answer
127 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? ...
2
votes
1answer
150 views

Global solution for spectral clustering

I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...
1
vote
2answers
191 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 ...
3
votes
2answers
70 views

Graphs with zero spectrum / nilpotent symmetric matrices

Is there a graph theoretic characterization of those graphs with zero spectrum? Alternatively, can one at least characterize all symmetric nilpotent (complex) matrices, so that one could recognize ...
1
vote
1answer
95 views

Prove $MM^t=A+kI$ for matrices associated to graphs

How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices? It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), ...
1
vote
1answer
313 views

Adjacency matrix defines a distance metric

Let $A$ be adjacency matrix of a graph (perhaps weighted). Prove that \begin{equation} \sum_i \sum_j A_{ij} (f_i- f_j)^2 = \mathbf{f}^T L \mathbf{f} \end{equation} where $\mathbf{f}$ holds values of ...
0
votes
1answer
218 views

Eigenvalues of graph's laplacians

I'm trying to tackle a question from a homework assignment and one of the problems concerns the relation between eigenvalues of a graph's laplacian and its complement's laplacian. The relation is: ...
1
vote
2answers
108 views

Spectrum of a 3-regular graph

Let $D_n$ be the following graph on $2n$ vertices: $V=\mathbb{Z}_n\times\{0,1\}$ and $E=\{(i,j)(i+1,j): i\in \mathbb{Z}_n,j\in \{0,1\}\}\cup\{(i,0)(i,1):i\in\mathbb{Z}_n\}$. What is the spectrum of ...
2
votes
1answer
750 views

Spectrum of the cycle graph $C_n$

I am trying to find out the spectrum (the collection of eigenvalues) with their multiplicities of the cycle graph $C_n$. Assuming that $X=\pmatrix{x_1\\x_2\\\vdots\\x_n}$ is the eigenvector, by ...
1
vote
0answers
51 views

spectral graph theory with “potentials”

Let G be an undirected graph with bounded degree and n vertices. Let L[G] be the corresponding graph Laplacian, which is a symmetric $n \times n$ matrix. Let V be an $n \times n$ diagonal matrix. I am ...
35
votes
6answers
2k 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 ...
-1
votes
1answer
136 views

Eigenvalues of a connected graph $G$ are greater than or equal to $-1$ iff $G$ is perfect?

Consider $P_G$ as the characteristic polynomial of the adjacency matrix of the connected graph $G$. It is easy to prove that $P_{K_n}(x)=(x-n+1)(x+1)^{n-1}$, so all of the eigenvalues of a perfect ...
1
vote
3answers
337 views

How to find the spectrum of the hypercube?

I want to find the proof of the spectrum of the hypercube
1
vote
0answers
199 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 ...
4
votes
1answer
414 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 ...
5
votes
1answer
133 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$ ...
2
votes
1answer
459 views

The number of connected components of a $k$-regular graph equals the multiplicity of k

In similar vein to this question, I am trying to understand the proof of the fact that in a $k$-regular graph, the multiplicity of the eigenvalue $k$ equals the number of connected components. The ...
3
votes
2answers
2k 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
164 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 ...
1
vote
1answer
279 views

Strongly connected graph associated with a matrix

This type of matrices $L$ is called Leslie type matrices in Population dynamics: $$L = \begin{pmatrix} f_{11} & f_{12} & f_{13} & \dotsm & f_{1,i-1} & f_{1,i}& \dotsm & ...
7
votes
3answers
2k 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 ...
2
votes
1answer
409 views

Connectedness of a regular graph and the multiplicity of its eigenvalue

Suppose $X$ is a $k$-regular graph with adjacency matrix $A$. I wish to show that if $k$ has multiplicity $1$ as an eigenvalue of $A$ then $X$ is connected. By way of contradiction I assume that X is ...