a lower bound which is linear in $\eta$, as seen in the following.

\[db\] Let $A$ be a stochastic matrix with positive diagonal , and assume that is at least $\eta$. Also, let $(S^{-},S^{+})$ be a partition of the set $N=\{1,\ldots,n\}$ into two disjoint sets. If $$\sum_{i \in S^{-}, ~j \in S^{+}} w_{ij} > 0,$$ then $$\sum_{i
\in S^{-}, ~j \in S^{+}} w_{ij} \geq \frac{\eta}{2}.$$

Let $\sum_{i \in S^{-}, ~j \in S^{+}} w_{ij} >0$. From the definition of the weights $w_{ij}$, we have $w_{ij}=\sum_k
a_{ki}a_{kj}$, which shows that there exist $i\in S^-$, $j\in S^+$, and some $k$ such that $a_{ki}>0$ and $a_{kj}>0$. For either case where $k$ belongs to $S^-$ or $S^+$, we see that there exists an edge in the set $\E(A)$ that crosses the cut $(S^{-},S^{+})$. Let $(i^*,j^*)$ be such an edge. Without loss of generality, we assume that $i^* \in S^{-}$ and $j^* \in S^{+}$. We define $$\begin{aligned}
 C_{j^*}^{+} & = & \sum_{i \in S^{+}} a_{j^*i}, \\
C_{j^*}^{-} & =&  \sum_{i \in S^{-}} a_{j^*i}. \end{aligned}$$ See Figure \[cdef\](a) for an illustration. Since $A$ is a -stochastic matrix, we have $$C_{j^*}^{-} + C_{j^*}^{+}  =  1, $$implying that at least one of the following is true: $$\begin{aligned}
\mbox{ Case 