Questions tagged [graph-laplacian]
A simple graph has a symmetric matrix L = D - A associated with it called the Laplacian matrix, where D is the diagonal matrix of degrees and A is the adjacency matrix, often studied for its spectrum (eigenvalues).
0
votes
1answer
16 views
What is the normalized graph matrix if the row-sum of proximity matrix is zero?
Let $S \in \mathbb{R}_{\ge 0}^{n \times n}$ be the proximity (or similarity) matrix of a graph, e.g.
$$
S = \left[ \begin{matrix}
0 & 0.9 & 0.3 \\
0.9 & 0 & 0.4 \\
0.3 & 0.4 & ...
0
votes
0answers
28 views
Why is normalisation of a Laplacian matrix defined as $L - I$?
I have a piece of code that computes the Laplacian matrix using $I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$, that is, it computes the symmetric normalised Laplacian. This Laplacian is not defined when $...
0
votes
1answer
33 views
When do the eigenvectors of a Laplacian matrix form a basis?
Eigenvectors do not always form a basis. When do the eigenvectors of a Laplacian matrix form a basis? When the associated adjacency matrix is symmetric? Why?
0
votes
0answers
6 views
A proof for the existence of $n$ non-negative eigenvalues of the Graph Laplacian
For the Graph Laplacian, we have
$$L = D - W $$
Where $D$ is the degree matrix and $W$ is the weighted adjacency matrix. Can anyone provide a proof for the existence of $n$ non-negative eigenvalues ...
0
votes
1answer
25 views
Explanation in a step of proving the positive semidefinite property of the graph Laplacian
Here, $W$ is the adjacency matrix, $D$ is the diagonal matrix with entries $D_{ii} = \sum_{j \neq i} w_{ij} $. I'm not so sure of the second step from the last line. In particular, I can't see how
$$...
0
votes
1answer
23 views
Basic questions about Laplacian matrices in graph theory
In graph theory, given a graph $G$ with $n$ nodes and an edge set $E$, the Laplacian matrix is defined as the difference of the degree matrix and the adjacency matrix:
$$
L=D-A \tag{1}
$$
As shown ...
1
vote
1answer
36 views
Connectedness and invertibility of Laplacian matrix
Context:
In the context of circuit theory and graph theory, suppose we have a graph $G,$ then the Laplacian (Kirchhoff) matrix $L$ is defined as follows:
$$
L = D-A \tag{1}
$$
where $D$ is the ...
2
votes
1answer
35 views
Largest eigenvalue of the Laplacian Matrix in an odd cycle
Problem:
We have an odd cycle, $C_{2n+1}$, for $n \geq 1$, and the edges $e \in E\ $ have all one weights $w \in \{1\}^E$.
Question: Denote the largest eigenvalue of the Laplacian matrix of this ...
1
vote
0answers
38 views
Matrix product and eigen values
Is there any relationship between eigenvalues(or spectrum) of graph Laplacian matrix and the eigenvalues of the product of a real symmetric matrix and the Laplacian matrix?
My problem at hand is as ...
0
votes
0answers
19 views
Product of a positive semi definite matrix with an indefinite matrix
I see from my examples that the product of a positive semidefinite matrix(graph Laplacian) and an indefinite matrix (real matrices), comes to be a positive semidefinite matrix. Is there a proof for ...
0
votes
0answers
10 views
What would be the restrictions to diagonalization of this type transformation of Laplacian matrix?
This question is a little specific. I have read about graph theory and saw in one place the following transformation of an Laplacian matrix $L$:
\begin{eqnarray}
ULW=\begin{bmatrix}
-(l_{11}-l_{22})&...
2
votes
0answers
26 views
Algebraic Connectivity of Trees
Question: In a paper I'm reading it makes the following statement: "It is known that among all trees on $n$ vertices the algebraic connectivity is maximized for a star". I've searched around and I can'...
0
votes
0answers
18 views
Monotone eigenvector of the normalized Laplacian
Let $u_0 \geq u_1 \geq \cdots \geq u_{n-1}$ be positive numbers and define a matrix $n\times n$ by $M_{i,j} = u_{\left|i-j\right|}$ for all $i,j$.
Let $L = I - D^{-1/2}MD^{-1/2}$ be the normalized ...
0
votes
0answers
44 views
Eigenvalues for matrix with particular structure
I have a square matrix of the form:
$$
\begin{pmatrix}
a & b \\
-b & a
\end{pmatrix}
$$
where
$$
a = \begin{pmatrix}
D1 & t & 0 & 0 & t & 0 \ldots t \\ t&D2&t&...
0
votes
0answers
26 views
A relation between Laplacians
I'm currently working on the following problem, that consists in establishing conditions (if any) for the existence of two weighted Laplacian matrices that verify a given relation. I make the ...
0
votes
0answers
73 views
Lower bound on the nonzero Laplacian eigenvalue with the smallest real part
Consider a directed graph with $n$ vertices. The graph is not assumed to be connected, and therefore the multiplicity of the eigenvalue 0 may be greater than 1. I am looking for a nonzero lower bound ...
-1
votes
1answer
28 views
How to understand poles and zeroes intuitively?
I am currently studying root locus method to analyze the stability of a given system which depends mostly on the poles of a given characteristic equation. However for better understanding I want to ...
0
votes
2answers
183 views
Why is the largest eigenvalue of a laplacian matrix equal to the number of nodes in the graph?
I've been posed the following question:
The spectrum of the Laplacian matrix $Q$ of the complete graph $K_{N}$ on $N$ nodes is:
$1^{[1]}$ and $N^{[N-1]}$
$0^{[1]}$ and $(N-1)^{N-1}$
$1^{[1]}$, $0^{[...
1
vote
0answers
60 views
Why does the normalized graph Laplacian give negative square root at off-diagonal cells?
The normalized graph Laplacian fits the relationship $L=D^{-1/2}(D-A)D^{-1/2}=I-D^{-1/2}AD^{-1/2}$, where $I$ is the identity matrix, $D^{-1/2}$ is the diagonal matrix with $D(i,i)=\frac{-1}{\sqrt{n_{...
1
vote
1answer
457 views
Laplacian of a directed weighted graph
I know that for a simple undirected graph $\mathcal{G}(V,E) $ the Laplacian matrix $L$ is defined as:
$$ L:=D-A$$ where $D$ is the degree diagonal matrix and $A$ is the adjacency matrix of $\mathcal{G}...
0
votes
1answer
119 views
Laplacian matrix of the weighted graph
The weighted Laplacian matrix element is given by
\begin{align}
L_{ij} \; = \; \Big( \sum_{k} w_{ik} A_{ik} \Big) \, \delta_{ij} - w_{ij} A_{ij}
\end{align}
$A_{ij}$ is the adjacency matrix element ...
0
votes
0answers
19 views
How to minimize laplacian matrix?
Given $\sum_{i,j=1}^{N_{t}} w_{t,i,j}{\|{a_{t,i}}^{s}-{a_{t,j}}^{s}\|}^{2}=Tr({A_t}^{s}L_t{A_t}^{s'})$
where $ L_{t}=D_{t}-W_{t}$ where $D_{t}$ is the diagnol matrix whose diagnol elements are the ...
2
votes
1answer
61 views
Is it possible that $L+L^T$ is a positive definite matrix?
If $L$ is a nonsymmetric Laplacian matrix, is it possible that $L+L^T$ is a positive definite matrix?
1
vote
1answer
107 views
Moore-Penrose psuedoinverse of Laplacian
I am trying to attain the Moore-Penrose psuedoinverse of a a very large, sparse, rank degenerate, singular, and square matrix. (75000x75000, near rank) I realize the inverse will be very dense. I have ...
0
votes
1answer
78 views
Proof that the Laplacian matrix of a complex weighted graph is positive semi-definite.
In graph theory the Laplacian matrix, $L$, is given by
$$L=D-A$$
For simple graphs $D$ is a diagonal matrix where
$$D_{ii}=deg(v_i)$$
and $A$ is its adjacency matrix.
Suppose we now consider the ...
2
votes
1answer
187 views
Why the second smallest eigenvalue of the Laplacian of a tree is $\leq1$
I know that the second smallest eigen value of the Laplacian of a star with $n>2$ is $1$.
I want to show the vice versa, i.e., if the second smallest eigen value of a tree is $1$ then the tree is ...
0
votes
0answers
20 views
Does anybody know how to compute the Laplace Matrix for Weighted Directed Graph?
I have found generalisation of graph Laplacian for (a) weighted, and (b) directed graph, but not for both. I would like to use this to perform Spectral Clustering on network of objects characterised ...
0
votes
0answers
28 views
What information the i-th eigenvector and i-th eigenvalue of Laplacian encodes?
If the the second smallest eignevalue informs about the algebraic connectivity, l'm wondering what the i-th eigenvalue and eigenvectors encodes ? what information l can derive?
such that i=[2,n] ...
1
vote
1answer
67 views
Determinant of Laplacian removing $2$ (or more) rows and columns
Based on Kirchoff's theorem, I'm wondering what can be said about the determinant of the Laplacian, after removing the columns and rows corresponding to two vertices. The motivation would be to see if ...
3
votes
1answer
68 views
Why eigenvalues of a symmetric matrix with zero row sum are not affected with this special manipulation?
Let $A$ with row vectors $a_1$, $\ldots, $ $ a_N$ be an $N \times N$ real symmetric matrix with zero row sum. For example,
$A= \begin{bmatrix} a_1 \\a_2 \\ a_3 \end{bmatrix} = \begin{bmatrix} 2 & ...
1
vote
0answers
45 views
SVD with Laplacian regularization and $L_{1,2}$ group-norm
I have a data matrix of the form $X \in \mathbb{R}^{n\times m}$ where the $n$ rows have spatial relationships and $m$ columns have temporal relationships. I am trying to model an objective function of ...
0
votes
2answers
186 views
Prove that grounded Laplacian/reduced conductance matrix is non-singular
Consider a simple, connected graph $G = (V,E)$ with $|V| = n $.
The Laplacian matrix $L$ is defined as $L = D - A$, where $D$ is the diagonal matrix with $D_{ii} = \text{degree of node $i$}$, and $A$ ...
2
votes
1answer
146 views
Does the largest eigenvalue give the order of the largest connected component?
I've been learning about the Laplacian of a graph, and all the cool things you can tell from it. For example, I know the smallest eigenvalue is always 0, and the mulitiplicity of that zero eigenvalue ...
2
votes
0answers
60 views
Does a Laplacian matrix characterize a Graph?
Given a Laplacian matrix can we have more than one graphs that has the given Laplacian?
Also is there any work on how to construct a graph, given its corresponding Laplacian matrix?
1
vote
2answers
96 views
What is the origin of negative eigenvalues for Laplacian matrix?
I'm trying to write some small clustering program in Python. I've constructed the Laplacian matrix L = D - W using symmetric adjacency matrix W and diagonal degree matrix D, D_ii = sum_j W_ij. Then I ...
1
vote
0answers
12 views
Proving an inequality on commute times of two different weight functions
Let $G = (V, E)$ be an undirected, connected graph of $n$ vertices, ordered from 1 to $n$. I have two weight functions $w_1, w_2 : E \to \mathbb{R}$, where $w_1$ is just given by $w_1(e) = 1$, $\...
1
vote
1answer
54 views
Is the following fact for laplace matrix true? And how to prove it?
$A$ is a matrix with $0$ or $1$ element. $L$ is the lapace matrix of $A$. $S$ is a real vector, we define $\mathbb{sign}(S) = [\mathbb{sign}(s_1),...,\mathbb{sign}(s_n)]^T$. I find the following fact ...
2
votes
2answers
127 views
Is the Perturbed Laplacian Matrix positive Definite?
Let $\mathcal{L}$ be the Laplacian matrix of a connected, undirected and unweighted graph $\mathcal{G}$ with $n$ vertices, and let $\Delta \in \mathbb{R}^{n\times n}$ be a diagonal matrix with at ...
2
votes
0answers
115 views
Sherman-Morrison formula for non-invertible bmatrices
I am trying to find an expression for inverse of the following matrix
$(L+\frac{1}{n}J)$
Where $L$ is the Laplacian of a simple, connected graph with $n$ vertices and $m$ edges, and $J=11^T$ is ...
1
vote
2answers
46 views
how to prove multiplicity of the $\mu _2$ is one
graph $G$ is tree and $\mu _{2}$ is the second small eigenvalue of laplacian matrix. if there exist eigenvector of $\mu _2$ such that all component of eigenvector is positive. how to prove ...
1
vote
1answer
38 views
How to prove the equation aboute the number of $\lambda_{i} $ in laplacian tree
Say $A$ is Laplacian matrix of graph, which is a tree, and $\lambda _{i}$ the eigenvalues of $A$.Define $m_{T} (\lambda_{i}) $ to be the number of the $\lambda _{i} $(repeat of $\lambda _{i}$ ), and ...
4
votes
1answer
433 views
Maximizing the smallest positive eigenvalue of the Laplacian matrix via SDP
On page 5 of Stephen Boyd's Convex Optimization of Graph Laplacian Eigenvalues, a weighted undirected graph has nonnegative weights $w \in \mathbb R^m$ associated to its edges, with $\mathbf{1}^T w = ...
1
vote
1answer
120 views
Bound on Largest Eigenvalue of Laplacian Matrix of a Graph
I am self-studying graph (spectral) theory and trying to prove the following problem. Assume we have a graph $G = (V,E)$ with adjacency matrix $A$ and diagonal degree matrix $D$ (where each diagonal ...
1
vote
1answer
299 views
Biggest eigenvalue of a normalized graph Laplacian for some graph G
I was able to show that the eigenvalues are in range $[0,2]$.
However, I have no idea how to show that the graph G must be bipartite if $\lambda_n = 2$.
All help is welcome!
0
votes
1answer
41 views
Graphs and Laplacian
Let $G$ be a non-directed graph with non negative weights. Prove that the multiplicity of the eigenvalue $0$ of $L_s$ is the same as the number of convex components $A_1,\dots, A_k$ of the graph. And ...
1
vote
1answer
218 views
Null space of an augmented graph Laplacian matrix
Let us consider $\mathbf{L}$ is a Laplacian matrix of a connected graph having $n$ nodes. I want to check whether $\mathbf{B} = (\mathbf{L}+\alpha\mathbf{J})$ is a full rank matrix or not. Note that: $...
0
votes
0answers
171 views
Conjecture regarding second smallest eigenvalue of a Laplacian matrix
I am conjecturing that: Let $G$ be a connected graph, after min-cut let $C_1$ and $C_2$ are two almost equal sized (vertex difference should not go beyond 1) connected components of a graph $G$. Then ...
4
votes
1answer
213 views
Are the eigenvalues of Laplacian times Diagonal times Laplacian matrix non-negative?
Consider two (not identical) symmetric Laplacian matrices $L_1$ and $L_2$ and a diagonal matrix $D > 0$. My question is if the eigenvalues of the product $A =L_1 D L_2$ have non-negative real-part. ...
0
votes
1answer
33 views
On Laplacian spectrum of Graph
can somebody refer me the article/source in which it has been proved that $G:=K_1\vee (mK_n)$ is determined by its Laplacian spectrum
0
votes
1answer
44 views
Literature on Non-Scalar weights on edges of Graph?
I need to survey, if there exists, the literature that uses non-scalar weights on Graphs.
In my case, I would like to have weight matrices $\mathbf{W}_{ij}$ instead of scalars $w_{ij}$ on the edges ...
