Linear Algebra – Proving Total Unimodularity of Incidence Matrix

discrete optimizationlinear algebralinear programmingoptimizationtotal-unimodularity

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
enter image description here

Best Answer

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)

Related Question