Incidence matrix

Construction

This note is under construction.

TODO

This note has things to do.

• Restructre and rethink the “Variants” section. I would like to show the differences of incidence matrices for different graph types.
• What is a “vertex-edge incidence matrix”? Is there a “edge-vertex incidence matrix”?
• Lemmas, Theorems and Corollaries should be for each of the type.
• The stuff about LP relaxation and linear optimization should not be in this note, this violates atomicity of notes.
• Graph types
  • Directed graph
  • Undirected graph
  • Bipartite graph
  • Multi graph
  • Weighted graph
  • What about “simple graphs” and combinations of the graph types.

In graph theory, the incidence matrix ^[1][2] of a graph is a matrix that records the incidence of vertices and edges, with rows indexed by the vertex set and columns indexed by the edge set. Together with the adjacency matrix, it is one of the standard matrix representations of a graph.

TODO

---

Variants

---

The sections below cover the incidence matrix for several specific graph types. The undirected, directed, and edge-weighted cases differ in the shape or values of the matrix, while the cycle and bipartite cases are special graph families whose incidence matrices carry additional structure. Each keeps the same basic idea, encoding which vertices are endpoints of which edges.

Undirected graph

---

Definition 1 (Incidence matrix of an undirected graph)

Let $G=(V,E)$ be a simple undirected graph, i.e. one without self loops or parallel edges, with vertex set $V=\{v_1,\dots ,v_n\}$ and edge set $E=\{e_1,\dots ,e_m\}$. The incidence matrix of $G$ is the $n\times m$ binary matrix $\mathbf{M}=(m_{ij})$ given by

$$m_{ij}=\{\begin{array}{ll}1& \text{if }{v}_i\text{ is an endpoint of }{e}_j\\ 0& \text{otherwise}\end{array}$$

Properties

---

Lemma 1 (Column sums)

The incidence matrix of a simple undirected graph has exactly two $1$‘s in each column, one for each endpoint of the corresponding edge.

Proof of Lemma 1

Every edge $e_j$ of a simple graph has exactly two distinct endpoints, since $G$ has no self-loops. By Definition 1, $m_{ij}=1$ exactly for the two rows $i$ corresponding to those endpoints, and $m_{ij}=0$ for every other row. $\square$

Corollary 1 (Row sums give the degree)

For each vertex $v_i$, the row sum ${\sum }_{j=1}^m{m}_{ij}$ equals the degree of $v_i$.

Proof of Corollary 1

By Definition 1, $m_{ij}=1$ exactly when $v_i$ is an endpoint of $e_j$, and $0$ otherwise. Summing over $j$ therefore counts exactly the edges incident to $v_i$, which is the degree of $v_i$. $\square$

Examples

---

Example 1 (Cycle graph $C_4$)

For $G=(V,E)$ with $V=\{v_1,v_2,v_3,v_4\}$ and $E=\{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_4,v_1\}\}$, the incidence matrix is

$$\mathbf{M}=\left(\begin{array}{cccc}1& 0& 0& 1\\ 1& 1& 0& 0\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}\right)$$

Directed graph

---

Definition 2 (Incidence matrix of a directed graph)

Let $G=(V,E)$ be a directed graph with vertex set $V=\{v_1,\dots ,v_n\}$ and edge set $E=\{e_1,\dots ,e_m\}$. The incidence matrix of $G$ is the signed $n\times m$ matrix $\mathbf{M}=(m_{ij})$, distinguishing the tail from the head of each directed edge, given by

$$m_{ij}=\{\begin{array}{ll}-1& \text{if }{v}_i\text{ is the tail of }{e}_j\\ 1& \text{if }{v}_i\text{ is the head of }{e}_j\\ 0& \text{otherwise}\end{array}$$

Properties

---

Theorem 1 (Total unimodularity of the directed incidence matrix)

The incidence matrix of a directed graph is always totally unimodular.

Proof of Theorem 1

We show by induction on $k$ that every $k\times k$ square submatrix $B$ of $\mathbf{M}$ satisfies $\det (B)\in \{-1,0,1\}$.

Base case ($k=1$): every entry of $\mathbf{M}$ lies in $\{-1,0,1\}$ by Definition 2, so $\det (B)\in \{-1,0,1\}$.

Inductive step: assume the claim holds for all $(k-1)\times (k-1)$ square submatrices, and let $B$ be a $k\times k$ square submatrix of $\mathbf{M}$. Each column of $\mathbf{M}$ has at most one $-1$ (the tail’s row) and at most one $1$ (the head’s row), so each column of $B$ has $0$, $1$, or $2$ nonzero entries.

If some column of $B$ is entirely zero, then $\det (B)=0$.

If some column of $B$ has exactly one nonzero entry, expanding the determinant along that column gives $\det (B)=\pm \det (B^{\prime })$, where $B^{\prime }$ is the $(k-1)\times (k-1)$ submatrix of $\mathbf{M}$ obtained by deleting that row and column. By the inductive hypothesis, $\det (B^{\prime })\in \{-1,0,1\}$, so $\det (B)\in \{-1,0,1\}$.

Otherwise, every column of $B$ has exactly two nonzero entries, a $1$ and a $-1$, which cancel. Then the rows of $B$ sum to the zero vector, so they are linearly dependent and $\det (B)=0$.

In every case $\det (B)\in \{-1,0,1\}$. $\square$

Examples

---

Example 2 (Directed cycle graph)

For $G=(V,E)$ with $V=\{v_1,v_2,v_3\}$ and $E=\{(v_1,v_2),(v_2,v_3),(v_3,v_1)\}$, labeled $e_1=(v_1,v_2)$, $e_2=(v_2,v_3)$, $e_3=(v_3,v_1)$, the incidence matrix is

$$\mathbf{M}=\left(\begin{array}{ccc}-1& 0& 1\\ 1& -1& 0\\ 0& 1& -1\end{array}\right)$$

Edge-weighted graph

---

Definition 3 (Incidence matrix of an edge-weighted graph)

Let $G=(V,E)$ be an edge-weighted graph with weight function $w:E\to \mathbb{R}$. The incidence matrix of $G$ is the $n\times m$ matrix $\mathbf{M}=(m_{ij})$ given by

$$m_{ij}=\{\begin{array}{ll}w(e_j)& \text{if }{v}_i\text{ is an endpoint of }{e}_j\\ 0& \text{otherwise}\end{array}$$

with $w(e_j)$ replaced by $\pm w(e_j)$ in the signed, directed case.

Examples

---

Example 3 (Edge-weighted triangle graph)

For $G=(V,E)$ with $V=\{v_1,v_2,v_3\}$, $E=\{e_1=\{v_1,v_2\},e_2=\{v_2,v_3\},e_3=\{v_3,v_1\}\}$ and weights $w(e_1)=2$, $w(e_2)=5$, $w(e_3)=3$, the incidence matrix is

$$\mathbf{M}=\left(\begin{array}{ccc}2& 0& 3\\ 2& 5& 0\\ 0& 5& 3\end{array}\right)$$

Cycle graph

---

A cycle graph $C_k$ is a simple undirected graph, so its incidence matrix is the one given by Definition 1. Its distinguishing feature is that the determinant of this matrix is governed by the parity of $k$.

Properties

---

Lemma 2 (Cycle determinant)

Let $C_k$ be the cycle graph on vertices $v_1,\dots ,v_k$ with edges $e_i=\{v_i,v_{i+1}\}$ (indices mod $k$), and let ${\mathbf{M}}_k$ be its incidence matrix. Then $\det ({\mathbf{M}}_k)=0$ if $k$ is even, and $\det ({\mathbf{M}}_k)=\pm 2$ if $k$ is odd.

Proof of Lemma 2

Row $i$ of ${\mathbf{M}}_k$ has nonzero entries only in columns $i-1$ and $i$ (indices mod $k$), since $v_i$ is an endpoint only of $e_{i-1}$ and $e_i$. In the Leibniz expansion of $\det ({\mathbf{M}}_k)$, a permutation $\sigma$ contributes only if $\sigma (i)\in \{i-1,i\}$ for every row $i$. Any such $\sigma$ that is neither the identity nor the full cyclic shift $i\mapsto i-1$ must mix the two choices, which forces two rows to map to the same column, so $\sigma$ would not be a bijection. Hence the only two permutations contributing to the determinant are the identity, with sign $+1$, and the $k$-cycle $i\mapsto i-1$, with sign $(-1{)}^{k-1}$. Therefore

$$\det ({\mathbf{M}}_k)=1+(-1{)}^{k-1}.$$

If $k$ is even, $(-1{)}^{k-1}=-1$, so $\det ({\mathbf{M}}_k)=0$. If $k$ is odd, $(-1{)}^{k-1}=1$, so $\det ({\mathbf{M}}_k)=2$. $\square$

Examples

---

Example 4 (Triangle graph $C_3$)

For $G=(V,E)$ with $V=\{v_1,v_2,v_3\}$ and $E=\{e_1=\{v_1,v_2\},e_2=\{v_2,v_3\},e_3=\{v_3,v_1\}\}$, the incidence matrix is

$$\mathbf{M}=\left(\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& 1\end{array}\right)$$

Since $k=3$ is odd, $\det (\mathbf{M})=2$, in agreement with Lemma 2.

Bipartite graph

---

Definition 4 (Incidence matrix of a bipartite graph)

Let $G=(U,V,E)$ be a bipartite graph with partitions $U=\{u_1,\dots ,u_n\}$ and $V=\{v_1,\dots ,v_k\}$, and edge set $E=\{e_1,\dots ,e_m\}$. Let $w_1,\dots ,w_{n+k}$ be the vertices of $G$ listed with $U$ first and $V$ second, so $w_i=u_i$ for $1\le i\le n$ and $w_{n+i}=v_i$ for $1\le i\le k$. The incidence matrix of $G$ is the $(n+k)\times m$ matrix $\mathbf{M}=(m_{ij})$ given by

$$m_{ij}=\{\begin{array}{ll}1& \text{if }{w}_i\text{ is an endpoint of }{e}_j\\ 0& \text{otherwise}\end{array}$$

Properties

---

The incidence matrix of a bipartite graph is a principal source of totally unimodular matrices, a property rooted in the block structure that the bipartite row ordering imposes.

Lemma 3 (Bipartite block structure)

The incidence matrix of a bipartite graph $G=(U,V,E)$, with rows ordered as $U$ followed by $V$, has in each column exactly one nonzero entry among the rows corresponding to $U$ and one among the rows corresponding to $V$, since every edge joins a vertex in $U$ to one in $V$.

Proof of Lemma 3

By definition of a bipartite graph, every edge $e_j$ has one endpoint in $U$ and one endpoint in $V$. By Definition 4, $m_{ij}=1$ exactly for the two rows $i$ corresponding to those endpoints, one among $w_1,\dots ,w_n$ (the $U$-rows) and one among $w_{n+1},\dots ,w_{n+k}$ (the $V$-rows), and $m_{ij}=0$ for every other row. $\square$

The block structure underlies the following characterization of total unimodularity for undirected incidence matrices.

Theorem 2 (Total unimodularity criterion)

The incidence matrix of an undirected graph $G$ is totally unimodular if and only if $G$ is bipartite.

Proof of Theorem 2

($\Leftarrow$) Suppose $G=(U,V,E)$ is bipartite, with incidence matrix $\mathbf{M}$ as in Definition 4. Let ${\mathbf{M}}^{\prime }$ be the matrix obtained from $\mathbf{M}$ by multiplying every row corresponding to $V$ by $-1$. By Lemma 3, each column of $\mathbf{M}$ has exactly one $1$ among the $U$-rows and one $1$ among the $V$-rows, so each column of ${\mathbf{M}}^{\prime }$ has exactly one $1$ and one $-1$, the same pattern as the incidence matrix of a directed graph (Definition 2). By Theorem 1, ${\mathbf{M}}^{\prime }$ is totally unimodular. Multiplying rows by $-1$ changes the sign but not the absolute value of the determinant of any square submatrix, so $\mathbf{M}$ is totally unimodular as well.

($\Rightarrow$) We prove the contrapositive. Suppose $G$ is not bipartite, so it contains an odd cycle $C_k$ on some subset of its vertices and edges. The submatrix of $\mathbf{M}$ restricted to these rows and columns is exactly the incidence matrix of $C_k$, so by Lemma 2 its determinant is $\pm 2\notin \{-1,0,1\}$. Hence $\mathbf{M}$ is not totally unimodular. $\square$

Examples

---

Example 5

For $G$ with $U=\{u_1,u_2\}$, $V=\{v_1,v_2\}$ and $E=\{e_1=\{u_1,v_1\},e_2=\{u_1,v_2\},e_3=\{u_2,v_2\}\}$, ordering rows as $u_1,u_2,v_1,v_2$, the incidence matrix is

$$\mathbf{M}=\left(\begin{array}{ccc}1& 1& 0\\ 0& 0& 1\\ 1& 0& 0\\ 0& 1& 1\end{array}\right)$$

References

1. [1]

   “Incidence matrix”, Wikipedia, Available: https://en.wikipedia.org/wiki/Incidence_matrix, Accessed: 2026-07-15 ↩

2. [2]

   “Incidence Matrix”, Wolfram MathWorld, Available: https://mathworld.wolfram.com/IncidenceMatrix.html, Accessed: 2026-07-15 ↩