I have the matrix below:
$A=\begin{pmatrix} 0&1&0&0&0 \\ 0&1&1&1&1\\ 1&0&1&1&1\\ 1&0&0&1&0\\ 1&0&0&0&0\\ \end{pmatrix}.$
It satisfies the consecutive ones property and thus, is a totally unimodular matrix (TUM). The consecutive ones property is proven by the partition theorem, which states that:
A is TU iff for every $Q \subset \{ 1,\cdots,m \}$, there exists a partition $Q_1$, $Q_2$ of $Q$ such that:
$\sum_{i\in Q_1}a_{ij}-\sum_{i\in Q_2}a_{ij} \in \lbrace 0,\pm1 \rbrace$
However, if I choose the third and fourth row, the difference cannot be less than 2. What am I understanding wrong here?
PS: This is my first post, so I am not completely sure about the rules. Please let me know if I am making a mistake. I will correct it. Thank you.
The difference-of-sums condition is applied separately for each column $j$. In other words, it should be written as $$\sum_{i\in Q_1}a_{ij}-\sum_{i\in Q_2}a_{ij} \in \lbrace 0,\pm1 \rbrace\quad \forall j.$$ If you set $Q=\lbrace 3,4\rbrace$, then $Q_1 = \lbrace 3 \rbrace$ and $Q_2 = \lbrace 4 \rbrace$ (or vice versa). Using the former, your differences are $0,0,1,0,1.$