In the following picture the "BUTTERFLY NETWORKS" with edge capacity equal $1$,
we define vector associated to edge $ST$ by $f_{ST}$, so we have the vectors for all edges as :
and also from the max flow min cut theorem, the max flow from source $S$ to any node in the network is the number of edges whose removable disconnect $S$ to this node , because the capacity of edges here is one. we not the max flow from $S$ to any node non source (not $S$) $T$ on this network by $$maxflow(T).$$For example $maxflow(U)=1$,$maxflow(Z)=2$.
Write $V_T =\langle \{f_e : e \in In(T)\} \rangle$ , where $\langle \cdot \rangle$ is spane, and $e \in In(T)$ the vector for edges in in node $T$.
For example $V_W =\langle \{f_{TW},f_{UW} \} \rangle$.
We define for this example $\omega=2$.
and we have the following condition :
(2.5) $dim(V_T) = \omega$ for every non-source ( not node $S$) node $T$ with $maxflow(T) ≥ ω$.
So to meets the criterion (2.5) for this example we must have:
$f_{TW}$ and $f_{UW}$ are linearly independent.
$f_{TY}$ and $f_{XY}$ are linearly independent.
$f_{UZ}$ and $f_{XZ}$ are linearly independent.
Equivalently, the criterion says that $$s,t,u,v,y,z, nr − pq$$ $$npsw + nrux - pnsw - pqux, \text{ and } rnsw + rqux - qpsw - qrux$$ are all nonzero.
My question is, I haven't understood why : Equivalently, the criterion says that $$s,t,u,v,y,z, nr − pq$$ $$npsw + nrux - pnsw - pqux, \text{ and } rnsw + rqux - qpsw - qrux$$ are all nonzero ?.
I hope to find the answer, thanks.
First, each vector in the constraint cannot be a zero vector. For example, if $s=0$ then $f_{TW}$ becomes a zero vector. Therefore, $s \neq 0$. Likewise, you can prove $t,u,v,y,z$ are also non-zero.
Second, two vectors $v_1 = \begin{bmatrix}\alpha \\ \beta \end{bmatrix}$ and $v_2 =\begin{bmatrix}\gamma \\ \delta \end{bmatrix}$ are linearly independent when $$\frac{\alpha}{\beta} \neq \frac{\gamma}{\delta}.$$ Equivalently, when $$\alpha \delta - \beta \gamma\neq 0.$$ Using this relationship, it is easy to verify that other expressions should not be equal to zero.