Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...