The incidence matrix of a weighted graph

Question

How to correctly build the incidence matrix of a undirected weighted graph? May you show a little example?

Answer 1

An incidence matrix $M$ is a matrix in $\mathbb{R}^{|V| \times |E|}$, where $M_{ij} = 1$ if vertex $i$ is incident to edge $j$, and $M_{ij} = 0$ otherwise.

You can replace the indicator value of $1$ with the edge weight instead.

Answer 2

I found a example in the following lecture (p.23):

https://www.fd.cvut.cz/personal/nagyivan/MatModEk/MME_Lectures.pdf

Answer 3

Although this question has already been resolved, I would like to add an additional comment since the current responses are, in my opinion, unsatisfactory.

The Unweighted Case

Following the notation of Biyikoglu et al., the incidence matrix $\nabla$ of an unweighted graph $G(V, E)$ is a $(|E| \times|V|)$ matrix defined by $$ \nabla_{e, v}=\left\{\begin{array}{ll} -1 & \text{if $x$ is the initial vertex of edge $e$}\\ +1 & \text{if $x$ is the terminal vertex of edge $e$} \\ 0 & \text { otherwise } \end{array}\right. $$

Note that this is equivalent to

$$ \nabla_{e, v}=\left\{\begin{array}{ll} -\sqrt{A_e} & \text{if $x$ is the initial vertex of edge $e$}\\ +\sqrt{A_e} & \text{if $x$ is the terminal vertex of edge $e$} \\ 0 & \text { otherwise } \end{array}\right. $$ where $A$ is the adjacency matrix of $G$. One crucial property of this matrix is that it satisfies the following relation

$$ \mathbf{L}=\mathbf{\nabla}^{\top} \mathbf{\nabla} $$

where $L$ is the Laplacian matrix of $G$

$$ L_{x y}=\sum_{e \in E} \nabla_{e x} \nabla_{e y}=\left\{\begin{array}{ll} -1 & \text { if } x y \in E \\ d(x) & \text { if } x=y \\ 0 & \text { otherwise } \end{array}\right. $$ Equivalently, $$L = D - A$$ where $D$ is the degree matrix.

The Weighted Case

Now, if we consider a weighted graph $G(V, W)$, we would like similar properties. Since the Laplacian for the weighted case is defined as

$$L = D - W$$

(note that we replaced the adjacency matrix with the weight matrix)

We would like to find a $(|E| \times|V|)$ matrix $\nabla$ such that

$$ \mathbf{L}=\mathbf{\nabla}^{\top} \mathbf{\nabla} $$

Fixing an arbitrary orientation, the matrix defined by

$$ \nabla_{e, v}=\left\{\begin{array}{ll} -\sqrt{W_e} & \text{if $x$ is the initial vertex of edge $e$}\\ +\sqrt{W_e} & \text{if $x$ is the terminal vertex of edge $e$} \\ 0 & \text { otherwise } \end{array}\right. $$

satisfies the desired relation.

Refs

Biyikoglu, T., Leydold, J., & Stadler, P. F. (2007). Laplacian eigenvectors of graphs: Perron-Frobenius and Faber-Krahn type theorems. Springer.

Kelner, J. (2007). An Algorithmist’s Toolkit: Lecture Notes. Lecture 2. MIT.