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

3
votes
1answer
29 views

How to perturb an adjacecny matrix in order to have the highest increase in spectral radius?

Let's suppose I have a generic directed graph $G$ and it's adjacency matrix $A$. I can add an arc wherever I want in the graph. (i.e. perturb the matrix A changing a single 0 into a 1). Where should ...
0
votes
1answer
35 views

Relation between edge expansion of graph and sparsity

I was going through the lectures of Graph Partitioning and Expanders - Stanford Online. In lecture 1, near the end of page 5, I came across this inequality for regular graphs: $$\phi(S) \leq h(S) \leq ...
3
votes
0answers
40 views

What do we know about inverses of matrices which are “like” Laplacians of graphs?

Consider the Laplacian $L$ of a bipartite graph. Is there any generic understanding we have about what $1/(z-L)$ looks like? [say $z > \lambda_\max(L)$)] You can consider variations of $L$ like ...
3
votes
0answers
30 views

How networks with high largest eigenvalues are more robust?

In the literature, it sometimes indicates that network with high value of largest eigenvalue (either adjacency matrix or its Laplacian counterpart) are more robust. Robustness here is relevant to link/...
0
votes
1answer
36 views

Construction of graph Laplacian

I have a weighted undirected graph, and all the edge-weights are non-negative. According to the definition of the graph Laplacian matrix, $L=D-W$. In literature, I found that $D$ is known as degree ...
2
votes
0answers
53 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
64 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
68 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
75 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
98 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
81 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
57 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
64 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
65 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
148 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
143 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
134 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
121 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
28 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
366 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
873 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
139 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
103 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
217 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
75 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
91 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
80 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
204 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
103 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
53 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
952 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
46 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
146 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
152 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
75 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 ...