Integral Polyhedra and Totally Unimodular Matrices

Author

Your Name

Published

January 30, 2025

Introduction

This lecture focuses on integral polyhedra and their importance in integer programming. We will investigate how the integrality property, where all vertices of a polyhedron are integer vectors, leads to integer solutions when solving linear programs over these polyhedra. This "naturally integer" characteristic is highly desirable, as it enables us to solve integer programming problems using more efficient linear programming techniques.

We will then introduce Totally Unimodular Matrices (TUM), a special class of matrices crucial for ensuring the integrality of polyhedra. We will define TUM matrices, examine their properties, and discuss sufficient conditions for a matrix to be totally unimodular. Understanding TUM matrices is essential for identifying integer programming problems that can be solved efficiently as linear programs.

Finally, we will explore corollaries and applications of TUM matrices, particularly in graph theory, including incidence matrices of directed and bipartite graphs. These applications highlight the practical importance of TUM matrices in various optimization problems, such as flow problems, path problems, and transportation problems.

Integral Polyhedra and Integer Programming

Definition of Integral Polyhedra

A polyhedron $P$ is called integral (or integer) if all its vertices are integer vectors. That is, for every vertex $v$ of $P$, $v \in \mathbb{Z}^n$.

An integral polyhedron is a polyhedron where every corner point has only integer coordinates.

Linear Programming Relaxation

The linear programming relaxation of an integer programming problem is obtained by removing the integrality constraints on the variables. Let $P$ be the feasible region of the linear programming relaxation. In general, $P$ may have fractional vertices. However, if $P$ is an integral polyhedron, then all its vertices are integer vectors.

Naturally Integer Programs

The Concept of "Free" Integrality

If the polyhedron $P$ resulting from the linear programming relaxation of an integer program is integral, then solving the linear program over $P$ will always yield an integer optimal solution, if one exists. In this case, the integer programming problem is said to be naturally integer. The integrality comes "for free" because it is a property of the polyhedron itself, not enforced by explicit integrality constraints.

Implications for Solving Integer Programs

For naturally integer programs, the integrality constraint can be removed without changing the integer optimal solution. To find an integer optimal solution, we can simply solve the linear programming relaxation. The optimal solution obtained from the linear program will automatically be an integer solution. This significantly simplifies the problem, as linear programming problems can be solved efficiently in polynomial time, whereas general integer programming is NP-hard.

Naturally integer problems are highly desirable because they allow us to leverage efficient linear programming algorithms to solve problems that are inherently integer in nature.

Totally Unimodular Matrices (TUM)

Definition of Total Unimodularity

Determinant of Submatrices

A matrix $A \in \mathbb{R}^{m \times n}$ is called totally unimodular (TUM) if the determinant of every square submatrix of $A$ is either $0$, $+1$, or $-1$.

Restriction on Matrix Elements

A key implication of total unimodularity is that all entries of a TUM matrix must be either $0$, $+1$, or $-1$. This is because each individual entry of a matrix can be considered as a $1 \times 1$ submatrix, and its determinant (which is the entry itself) must be $0$, $+1$, or $-1$.

Example of a TUM Matrix

Consider the following matrix: \[A = \begin{pmatrix} 1 & 0 & 1 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 1 \end{pmatrix}\] This is a $3 \times 4$ matrix. To check if it is totally unimodular, we need to examine the determinants of all its square submatrices.

$1 \times 1$ submatrices: The determinants are the entries themselves, which are $0, 1, -1$.
$2 \times 2$ submatrices: For example, taking the first two columns: \[\begin{vmatrix} 1 & 0 \\ -1 & 1 \end{vmatrix} = (1)(1) - (0)(-1) = 1\] Taking the first and third columns, second and third rows: \[\begin{vmatrix} -1 & 0 \\ 0 & -1 \end{vmatrix} = (-1)(-1) - (0)(0) = 1\]
$3 \times 3$ submatrices: Taking the first three columns: \[B = \begin{pmatrix} 1 & 0 & 1 \\ -1 & 1 & 0 \\ 0 & -1 & -1 \end{pmatrix}\] Row 1 + Row 3 = $(1, -1, 0) = -$Row 2. Thus the rows are linearly dependent, and $\det(B) = 0$.

It can be verified that the determinant of every square submatrix of $A$ is $0$, $1$, or $-1$. Therefore, $A$ is a totally unimodular matrix.

Properties of TUM Matrices

Inverses of Non-Singular Submatrices

Let $A$ be a totally unimodular matrix, and let $B$ be a non-singular square submatrix of $A$. Then, the inverse of $B$, $B^{-1}$, is an integer matrix, and all entries of $B^{-1}$ are either $0$, $+1$, or $-1$.

Proof of the Inverse Property

@plus6

Let $B$ be a non-singular $m \times m$ submatrix of $A$. From linear algebra, we know that the inverse of $B$ can be expressed using the adjugate formula: \[(B^{-1})_{ij} = \frac{(-1)^{i+j} \det(B_{ji})}{\det(B)}\] where $B_{ji}$ is the $(j, i)$-th minor of $B$, obtained by deleting the $j$-th row and $i$-th column of $B$.

Since $A$ is totally unimodular and $B$ is a submatrix of $A$, $B$ is also totally unimodular. Therefore, the determinant of any square submatrix of $B$, including $B_{ji}$ and $B$ itself, is either $0$, $+1$, or $-1$.

Since $B$ is non-singular, $\det(B) \neq 0$, so $\det(B)$ must be either $+1$ or $-1$. Thus, $\det(B) \in \{+1, -1\}$.

Also, $B_{ji}$ is a $(m-1) \times (m-1)$ submatrix of $B$ (and thus of $A$), so $\det(B_{ji}) \in \{0, +1, -1\}$.

Therefore, \[(B^{-1})_{ij} = \frac{(-1)^{i+j} \det(B_{ji})}{\det(B)} \in \left\{ \frac{0}{\pm 1}, \frac{\pm 1}{\pm 1} \right\} = \{0, +1, -1\}\] This shows that every entry of $B^{-1}$ is either $0$, $+1$, or $-1$. Hence, $B^{-1}$ is an integer matrix with entries from $\{0, +1, -1\}$. endpefalse

The Significance of TUM Matrices in Integer Programming

Integer Solutions Guaranteed by TUM

Standard Form Integer Programs

Consider an integer programming problem in standard form: \[\begin{aligned} \max & \quad c^T x \\ \text{s.t.} & \quad Ax = b \\ & \quad x \geq 0 \\ & \quad x \in \mathbb{Z}^n \end{aligned}\] where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^m$, and $c \in \mathbb{R}^n$.

If $A$ is a totally unimodular matrix and $b$ is an integer vector, then every basic feasible solution of the linear programming relaxation \[\begin{aligned} \max & \quad c^T x \\ \text{s.t.} & \quad Ax = b \\ & \quad x \geq 0 \end{aligned}\] is an integer vector. Consequently, if an optimal solution exists, there is an integer optimal solution.

Canonical Form Integer Programs

Similarly, for canonical form integer programs: \[\begin{aligned} \max & \quad c^T x \\ \text{s.t.} & \quad Ax \leq b \\ & \quad x \geq 0 \\ & \quad x \in \mathbb{Z}^n \end{aligned}\] where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^m$, and $c \in \mathbb{R}^n$.

If $A$ is a totally unimodular matrix and $b$ is an integer vector, then every vertex of the polyhedron defined by $\{x \mid Ax \leq b, x \geq 0 \}$ is an integer vector. Consequently, if an optimal solution exists for the linear programming relaxation, there is an integer optimal solution.

Solving Integer Programs as Linear Programs

When the constraint matrix $A$ is totally unimodular and the right-hand side vector $b$ is integer, we can solve the integer programming problem by solving its linear programming relaxation. The optimal solution obtained from the linear program will automatically be an integer solution. This is a powerful result, as it allows us to use efficient linear programming algorithms (like the simplex method or interior-point methods) to solve certain classes of integer programming problems.

@plus6

Let $x^*$ be a basic feasible solution of the linear programming relaxation. Then, there exists a basis $B$ (a set of $m$ linearly independent columns of $A$) such that we can partition the variables into basic variables $x_B$ and non-basic variables $x_N$, where $x_N = 0$. The system $Ax = b$ can be rewritten as $Bx_B + Nx_N = b$, so $Bx_B = b$. Thus, $x_B = B^{-1}b$.

Since $A$ is totally unimodular and $B$ is a submatrix of $A$, $B$ is also totally unimodular. As $B$ is a basis, it is non-singular. From the previous theorem, we know that $B^{-1}$ is an integer matrix. Since $b$ is also an integer vector, the product $x_B = B^{-1}b$ is an integer vector. Also, $x_N = 0$ is an integer vector. Therefore, the basic feasible solution $x^* = (x_B, x_N)$ is an integer vector. endpefalse

Sufficient Conditions for Total Unimodularity

Conditions Based on Column Structure

Maximum Two Non-Zero Elements per Column

A useful sufficient condition for total unimodularity is based on the structure of the columns of the matrix.

Let $A \in \{0, +1, -1\}^{m \times n}$ be a matrix such that:

Each entry $a_{ij} \in \{0, +1, -1\}$.
In each column of $A$, there are at most two non-zero entries.
We can partition the set of row indices $M = \{1, 2, \dots, m\}$ into two sets $R_1$ and $R_2$ such that for each column $j$:
- If column $j$ has two non-zero entries with opposite signs, then both are in rows in $R_1$ or both are in rows in $R_2$.
- If column $j$ has two non-zero entries with the same sign, then one is in a row in $R_1$ and the other is in a row in $R_2$.
- If column $j$ has at most one non-zero entry, the condition is trivially satisfied.

Then, $A$ is totally unimodular.

Example Application of the Sufficient Conditions

Let’s revisit the example matrix: \[A = \begin{pmatrix} 1 & 0 & 1 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 1 \end{pmatrix}\] We can partition the rows into $R_1 = \{1, 2, 3\}$ and $R_2 = \emptyset$.

Column 1: Non-zero entries are $1$ and $-1$ (opposite signs). Both are in $R_1$. Condition satisfied.
Column 2: Non-zero entries are $1$ and $-1$ (opposite signs). Both are in $R_1$. Condition satisfied.
Column 3: Non-zero entries are $1$ and $-1$ (opposite signs). Both are in $R_1$. Condition satisfied.
Column 4: Non-zero entry is $1$. Condition satisfied.

Since all conditions are met, $A$ is totally unimodular according to this sufficient condition.

Proof of the Sufficient Conditions

We will prove the theorem by induction on the order $k$ of the square submatrix $B$. We want to show that for any $k \times k$ submatrix $B$ of $A$, $\det(B) \in \{0, +1, -1\}$.

Base Case (k=1)

For $k=1$, a $1 \times 1$ submatrix is just a single entry of $A$. Since $a_{ij} \in \{0, +1, -1\}$, the determinant is also in $\{0, +1, -1\}$. The base case holds.

Inductive Step (k>1)

Assume that for all $l < k$, the determinant of any $l \times l$ submatrix of $A$ is in $\{0, +1, -1\}$. We want to show this for a $k \times k$ submatrix $B$.

Consider a $k \times k$ submatrix $B$ of $A$. We consider different cases based on the columns of $B$.

Cases with Zero Columns or Single Non-Zero Elements

Case 1: If $B$ has a column of all zeros, then $\det(B) = 0$.
Case 2: If $B$ has a column with exactly one non-zero entry, say in row $i$ and column $j$, we can expand the determinant along column $j$. Then, \[\det(B) = (-1)^{i+j} b_{ij} \det(B_{ij})\] where $B_{ij}$ is the $(k-1) \times (k-1)$ submatrix obtained by removing row $i$ and column $j$. By the induction hypothesis, $\det(B_{ij}) \in \{0, +1, -1\}$. Also, $b_{ij} \in \{+1, -1\}$. Therefore, $\det(B) \in \{0, +1, -1\}$.

Case with Two Non-Zero Elements in Every Column

Case 3: Assume every column of $B$ has exactly two non-zero entries. Let $R_1, R_2$ be the partition of rows of $A$ satisfying condition 3. Let $r_i$ be the $i$-th row of $B$. Consider the vector $u = \sum_{i \in I_1} r_i - \sum_{i \in I_2} r_i$, where $I_1$ and $I_2$ are the row indices of $B$ that correspond to rows in $R_1$ and $R_2$ respectively.

For each column $j$ of $B$, let $b_{i_1j}$ and $b_{i_2j}$ be the two non-zero entries in column $j$. According to condition 3, if $b_{i_1j}$ and $b_{i_2j}$ have opposite signs, then both are in $R_1$ or both are in $R_2$. If they have the same sign, then one is in $R_1$ and the other is in $R_2$.

Let’s consider the sum of rows in $R_1$ minus the sum of rows in $R_2$ for matrix $B$. If the two non-zero entries have opposite signs ($+1, -1$) and both are in $R_1$, then the sum is $1 + (-1) = 0$. If the two non-zero entries have the same sign ($+1, +1$) and one is in $R_1$, one in $R_2$, then the sum is $1 - 1 = 0$. Therefore, in every column $j$, the sum $\sum_{i \in I_1} b_{ij} - \sum_{i \in I_2} b_{ij} = 0$. This means the linear combination of rows is the zero vector. Thus, the rows of $B$ are linearly dependent, and $\det(B) = 0$.

In all cases, $\det(B) \in \{0, +1, -1\}$. By induction, $A$ is totally unimodular.

Corollaries and Applications

Incidence Matrix of Directed Graphs

Total Unimodularity of Directed Graph Incidence Matrices

Let $G = (V, E)$ be a directed graph. The node-arc incidence matrix $A$ of $G$ is an $|V| \times |E|$ matrix defined as follows: for each edge $e = (i, j) \in E$ (from node $i$ to node $j$), there is a column in $A$ such that $a_{ie} = +1$, $a_{je} = -1$, and all other entries in that column are $0$.

The node-arc incidence matrix of a directed graph is totally unimodular.

@plus6

Let $A$ be the incidence matrix.

Each entry $a_{ij} \in \{0, +1, -1\}$.
Each column of $A$ has exactly two non-zero entries: $+1$ and $-1$.
Let $R_1 = V$ and $R_2 = \emptyset$. For each column $j$ (corresponding to edge $(i, j)$), we have $a_{ij} = +1$ and $a_{jj} = -1$. Both entries have opposite signs and are in $R_1$.

Thus, the incidence matrix of a directed graph satisfies the sufficient conditions and is totally unimodular. endpefalse

Incidence Matrix of Bipartite Graphs

Total Unimodularity of Bipartite Graph Incidence Matrices

Let $G = (V, E)$ be an undirected bipartite graph with bipartition $V = V_1 \cup V_2$. The node-edge incidence matrix $A$ of $G$ is a $|V| \times |E|$ matrix defined as follows: for each edge $e = \{u, v\} \in E$, there is a column in $A$ such that $a_{ue} = 1$, $a_{ve} = 1$, and all other entries in that column are $0$.

The node-edge incidence matrix of a bipartite graph is totally unimodular.

@plus6

Let $A$ be the incidence matrix of a bipartite graph.

Each entry $a_{ij} \in \{0, 1\}$.
Each column of $A$ has exactly two non-zero entries, both are $+1$.
Partition the rows according to the bipartition: $R_1 = V_1$ and $R_2 = V_2$. For each column $j$ (corresponding to edge $\{u, v\}$), we have $a_{uj} = 1$ and $a_{vj} = 1$. Since $G$ is bipartite, one endpoint is in $V_1$ and the other is in $V_2$. Thus, one entry is in a row in $R_1$ and the other is in a row in $R_2$. Both entries have the same sign, and one is in $R_1$ and the other is in $R_2$.

Thus, the incidence matrix of a bipartite graph satisfies the sufficient conditions and is totally unimodular. endpefalse

Implications for Optimization Problems on Graphs

Flow Problems, Path Problems, Transportation Problems

The total unimodularity of incidence matrices of directed and bipartite graphs has significant implications for optimization problems defined on these graphs. Many important problems can be formulated as integer programs where the constraint matrix is an incidence matrix. Since these matrices are TUM, we can solve these integer programs as linear programs, guaranteeing integer solutions.

Examples of such problems include:

Maximum Flow Problems: Can be formulated using the incidence matrix of a directed graph. The integrality theorem for max-flow min-cut follows from the TUM property.
Shortest Path Problems: Can be seen as minimum cost flow problems and formulated using incidence matrices.
Minimum Cost Flow Problems: A generalization of max-flow and shortest path, also formulated with incidence matrices.
Transportation Problems: Can be modeled using bipartite graphs and their incidence matrices.
Assignment Problems: A special case of transportation problems, also solvable using TUM properties.

These problems, when formulated using incidence matrices of directed or bipartite graphs, become naturally integer programs. This means we can efficiently solve them using linear programming techniques, which is a significant advantage in computational optimization.

Conclusion

In this lecture, we explored the concept of integral polyhedra and totally unimodular matrices. We learned that integral polyhedra guarantee integer solutions for linear programming relaxations, leading to naturally integer programs. Totally unimodular matrices play a crucial role in ensuring the integrality of polyhedra. We defined TUM matrices and examined their properties, including the integrality of the inverse of their non-singular submatrices. We also discussed sufficient conditions for a matrix to be totally unimodular, based on the structure of its columns and a partition of its rows.

We highlighted the significance of TUM matrices in integer programming by showing that if the constraint matrix of an integer program is TUM and the right-hand side vector is integer, then the integer program can be solved as a linear program. This dramatically simplifies the solution process for certain classes of integer programming problems.

Finally, we explored important applications of TUM matrices in graph theory, particularly in relation to incidence matrices of directed and bipartite graphs. We saw that the incidence matrices of directed graphs and bipartite graphs are totally unimodular. This property ensures that many optimization problems on graphs, such as flow problems, path problems, and transportation problems, can be solved efficiently using linear programming, yielding integer optimal solutions.

This understanding of integral polyhedra and totally unimodular matrices provides powerful tools for solving a wide range of optimization problems, especially those arising in network flows and combinatorial optimization. Further study in this area can lead to deeper insights and more efficient algorithms for complex optimization challenges.

Follow-up questions and topics for the next lecture could include:

More examples of problems that can be modeled using TUM matrices.
Algorithms specifically designed for network flow problems.
Further exploration of sufficient and necessary conditions for total unimodularity.
Applications of TUM matrices in more advanced optimization contexts.

--- title: "Integral Polyhedra and Totally Unimodular Matrices" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture focuses on integral polyhedra and their importance in integer programming. We will investigate how the integrality property, where all vertices of a polyhedron are integer vectors, leads to integer solutions when solving linear programs over these polyhedra. This \"naturally integer\" characteristic is highly desirable, as it enables us to solve integer programming problems using more efficient linear programming techniques. We will then introduce Totally Unimodular Matrices (TUM), a special class of matrices crucial for ensuring the integrality of polyhedra. We will define TUM matrices, examine their properties, and discuss sufficient conditions for a matrix to be totally unimodular. Understanding TUM matrices is essential for identifying integer programming problems that can be solved efficiently as linear programs. Finally, we will explore corollaries and applications of TUM matrices, particularly in graph theory, including incidence matrices of directed and bipartite graphs. These applications highlight the practical importance of TUM matrices in various optimization problems, such as flow problems, path problems, and transportation problems. # Integral Polyhedra and Integer Programming ## Definition of Integral Polyhedra ::: tcolorbox A polyhedron $P$ is called **integral** (or integer) if all its vertices are integer vectors. That is, for every vertex $v$ of $P$, $v \in \mathbb{Z}^n$. ::: An integral polyhedron is a polyhedron where every corner point has only integer coordinates. ## Linear Programming Relaxation The **linear programming relaxation** of an integer programming problem is obtained by removing the integrality constraints on the variables. Let $P$ be the feasible region of the linear programming relaxation. In general, $P$ may have fractional vertices. However, if $P$ is an integral polyhedron, then all its vertices are integer vectors. ## Naturally Integer Programs ### The Concept of \"Free\" Integrality If the polyhedron $P$ resulting from the linear programming relaxation of an integer program is integral, then solving the linear program over $P$ will always yield an integer optimal solution, if one exists. In this case, the integer programming problem is said to be **naturally integer**. The integrality comes \"for free\" because it is a property of the polyhedron itself, not enforced by explicit integrality constraints. ### Implications for Solving Integer Programs For naturally integer programs, the integrality constraint can be removed without changing the integer optimal solution. To find an integer optimal solution, we can simply solve the linear programming relaxation. The optimal solution obtained from the linear program will automatically be an integer solution. This significantly simplifies the problem, as linear programming problems can be solved efficiently in polynomial time, whereas general integer programming is NP-hard. ::: tcolorbox Naturally integer problems are highly desirable because they allow us to leverage efficient linear programming algorithms to solve problems that are inherently integer in nature. ::: # Totally Unimodular Matrices (TUM) ## Definition of Total Unimodularity ### Determinant of Submatrices ::: tcolorbox A matrix $A \in \mathbb{R}^{m \times n}$ is called **totally unimodular (TUM)** if the determinant of every square submatrix of $A$ is either $0$, $+1$, or $-1$. ::: ### Restriction on Matrix Elements A key implication of total unimodularity is that all entries of a TUM matrix must be either $0$, $+1$, or $-1$. This is because each individual entry of a matrix can be considered as a $1 \times 1$ submatrix, and its determinant (which is the entry itself) must be $0$, $+1$, or $-1$. ## Example of a TUM Matrix ::: tcolorbox Consider the following matrix: $$A = \begin{pmatrix} 1 & 0 & 1 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 1 \end{pmatrix}$$ This is a $3 \times 4$ matrix. To check if it is totally unimodular, we need to examine the determinants of all its square submatrices. - $1 \times 1$ submatrices: The determinants are the entries themselves, which are $0, 1, -1$. - $2 \times 2$ submatrices: For example, taking the first two columns: $$\begin{vmatrix} 1 & 0 \\ -1 & 1 \end{vmatrix} = (1)(1) - (0)(-1) = 1$$ Taking the first and third columns, second and third rows: $$\begin{vmatrix} -1 & 0 \\ 0 & -1 \end{vmatrix} = (-1)(-1) - (0)(0) = 1$$ - $3 \times 3$ submatrices: Taking the first three columns: $$B = \begin{pmatrix} 1 & 0 & 1 \\ -1 & 1 & 0 \\ 0 & -1 & -1 \end{pmatrix}$$ Row 1 + Row 3 = $(1, -1, 0) = -$Row 2. Thus the rows are linearly dependent, and $\det(B) = 0$. It can be verified that the determinant of every square submatrix of $A$ is $0$, $1$, or $-1$. Therefore, $A$ is a totally unimodular matrix. ::: ## Properties of TUM Matrices ### Inverses of Non-Singular Submatrices ::: tcolorbox Let $A$ be a totally unimodular matrix, and let $B$ be a non-singular square submatrix of $A$. Then, the inverse of $B$, $B^{-1}$, is an integer matrix, and all entries of $B^{-1}$ are either $0$, $+1$, or $-1$. ::: ### Proof of the Inverse Property \@plus6 Let $B$ be a non-singular $m \times m$ submatrix of $A$. From linear algebra, we know that the inverse of $B$ can be expressed using the adjugate formula: $$(B^{-1})_{ij} = \frac{(-1)^{i+j} \det(B_{ji})}{\det(B)}$$ where $B_{ji}$ is the $(j, i)$-th minor of $B$, obtained by deleting the $j$-th row and $i$-th column of $B$. Since $A$ is totally unimodular and $B$ is a submatrix of $A$, $B$ is also totally unimodular. Therefore, the determinant of any square submatrix of $B$, including $B_{ji}$ and $B$ itself, is either $0$, $+1$, or $-1$. Since $B$ is non-singular, $\det(B) \neq 0$, so $\det(B)$ must be either $+1$ or $-1$. Thus, $\det(B) \in \{+1, -1\}$. Also, $B_{ji}$ is a $(m-1) \times (m-1)$ submatrix of $B$ (and thus of $A$), so $\det(B_{ji}) \in \{0, +1, -1\}$. Therefore, $$(B^{-1})_{ij} = \frac{(-1)^{i+j} \det(B_{ji})}{\det(B)} \in \left\{ \frac{0}{\pm 1}, \frac{\pm 1}{\pm 1} \right\} = \{0, +1, -1\}$$ This shows that every entry of $B^{-1}$ is either $0$, $+1$, or $-1$. Hence, $B^{-1}$ is an integer matrix with entries from $\{0, +1, -1\}$. endpefalse # The Significance of TUM Matrices in Integer Programming ## Integer Solutions Guaranteed by TUM ### Standard Form Integer Programs Consider an integer programming problem in standard form: $$\begin{aligned} \max & \quad c^T x \\ \text{s.t.} & \quad Ax = b \\ & \quad x \geq 0 \\ & \quad x \in \mathbb{Z}^n \end{aligned}$$ where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^m$, and $c \in \mathbb{R}^n$. ::: tcolorbox If $A$ is a totally unimodular matrix and $b$ is an integer vector, then every basic feasible solution of the linear programming relaxation $$\begin{aligned} \max & \quad c^T x \\ \text{s.t.} & \quad Ax = b \\ & \quad x \geq 0 \end{aligned}$$ is an integer vector. Consequently, if an optimal solution exists, there is an integer optimal solution. ::: ### Canonical Form Integer Programs Similarly, for canonical form integer programs: $$\begin{aligned} \max & \quad c^T x \\ \text{s.t.} & \quad Ax \leq b \\ & \quad x \geq 0 \\ & \quad x \in \mathbb{Z}^n \end{aligned}$$ where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^m$, and $c \in \mathbb{R}^n$. ::: tcolorbox If $A$ is a totally unimodular matrix and $b$ is an integer vector, then every vertex of the polyhedron defined by $\{x \mid Ax \leq b, x \geq 0 \}$ is an integer vector. Consequently, if an optimal solution exists for the linear programming relaxation, there is an integer optimal solution. ::: ## Solving Integer Programs as Linear Programs When the constraint matrix $A$ is totally unimodular and the right-hand side vector $b$ is integer, we can solve the integer programming problem by solving its linear programming relaxation. The optimal solution obtained from the linear program will automatically be an integer solution. This is a powerful result, as it allows us to use efficient linear programming algorithms (like the simplex method or interior-point methods) to solve certain classes of integer programming problems. \@plus6 Let $x^*$ be a basic feasible solution of the linear programming relaxation. Then, there exists a basis $B$ (a set of $m$ linearly independent columns of $A$) such that we can partition the variables into basic variables $x_B$ and non-basic variables $x_N$, where $x_N = 0$. The system $Ax = b$ can be rewritten as $Bx_B + Nx_N = b$, so $Bx_B = b$. Thus, $x_B = B^{-1}b$. Since $A$ is totally unimodular and $B$ is a submatrix of $A$, $B$ is also totally unimodular. As $B$ is a basis, it is non-singular. From the previous theorem, we know that $B^{-1}$ is an integer matrix. Since $b$ is also an integer vector, the product $x_B = B^{-1}b$ is an integer vector. Also, $x_N = 0$ is an integer vector. Therefore, the basic feasible solution $x^* = (x_B, x_N)$ is an integer vector. endpefalse # Sufficient Conditions for Total Unimodularity ## Conditions Based on Column Structure ### Maximum Two Non-Zero Elements per Column A useful sufficient condition for total unimodularity is based on the structure of the columns of the matrix. ::: tcolorbox Let $A \in \{0, +1, -1\}^{m \times n}$ be a matrix such that: 1. Each entry $a_{ij} \in \{0, +1, -1\}$. 2. In each column of $A$, there are at most two non-zero entries. 3. We can partition the set of row indices $M = \{1, 2, \dots, m\}$ into two sets $R_1$ and $R_2$ such that for each column $j$: - If column $j$ has two non-zero entries with opposite signs, then both are in rows in $R_1$ or both are in rows in $R_2$. - If column $j$ has two non-zero entries with the same sign, then one is in a row in $R_1$ and the other is in a row in $R_2$. - If column $j$ has at most one non-zero entry, the condition is trivially satisfied. Then, $A$ is totally unimodular. ::: ## Example Application of the Sufficient Conditions Let's revisit the example matrix: $$A = \begin{pmatrix} 1 & 0 & 1 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 1 \end{pmatrix}$$ We can partition the rows into $R_1 = \{1, 2, 3\}$ and $R_2 = \emptyset$. - Column 1: Non-zero entries are $1$ and $-1$ (opposite signs). Both are in $R_1$. Condition satisfied. - Column 2: Non-zero entries are $1$ and $-1$ (opposite signs). Both are in $R_1$. Condition satisfied. - Column 3: Non-zero entries are $1$ and $-1$ (opposite signs). Both are in $R_1$. Condition satisfied. - Column 4: Non-zero entry is $1$. Condition satisfied. Since all conditions are met, $A$ is totally unimodular according to this sufficient condition. ## Proof of the Sufficient Conditions We will prove the theorem by induction on the order $k$ of the square submatrix $B$. We want to show that for any $k \times k$ submatrix $B$ of $A$, $\det(B) \in \{0, +1, -1\}$. ### Base Case (k=1) For $k=1$, a $1 \times 1$ submatrix is just a single entry of $A$. Since $a_{ij} \in \{0, +1, -1\}$, the determinant is also in $\{0, +1, -1\}$. The base case holds. ### Inductive Step (k\>1) Assume that for all $l < k$, the determinant of any $l \times l$ submatrix of $A$ is in $\{0, +1, -1\}$. We want to show this for a $k \times k$ submatrix $B$. Consider a $k \times k$ submatrix $B$ of $A$. We consider different cases based on the columns of $B$. ### Cases with Zero Columns or Single Non-Zero Elements - Case 1: If $B$ has a column of all zeros, then $\det(B) = 0$. - Case 2: If $B$ has a column with exactly one non-zero entry, say in row $i$ and column $j$, we can expand the determinant along column $j$. Then, $$\det(B) = (-1)^{i+j} b_{ij} \det(B_{ij})$$ where $B_{ij}$ is the $(k-1) \times (k-1)$ submatrix obtained by removing row $i$ and column $j$. By the induction hypothesis, $\det(B_{ij}) \in \{0, +1, -1\}$. Also, $b_{ij} \in \{+1, -1\}$. Therefore, $\det(B) \in \{0, +1, -1\}$. ### Case with Two Non-Zero Elements in Every Column Case 3: Assume every column of $B$ has exactly two non-zero entries. Let $R_1, R_2$ be the partition of rows of $A$ satisfying condition 3. Let $r_i$ be the $i$-th row of $B$. Consider the vector $u = \sum_{i \in I_1} r_i - \sum_{i \in I_2} r_i$, where $I_1$ and $I_2$ are the row indices of $B$ that correspond to rows in $R_1$ and $R_2$ respectively. For each column $j$ of $B$, let $b_{i_1j}$ and $b_{i_2j}$ be the two non-zero entries in column $j$. According to condition 3, if $b_{i_1j}$ and $b_{i_2j}$ have opposite signs, then both are in $R_1$ or both are in $R_2$. If they have the same sign, then one is in $R_1$ and the other is in $R_2$. Let's consider the sum of rows in $R_1$ minus the sum of rows in $R_2$ for matrix $B$. If the two non-zero entries have opposite signs ($+1, -1$) and both are in $R_1$, then the sum is $1 + (-1) = 0$. If the two non-zero entries have the same sign ($+1, +1$) and one is in $R_1$, one in $R_2$, then the sum is $1 - 1 = 0$. Therefore, in every column $j$, the sum $\sum_{i \in I_1} b_{ij} - \sum_{i \in I_2} b_{ij} = 0$. This means the linear combination of rows is the zero vector. Thus, the rows of $B$ are linearly dependent, and $\det(B) = 0$. In all cases, $\det(B) \in \{0, +1, -1\}$. By induction, $A$ is totally unimodular. # Corollaries and Applications ## Incidence Matrix of Directed Graphs ### Total Unimodularity of Directed Graph Incidence Matrices Let $G = (V, E)$ be a directed graph. The **node-arc incidence matrix** $A$ of $G$ is an $|V| \times |E|$ matrix defined as follows: for each edge $e = (i, j) \in E$ (from node $i$ to node $j$), there is a column in $A$ such that $a_{ie} = +1$, $a_{je} = -1$, and all other entries in that column are $0$. ::: tcolorbox The node-arc incidence matrix of a directed graph is totally unimodular. ::: \@plus6 Let $A$ be the incidence matrix. 1. Each entry $a_{ij} \in \{0, +1, -1\}$. 2. Each column of $A$ has exactly two non-zero entries: $+1$ and $-1$. 3. Let $R_1 = V$ and $R_2 = \emptyset$. For each column $j$ (corresponding to edge $(i, j)$), we have $a_{ij} = +1$ and $a_{jj} = -1$. Both entries have opposite signs and are in $R_1$. Thus, the incidence matrix of a directed graph satisfies the sufficient conditions and is totally unimodular. endpefalse ## Incidence Matrix of Bipartite Graphs ### Total Unimodularity of Bipartite Graph Incidence Matrices Let $G = (V, E)$ be an undirected bipartite graph with bipartition $V = V_1 \cup V_2$. The **node-edge incidence matrix** $A$ of $G$ is a $|V| \times |E|$ matrix defined as follows: for each edge $e = \{u, v\} \in E$, there is a column in $A$ such that $a_{ue} = 1$, $a_{ve} = 1$, and all other entries in that column are $0$. ::: tcolorbox The node-edge incidence matrix of a bipartite graph is totally unimodular. ::: \@plus6 Let $A$ be the incidence matrix of a bipartite graph. 1. Each entry $a_{ij} \in \{0, 1\}$. 2. Each column of $A$ has exactly two non-zero entries, both are $+1$. 3. Partition the rows according to the bipartition: $R_1 = V_1$ and $R_2 = V_2$. For each column $j$ (corresponding to edge $\{u, v\}$), we have $a_{uj} = 1$ and $a_{vj} = 1$. Since $G$ is bipartite, one endpoint is in $V_1$ and the other is in $V_2$. Thus, one entry is in a row in $R_1$ and the other is in a row in $R_2$. Both entries have the same sign, and one is in $R_1$ and the other is in $R_2$. Thus, the incidence matrix of a bipartite graph satisfies the sufficient conditions and is totally unimodular. endpefalse ## Implications for Optimization Problems on Graphs ### Flow Problems, Path Problems, Transportation Problems The total unimodularity of incidence matrices of directed and bipartite graphs has significant implications for optimization problems defined on these graphs. Many important problems can be formulated as integer programs where the constraint matrix is an incidence matrix. Since these matrices are TUM, we can solve these integer programs as linear programs, guaranteeing integer solutions. Examples of such problems include: - **Maximum Flow Problems**: Can be formulated using the incidence matrix of a directed graph. The integrality theorem for max-flow min-cut follows from the TUM property. - **Shortest Path Problems**: Can be seen as minimum cost flow problems and formulated using incidence matrices. - **Minimum Cost Flow Problems**: A generalization of max-flow and shortest path, also formulated with incidence matrices. - **Transportation Problems**: Can be modeled using bipartite graphs and their incidence matrices. - **Assignment Problems**: A special case of transportation problems, also solvable using TUM properties. These problems, when formulated using incidence matrices of directed or bipartite graphs, become naturally integer programs. This means we can efficiently solve them using linear programming techniques, which is a significant advantage in computational optimization. # Conclusion In this lecture, we explored the concept of integral polyhedra and totally unimodular matrices. We learned that integral polyhedra guarantee integer solutions for linear programming relaxations, leading to naturally integer programs. Totally unimodular matrices play a crucial role in ensuring the integrality of polyhedra. We defined TUM matrices and examined their properties, including the integrality of the inverse of their non-singular submatrices. We also discussed sufficient conditions for a matrix to be totally unimodular, based on the structure of its columns and a partition of its rows. We highlighted the significance of TUM matrices in integer programming by showing that if the constraint matrix of an integer program is TUM and the right-hand side vector is integer, then the integer program can be solved as a linear program. This dramatically simplifies the solution process for certain classes of integer programming problems. Finally, we explored important applications of TUM matrices in graph theory, particularly in relation to incidence matrices of directed and bipartite graphs. We saw that the incidence matrices of directed graphs and bipartite graphs are totally unimodular. This property ensures that many optimization problems on graphs, such as flow problems, path problems, and transportation problems, can be solved efficiently using linear programming, yielding integer optimal solutions. This understanding of integral polyhedra and totally unimodular matrices provides powerful tools for solving a wide range of optimization problems, especially those arising in network flows and combinatorial optimization. Further study in this area can lead to deeper insights and more efficient algorithms for complex optimization challenges. Follow-up questions and topics for the next lecture could include: - More examples of problems that can be modeled using TUM matrices. - Algorithms specifically designed for network flow problems. - Further exploration of sufficient and necessary conditions for total unimodularity. - Applications of TUM matrices in more advanced optimization contexts.