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

0
votes
0answers
45 views

Graph Combinatorics: How many such Graphs are there?

How many $4$-regular graphs exist on $8$ vertices? I found that such a graph can't be disconnectd since if so, then graph can be written as disjoint union of atleast two graphs. $4$ regularity ...
0
votes
0answers
11 views

How to show a random matrix has large spectral gap?

If I know $Y$ is a random d-regular bipartite graph (tanner code in coding theory), can I show $Y^TY$ has large spectral gap with high probability? More specifically: If I know $Y=AX \in ...
1
vote
0answers
17 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...
1
vote
1answer
46 views

Icosahedral Graph

Let $Γ$ be a graph cospectral with the icosahedral graph having spectrum $\{[5]^1,[\sqrt{5}]^3, [-1]^5,[-\sqrt{5}]^3\}$. I have shown that Γ has 12 vertices, 30 edges, regular with each vertex having ...
0
votes
0answers
21 views

How to find spectral radius of ${0,1}$ and ${0,1,-1}$ matrices?

[this is kind of a continuation of this question ] It seems that the following is true, Among $n=3$ dimension symmetric matrices over $\{0,1\}$ which have $d=7$ ones the maximum spectral radius is ...
0
votes
1answer
42 views

What is known about optimization of spectral properties of matrices over finite fields?

[I am solving the characteristic polynomial over complex numbers but since the matrices are symmetric all eigenvalues are real] Like for symmetric $d-$regular matrices over 0/1 or 0/1/-1 what are ...
-2
votes
0answers
34 views

Does new matrix also have integral eigen values?

$K_n$ is complete graph on n vertices. Laplacian matrix of $K_n$ has integer eigenvalues. If we are taking compliment of a $K_m$ (alongwith n-m isolated vertices) ; $m<n$ in $K_n$, Does Laplacian ...
4
votes
1answer
38 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 ...
2
votes
1answer
53 views

About Cayley graphs on finite fields.

If one is given $n$ vectors of length $n$ $\in \mathbb{F}_{p^k}^n$ for some prime number $p$ and $k \in \mathbb{Z}^+$ then how can one check if they are linearly independent? (the issue is if there ...
0
votes
0answers
20 views

Intuition behind spectral radius of a graph

Suppose that I have a graph G, along with its respective adjacency matrix A. The definition of how one can compute the spectral radius of this graph is not hard to grasp, but I was wondering about the ...
0
votes
0answers
22 views

Graph Centrality: spectral techniques

What is the difference between: normalizing the row of an adjacency matrix and taking the right eigenvector normalizing the row of an adjacency matrix and taking the left eigenvector ...
3
votes
0answers
77 views

Clustering with SVD

I'm trying to do some clustering on a graph, which is represented by an adjacency matrix $B = A^2$, where $A$ is symmetric. I tried several methods like taking the eigenvectors of the Laplacian $L = ...
1
vote
1answer
54 views

A curious way to write the eigenvectors of the Boolean hypercube

It seems that one can write the eigenvectors of the hypercube $\{ \pm 1\}^n$ as the functions, $\{ \chi_S \}_{S \subseteq [n] }$. And these functions $\chi_S$ are defined on the vertices $x \in \{ \pm ...
2
votes
1answer
24 views

Efficiently compute the eigenvectors of the Laplacian of a symmetric positive matrix

I am working with a matrix A relatively large (200k x 200k), and I want to compute the eigenvectors of the Laplacian: $L = D - A^2$, where $A$ is symmetric. I don't need all eigenvectors, just a few ...
0
votes
1answer
18 views

What conditions on a graph $G$ allow it to be uniquely determined by the spectrum of $A(G)$?

What conditions on an undirected graph $G$ allow it to be uniquely determined by the spectrum of its adjacency matrix $A(G)$? Very simple examples show that one needs connectivity, and I imagine ...
7
votes
0answers
74 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,...,x_m$ in the euclidean space $\mathbb{R}^n$, we can form a $m$ x $m$ Euclidean Distance Matrix $D$ where $D_{ij}={||x_i-x_j||}^2$. We know a little bit about these ...
1
vote
0answers
18 views

Adjacency vs Laplacian matrix

There are different ways to represent a graph but adjacency and laplacian matrices are the two most powerful ones having various properties. Recently, a student asked me when exactly we should use ...
4
votes
0answers
46 views

What do the eigenvalues/vectors of a metric describe?

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$? ...
0
votes
1answer
47 views

Polynomials and adjacency matrix of a graph

If $p$ is some polynomial such that $[p(A)]_{ij} \neq 0$ and $A$ is the adjacency matrix of a graph. Does the existence of such a $p$ say anything about the graph?
0
votes
0answers
24 views

What physical intuition the eigen values and eigen vectors of adjacency matrix and laplacian of a graph provide?

So I have a undirected graph and its corresponding adjacency matrix $A$ and laplacian $L = D -A$, where $D$ is a diagonal degree matrix. What physical intuition can the eigen values and eigen vectors ...
2
votes
3answers
138 views

Graphs interpreted as adjacency matrices

Consider a real symmetric matrix. Such a matrix can be considered as an adjacency matrix of a graph, and in fact may be identified with the graph itself. Now consider the equivalence class of the ...
1
vote
1answer
32 views

Automorphism group of a graph as a group of matrices

Let $G$ be a graph and $A$ its adjacency matrix. Is it correct to say: $$\text{Aut}(G)=\{PAP^T:P\text{ is a permutation matrix}\}$$ I believe so, but I have never seen it written this way. If so, ...
1
vote
0answers
22 views

Spectral gaps of common graphs

I'm looking for the spectral gap of common graphs (alternatively, the mixing time of a (lazy) random walk on these graphs). Asymptotic values are fine. Assume that every node has a sufficient number ...
0
votes
1answer
31 views

What is the notion of “character” in the context of Cayley graphs?

I am looking at these notes, http://www.eecs.berkeley.edu/~luca/books/expanders.pdf On page 37, Lemma 5.16, the notion of "character" defined seems to be any map from the finite Abelian group to ...
1
vote
1answer
41 views

The second smallest eigenvalue of a complete binary tree

Apparently it is true that the second smallest eigenvalue of a complete binary tree is $\theta(\frac{1}{n})$. Can someone point out a reference which proves this?
4
votes
1answer
64 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 ...
1
vote
0answers
32 views

Properties of non-negative non-symmetric square matrices

I've done some searching but couldn't get much from the web. I am looking for some pointers regarding the properties of non-negative non-symmetric square matrices. The elements within the matrix are ...
1
vote
1answer
28 views

Spectral gap vs. algebraic connectivity

Can someone please clarify how the spectral gap of a graph relates to its algebraic connectivity (aka Fiedler value) and whether these use the adjacency matrix or laplacian matrix?
1
vote
0answers
46 views

Is there such a notion of “expansion” in groups?

Given a subset of elements of a finite group $G$, I would like it to be such that the set of all distinct words (as elements of $G$) that can be formed from this set is exponentially large in the size ...
0
votes
0answers
26 views

Reference for the proof of interlacing of eigenvalues of submatrices

If one has a $n \times n$ Hermitian matrix $A$ and one removes $k$ of the rows and their corresponding columns then the eigenvalues of the remnant interlace the eigenvalues of the full matrix. Can ...
2
votes
2answers
79 views

Why Laplacian Matrix need normalization and how come the sqrt of Degree Matrix?

I am new here. If I do any rough, please forgive me. My question: Why Laplacian Matrix need normalization and how come the sqrt-power of Degree Matrix? The ...
0
votes
0answers
32 views

the number of ways a planar graph can be partitioned

i have a connected planar graph to cut into k parts and want to know how many possible solutions there are. it clearly depends on the shape of the graph since nodes all in a row cannot be partitioned ...
1
vote
1answer
30 views

Can we say anything about the order of the second largest eigen-value?

Suppose we have a vertex-transitive graph ($G$) with degree $n$ and the number of vertices $N$. Is it possible to say anything about the exact order of $\frac{1}{n-\lambda _2}$ in terms of $N$ and ...
2
votes
2answers
51 views

How to use spectral graph theory to get a measure for graph symmetry?

I looked at graphs, like $K_{12}$ or Frucht's graph and wondered if their spectrum, more specific the degenercies of their eigenvalues, is a mesaure for the (a)symmetry of the corresponding graph? ...
2
votes
3answers
138 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?
0
votes
0answers
21 views

Extremal eigenvalues & eigenvectors of skew-adjacency matrix

I am looking for ways to obtain the extremal eigenvalues and eigenvectors of the skew-adjacency matrix of a directed graph. The graphs I am interested in are not regular (but they have a maximum ...
1
vote
0answers
30 views

About the topology of a $d$-regular tree

What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph? Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see ...
2
votes
0answers
27 views

Spectral radius of a time-varying matrix with strictly positive increment

Consider a time varying non-negative matrix $A(t)$ and its spectral radius $\rho(A(t))$ where $t$ denotes the time. If $A(t)$ changes over time with each time a random element in $A(t)$ is being ...
2
votes
1answer
89 views

What is the smallest and the largest possible adjacency eigenvalue of a regular graph?

For a $d-$regular graph I think $d$ is always the largest adjacency eigenvalue and if its bipartite then I think $-d$ is the smallest possible.
1
vote
1answer
31 views

give an example to show it is possible to remove one vertex and the multiplicity of one of eigenvalue rise.

I know that if we consider a graph $G$ with $\lambda$ as one of its eigenvalue of adjacency matrix with multiplicity $n$ ,there is a vertex of $G$ that by removing it ,the multiplicity of $\lambda$ ...
1
vote
1answer
44 views

Spectrum of infinite d-regular tree

Consider the adjacency matrix of the infinite d-regular tree, call it A. To find the spectrum we consider it as an operator in $L^2(V)$. It is stated that $A-\lambda I$ is always one-to-one. I do ...
1
vote
1answer
47 views

Prove a certain matrix is positive semidefinte.

Consider a stochastic matrix $P$, i.e. real, non-negative, square, rows sum to one. Consider $\Xi$ to be a diagonal matrix with a principal left eigenvector of $P$ on the main diagonal and zeros ...
0
votes
0answers
14 views

Faber-Krahn inequality for domain in Z^d with nearest-neighbor connections

In $\mathbb{R}^d$ there is a theorem that if you are looking for the first Dirichlet eigenvalue $\lambda_1$ of a domain $D \subset \mathbb{R}^d$ with a given volume $V$, then $\lambda_1$ will be ...
1
vote
1answer
67 views

What is the multiplicity of the largest eigenvalue of a graph?

The Laplacian of a graph is a symmetric positive semi-definite matrix and hence has all real eigenvalues. Is there any characterization for the multiplicity of the largest Laplacian (and/or Adjacency ...
0
votes
0answers
11 views

correlations between network parameters

I am calculating spectral densities for networks. Is there a reason why skewness and kurtosis would, in general, be correlated across many networks? That is, as a feature of networks rather than ...
0
votes
0answers
30 views

Spectral methods with linear programming

Is it possible to model and solve some fundamental spectral methods (say Singular-Value Decomposition) with (Integer?) Linear Programming? Update: say you want to do SVD. Can you model it as a ...
2
votes
1answer
68 views

Is there any graph property which is equivalent to that the spectral radius of its adjacency matrix is less then $1$?

Let $G$ be a directed graph and $A$ the corresponding adjacency matrix. I'll denote with $\rho$ the spectral radius, and with $I$ the identity matrix. What can we say about $G$ when the spectral ...
3
votes
2answers
147 views

How adjacency matrix shows that the graph have no cycles?

Let $G$ a directed graph and $A$ the corresponding adjacency matrix. Let denote the identity matrix with $I$. I've read in a wikipedia article, that the following statement is true. Statement. $I-A$ ...
0
votes
0answers
18 views

Modifications to the definition of graph Laplacian?

Many people have defined various definitions for graph Laplacian. For example see here [1]. What is common between various definitions of Laplacian that makes all of them ``Laplacian"? For example ...
1
vote
0answers
36 views

Weighted undirected graphs, complex Laplacian, complex eigenvalues & spectral clusering

I am rather puzzled and confused, I have been trying to get a clear understanding of how would spectral clustering work for an undirected weighted graph, I have used the normalized Laplacian, but I ...