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
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
20 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
37 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 ...
3
votes
3answers
150 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 ...
3
votes
2answers
218 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
1answer
33 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
31 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
10 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 ...
1
vote
1answer
58 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 ...
1
vote
1answer
74 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
39 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? ...
3
votes
0answers
39 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
63 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
15 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
1answer
50 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 ...
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 ...
0
votes
0answers
27 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
46 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
49 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
64 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
26 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 ...
2
votes
0answers
90 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 = ...
0
votes
0answers
24 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 ...
1
vote
1answer
65 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 ...
0
votes
0answers
26 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 ...
2
votes
1answer
42 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
111 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
22 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
65 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?
2
votes
3answers
152 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 ...
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 ...
1
vote
1answer
34 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, ...
3
votes
1answer
492 views

Does an $n\times n$ adjacency matrix of a scale-free network graph have $n$ distinct eigenvalues?

Question updated Suppose that I have an $n\times n$ adjacency matrix $\mathbf{A}$ of a simple graph $G$ where the entry $(i,j)$ represent the number of edges between node $i$ and $j$ in $G$. Note ...
1
vote
0answers
27 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 ...
1
vote
1answer
45 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?
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 ...
4
votes
1answer
69 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
41 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
51 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 ...
0
votes
0answers
30 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 ...
5
votes
2answers
476 views

A finite graph G is $d$-regular if, and only if, its adjacency matrix has the eigenvalue $λ = d$

Show that a graph $G$ finite with $n$ vertices is $d$-regular if, and only if, the vector with all the coordinates equals to 1 is eigenvetor from eigenvalue $λ = d$ from the adjacency matrix $A$ ...
2
votes
0answers
88 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 ...
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 ...