NO - TUM (Total Unimodular Matrix)

---

More Information: How can we identify a TU Matrix

NO - Identify a TUM (Totally Unimodular Matrix)

• Original Source: Wikipedia

---

A Matrix $M$ is TU (Totally Unimodular) if:

1. Every entry in $M$ is $0$, $+1$, or $-1$.
2. Every column of $M$ contains at most two non-zero (i.e., $+1$ or $-1$) entries
3. Assert that it is possible to divide the rows of $M$ in 2 groups ($\mathcal{B}$ and $\mathcal{C}$) respecting the following rules: → If two non-zero entries in a column of $M$ have the same sign, then the row of one is in the $\mathcal{B}$ group and the other one in the $\mathcal{C}$ group → If two non-zero entries in a column of $M$ have opposite signs, then the rows of both are in the $\mathcal{B}$ group, or are both in the $\mathcal{C}$ group.

NOTE: If one of the 2 groups ($\mathcal{B}$ or $\mathcal{C}$) is empty then the related IP (Integer Problem) is unbounded

---

~ Ex.: $2\times 2$ Matrix

$$\left[\begin{array}{cc}1& -1\\ 1& 1\end{array}\right]$$

✓ All elements are either $-1$, $0$, $+1$ ✓ In each column we have at most 2 non-zero elements ✗ According to the first column the 2 rows must be in the same group, but according to the second column the 2 rows must also be in different groups → This matrix is not TU

---

~ Ex.: $4\times 4$ Matrix

$$\left[\begin{array}{cccc}1& -1& -1& 0\\ -1& 0& 0& -1\\ 0& 1& 0& -1\\ 0& 0& 1& 0\end{array}\right]$$

✓ All elements are either $-1$, $0$, $+1$ ✓ In each column we have at most 2 non-zero elements ✓ ${\text{row}}_1\in \mathcal{B}$, ${\text{row}}_2\in \mathcal{B}$ ✓ ${\text{row}}_1\in \mathcal{B}$, ${\text{row}}_3\in \mathcal{B}$ ✓ ${\text{row}}_1\in \mathcal{B}$, ${\text{row}}_4\in \mathcal{B}$ ✓ ${\text{row}}_2\in \mathcal{B}$, ${\text{row}}_3\in \mathcal{C}$

$$\begin{array}{cc}\begin{array}{c}\mathcal{B}\\ \mathcal{B}\\ \mathcal{C}\\ \mathcal{B}\end{array}& \left[\begin{array}{cccc}1& -1& -1& 0\\ -1& 0& 0& -1\\ 0& 1& 0& -1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

→ This matrix is TU

Link to original

---

Another explanation I found on YouTube is reported here

---

---

More Information: Why are TUM Matrices important ?

• Original Source: Wikipedia

From previous slides we have seen that Pure LP (Linear Problems) are $\mathcal{P}$ problems (solvable in polynomial time), due to the fact that all vertices of the feasible solution are local optima and one of them is the optimal solution, (or the problem is unbounded or unfeasible), we have also seen one algorithm (the simplex method) to find the optimal solution.

So if a given IP have all integer vertices we can use the same method, to easily see if that is the case we assert that the $A$ matrix of the canonical formulation is a TUM (Totally Unimodular Matrix).

If it is than we can say that the feasible region of the problem is an integer polyhedron an all vertices of the problem are in fact integers.

A TU Matrix is most often found in graph-related problems, for example take the incidence matrix of a graph, its elements can only be $\{0,-1,+1\}$.