An inequality for stochastic matrix Consider row stochastic matrix $A = [a_{ij}]_{i,j=1}^{n}$, that is, $0 \leq a_{ij} \leq 1$ and $\sum_{j=1}^{n}a_{ij} = 1$ for all $i=1,...,n$.
The following inequality seems true from numerical simulations:
$$\displaystyle\sum_{k=1}^{n} \min\left(a_{ik}, a_{jk}\right) \geq \underset{i\neq j}{\min}\left(a_{ii} + a_{ji}\right), \quad \text{for all} \, i\neq j.$$
The above defines ${n}\choose{2}$ inequalities, since the left-hand-side depends on the choice of the pair of rows: $i$-th and $j$-th row, $i\neq j$. The expression on the right-hand-side is a constant.
How to prove/disprove this?
 A: The inequality doesn't hold for general row stochastic matrices. As counterexample, consider $2\times 2$ case: 
$$A = \begin{pmatrix}\alpha & 1-\alpha\\ \beta & 1-\beta\end{pmatrix}, \quad 0\leq \alpha,\beta\leq 1.$$
Then left-hand-side (LHS) of the inequality $= \min(\alpha,\beta) + \min(1-\alpha,1-\beta)$, and right-hand-side (RHS) $= \min(\alpha+\beta,2-\alpha-\beta)$. Using the identity $\min(a,b) = \frac{1}{2}\left(a+b - |a-b|\right)$ for each pointwise minimum in the LHS and RHS, we see that
$$\text{LHS} = 1 - |\alpha - \beta|, \quad \text{RHS} = 1 - |\alpha + \beta - 1|,$$
and hence proving our inequality is equivalent to proving $|\alpha - \beta| \leq |\alpha + \beta - 1|$, which fails for example at $\alpha = 0.2$, $\beta=0.6$. 
Edit:
More numerical simulations show that the inequality fails for $n\geq 3$ as well, although failure seems rare at higher dimensions. For example, out of 10,000 randomly generated $6\times 6$ stochastic matrices, the inequality seems to fail 1 or 2 times, i.e., failure percentage is of the order of $10^{-2}$.  
