Tagged Questions
1
vote
0answers
35 views
Proof is needed for a lower bound of the maximal eigen-value of a non-negative, irreducible, integer matrix
$A$ is a non-negative, integer, irreducible, $m$ by $m$ matrix. It is well known (Perron-Frobenius) that $A$ has a positive eigen value (denote it by $\lambda$) with a positive eigen vector ($x$). It ...
1
vote
1answer
34 views
Godsil & Royle, Theorem 9.5.1: Extension for digraphs?
I was wondering if there is an extension to digraphs for Theorem 9.5.1 in Godsil & Royle's Algebraic Graph Theory.
The Theorem can also be found in Willem Haemers paper Interlacing Eigenvalues ...
0
votes
0answers
30 views
Signed incidence matrix determinant and spanning tree
$G=(V,E)$ is a directed graph with $n$ vertices and $m$ edges, $n \geq 2$. $F \subseteq E$ and $|F| = n -1$.
$Q$ is the $n \times m$ signed incidence matrix of $G$ over indeterminates $x_e$ with $e ...
1
vote
1answer
73 views
How can i convert to the undirected matrix to an directed matrix?
Here A square matrix and first figure(AU) shows undirected connection graph and second one shows directed one.Assume that only i have Au metrix and how can i create Ad metrix from Au matrix in ...
2
votes
1answer
74 views
Global solution for spectral clustering
I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...
1
vote
0answers
23 views
finding the decomposition of Laplacian matrix with position of zero elements unchanged
I'd like to know whether it's possible to find the decomposition of a Lapalacian matrix $A$
$B^TB = A$
where $B$ has the same dimension with $A$ and the position of zero elements in $B$ is the same ...
0
votes
1answer
64 views
Prove $MM^t=A+kI$ for matrices associated to graphs
How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices?
It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), ...
1
vote
1answer
54 views
Spectrum of the cycle graph $C_n$
I am trying to find out the spectrum (the collection of eigenvalues) with their multiplicities of the cycle graph $C_n$. Assuming that $X=\pmatrix{x_1\\x_2\\\vdots\\x_n}$ is the eigenvector, by ...
2
votes
0answers
81 views
Low-rank approximation to the Graph Laplacian matrix of a regular grid.
As mentioned in the title, does anybody know any methods of efficient low-rank approximation $LL^T$ to the Graph Laplacian matrix $A$ corresponding to a square lattice? (except PCA)
4
votes
1answer
120 views
What is the difference between first and second right eigenvectors of a row stochastic matrix and their meaning?
In an $n\times n$ non negative row stochastic matrix (rows sum up to 1).
The entries of the stochastic matrix I have represent directed links between countries.
Why is the first right eigenvector a ...
9
votes
1answer
233 views
Why does this matrix have 3 nonzero distinct eigenvalues
Consider the $n \times n$ matrix $$A=\left[
\begin{array}{cccc}
0 & 1 & ... & 1 \\
1 & 0 & & 0 \\
\vdots & & \ddots & \\
1 & 0 & & 0%
...
19
votes
5answers
386 views
Motivation for spectral graph theory.
Why do we care about eigenvalues of graphs?
There must be some reason. There is an entire mathematical discipline about them.
I always assumed that spectral graph theory is an extension of graph ...
1
vote
2answers
89 views
A multiple-part question about interpreting powers of the adjacency matrix of a graph
Suppose that we have a group of six people, each of whom owns a communication device. We define a $6\times 6$ matrix $A$ as follows: For $1\le i\le 6$, let $a_{ii}=0$; and for $i\ne j$, ...
4
votes
1answer
59 views
Tensor product of graphs
Let $G$ and $H$ be graphs, then connect two elements $(g, h)$ and $(g', h')$ of $G\times H$ if and only if $gg'\in G$ and $hh' \in H$.
Does the tensor product of graphs have to do with the tensor ...
1
vote
2answers
115 views
A property of incidence matrix of a graph
Let $G$ be an oriented graph with incidence matrix $Q$, and let $B:=[b_{ij}]$ be a $k\times k$ sub-matrix of $Q$ which is non-singular. Can there exist two distinct permutations $\sigma$ and ...
1
vote
0answers
57 views
Is there a simple interpretation of the eigenvectors of a graph (visualizable?)?
I want to understand eigenvectors obtain from graphs (adjacency matrices) in an analogous way as they are interpreted from principal component analysis of a set of images, which is easy:Eigenfaces ...
0
votes
2answers
88 views
How to test if a graph is fully connected and finding isolated graphs from an adjacency matrix
I have large sparse adjacency matrices that may or maybe not be fully connected. I would like to find out if a matrix is fully connected or not and if it is, which groups of nodes belong to a ...
0
votes
0answers
37 views
What is the name of the matrices which reorder edges in an adjancency so that they are closer to the diagonal? (modularity/structure)
I have seen adjacency matrices presented where the edges formed box like formations along the diagonal (not block matrices). This helped view the modularity and community structure of the group of ...
2
votes
1answer
105 views
Intuitive interpretation of the adjacency matrix as a linear operator.
Naturally we can describe graphs via tables of "yes there is an edge" or "no there is not" between each pair of vertices, so the definition of an adjacency matrix is easily understood. Thinking of ...
6
votes
2answers
123 views
Graphs with commuting adjacency matrices
Let A and B be adjacency matrix of two undirected simple graphs. Can we assign some combinatorial interpretations to this pair of graphs if A and B commute?
2
votes
0answers
35 views
maxcut and the minimal eigenvalue
For an adjacency matrix $A$ that represent a graph $G=\langle V,E\rangle$, I need to show that the maxcut is bounded by:
$$
\mathrm{maxcut} \leq \frac{1}{2}|E| - \frac{|V| \lambda_{\min}(A)}{4},
$$
...
4
votes
1answer
116 views
A regular graph of degree k is connected if and only if the eigenvalue k has multiplicity one
I saw this sentence in Wikipedia:
A regular graph of degree k is connected if and only if the eigenvalue k has multiplicity one
I couldn't find a proof to that statement - can someone address me to ...
2
votes
1answer
169 views
Sum of the eigenvalues of adjacency matrix
Let $G$ be a simple undirected graph with $n$ vertices, and let $A_G$ be the corresponding adjacency matrix. Let $\kappa_1, \dots , \kappa_n$ be the eigenvalues of the adjacency matrix $A_G$. I have ...
0
votes
1answer
99 views
When does the adjacency matrix of a graph have an eigenvalue zero?
When does the adjacency matrix $A$ of an undirected graph $G$ not have full rank? Is there any intuition to understanding this?
2
votes
3answers
144 views
The inverse of the adjacency matrix of an undirected cycle
Is there an expression for $A^{-1}$, where $A_{n \times n}$ is the adjacency matrix of an undirected cycle $C_n$, in terms of $A$?
I want this expression because I want to compute $A^{-1}$ without ...
1
vote
1answer
108 views
Relationship Between Two Adjacency Matrices
Given a graph $A$ with nodes $p_{1},p_{2},...,p_{n}$, let $\{A^{*}\}$ be the set of all graphs isomorphic to $A$. Consider a graph $Q$ with vertices $a,b,$ and $c$ where there are three edges between ...
2
votes
1answer
64 views
Dynamical changing of an eigenvector
Consider a matrix $A\in\mathbb{R}^{n\times n}$. One of the eigenvalues of $A$ is zero and all the others are positive. Suppose $w\in\mathbb{R}^n$ is an eigenvector with the zero eigenvalue, i.e,
...
1
vote
2answers
214 views
How does the Kronecker delta work for matrices?
I am trying to understand the effect of the kronecker delta function in this expression $\sum_{i,j}(1+\delta_{i,j})M_{ij}$ given that $M$ is a matrix with real-entries.
How does this operation work!?
...
5
votes
3answers
403 views
Eigenvalues of a bipartite graph
Let $X$ be a connected graph with maximum eigenvalue $k$. Assume that $-k$ is also an eigenvalue. I wish to prove that $X$ is bipartite.
Now if $\vec{x}=(x_1,\cdots ,x_n)$ is the eigenvector for ...
2
votes
1answer
125 views
Connectedness of a regular graph and the multiplicity of its eigenvalue
Suppose $X$ is a $k$-regular graph with adjacency matrix $A$. I wish to show that if $k$ has multiplicity $1$ as an eigenvalue of $A$ then $X$ is connected.
By way of contradiction I assume that X is ...
0
votes
1answer
49 views
Question related to a proof about the multiplicity of some eigenvalues
I have a question related to Lemma 4.2 from this pdf (which is, btw quite a nice exposition of Hoffman Singleton work on the classifications of Moore graphs of diameter 2 and 3.)
We are given a $n ...
2
votes
1answer
74 views
Possible relation between spectra bounds of two matrices
A Laplacian matrix $L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, \begin{equation}
l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\
-w_{ij} & ...
2
votes
1answer
159 views
interpreting the power of adjacency matrix
Given a directed graph $G$, and let $A$ be $G$'s adjacency matrix, whose $(i,j)$-entry is 1 when there is an edge from $i$ to $j$.
Is there any interpretative meaning of the $(i,j)$-entry of the ...
3
votes
1answer
77 views
is there a way to find or upper bound the largest eigenvalue of the following matrix?
I have a matrix $A \in \{0,1\}^{n \times n}$ -- i.e. a matrix with 1s and 0s only.
Is there a way to find or upper bound its largest eigenvalue?
I have a feeling it is related to connectivity of ...
4
votes
1answer
108 views
Eigenvalues of a special block matrix associated with strongly connected graph
Definition
Let $G=(V,E,A)$ be a strongly connected directed graph, where $V=\{1,2,...,n\}$ denotes the vertex set, $E$ is the edge set, and $A$ is the associated adjacent matrix with $0-1$ weighting, ...
4
votes
0answers
70 views
Extension of Cheeger's inequality with distinguished vertices
The standard Cheeger's inequality for graph $G$ states that
$\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$
where $\lambda$ is the second smallest eigenvalue of the normalized ...
3
votes
0answers
165 views
Finite dimensional function space “different” from $\mathbb{R}^n$ generically
If you pick a random vector in $\mathbb{R}^n$ with some fixed basis, there is no special relationship between components. The relationship between the $1^{st}$ component and the $5^{th}$ component is ...
1
vote
1answer
250 views
How to prove that a matrix is positive definite?
Let $L$ be a Laplacian matrix of a strong connected and balanced directed
graph. Define
$$
L^{s}=\frac{1}{2}\left( L+L^{T}\right) .$$
Let $D$ be a diagonal matrix with
$$
D=\begin{bmatrix}
d_{1} & ...
0
votes
2answers
219 views
Why is every irreducible matrix with period 1 primitive?
In a certain text on Perron-Frobenius theory, it is postulated that every irreducible nonnegative matrix with period $1$ is primitive and this proposition is said to be obvious. However, when I tried ...
3
votes
2answers
152 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
75 views
How matroids can help me locating trees inside a graph?
Background
I am working on a project at present involving graph analysis. I basically need to mathematically model trees inside my graph. How can this be done using Matroids?
What I am looking for
...
0
votes
1answer
60 views
Diffusion kernels as stochastic processes
I'm trying to refresh my memory on diffusion kernels, and am reading this paper. I don't understand the derivation of equation 11 on page 3.
EDIT: I don't understand how the two equations:
...
1
vote
0answers
132 views
Eigenvalues of regular graphs
Could someone give me a hint for exercise 2.iii of these lecture notes? The exercise asks to show that a $k$-regular undirected graph (without loops) whose adjacency matrix $A$ has eigenvalues ...
2
votes
3answers
221 views
vectors in graph theory
I am reading from a book (Combinatorial optimization by Schrijver) and at one point I am not clear as to how his arguments follow. Consider the following:
Let $G(V,E)$ be an undirected graph and let ...
7
votes
1answer
183 views
Spielman's proof of graph connectivity
I use Spielman's lectures on course Spectral Graph Theory
I have few question regarding Lecture 2. The Laplacian, especially Lemma 2.3.1 (Graph connectivity). Please, help me to make it a little bit ...
2
votes
1answer
239 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 ...
4
votes
2answers
173 views
Graphs with eigenvalues of large multiplicity
For a strongly regular graph, there are exactly 3 eigenvalues, all nonzero (I believe). One has multiplicity 1, which means the other two have pretty high multiplicities. There are tables that give ...
-2
votes
1answer
225 views
Nullity of line graph of a tree is at least $1$ [closed]
$\mathbf{A}$ is adjacency matrix of line graph $T$ and $T$ is a tree.
I want to show that $\operatorname{null}(\mathbf{A})\ge 1$. Please advise me.
2
votes
1answer
377 views
Is there any relation between the principal eigenvector of the original matrix and its inverse?
This question pop'd up when I was studying graph.
I am thinking about the relation between principal eigenvector of adjacency matrix $A$ and its inverse $A^{-1}$, do they have any relation?
2
votes
1answer
151 views
Does this matrix have a name?
If $L$ is a lower triangular matrix of ones, does the following matrix have a special name?
$$A = \left(\begin{matrix}L & -L \\
-L & L \end{matrix}\right)$$
