Finding a strictly positive “good” permutation in a doubly stochastic matrix

Question

Let $n$ be a positive integer and $\mathbf X\equiv[x_{ij}]_{i=1,j=1}^{i=n,j=n}$ a doubly stochastic matrix; that is, a matrix with non-negative elements such that the sum of every row and the sum of every column are $1$. From now on, let $N\equiv\{1,\ldots,n\}$.

Suppose that to each row $i\in N$, there corresponds a non-empty index set $G(i)\subseteq N$. For terminological simplicity, declare that $j\in N$ is a “good column” for row $i\in N$ whenever $j\in G(i)$.

Suppose also that the following are true (the first of these assumptions should be replaced–see my answer below):

• For every row $i\in N$, if $x_{ij^*}>0$ for some $j^*\in N\setminus G(i)$, then $x_{ij}>0$ for every $j\in N$.
• There exists at least one permutation $\sigma:N\to N$ such that $\sigma(i)\in G(i)$ for every $i\in N$.

In words: if, for a fixed row, there is a positive element in some “bad column,” then the whole row is positive. Moreover, one can match the rows to the columns in such a way that every row gets matched to a “good column” (possibly in more than one way).

Question: Does there exist a permutation $\pi: N\to N$ such that for every $i\in N$:

• $x_{i,\pi(i)}>0$; and
• $\pi(i)\in G(i)$?

In words: can one match the rows to the columns such that (i) all the resulting elements will be strictly positive; and (ii) every row gets matched to a “good column”?

---

The answer is affirmative in the special case in which $G(i)=N$ for all $i\in N$; that is, when every column is “good” for every row. In this case, one can invoke the Birkhoff–von Neumann theorem to derive the existence of a strictly positive permutation without having to worry about “goodness.”

I wonder about the more general case with the assumptions posited above. My hunch tells me that the answer should be affirmative, since if a row gets matched to a “bad” column, then the positivity of the whole row and the fact that the matrix is doubly stochastic may make it possible to rearrange the permutation by selecting another row with a positive element for which the column in question will be “good.”

Any feedback would be much appreciated.

Answer 1

UPDATE #1: I found a counterexample (the “good” entries in each row are boxed):

\begin{align*} \begin{array}{ccc} \boxed{1/3}&1/3&1/3\\ 1/6&\boxed{1/6}&2/3\\ \boxed{1/2}&\boxed{1/2}&\boxed{\phantom{i}0\phantom{i}} \end{array} \end{align*}

---

But! I wonder if the conclusion can be salvaged if the assumptions in the question above are replaced with the following:

• For every row $i\in N$, if $x_{ij^*}>0$ for some $j^*\in N\setminus G(i)$, then

$\phantom{---i}$(i) $x_{ij}>0$ for every $j\in G(i)$; and

$\phantom{---}$(ii) there is some other row $k\in N$ such that $x_{kj^*}>0$ and $j^*\in G(k)$.

• There exists at least one permutation $\sigma:N\to N$ such that $\sigma(i)\in G(i)$ for every $i\in N$.

That is, the first original assumption is (i) weakened in the sense that the positivity of a “bad” entry implies only the positivity of the “good” entries in that row (as opposed to all entries in that row); and also (ii) strengthened in the sense that the positivity of a “bad” entry implies the existence of a positive “good” entry in the same column.

---

UPDATE #2: Here is a counterexample to the modified conjecture (again, the “good” entries in each row are boxed):

\begin{align*} \begin{array}{cccx} \boxed{1/8}&1/8&3/8&3/8\\ \boxed{1/8}&\boxed{1/8}&3/8&3/8\\ \boxed{1/2}&\boxed{1/2}&\boxed{\phantom{i}0\phantom{i}}&\boxed{\phantom{i}0\phantom{i}}\\ \boxed{1/4}&\boxed{1/4}&\boxed{1/4}&\boxed{1/4} \end{array} \end{align*}

---

But! Notice that in each of the two counterexamples, if one considers a separate matrix in which the “good” entries are $1$ and the “bad” entries are $0$, then the resulting matrix is reducible. I still wonder if either form of the conjecture holds under the following additional assumption:

• The matrix formed by the “good” and “bad” entries is irreducible.