Paul Seymour is an english mathematician, graduated from Oxford. He is currently teaching at Princeton.

His research area concentrates on discrete mathematics, where he obtained important results including in Regular Matroids, Totally Unimodular Matrices and the Four Color Theorem, being awarded the Fulkerson Prize four times.

In this post we’ll present one of his results regarding decomposition of totally unimodular matrices, which are the key piece in deciding whether a given matrix is TU.

This is the third post about Totally Unimodular (TU) matrices. We introduced them here and described a special case called Network matrices here.

Although it’s not true that all TU matrices are network matrices, Seymour’s theorem basically says that all TU matrices are some kind of combination of network matrices and the following matrices:

It’s possible to show that TU matrices are closed under the following operations:

(i) permuting rows or columns

(ii) taking the transpose

(iii) multiplying a row or column by -1

(iv) pivoting, that is, transforming

into

where is a scalar and and are a row and a column vector of the appropriate sizes, respecitvely.

(v) adding a row or column with at most one non-zero entry

(vi) repeating a row or a column

Also, given TU matrices A and B, the following operations preserve total unimodularity:

1-sum:

(vii)

2-sum:

(viii)

3-sum:

(ix)

We can now state Seymour’s theorem:

**Theorem 1.** (Seymour’s decomposition theorem for totally unimodular matrices). *A matrix is totally unimodular if and only if arises from network matrices and the matrices (1) and (2) by applying the operations (i) to (ix). Here, the operations (vii) to (ix) are only applied if for and , the number of rows and columns added is at least 4.*

### Recognizing Total Unimodularity

The algorithm for recognizing whether a given matrix is TU consists in finding whether it is a network matrix or one the matrix (1) or (2).

1. If any of the entries of M is not in , then is not TU.

2. Remove all rows and columns with one or less non-zero entries (Property (v)).

3. Remove repeated rows and columns (Property (vi)).

4. Test if or its transpose is a network matrix or (1) or (2), possibly permuting and multiplying rows and columns by -1 (Properties (i), (ii) and (iii)). If yes, then the matrix is TU.

At this point of the algorithm, we still don’t know whether our matrix is TU. We’ll now check whether can be decomposed as follows:

(3)

such that and for both and , the number of rows plus the number of columns is greater or equal than 4.

Cunningham and Edmonds stated it’s possible to find such a decomposition for a matrix or conclude no such decomposition exists in polynomial time using the matroid intersection algorithm.

Going back to the algorithm:

5. If has cannot be decomposed as (3), then it’s not TU.

6. If it can, then we break into cases depending on the values of and . Given that , we have the 6 possible combinations:

*Case 1:*

A matrix with rank zero is the zero matrix, so we have

By Property (vii), if and are TU, is TU. Since and are submatrices of , the converse holds, so it suffices to recursively verify that and are TU.

*Case 2:*

Since has rank 1, it has all duplicate rows/columns or rows/columns with all zeroes. Thus, we can write it as , where is a column vector and is a row vector. In this form, we can write M as the result of the 3-sum operation:

From Property (viii), if and are TU, is TU. Also, since both are submatrices of , if one of them is not TU, then can’t be TU either, so we can test and recursively.

*Case 3:* Analogous to Case 2.

*Case 4: *

In this case, both and have all duplicate rows/columns or rows/columns with all zeroes. We can re-arrange the rows and columns in such a way that looks like this:

where

and

We define a bipartite graph with one partition being the set of rows of and the other partition the set of columns of . There’s an edge between two vertices and if the entry is non-zero in .

Let be the set of vertices of the row partition that intercepts and those of the column partition that intercepts . If there’s no path between and , then we can reduce to Cases 2 and 3, so without loss of generality, consider the shortest path between and .

Since and are in different partitions, has odd length . Let

and defined analogously.

(4)

(5)

The algorithm says that M is TU if and only if (4) and (5) are TU.

*Case 5:* Can be reduced to Case 4 by pivoting (Property iv).

*Case 6:* Analogous to Case 5.

### Complexity and Implementation

In [2], Truemper presents a algorithm for the total unimodularity testing and in [3] he Walter and Truemper provides an implementation in C++ of a simplified version.

### Conclusion

The matroid intersection algorithm is used in one of the steps of the algorithm. I’ve heard about this algorithm before, but never studied it, so this will the next subject I’m researching about in the series of posts on Combinatorial Optimization.

### References

[1] Theory of Linear and Integer Programming – A. Schrijver (Chapter 20)

[2] A decomposition theory for matroids. V. Testing of matrix total unimodularity – K. Truemper

[3] Implementation of a Unimodularity Test – M. Walter and K. Truemper

I have C matrix made up of block matrices as follows

C = [

A 0 0 0 .. 0 0

B 0 0 0 .. 0 0

0 A 0 .. 0 0

0 B 0 .. 0 0

…

0 0 0 … 0 A

0 0 0 .. 0 B

———————–

I I 0 .. 0 0

0 I I .. 0 0

0 0 I .. 0 0

….

0 0 0 … I I

]

where

A = [

1 1 .. 1 0 0 .. 0 0 0 .. 0 …… 0 0 .. 0

0 0 .. 0 1 1 .. 1 0 0 .. 0 …… 0 0 .. 0

0 0 .. 0 0 0 .. 0 1 1 .. 1 …… 0 0 .. 0

…..

0 0 .. 0 0 0 .. 0 0 0 .. 0 …… 1 1 .. 1

]

with runs of 1 in all the rows having the same length,

B = [

1 0 .. 0 1 0 .. 0 1 0 .. 0 …… 1 0 .. 0

0 1 .. 0 0 1 .. 0 0 1 .. 0 …… 0 1 .. 0

0 0 .. 0 0 0 .. 0 0 0 .. 0 …… 0 0 .. 0

…..

0 0 .. 1 0 0 .. 1 0 0 .. 1 …… 0 0 .. 1

]

where identity matrices (with size same as the runs of 1 in A matrix) are concatenated in column dimension

and

I is identity matrix compatible with size same as the number of columns of A (or B).

Is this matrix totally, unimodular or balanced or perfect?