In this post we’re going to write about a special case of the matrix, which is called network matrix. They play an important role in our study of totally unimodular matrices.
We’ll first define a network matrix and provide an example. We’ll later show some properties and then describe a polynomial-time algorithm to recognize network matrices.
Network matrices were first defined by William Tutte (1965) . The definition is the following:
Let be a directed graph and be a directed tree on the vertex set . Let be the matrix -matrix defined by and .
Matrices with this structure are called network matrices.
Example. In Figure 1 we see a sample digraph and a given directed tree on the vertex set . The corresponding network matrix represented by and is given on Table 1.
For each arc , we have a column in representing the path from to in T. The signs indicate the direction of the edges in the path.
Let be a network matrix, represented by the digraph and the directed tree .
1) Multiplying a row of by -1 is equivalent to inverting the direction of the corresponding edge in .
2) Multiplying a column of by -1 is the same as inverting the direction of the corresponding edge in .
3) Deleting a row of corresponding to edge of , is the same as shrinking vertex and into a single vertex.
4) Deleting a column of is equivalent to removing the corresponding edge from .
Combining properties (3) and (4), we have that:
5) A submatrix of a network matrix is a network matrix as well.
The following theorem is the most important property about Network Matrices, that we’ll explore in the forthcoming posts about Integer Programming Theory:
Theorem 1. Networks matrices are Totally Unimodular.
Recognizing Network Matrices
There is a polynomial-time algorithm for deciding whether a matrix is a network matrix. Without loss of generality we restrict ourselves to matrices, since all network matrices are of this type and we can easily find out whether a matrix has such property.
We now divide it in two cases. Case 1: for all columns of , it has at most two non-zero entries; Case 2: the remaining types, that is, has at least one column with three or more non-zero entries.
Case 1. Let’s describe the algorithm for the first case. Let M be a , matrix with at most 2 non-zero entries.
If has, for each column, at most one entry 1 and at most on entry -1, we can show it’s a network matrix by constructing a digraph and a tree such that their corresponding network matrix is . We first build a direct star with m vertices and with all edges pointing towards the center vertex . We now build the digraph with the same vertex set. For each column in that has an entry +1 and -1 for rows and we add an edge . For columns having a single entry for row , we add the to if it’s +1 or if it’s -1.
The problem is that even in the restrictive Case 1, we may have both entries with the same signal. From property (1) though, we can multiply some rows by -1 and try to reach the case above. The question is then: can we split the rows into sets and , in such a way that if we multiply rows in by -1, we have at most one entry +1 and at most one entry -1 for all columns?
This question can be answered by a neat reduction to problem of deciding wether a graph is bipartite. Let be a graph with vertex set corresponding to each row of plus some artificial vertices. We add an edge if the corresponding rows have the same signal for some column. We add edges and if the have different signs. We then try to split this graph into two partitions and .
The idea is that if such a partitioning exists, vertex with different signs will be in the same partition because they share a common vertex and vertex with the same signs must be on different partitions. If we now multiply all rows in by -1, we’ll have our property.
Conversely, if no partition exists, it’s possible to show (see Example 1, from this post) that such matrix is not TU. Since by Theorem 1 all network matrices are TU, we conclude that this matrix is also not a network matrix. Summarizing we have that
Observation 1. The matrix from the Case 1 is a network matrix if and only if its graph define as above is bipartite.
Case 2. Now let’s concentrate on the more general case, where the matrix has at least one column with 3 or more non-zero entries.
For each row i of , we define a graph with vertex set . There’s an edge between and if exists any column in M such that it has non-zero entries for j and k, but 0 for i. We have the following observation:
Observation 2. If is a network matrix, there exists a row for which is disconnected.
The basic idea in understanding this observation is that since there is at least one column in with three non-entries, there must be a path in T that connects two vertices in with length at least 3. There is some edge i from the middle of this path that is not the first nor the last edge, henceforth denoted as and . If we remove this edge, we will split it into two components. It’s then easy to see that any path in the tree that has and needs to go through . In turn, this means that there is no edge between the corresponding vertices in .
From Observation 2, we can conclude that if a given matrix has for all possible columns , then is not a network matrix.
So we can now suppose our candidate matrix has a disconnected (we can assume without loss of generality. Let be the connected components of .
* as the set of column indexes for which the first row of M has non-zero entries;
* the set of column indexes for which the -th row of has non-zero entries;
Now, we build a graph with vertex set , with an edge if the following conditions are met:
and let be the submatrix formed by the rows of corresponding to vertices in .
We now can state the following Theorem:
Theorem 2. M is a Network Matrix if and only if: is bipartite and is a network matrix for .
Theorem 3. The algorithm above to detect whether a given matrix is a network matrix has polynomial-time complexity.
1. Check if has only entries in
2. Test if has at most two non-zero entries for each column (Case 1 or Case 2)
3. Case 1: Construct the graph and check whether it is bipartite.
4. Case 2: For each column i, construct graph and check if it is not connected. In this case, we build the graph and build each of the submatrices .
If we assume the matrix is , (1) and (2) can be performed in linear size of the matrix, . We can construct in as well and test for bipartiteness in linear time on the number of vertices plus the edges of , which are both , so (3) is bounded by too.
For step (4), we need to generate the graph . Its edges are bounded by and we can decide it’s connected in linear time of its size. Doing this for all columns we a total complexity of .
For the recursive complexity, we can relax our complexity for Steps 1 to 4 to be for a fixed constant . By induction, we assume our total complexity for a given level of the recursion is .
The matrix has rows and columns, can be solved, by induction, in . Summing up all the complexities we have:
The base is when we do steps 1 to 4 without building any submatrices, which we saw it is .
The main points to be taken from this post is that network matrices are totally unimodular and that they can be recognized in polynomial-time.
We provided explanations about the two observations, but we left out the proofs of the Theorems 1 and 2, which are quite long and complicated, and thus out of the scope of the post. Nevertheless, they can be found on .
 Theory of Linear and Integer Programming – A. Schrijver (Chapter 19)