Recall what the meaning of the Paull matrix is: entry (i,j) contains the set of numbers m[i,j] such that the left crossbar i is connected via all k ∈ m[i,j] to the right crossbar j. If crossbar k would occur more than once in a row, e.g., in entries (i,j1) and (i,j2), it would mean that we connect input crossbar i to the middle crossbar k which should then be connected to the two output corssbars j1 and j2. However, that is impossible since the input i of the middle crossbar k is routed either to its output j1 or j2, but not to both.
Analogously, if crossbar k would occur more than once in a column, e.g., in entries (i1,j) and (i2,j), it would mean that we connect input crossbars i1 and i2 to the middle crossbar k which should then be connected to the output corssbar j. However, that is impossible since only either input i1 or i2 of the middle crossbar k can be connected to its output j, but not to both.
Hence, every k∈{0,...,r2−1} can occur at most once in each row and at most once in each column. Do you agree?
For routing in Clos networks, there are many solutions in general. The problem is equivalent to find perfect matchings in bipartite graphs which also has typically more than one solution.
