# What's the full assumption for Laplacian matrix $L=BB^T=\Delta-A$?

Graph with no-selfloop, no-multi-edges, unweighted.

directed

For directed graph Adjacency matrix is a non-symmetric matrix $$A_{in}$$ considering indegree or $$A_{out}$$ considering outdegree. Degree matrix $$\Delta$$ is diagonal matrix $$\Delta=\Delta_{in}+\Delta_{out}$$. The diagonal elements are sum of indegree and outdegree. The oriented incidence matrix $$B_{oriented}$$, $$N\times M$$. $$b_{im}=1$$ if edge $$m$$ start from $$i$$. $$b_{im}=−1$$ if edge $$m$$ ended to $$i$$. $$b_{im}=0$$ otherwise.

$$\Delta-A_{in}\neq\Delta-A_{out}\neq B_{oriented}B_{oriented}^T$$

undirected

For undirected graph and oriented incidence matrix $$B_{oriented}$$ have dimension $$N\times 2M$$. $$B_{oriented}B_{oriented}^T=2\Delta-2A$$.

unoriented incidence matrix: $$b_{im}=1$$ if link $$m$$ incident -- start from $$i$$ or end to $$i$$. $$b_{im}=0$$ otherwise. $$B_{unoriented}B_{unoriented}^T=\Delta+A$$.

Problem

When Laplacian matrix $$L=BB^T=\Delta-A$$? Many definitions I saw do not give clear assumption in the context. Say, undirected or directed, oriented or unoriented, $$A_{in}$$ or $$A_{out}$$ or $$A$$? or whatever ... ?

Any references would be greatly appreciated. Thank you.

EDIT

The reference which make me confused is 2011, P.V. Mieghem, Graph Spectra for Complex Networks Chapter 2 Algebraic graph theory P14. 2. The relation between adjacency and incidence matrix is given by the admittance matrix or Laplacian $$Q=BB^T=\Delta-A$$

EDIT2

unweighted, nomultiple-edges $$A$$, $$N\times N$$, noselfloop $$a_{ii}=0$$

### 1.1 directed

$$A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

### 1.2 undirected

$$A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix}$$

## 2. incidence matrix $$B$$,

$$N\times M$$, $$M$$ are edges. lexicographically ordered.

### 2.1 directed

$$N\times M$$, $$N=6$$, $$M=9$$,

$$e_1=1\rightarrow 2$$, $$e_2=1\rightarrow 3$$, $$e_3=1\leftarrow 6$$,

$$e_4=2\rightarrow 3$$, $$e_5=2\leftarrow 5$$,$$e_6=2\rightarrow 6$$,

$$e_7=3\rightarrow 4$$,

$$e_8=4\leftarrow 5$$,

$$e_9=5\leftarrow 6$$

$$B_{oriented}=\begin{pmatrix} 1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ -1 & 0 & 0 & 1 & -1 & 1 &0 & 0 & 0\\ 0 & -1 & 0 & -1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & -1\\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 1 \end{pmatrix}$$

### 2.2 undirected

(oriented) $$N\times 2M$$

$$N=6$$, $$M=18$$,

$$e_1=1\rightarrow 2$$, $$e_2=1\leftarrow 2$$, $$e_3=1\rightarrow 3$$,

$$e_4=1\leftarrow 3$$, $$e_5=1\rightarrow 6$$, $$e_6=1\leftarrow 6$$,

$$e_7=2\rightarrow 3$$, $$e_8=2\leftarrow 3$$, $$e_9=2\rightarrow 5$$,

$$e_{10}=2\leftarrow 5$$, $$e_{11}=2\rightarrow 6$$, $$e_{12}=2\leftarrow 6$$,

$$e_{13}=3\rightarrow 4$$, $$e_{14}=3\leftarrow 4$$,

$$e_{15}=4\rightarrow 5$$, $$e_{16}=4\leftarrow 5$$,

$$e_{17}=5\rightarrow 6$$, $$e_{18}=5\leftarrow 6$$

$$B_{oriented}=\begin{pmatrix} 1 & -1 & 1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 1 & -1 \\ 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1\\ \end{pmatrix}$$

$$(oriented)~b_{im}= \begin{cases} 1, & \text{if link e_m=i\rightarrow j} \\ -1, & \text{if link e_m=i\leftarrow j} \\ 0, & \text{otherwise} \end{cases}$$

(unoriented) $$N\times M$$

$$e_1=1 - 2$$, $$e_2=1 - 3$$, $$e_3=1 - 6$$,

$$e_4=2 - 3$$, $$e_5=2 - 5$$,$$e_6=2 - 6$$,

$$e_7=3 - 4$$,

$$e_8=4 - 5$$,

$$e_9=5 - 6$$

$$B_{unoriented}=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 1 &0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}$$

$$(unoriented)~b_{im}= \begin{cases} 1, & \text{if link e_m=i - j incident} \\ 0, & \text{otherwise} \end{cases}$$

## 3. degree matrix

$$\Delta_{ii} =deg(i) = \sum_j A_{ij}$$. $$\Delta_{ij}=0$$, $$i\neq j$$

### 3.1 directed

$$\begin{pmatrix} 2＋1 & 0 & 0 & 0 & 0 & 0\\ 0 & 2＋2 & 0 & 0 & 0 & 0\\ 0 & 0 & 1＋2 & 0 & 0 & 0\\ 0 & 0 & 0 & 0＋2 & 0 & 0\\ 0 & 0 & 0 & 0 & 2＋1 & 0\\ 0 & 0 & 0 & 0 & 0 & 2＋1 \end{pmatrix}$$

### 3.2 undirected

$$\begin{pmatrix} 3 & 0 & 0 & 0 & 0 & 0\\ 0 & 4 & 0 & 0 & 0 & 0\\ 0 & 0 & 3 & 0 & 0 & 0\\ 0 & 0 & 0 & 2 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 0 & 0 & 0 & 3 \end{pmatrix}$$

## 4. Laplacian matrix

### 4.1 directed

$$B_{oriented}B_{oriented}^T$$

$$\begin{pmatrix} 3 & -1 & -1 & 0 & 0 & -1\\ -1 & 4 & -1 & 0 & -1 & -1\\ -1 & -1 & 3 & -1 & 0 & 0\\ 0 & 0 & -1 & 2 & -1 & 0\\ 0 & -1 & 0 & -1 & 3 & -1\\ -1 & -1 & 0 & 0 & -1 & 3 \end{pmatrix}$$

### 4.2 undirected

(oriented)

$$B_{oriented}B_{oriented}^T=2\Delta -2A$$

$$\begin{pmatrix} 6 & -2 & -2 & 0 & 0 & -2\\ -2 & 8 & -2 & 0 & -2 & -2 \\ -2 & -2 & 6 & -2 & 0 & 0 \\ 0 & 0 & -2 & 4 & -2 & 0 \\ 0 & -2 & 0 & -2 & 6 & -2 \\ -2 & -2 & 0 & 0 & -2 & 6 \end{pmatrix}$$

(unoriented)

$$B_{unoriented}B_{unoriented}^T=\Delta + A$$

$$\begin{pmatrix} 3 & 1 & 1 & 0 & 0 & 1\\ 1 & 4 & 1 & 0 & 1 & 1\\ 1 & 1 & 3 & 1 & 0 & 0\\ 0 & 0 & 1 & 2 & 1 & 0\\ 0 & 1 & 0 & 1 & 3 & 1\\ 1 & 1 & 0 & 0 & 1 & 3 \end{pmatrix}$$

• When you want to calculate Laplacian matrix by $D−A$, you must use symmetric adjacency matrix which is come from undirected graph (section 1.2) not directed graph (section 1.1). Now: $L=\tilde{D}\tilde{D}^\intercal =D−A$ Jun 6 at 21:14

As far as I know Laplacians worthy of the name always assume undirected graphs, because you want them to be symmetric. If you want to define the Laplacian of a directed graph, it should end up being the Laplacian of the symmetrized (hence undirected) graph, a priori. There might be papers dealing with other definitions but they should make it clear then.

• Could you refer to some of these papers? Jun 6 at 20:17

Here is one most closest to the expectation

Definition 2.5. Given a directed or undirected graph $$G= (V,E)$$, with $$V=\{v_1,\cdots,v_m\}$$,the adjacency matrix $$A(G)$$ of $$G$$ is the symmetric $$m\times m$$ matrix $$(a_{ij})$$ such that

(1) If $$G$$ is directed, then $$a_{ij}=1$$ (if there is some edge $$(v_i,v_j)\in E$$ or some edge $$(v_j,v_i)\in E$$), otherwise $$a_{ij}=0$$.

(2) Else if $$G$$ is undirected, then $$a_{ij}=1$$ (if there is some edge $$(v_i,v_j)\in E$$) , otherwise $$a_{ij}=0$$.

So that, the adjacency of directed graph is same with the undirected graph which is symmetric.

Proposition 2.1. Given any directed graph $$G$$ if $$\tilde{D}$$ is the incidence matrix of $$G$$, $$A$$ is the adjacency matrix of $$G$$, and $$D$$ is the degree matrix such that $$D_{ii}=d(v_i)$$, then $$\tilde{D}\tilde{D}^\intercal=D−A$$.

Well, for directed graph with same adjacency matrix of corresponding undirected graph, $$\tilde{D}\tilde{D}^\intercal=D−A$$.

Consequently, $$\tilde{D}\tilde{D}^\intercal$$ is independent of the orientation of $$G$$ and $$D−A$$ is symmetric, positive,semidefinite; that is, the eigenvalues of $$D−A$$ are real and nonnegative.

In my test, The symmetric of $$\tilde{D}\tilde{D}^\intercal$$ is independent of the orientation of $$G$$.

The matrix $$L=\tilde{D}\tilde{D}^\intercal =D−A$$ is called the (unnormalized) graph Laplacian of the graph $$G$$.