# How to prove that incidence matrix is totally unimodular

Problem: Prove that the incidence matrix $$A$$ of a graph define as follows: $$A_{ij}= \begin{cases} -1 & \text{ if the edge } e_j \text{ leaves the vertex } v_i\\ 1 & \text{ if the edge } e_j \text{ enters the vertex } v_i\\ 0 & \text{ otherwise} \end{cases}$$ is totally unimodular.

My attempt: Using induction on the size of the minor of $$A$$.

By the definition of the incident matrix $$A$$, all entries of $$A$$ belong to the set $$\left\{-1,0,1\right\}$$. Hence, every $$1\times 1$$ minor of $$A$$ belongs to $$\{-1,0,+1\}$$.

Suppose that every $$k\times k$$ minor of $$A$$ belongs to $$\{-1,0,+1\}$$, $$k \ge 2$$. We prove that it is the same for every $$(k+1)\times (k+1)$$ minors.

Let $$B$$ be a $$(k+1)\times (k+1)$$ submatrix of $$A$$. We want to prove that $$\det(B) \in \left\{-1,0,1\right\}$$.

Since each column of $$A$$ has at most 2 non-zero coefficients (because each edge is incident to at most two vertices), then either is $$B$$.

• Case 1. If a column of $$B$$ has 0 non-zero coefficients then $$\det(B) = 0$$.
• Case 2. If a column of $$B$$ has 1 non-zero coefficients, assume it is $$b_{ij}$$. Then, by Laplace theorem, we have $$\det(B) = b_{ij}(-1)^{i+j} \det(M_{ij}) = \begin{cases} (-1)^{i+j}\det(M_{ij}) &, \text{ if } b_{ij} = 1\\ (-1)^{i+j+1}\det(M_{ij}) &, \text{ if } b_{ij} = -1 \end{cases},$$ where $$M_{ij}$$ is a $$k \times k$$ submatrix of $$B$$ obtained by removing row $$i$$-th and column $$j$$-th. Now, $$M_{ij}$$ is a $$k\times k$$ submatrix of $$A$$ and hence $$\det(M_{ij}) \in \left\{-1,0,1\right\}$$. It follows that $$\det(B) \in \left\{-1,0,1\right\}$$.
• Case 3. If a column of $$B$$ has 2 non-zero coefficients, assume that they are $$b_{ij}$$ and $$b_{lj}$$. Without losing generality, suppose that $$b_{ij} = 1$$ and $$b_{lj} = -1$$. Then, by Laplace theorem, we have $$\det(B) = (-1)^{i+j}\det(M_{ij}) - (-1)^{k+j}\det(M_{lj}),$$ where $$M_{ij}$$, $$M_{lj}$$ are $$k \times k$$ submatrices defined as in case 2.

Now, I am stuck at the case 3. So, I wonder if there is another way to overcome this case.

Edit: For more details, the context I am dealing with is the max flow problem

• In Case $3$, you can assume all columns of $B$ has exactly two non-zero coefficients. But then the rows sum up to zero, so the matrix is singular and thus has determinant zero ? Commented Nov 5, 2023 at 17:47
• @dezdichado I wonder why could we assume that? In addition, I also edited more detail in the post. Commented Nov 5, 2023 at 18:13
• Typically, the columns correspond to edges and each edge enters exactly one vertex and leaves one vertex right ? Unless, you are using some other definition. Commented Nov 5, 2023 at 18:28
• @dezdichado I use the same definition as you. But, the assumption all columns has exactly 2 non-zero coefficients does not always hold right? Commented Nov 5, 2023 at 18:54
• Didn't you rule out case 1 and case 2 ? If not all of the $k+1$ columns has exactly two elements, then case 1 or case 2 is not ruled out and you get determinant zero. Commented Nov 5, 2023 at 19:01

By the definition of the incident matrix $$A$$, all entries of $$A$$ belong to the set $$\left\{-1,0,1\right\}$$. Hence, every $$1\times 1$$ minor of $$A$$ belongs to $$\{-1,0,+1\}$$.

Suppose that every $$k\times k$$ minor of $$A$$ belongs to $$\{-1,0,+1\}$$, $$k \ge 2$$. We prove that it is the same for every $$(k+1)\times (k+1)$$ minors.

Let $$B$$ be a $$(k+1)\times (k+1)$$ submatrix of $$A$$. We want to prove that $$\det(B) \in \left\{-1,0,1\right\}$$.

Since each column of $$A$$ has at most 2 non-zero coefficients (because each edge is incident to at most two vertices), then either is $$B$$.

• Case 1. If a column of $$B$$ has 0 non-zero coefficients then $$\det(B) = 0$$.
• Case 2. If a column of $$B$$ has 1 non-zero coefficients, assume it is $$b_{ij}$$. Then, by Laplace theorem, we have $$\det(B) = b_{ij}(-1)^{i+j} \det(M_{ij}) = \begin{cases} (-1)^{i+j}\det(M_{ij}) &, \text{ if } b_{ij} = 1\\ (-1)^{i+j+1}\det(M_{ij}) &, \text{ if } b_{ij} = -1 \end{cases},$$ where $$M_{ij}$$ is a $$k \times k$$ submatrix of $$B$$ obtained by removing row $$i$$-th and column $$j$$-th. Now, $$M_{ij}$$ is a $$k\times k$$ submatrix of $$A$$ and hence $$\det(M_{ij}) \in \left\{-1,0,1\right\}$$. It follows that $$\det(B) \in \left\{-1,0,1\right\}$$.
• Case 3. Every column of $$B$$ has exactly 2 non-zero coefficients, which are $$-1$$ and 1. Hence, the sum of all row vectors of the matrix $$B$$ equals to vector 0, i.e., $$r_1 + r_2 +\ldots + r_{k+1} = 0 \in \mathbb{R}^{k+1}.$$ Therefore, row vectors of $$B$$ are linearly dependent and it follows that $$\det(B) = 0$$.

In summary, we have prove that $$\det(B) \in \left\{-1,0,1\right\}$$ in all cases, or in other words, every $$(k+1)\times (k+1)$$ minors of $$A$$ belongs to $$\left\{-1,0,1\right\}$$. (QED)