Selecting a strictly positive permutation from a stochastic matrix

This question is related to another one I recently posed. I am posting this new question because (i) trying to prove that other conjecture seems to have been quite fruitless so far; and (ii) the instant conjecture can be relatively easily verified to hold in low dimensions, since there are only a finite number of possible cases to check. Moreover, a positive answer to the conjecture posed in this question will be sufficient for my purposes.

Let $n$ be a positive integer and let $N\equiv\{1,\ldots,n\}$. Consider an $n\times n$ square matrix $\mathbf A\equiv[a_{ij}]_{(i,j)\in N\times N}$ with the following properties:

• each element of the matrix is non-negative;
• the sum of each row is $1$ (that is, $\mathbf A$ is a stochastic matrix);
• the diagonal is strictly positive; and
• each non-zero entry in the matrix is the reciprocal of the number of non-zero entries in that row.

For example: \begin{align*} \begin{array}{cccc} 1&0&0&0\\ 0&1/2&1/2&0\\ 1/3&0&1/3&1/3\\ 1/4&1/4&1/4&1/4 \end{array} \end{align*}

Consider another matrix $\mathbf B\equiv[b_{ij}]_{(i,j)\in N\times N}$ with the following properties:

• each element of $\mathbf B$ is non-negative;
• the sum of each row of $\mathbf B$ is $1$ (that is, $\mathbf B$ is also a stochastic matrix);
• the sum of each column of $\mathbf B$ is the same as the sum of the corresponding column of $\mathbf A$, that is: $$\sum_{i\in N}b_{ij}=\sum_{i\in N}a_{ij}\quad\text{for every $j\in N$; and}$$
• any element of $\mathbf B$ is positive only if the corresponding element in $\mathbf A$ is positive, that is: $$a_{ij}=0\text{ implies }b_{ij}=0\quad\text{for each $(i,j)\in N\times N$.}$$

Note that each specific entry of $\mathbf B$ may take any value otherwise (subject to the above restrictions). It is not constrained to be the reciprocal of the number of non-zero entries in its row, unlike for the entries of $\mathbf A$.

Conjecture: There exists a permutation $\pi:N\to N$ along which the elements of $\mathbf B$ are positive, that is: $$b_{i,\pi(i)}>0\quad\text{for every $i\in N$}.$$

(Note: The assumption that $a_{ii}>0$ for every $i\in N$ ensures the existence of an analogous strictly positive permutation for the matrix $\mathbf A$.)

I checked all the possible cases “manually” up to $n\leq3$, and found that the conjecture holds true (unless I made a mistake or omission). I wonder about the general case. Any feedback would be much appreciated.

Solution 1:

$A=\begin{pmatrix} 1&0&0&0\\1/2&1/2&0&0\\1/3&1/3&1/3&0\\1/4&1/4&1/4&1/4 \end{pmatrix}$
$B=\begin{pmatrix} 1&0&0&0\\1&0&0&0\\1/12&7/12&1/3&0\\0&1/2&1/4&1/4 \end{pmatrix}$
$\pi(1)=1$ , but $\pi(2)$ is undefined.

if this example doesnt work, then i might have misunderstood qn.