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

239 questions
Filter by
Sorted by
Tagged with
20 views

### Missing eigenvectors of the ring graph Laplacian

Spielman has some notes where he explains that the eigenvectors of the Laplacian of the ring graph are $$x_k(u) = \sin(\frac{2\pi ku}{n})\\y_k(u) = \cos(\frac{2\pi ku}{n})$$ for $1 \leq k \leq n/2$ ...
6 views

### Laplacian integral graphs and graph Join

There is one famous theorem that states the following: Let $G$ be a connected graph of order $n$. Then $n$ is a Laplacian eigenvalue of $G$ if and only if $G$ is the join of two graphs. In connection ...
12 views

• 392
1 vote
61 views

### Most efficient to solve $(I + L)x = b$ where $L$ is graph Laplacian

Assume $G$ is a graph with $n$ vertices, and $L = D - W$ is its graph Laplacian matrix. I want to solve the linear equation $(I + L)x = b$, where $I$ is the identity matrix, $b$ is a constant vector, ...
64 views

### Relationship between square of adjacency matrix and Laplacian matrix

Consider a simple undirected graph with $n$ elements. Let $A$ be the adjacency matrix of the graph with elements $a_{ij}$. Let $L$ be the graph Laplacian with $L=D-A$ where $D$ is the degree matrix. ...
• 71
38 views

### Sum of unstable diagonal matrix with laplacian

I am trying to solve the following problem that seems trivial at first sight but I don't know where to start for a rigorous approach. Consider the following matrix $M = A - L$ where $A$ is an unstable,...
• 387
40 views

### Range $u_{\mathrm{max}}-u_{\mathrm{min}}$ of the solution to graph Poisson equation $Lu=b$

I found out an interesting phenomenon when trying to solve the linear equation $Lu=b$, and I don't know how to interpret such phenomenon. Goal: Fit $u(x, y)=\cos(x)$ for $x,y \in [0,\pi]$. We draw ...
• 23
34 views

97 views

### Linear Algebra: if matrices $\mathbf{A} + \mathbf{B} = \mathbf{I}$, then do $\mathbf{A}$ and $\mathbf{B}$ have the same eigenvectors?

Just had a quick question which I think ought to be simple, but I can't fully convince myself of the result. Question: If matrices $\mathbf{A} + \mathbf{B} = \mathbf{I}$, ($\mathbf{I}$ is the identity ...
22 views

### if $B^3=C^3=BC=\mathbb I$ can we say anything about $L$ if $e^L=B+C?$

My intuition on matrix exponentials, hermitian matrices, unitary matrices, adjacency matrices, and Laplacian matrices is not superb now. For example, let $A$ be a matrix with $A^2=\mathbb I$. $A$ may ...
• 253
62 views

### Row/Column Sum of a Laplacian Matrix

so I know that the row sum and the column sum for a laplacian matrix should always be 0. I am running a code on Matlab and after a certain time, one of the row sums comes out to be 0.0001. Is that ...
43 views

• 1,401
1 vote
52 views

### Rank-one modification of a Laplacian as the Laplacian of a larger, weighted graph

The Laplacian $L$ is usually defined for simple graphs, that is, graphs with no self-loops or multiple edges. Consider however the $n\times n$ matrix $M=L+P$, where $P$ has null entries except for one ...
157 views

### What does it mean that a laplacian of directed graph has full rank?

Suppose we have a directed graph $G=(V, E)$ with $N=|V|$ nodes. Define normalized graph laplacian as $L=I-AD^{-1}$ where $A$ is a adjacency matrix of $G$ and $D$ is a degree matrix of $G$. I'm ...
277 views

### Laplacian of bipartite graph

It is well know that in the case of weighted graph with positive weights, the dimension of the kernel of the Laplacian is the number of connected components of the corresponding graph. This fails when ...
1 vote
Question: Let $K_{m,n}$ be a weighted complete bipartite graph with weights $w_{ij}$ for each edge $(i,j)$. What is the effective resistance $R_{i,j}$ between any two nodes of the graph? I am ...