Bound on column sums of row-normalized nonnegative matrix Let $A$ be a nonnegative square matrix, and let $U$, respectively $V$, be obtained from $A$ by normalizing the rows, respectively columns of $A$ so that they sum to one. That is, $U = (A_{ij} / \sum_{r} A_{ir})$ and $V = (A_{ij} / \sum_{k} A_{kj})$ assuming the sums are nonzero.
Let us further assume that $1-U_{kk} \le \alpha$ and $1 - V_{kk} \le \alpha$ for all $k$. Can we obtain a bound on the deviations of the column sums of $U$ from one: say $$\sum_{i} U_{ij} \le 1 + c \,\alpha, \forall j$$ for some constant $c > 0$ (independent of the dimension of the matrices)? We can assume $\alpha$ is sufficiently small if need be.
 A: Consider the $n\times n$ matrix $$A=\left[\begin{array}{ccccc}1-\alpha&0&0&\cdots&0\\ \alpha/(n-1)&\epsilon&0&\cdots&0\\\alpha/(n-1)&0&\epsilon&\ddots&0\\\vdots&\vdots&\ddots&\ddots&\vdots\\\alpha/(n-1)&0&0&\cdots&\epsilon\end{array}\right],$$ and let $\alpha'=\alpha/(n-1).$ Then $V$ satisfies $1-V_{k,k}\leq\alpha$ for all $k,$ since $V_{1,1}=1-\alpha,$ and $V_{k,k}=1$ for all $k\geq 2.$ We have $$U=\left[\begin{array}{ccccc}1&0&0&\cdots&0\\\alpha'/(\alpha'+\epsilon)&\epsilon/(\alpha'+\epsilon)&0&\cdots&0\\\alpha'/(\alpha'+\epsilon)&0&\epsilon/(\alpha'+\epsilon)&\ddots&0\\\vdots&\vdots&\ddots&\ddots&\vdots\\\alpha'/(\alpha'+\epsilon)&0&0&\cdots&\epsilon/(\alpha'+\epsilon)\end{array}\right].$$ Then if we choose $\epsilon=(1-\alpha)/(n-1),$ we have that $U_{k,k}=1-\alpha$ for all $k\geq2,$ so $1-U_{k,k}\leq\alpha$ for all $k.$ Note that $U_{k,1}=\alpha'/(\alpha'+\epsilon)=\alpha$ for all $k\geq2,$ so we have that $\sum_{i=1}^{n}U_{i,1}=1+(n-1)\alpha.$ This shows that it is impossible for there to exist such a $c$ which is independent of $n.$
