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
0answers
52 views

When do a Regular graph has an odd eigenvalue?

Merely looking at adjacency matrix of a regular graph, without explicit calculation, can we decide that graph will have an odd eigenvalue or not? If regularity is odd, we are sure that it will be an ...
1
vote
1answer
60 views

spectrum of complete p-partite graphs

I need to determine the spectrum of the complete p-partite graph ( in which each partite set has m vertices) using the complement. How can i show this? I know the spectrum of the adjacency matrix of ...
2
votes
0answers
66 views

Interpretations of a weighted adjacency matrix's eigenvectors and eigenvalues?

Suppose that I have weighted undirected graph $G$, and the corresponding adjacency matrix which is a symmetric matrix $A$. Suppose that the edge between node $i$ and $j$ has weight $w_{ij}$, then $$ ...
2
votes
1answer
95 views

Eigen value and Regular Graph (not Strongly Regular graph).

$A,B$ are 2 adjacency matrices of $d$ Regular graphs(not Strongly Regular graphs). I would like to know- 1.Results/ information related to Eigen values of A,B. There is a formula for ...
1
vote
1answer
74 views

Triangles incident to a node i

I'm trying to use some fragment-based measures for a network. Given an adjacency matrix representing a (large) network how do you calculate the number of triangles that are incident to every node i? ...
2
votes
1answer
94 views

Eigen value of principal submatrix.

I was studying "interlacing property" and trying to find out the below fact- $A$ is an adjacency matrix of a $r$ regular graph $G$. $u,v \in G $;$u,v$ are not similar vertices. $B$ is the ...
3
votes
0answers
79 views

Is there an easy way to realize a graph (i.e. get adjacency matrix) from a fundamental cut-set or loop matrix?

I am looking to realize a graph (i.e. write down its adjacency or incidence matrix) given a fundamental cut-set matrix or loop matrix (with respect to an arbitrary spanning tree). Is there some ...
0
votes
0answers
79 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 ...
1
vote
0answers
56 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 \mathbb{R}^{...
1
vote
0answers
29 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
63 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
1answer
55 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 ...
4
votes
1answer
64 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
145 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 ...
2
votes
0answers
141 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
127 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
117 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
27 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 ...
19
votes
1answer
356 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 ...
13
votes
4answers
829 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 ...
1
vote
0answers
36 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
137 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
102 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?
2
votes
4answers
214 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
42 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, ...
2
votes
0answers
71 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
40 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
74 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
89 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
79 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 ...
2
votes
1answer
192 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
101 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
47 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 ...
3
votes
3answers
1k 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
47 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
36 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 $n$...
2
votes
2answers
73 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? ...
4
votes
3answers
911 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?
2
votes
0answers
44 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
38 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
142 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
35 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
147 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 ...
4
votes
0answers
74 views

Question about Szemeredi's regularity lemma and eigenvalues of a graph

In the context of Szemeredi's regularity lemma, is there any way to relate the eigenvalues of the ambient graph with the densities of an $\epsilon$-regular partition? More precisely, if $V(G) = V_{0}...
1
vote
1answer
49 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 ...
1
vote
1answer
132 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
58 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 ...
3
votes
1answer
90 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
484 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. Question. Is it ...
1
vote
0answers
151 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 ...