Incidence matrix

In graph theory, the incidence matrix ^[1][2], or vertex-edge incidence matrix, 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. Its transpose, with rows indexed by edges and columns by vertices, is the edge-vertex incidence matrix. Together with the adjacency matrix, it is one of the standard matrix graph representations.

Definition

---

Definition 1 (Vertex-edge incidence matrix)

Let $G=(V,E)$ be a graph with vertex set $V=\{v_1,\dots ,v_n\}$ and edge set $E=\{e_1,\dots ,e_m\}$. A vertex-edge incidence matrix of $G$ is an $n\times m$ matrix $\mathbf{M}=(m_{ij})$, with rows indexed by $V$ and columns by $E$, such that

$$m_{ij}=0\text{ if }{v}_i\text{ is not an endpoint of }{e}_j,$$

and $m_{ij}\ne 0$ if $v_i$ is an endpoint of $e_j$. The concrete nonzero value depends on the class of graph under consideration.

Corollary 1 (Edge-vertex incidence matrix)

The transpose ${\mathbf{M}}^{\mathsf{T}}$ of a vertex-edge incidence matrix of $G$ is an $m\times n$ matrix, with rows indexed by $E$ and columns by $V$, called the edge-vertex incidence matrix of $G$.

Proof of Corollary 1

Transposing swaps the roles of rows and columns, so $({\mathbf{M}}^{\mathsf{T}}{)}_{ji}=m_{ij}$ is indexed by edges in its rows and vertices in its columns. By Definition 1, this entry is nonzero exactly when $v_i$ is an endpoint of $e_j$, the same incidence relation recorded by $\mathbf{M}$. $\square$

Variants

---

Each of the following variants specializes Definition 1 to a class of graphs by fixing what the nonzero entries $m_{ij}$ record.

Undirected graph

---

Definition 2 (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 2, $m_{ij}=1$ exactly for the two rows $i$ corresponding to those endpoints, and $m_{ij}=0$ for every other row. $\square$

Corollary 2 (Row sums give the degree)

For each vertex $v_i$, the row sum equals the degree of $v_i$:

$$\sum _{j=1}^m{m}_{ij}=\mathrm{deg}(v_i)$$

Proof of Corollary 2

By Definition 2, $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 3 (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

---

Lemma 2 (Column sums vanish)

Every column of the incidence matrix of a directed graph sums to $0$, since it has exactly one entry equal to $-1$ and one entry equal to $1$.

Proof of Lemma 2

Every edge $e_j$ has exactly one tail and one head, which are distinct vertices. By Definition 3, $m_{ij}=-1$ for the row $i$ corresponding to the tail, $m_{ij}=1$ for the row corresponding to the head, and $m_{ij}=0$ for every other row. Hence column $j$ sums to $-1+1=0$. $\square$

Corollary 3 (Rank bound)

The rank of the incidence matrix $\mathbf{M}$ of a directed graph $G=(V,E)$ with $|V|=n$ satisfies $\mathrm{rank}(\mathbf{M})\le n-1$.

Proof of Corollary 3

Let $1\in {\mathbb{R}}^n$ be the all-ones vector. By Lemma 2, every column of $\mathbf{M}$ sums to $0$, so $1^{\mathsf{T}}\mathbf{M}=0^{\mathsf{T}}$. Since $1\ne 0$, this is a nontrivial linear dependence among the $n$ rows of $\mathbf{M}$, so the rows are linearly dependent and span a subspace of dimension at most $n-1$. Hence $\mathrm{rank}(\mathbf{M})\le n-1$. $\square$

Theorem 1 (Total unimodularity of the directed incidence matrix)

The incidence matrix $\mathbf{M}$ 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 3, 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$

Theorem 2 (Forest criterion)

A directed graph $G=(V,E)$ is a directed forest if and only if the columns of its incidence matrix $\mathbf{M}$ are linearly independent.

Proof of Theorem 2

($\Leftarrow$) We prove the contrapositive: suppose $G$ is not a directed forest, so its underlying graph contains a cycle $v_1,v_2,\dots ,v_k,v_1$ (indices mod $k$), traversed by distinct edges $e_1,\dots ,e_k\in E$, where $e_i$ joins $v_i$ and $v_{i+1}$. For each $i$, let ${\epsilon }_i:=m_{v_i,e_i}\in \{-1,1\}$, the entry of $\mathbf{M}$ at row $v_i$ and column $e_i$. We claim

$$\sum _{i=1}^k{\epsilon }_i{\mathbf{M}}_{\cdot ,e_i}=0.$$

Row $v_j$ of this sum receives contributions only from $e_{j-1}$ and $e_j$, the two cycle edges incident to $v_j$. The term from $e_j$ equals ${\epsilon }_j{m}_{v_j,e_j}=m_{v_j,e_j}^2=1$, while the term from $e_{j-1}$ equals ${\epsilon }_{j-1}{m}_{v_j,e_{j-1}}=m_{v_{j-1},e_{j-1}}{m}_{v_j,e_{j-1}}$, the product of the two nonzero entries of column $e_{j-1}$, one equal to $-1$ (the tail) and the other to $1$ (the head), hence $-1$. The two contributions cancel, so row $v_j$ sums to $0$ for every $j$. Since the ${\epsilon }_i$ are all nonzero, this is a nontrivial linear dependence, so the columns of $\mathbf{M}$ are linearly dependent.

($\Rightarrow$) Suppose $G$ is a directed forest; we show the columns of $\mathbf{M}$ are linearly independent by induction on $m=|E|$. If $m=0$ the claim is vacuous. Otherwise, since the underlying graph is a forest with at least one edge, it has a vertex $v$ of degree $1$; let $e$ be its unique incident edge. By Definition 3, row $v$ of $\mathbf{M}$ has a single nonzero entry, in column $e$. If ${\sum }_{f\in E}{\lambda }_f{\mathbf{M}}_{\cdot ,f}=0$ for scalars ${\lambda }_f$, row $v$ of this equation gives ${\lambda }_e{m}_{v,e}=0$, so ${\lambda }_e=0$. The remaining equation ${\sum }_{f\ne e}{\lambda }_f{\mathbf{M}}_{\cdot ,f}=0$ involves only the columns of $G-e$, the directed forest obtained by deleting $e$, which has $m-1$ edges; by the inductive hypothesis its incidence matrix has linearly independent columns, so ${\lambda }_f=0$ for all $f\ne e$. Hence all ${\lambda }_f=0$, and the columns of $\mathbf{M}$ are linearly independent. $\square$

Corollary 4 (Row sums give the net degree)

For each vertex $v_i$, the row sum ${\sum }_{j=1}^m{m}_{ij}$ equals ${\mathrm{deg}}^{-}(v_i)-{\mathrm{deg}}^{+}(v_i)$, the in-degree of $v_i$ minus its out-degree.

Proof of Corollary 4

By Definition 3, $m_{ij}=1$ when $v_i$ is the head of $e_j$ and $m_{ij}=-1$ when $v_i$ is the tail of $e_j$. Summing over $j$, each edge with head $v_i$ contributes $1$ and each edge with tail $v_i$ contributes $-1$, so ${\sum }_{j=1}^m{m}_{ij}$ counts the edges directed into $v_i$ minus the edges directed out of $v_i$, that is ${\mathrm{deg}}^{-}(v_i)-{\mathrm{deg}}^{+}(v_i)$. $\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

---

An edge-weighted graph attaches a real-valued weight to each edge, and is what is usually meant by a weighted graph unless the weights are placed on the vertices instead.

Definition 4 (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.

Properties

---

Lemma 3 (Column sums)

In the incidence matrix of an edge-weighted graph, column $j$ has exactly two nonzero entries, each equal to $w(e_j)$.

Proof of Lemma 3

Every edge $e_j$ of a simple graph has exactly two distinct endpoints. By Definition 4, $m_{ij}=w(e_j)$ for the two rows $i$ corresponding to those endpoints, and $m_{ij}=0$ for every other row. $\square$

Corollary 5 (Row sums give the weighted degree)

For each vertex $v_i$, the row sum ${\sum }_{j=1}^m{m}_{ij}$ equals ${\sum }_{j:v_i\in e_j}w(e_j)$, the sum of the weights of the edges incident to $v_i$.

Proof of Corollary 5

By Definition 4, $m_{ij}=w(e_j)$ exactly when $v_i$ is an endpoint of $e_j$, and $0$ otherwise. Summing over $j$ therefore adds $w(e_j)$ for exactly the edges incident to $v_i$. $\square$

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 2. Its distinguishing feature is that the determinant of this matrix is governed by the parity of $k$.

Properties

---

Lemma 4 (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 4

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

Bipartite graph

---

Definition 5 (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 5 (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 5

By definition of a bipartite graph, every edge $e_j$ has one endpoint in $U$ and one endpoint in $V$. By Definition 5, $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 3 (Total unimodularity of the undirected incidence matrix)

The incidence matrix $\mathbf{M}$ of an undirected graph $G$ is totally unimodular if and only if $G$ is bipartite.

Proof of Theorem 3

($\Leftarrow$) Suppose $G=(U,V,E)$ is bipartite, with incidence matrix $\mathbf{M}$ as in Definition 5. Let ${\mathbf{M}}^{\prime }$ be the matrix obtained from $\mathbf{M}$ by multiplying every row corresponding to $V$ by $-1$. By Lemma 5, 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 3). 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 4 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]$$

Multigraph

---

A multigraph is an undirected graph in which loops and parallel edges are allowed, relaxing the simple-graph assumption of Definition 2.

Definition 6 (Incidence matrix of a multigraph)

Let $G=(V,E)$ be a multigraph 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$ matrix $\mathbf{M}=(m_{ij})$ given by

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

Properties

---

Lemma 6 (Column sums)

Every column of the incidence matrix of a multigraph sums to $2$: a single $2$ if the corresponding edge is a loop, or two $1$‘s otherwise.

Proof of Lemma 6

Let $e_j$ be an edge of $G$. If $e_j$ is a loop at some vertex $v_i$, then by Definition 6, $m_{ij}=2$ and $m_{i^{\prime }j}=0$ for every $i^{\prime }\ne i$, so column $j$ sums to $2$. If $e_j$ is not a loop, it has two distinct endpoints, so $m_{ij}=1$ for the two rows $i$ corresponding to those endpoints and $m_{ij}=0$ for every other row, so column $j$ again sums to $2$. $\square$

Corollary 6 (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$, with the usual convention that a loop at $v_i$ contributes $2$ to $\mathrm{deg}(v_i)$.

Proof of Corollary 6

By Definition 6, a non-loop edge at $v_i$ contributes $1$ to the row sum, and a loop at $v_i$ contributes $2$. This matches the standard convention for $\mathrm{deg}(v_i)$, so ${\sum }_{j=1}^m{m}_{ij}=\mathrm{deg}(v_i)$. $\square$

Examples

---

Example 6

For $G=(V,E)$ with $V=\{v_1,v_2,v_3\}$, a loop $e_1$ at $v_1$, an edge $e_2=\{v_1,v_2\}$, and parallel edges $e_3=\{v_2,v_3\}$, $e_4=\{v_2,v_3\}$, the incidence matrix is

$$\mathbf{M}=\left[\begin{array}{cccc}2& 1& 0& 0\\ 0& 1& 1& 1\\ 0& 0& 1& 1\end{array}\right]$$

Every column sums to $2$, in agreement with Lemma 6.

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 ↩