All Questions
Tagged with spectral-graph-theory linear-algebra
85 questions
21
votes
5
answers
2k
views
The middle eigenvalues of an undirected graph
Let $ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_{2n} $
be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any work or references ...
- 784
10
votes
0
answers
225
views
Cospectral mate of rhombic dodecahedron
I am wondering if the following pair of cospectral graphs was previously known.
The rhombic dodecahedron graph looks like this (graph6 string: 'M?????rrAiTOd_YO?'):
As far as I know, it was previously ...
- 2,339
9
votes
3
answers
3k
views
What happens to eigenvalues when edges are removed?
I am stuck at the following :
Let $G$ be a graph and $A$ is its adjacency matrix.
Let the eigenvalues of $A$ be $\lambda_1\le \lambda_2\leq \cdots \leq \lambda_n$.
If we remove some edges from the ...
- 444
9
votes
3
answers
356
views
Spectrum of orthogonality graph (2)
The orthogonality graph, $\Omega(n)$, has vertex set the set of $\pm 1$ vectors of length $n$, with orthogonal vectors being adjacent.
I am only interested when $4|n$, since otherwise $\Omega(n)$ is ...
- 421
9
votes
1
answer
3k
views
Connection between eigenvalues of matrix and its Laplacian.
Hello!
There are two definitions of graph spectrum:
1) Eigenvalues of adjacency matrix $A$.
2) Eigenvalues of Laplacian of adjacency matrix ($L$).
Different sources offer different properties based ...
- 89
9
votes
1
answer
420
views
Coherence between different ranking methods of a graph's vertices
Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.
Two natural ways of doing it are:
By the degrees.
By the entries in a Perron ...
- 6,962
7
votes
1
answer
412
views
Sum of the absolute eigenvalues of A>=B
Kindly help me to prove/disprove the following statement.
Let $A$ be a symmetric matrix of order $n \times n$ with all the diagonal entry equal to $0$, and other non-diagonal entry equal to $k$ (...
7
votes
1
answer
1k
views
Strategies for bounding the spectral norm of a tensor?
Let $A$ be a symmetric $k$-tensor over a real or complex vector field $W$. We may define its spectral norm $|A|$ by
$$|A| = \sup_{v\in W} \frac{|\langle A,x^{\otimes k}\rangle|}{|x|_2^k}.$$
(...
- 20.2k
7
votes
4
answers
1k
views
Minimum negative eigenvalue of zero-one matrices
The following question must have been answered decades ago.
For $n$ fixed, what is the most negative eigenvalue among all trace zero zero-one matrices (that is, all entries are either zero or one, ...
- 4,679
7
votes
1
answer
641
views
Lower bound on the eigenvalues of the Laplacian
I am looking for a graph for which $2 d_{i} < \mu_{i}$, for some index $i$, where $\mu_{1} \leq \mu_{2} \leq \dots\leq \mu_{n}$ are the eigenvalues of the Laplacian matrix $L(G)$ and $d_{1} \leq d_{...
- 123
6
votes
1
answer
312
views
Determinant of walk matrix for a skew-symmetric matrix of even order
Let $S=(s_{ij})$ be a skew-symmetric integral matrix of order $n$. We only consider the case that $n$ is even. Let $e$ be the all-one vector in $\mathbb{R}^n$. Define the walk matrix $$W(S)=[e,Se,\...
- 437
6
votes
1
answer
515
views
Non-diagonalizability of the adjacency matrix of a directed graph
Let $G$ be a directed graph with no multiple edges or loops and let $P_i$ be its vertices. Let $A$ be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$ if and only if there is a directed ...
- 4,058
6
votes
1
answer
744
views
Relationship between spectral gaps of adjacency and Laplacian matrices of graphs
Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...
- 150
5
votes
1
answer
1k
views
How many distinct eigenvalues does a random graph have?
It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.
But what is known about the ...
- 6,962
5
votes
2
answers
3k
views
Complex Eigenvalues of Directed Graphs
I have been computing eigenvalues of adjacency matrices for several directed (not necessarily strongly connected) graphs and one remarkable property seemed to hold (each graph that I have examined ...
- 83
5
votes
2
answers
1k
views
eigenvalue estimate of the adjacency matrix
The adjacency matrix of a nonempty (undirected) graph has a strictly positive largest eigenvalue $\lambda_\max$. A very easy upper estimate for it can be obtained directly by Gershgorin's theorem:
$$
...
- 3,388
5
votes
1
answer
706
views
What is the largest possible operator norm of a sparse (0,1)-matrix?
Inspired by this question, I was wondering about the following problem:
Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does ...
- 7,633
5
votes
1
answer
678
views
Finding zero-one vectors in the row space of a matrix
Suppose that $M$ is a square matrix with all elements on its main diagonal equal to $1$, and every row containing exactly two off-diagonal elements equal to $-1$; all other elements are equal to $0$. ...
- 23k
5
votes
1
answer
1k
views
The spectrum of the discrete Laplacian
Consider a connected (we define connected components by defining the set of vertices where every vertex has one neighbour) sublattice $V$ of the square lattice $V \subset\mathbb{Z}^2.$
On this we ...
- 53
5
votes
1
answer
1k
views
Intuition on Kronecker Product of a Transition Matrix
Let $T$ be a $N\times N$ transition matrix for a markov chain with $N$ states. Thus $T_{ij}$ is the probability of transition from state $i$ to state $j$ (and thus rows summing to one). Now consider ...
- 1,421
5
votes
2
answers
212
views
colored graph characteristic polynomial
This was asked previously on stackexchange and it was suggested to bring it here where more specialists could see it.
Given the adjacency matrix $\mathbf{A}$ for a simple connected graph, the ...
- 51
5
votes
1
answer
601
views
minimal polynomial for a graph
I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
- 51
5
votes
0
answers
397
views
spectrum of orthogonality graphs
The orthogonality graph $\Omega(n)$ with $2^n$ vertices is the graph with vertex set $\{-1,+1\}^n$, with two vertices being adjacent if and only if they are orthogonal (as vectors in the standard ...
- 421
4
votes
3
answers
2k
views
Spectral radius of a proper subgraph
I came across a Chinese reference in the paper "On the spectral radius of trees with fixed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of ...
- 475
4
votes
2
answers
202
views
Integral roots of circulant matrix
When does the circulant matrix have only integral roots?
For example: all roots of the adjacency matrix of the complete graph $K_n$ are integer, which its adjacency matrix is circulant, but in case ...
4
votes
1
answer
103
views
When do the nonzero eigenvalues of a directed graph Laplacian have the same absolute value?
Question: Let $G$ be a strongly connected directed graph on $n$ vertices with Laplacian $L(G)$. Then $L(G)$ has one zero eigenvalue $\lambda_1=0$ and $n-1$ nonzero eigenvalues $\lambda_2,\ldots,\...
- 145
4
votes
1
answer
464
views
Behaviour of eigenspaces of adjacency matrices after a single change to the graph
Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra ...
- 41
4
votes
1
answer
2k
views
Size of connected components of a graph via its spectrum
I know that we can determine the number of connected components of a graph from the eigenvalues of its Laplacian matrix. My question is:
Is there a way to understand the size of each connected ...
- 5,407
4
votes
2
answers
472
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 without diagonalizing it. The graphs I am interested in are not regular (but ...
- 163
4
votes
1
answer
2k
views
Relation of row sums to largest eigenvalue
I know that the largest eigenvalue of a graph is bounded between the minimal and maximal row sum of the matrix. If I have a $0-1$ symetric matrix (an adjacency matrix) and I know $k$ of the rows have ...
- 133
4
votes
1
answer
256
views
An elementary inequality for graph Laplacians
Let $G$ be an arbitrary graph on $n$ vertices and $\mathcal L$ be its Laplacian.
I need to show that
\begin{equation}\tag{$*$}
\langle \mathcal Lx,\mathcal L(|x|^{p-2}x)\rangle_{\mathbb R^n}\ge 0\...
- 3,388
4
votes
2
answers
399
views
Graphs whose degree vectors coincide for all powers of their adjacency matrices
Let symmetric $A,B \in \{0, 1\}^{n \times n}$ denote the adjacency matrices of two simple graphs. Further let $\mathbf{1}$ denote the all-one-vector.
Now assume that $A^k \mathbf{1} = B^k \mathbf{1}$ ...
- 340
4
votes
0
answers
148
views
Derivative of characteristic polynomial of a graph and derivative of characteristic polynomial of a vertex-deleted subgraph have a common root
Let $G$ be a simple graph and $G-i$ be one of its vertex-deleted subgraphs. Let $\phi(G,x)$ and $\phi(G-i,x)$ be the characteristic polynomials of $G$ and of $G-i$ respectively, with respect to their ...
- 327
4
votes
0
answers
141
views
algebraic connectivity of a tree
Suppose that $T$ is a tree with $n$ vertices and $L$ is the Laplacian matrix of $T$ and $0=\mu_1 \leq \mu_2 \leq \cdots \leq \mu_n$ are laplacian eigenvalues.
I think the multiplicity of $\mu_2$ can ...
- 221
4
votes
0
answers
126
views
An inequality from the "Interlacing-1" paper
This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132)
For the argument to ...
4
votes
0
answers
189
views
Relaxation = absorption?
Let $A$ be a stochastic matrix, that is, the entries are non-negative and each row adds to $1$. Assume that it is primitive, that is, $A^n$ has only positive entries for sufficiently large $n$. We ...
- 41
3
votes
1
answer
166
views
The spectral radius of a modified graph
Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$.
This situation has many different names: $G$ is called the cone or the ...
- 6,962
3
votes
1
answer
148
views
Spectrum of the adjacency matrix of certain directed graphs
For an undirected graph $G$, its adjacency matrix $A_G$ is symmetric, and by the (consequence of) spectral theorem, each of its Jordan blocks has size $1$. This is not true for a general directed ...
- 161
3
votes
1
answer
770
views
Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?
Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$.
But do we have any quantitative ...
- 1,893
3
votes
1
answer
427
views
Graph of Grassmannian
Let p be an integer, and let G be the graph $(V=Gr(k,\mathbb{F}_q ^n),E)$
where: $Gr(k,\mathbb{F}_q ^n)$ is the set of all subspace of $\mathbb{F}_q$ of dimension k, and $E=\{ W_1,W_2 \in V | W_1\...
- 33
3
votes
1
answer
2k
views
equitable partitions
It is well known that if $\pi$ is an equitable partition of a graph, then the spectrum of the corresponding partition matrix is a subset of the spectrum of the graph's matrix (where the matrix can be ...
- 6,962
3
votes
1
answer
271
views
Local-Global Principle in Graph Spectrum
The question is a bit vague, but any ideas/directions will be appreciated.
Let us fix an $n$-vertex $d$-regular graph $G=(V,E)$. As I understand it, the eigenvalues of the adjacency matrix $A$ of $G$ ...
- 949
3
votes
0
answers
919
views
Principal eigenvector of non-negative symmetric block matrix is approximated by a linear combination of the principal eigenvectors of the blocks
Let $
M \in \mathbb{R}^{n \times n} =
\begin{bmatrix}
A & B \\
B^T & C
\end{bmatrix}
$ for some nonnegative $A \in \mathbb{R}^{k \times k}, B \in \mathbb{R}^{k \times n-k}, C \in \mathbb{R}^{n-...
- 123
3
votes
0
answers
825
views
A problem on graph theory and complex numbers!
Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that
$$
||z_1||=\ldots = |...
3
votes
0
answers
156
views
inverse M-matrix times mixed-sign vector
Recently a colleague and I came across this unusual phenomenon.
Take $M\in\mathbb{R}^{n\times n}$ a singular irreducible M-matrix, and $b\in\mathbb{R}^{n}$ such that the system $Mx=b$ is solvable (so,...
- 20.2k
2
votes
1
answer
221
views
Are there good ways of relating a minor to the full determinant?
Say $A$ is a $(n-1)\times (n-1)$ matrix and we augment it by a $n^{th}$ row and a column and get a $n \times n$ matrix $B$. Is there a nice way to relate $det(B)$ and $det(A)$ and the added row and ...
- 1,893
2
votes
1
answer
238
views
Laplacian spectrum of $2-$lifts of graphs
We know that a $2-$ lift of a graph is specified by a $\pm 1$ assignment on the edges of the graph ( given as a signing matrix) denoting which edge is to be duplicated by the identity permutation on ...
- 1,893
2
votes
1
answer
94
views
Testing for equal characteristic polynomials using a single determinant calculation
Let $A_1,A_2$ be $n\times n$ symmetric matrices over $\{0,1\}$, and let $p_1, p_2$ be their respective characteristic polynomials over the rationals.
If $p_1 \ne p_2$, then there is some positive ...
- 37.7k
2
votes
1
answer
133
views
Is the sum of the circulant matrix with a super upper triangular matrix diagonalizable?
By the circulant matrix $C$ in $M_n(\mathbb{R})$, we mean that
$$C=[e_n|e_1|\cdots|e_{n-1}]$$ where $e_1,\cdots,e_n$ are the standard basis vectors in $\mathbb{R}^n$. It is well-known that
$$C=\...
- 4,058
2
votes
1
answer
1k
views
About distinct eigenvalues of a graph
if a graph with adjacency matrix $A$ and Laplacian $L$ has $k$ distinct eigenvalues then does this fact naturally help define or prove existence of a polynomial $p$ of degree $k-1$ such that $[p(A)]_{...
- 1,893