Link between the system matrix and the transportation tableau in the transportation problem

Question

I understand how the method of potentials works (I know the steps) and I can vaguely see its resemblance to revised simplex method. But I just don't have enough intuitive sense about it in order to understand some theory behind it.

In particular, in my textbook there is a proof about a theorem that characterizes what the basis of the problem matrix is when viewed from the transportation tableau point of view. I know, from solving problems, that it has something to do with specific types of cycles that can be detected on the transportation tableau, but I'm having trouble with the formal specifications.

Before I show the main theorem, here are some definitions and terminology that my textbook uses (it's not in English so some stuff might not be translated perfectly, but I hope it wont be a problem).

We defined the problem as follows: $$\min \sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij} \\ \text{subject to constraints:} \\ \sum_{j=1}^nx_{ij} = a_i \text{ for } i = 1, ... m \\ \sum_{i=1}^mx_{ij} = b_j \text{ for } j = 1, ... n \\ x_{ij} \geq 0 \text{ for } i = 1,...m \text{ } j=1,...n$$

We call the system matrix the actual matrix representing constraints of the problem (not the transportation tableau). So that would be the $(m+n) \times mn$ matrix. Then there is a short discussion stating a few characteristics of the system matrix. We notice, other then the obvious fact that all elements are either $1$s or $0$s, the fact that every column contains exactly two $1$s. This makes sense, since every variable will appear once per its corresponding $a$-constraint and once per $b$-constraint (also a piece of terminology further used).

Now we introduce a transportation tableau. We define it as a tableau of size $(m+1) \times (n+1)$ where the last row and last column are reserved for demands and supplies respectfully, while every other field $P_{ij}$ will correspond to a variable $x_{ij}$ which, in turn, corresponds to an entire column in our original system matrix.

Now we define cycles as follows:

Let $P_1, P_2, ... P_{2k}$ be a sequence of fields in the transportation tableau. We say that they form a cycle if $P_1$ and $P_2$ are in the same row, $P_2$ and $P_3$ are in the same column, ..., $P_{2k-1}$ and $P_{2k}$ are in the same row, $P_{2k}$ and $P_1$ are in the same column. A subset of fields of the transportation tableau that contains no cycles is called acyclic.

Then comes the following theorem:

For any set of columns from the system matrix, those columns are linearly independent if and only if their corresponding fields in the transportation tableau are acyclic.

Now comes the proof, which is in two parts (two implications)

1. In order to prove that if columns are linearly independent then their fields are acyclic, we will negate the theorem and reverse the implication direction, meaning we will prove that if fields are cyclic then the columns are NOT linearly independent. Let $P_1, .... P_{2m}$ be a cycle of fields from the tableau and let the column $k_i$ from the system matrix correspond to field $P_i$. We see that $k_1 - k_2 + k_3 - k_4 ... + k_{2m - 1} - k_{2m} = 0$, therefore the columns are not linearly independent. This seems to somewhat make sense since every time we move within the cycle we're either on the same $i$ or the same $j$ which means something will cancel out every time.

The other direction, however, is extremely confusing.

2. Now we're looking to show that if a set of fields is acyclic then their columns are linearly independent. We use contradiction: Assume that some columns are not linearly independent. Therefore some column $k_m$ can be expressed as $k_m = \sum_{j=1}^r\lambda_jk_j$. From this point on I will quote my textbook word for word since I can barely understand anything.

This representation of the column $k_m$ is unique, and the coefficients $\lambda_1, ... \lambda_r$ can be found using the Cramer's rule as the quotients of two minors of the system matrix. Since the matrix is totally unimodular, all coefficients are 0, -1 or 1 and they're not all zero. Using the fact that every column has two $1$s (one from $a$ and one from $b$) and every other element being zero, it is easy to see that the field $P_m$, with some other fields $P_j$ that correspond to coefficients $\lambda_j \neq 0$, forms a cycle.

This is so beyond my understanding that I cannot even make a single useful remark. It's as if the book assumes that I know this stuff already and is just giving me a small reminder.

So, could anyone help me out?

Thanks in advance.

Answer 1

Total unimodularity means that every square submatrix of your system matrix has determinant zero, one, or minus one.

Cramer's rule states that the $\lambda_j$ which solve the system $k_{r+1}=\sum_{j=1}^r \lambda_j k_j$ (not that I'm writing $r+1$ instead of $m$, as I find that a little bit clearer) can be written as ratio's of determinants of square submatrices of the system matrix; this is a general property of non-singular linear systems.

But, why is the system $k_{r+1}=\sum_{j=1}^r \lambda_j k_j$ non-singular? In this case, the non-singularity follows from the implicit assumption that the $k_1, \dots, k_r$ are linearly independent (even though $k_1, \dots, k_r, k_{r+1}$ are not). Indeed, if vectors $k_1,\dots,k_{r+1}$ are linearly dependent, then it is always possible to find a subset of vectors such that $k_1,\dots,k_{r'}$ are linearly independent but $k_1,\dots,k_{r'+1}$ are linearly dependent. To see this, start with the first vector $k_1$, and keep adding vectors, stopping as soon as you have a linearly dependent set of vectors.

I agree that your textbook muddles this point a little bit as it does not make it clear that the $k_1, \dots, k_r$ can be assumed linearly independent.

So, from this we know that the $\lambda_i$ are all $0$, $+1$, or $-1$. Without loss of generality, by dropping any columns with coefficients $0$, we know that there are columns in the set of fields such that:

$$\sum_{j=1}^{r+1}\lambda_j k_j=0$$

with all $\lambda_j\in\{+1,-1\}$. I've not reflected the change of indexing when removing columns that have zero coefficients, for ease of notation.

Now consider some column $k_{\ell}$ with $\ell\in\{1,\dots,r+1\}$, say with coefficient $\lambda_{\ell}=+1$, and with $k_{\ell i}=1$ and $k_{\ell j}=1$, where $i$ corresponds to a specific row in the transportation tableau, and $j$ corresponds to a specific column in the transportation tableau (and $k_{\ell}$ is zero everywhere else except at these two indices). By the linear relation that we derived, there must be at least one further column $k_{\ell'}$ which has a coefficient $\lambda_{\ell'}=-1$ and which also has $k_{\ell'i}=1$, and thus, corresponding to the same row in the transportation tableau. Similarly, there must be at least one further column $k_{\ell''}$ which has a coefficient $\lambda_{\ell''}=-1$ and which also has $k_{\ell''j}=1$, and thus, corresponding to the same column in the transportation tableau.

In case $\lambda_\ell=-1$, the reasoning is the same, except that now we'll have coefficients $\lambda_{\ell'}=+1$ and $\lambda_{\ell''}=+1$.

Remember that each column corresponds to a field in the transportation tableau. So, for every field in the set, we have shown that there is another field in the set on the same row of the tableau, and another field in the set on the same column of the tableau. Whence, these fields must clearly form a cycle.

To wrap up, we have shown that, for every set of fields, if the columns of the system matrix corresponding to the set are linearly dependent, then the set of fields must contain a cycle. Note that there may be more fields on the set than just the ones in the cycle. This makes sense, since we can always add fields and obviously still retain linear dependence.