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
29 views

Construction of a Strongly Regular Graph which has regular subgraphs in all iteration.

Notation and Defination: $G$ is a Strongly Regular Graph( not a complete , cycle graph) with Every two adjacent vertices have $\lambda$ common neighbours. Every two non-adjacent vertices have ...
1
vote
1answer
41 views

Computing eigenvalue of the adjacency matrix of a path

Let $A\in \{0,1\}^{n \times n}$ be the adjacency matrix of a path of length $n$, i.e. having ones on the two off-diagonals, and zeros elsewhere. How does one compute the eigenvalues of this? I know ...
1
vote
0answers
23 views

Eigenvalue of Block matrix: Adjacency of complete bipartite Graph

Let $A\in \{0,1\}^{mn \times mn}$ be the adjacency matrix of a complete bipartite graph with $m$ and $n$ vertices each, i.e. let $A$ be the matrix consisting of two blocks $A_1\in \{0,1\}^{m \times ...
2
votes
2answers
26 views

Confusion between spectral radius of matrix and spectral radius of the operator

The adjacency matrix $A(G)$ of an infinite undirected graph $G$ is considered as a bounded self-adjoint linear operator $A$ on the Hilbert Space $l^2(G)$ (last section of ...
-3
votes
1answer
42 views

Characteristic polynomial of a block matrix

Let $A$ be an $n\times n$ symmetric matrix whose diagonal are is covered by zero blocks (square, but not of a fixed size) and all other entries are $1$ (one). How can I find its Characteristic ...
1
vote
0answers
34 views

Highest eigenvalues/vectors of graph laplacian

In page 8 of the paper Laplacian Eigenmaps for dimensionality reduction and Data Representation it reads: Standard methods show that the solution is provided by the matrix of eigenvectors ...
1
vote
0answers
15 views

Size of intersection of balls on non-ameanable graphs

Let $G$ be a vertex-transitive non-ameanable graph and let $B(x,n)$ be the ball of radius $n$ centered on the vertex $x$. I am interested in estimates on the cardinality of the following set, ...
3
votes
0answers
11 views

how to have the highest increase in eigenvelue of an adjacecny matrix adding a single arc?

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
31 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 ...
0
votes
0answers
11 views

The image of a a vector in the edge space when multiplied by it's incidence matrix.

Consider a graph $G=(V,E)$ and it's incidence matrix $M$. Let $\textbf{x}$ be the characteristic vector for a standard basis vector in $\mathcal{E}$ (a vector corresponding to the one element edges ...
3
votes
0answers
36 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 ...
0
votes
0answers
3 views

PageRank metaphor as suspended unlimited capacity pools

What do you think about my metaphor of the centrality measure PageRank? PageRank is an algorithm for evaluating node centrality: it's a function $f:G \to R^n$ where $n$ is the number of nodes in the ...
3
votes
0answers
27 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 ...
0
votes
1answer
21 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
42 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
37 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 ...
1
vote
0answers
34 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 $$ ...
0
votes
0answers
13 views

Algebraic connectivity (normalized Laplacian): does the non-weighted instance define the upper bound for the weighted graphs with the same topology?

I am not a mathematician but I use a lot of maths. I came across some empirical evidence that the algebraic connectivity (2nd smallest eigenvalue of the random walk normalized laplacian matrix) of ...
2
votes
1answer
82 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
44 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
70 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
43 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
66 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
21 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
22 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
51 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
28 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
47 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
51 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
75 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
31 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
25 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 ...
2
votes
0answers
93 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
69 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
56 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
23 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 ...
8
votes
0answers
125 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
23 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
72 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
51 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
35 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
156 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
35 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
29 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
33 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
48 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
74 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
46 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
73 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
53 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 ...