Doubly stochastic matrix problems.

Question

Assume we have $4\times4$ doubly stochastic matrix $M$. Let us take $4$ elements of $M$, such that each element is taken from unique row and column. There is $4!=24$ ways to do it. For each $4$-tuple let us take minimum element - $min_k$. Let $x$ be maximum of $min_k$. The problem is to prove that for any $M$ we have $x>0$. Another problem is to find $\sup x$ among all $M$.

My progress:

Let $A_0 = M$, $a_i$ is sum of elements in a row or column of $A_i$, so $a_0=1$. Let us define $x_i$ for $A_i$ in the same way as $x$ for $M$. I was able to prove the following fact:

Either $x_i$ = $a_i/4$ or there is element $y$ in $A_i$ such that $a_i/4\leq y \leq a_i/2$. Indeed, there is an element $z_w \geq a_i/4$ in every column or row of $A_i$. If we can select several of $z_w$ to obtain $x_i= min(z_w) \geq a_i/4$ then we are done. Otherwise there are at least 5 of $z_w$, so there are 2 of $z_w$ in single column. Then minimal of those must be $\leq a_i/2$, otherwise their sum is more than $a_i$.

My hope how it can be solved:

I hope to construct $A_{i+1}$ from $A_i$ in a way that sum of elements in a row and in a column are all the same but $A_{i+1}$ has more zeros in it and $a_{i+1} < a_i$. I want to continue adding zeros until I get $x_i$. I will get it for sure when $A_i$ has only $4$ nonzero elements. Then I have to express $x=x_0$ and $x_i$ in terms of each other and $a_0$ in order to express $x$ in terms of $a=a_0=1$. I can swap columns and rows of $A_i$ without loosing properties of $A_i$. Let $m_i$ be minimal nonzero element of of $A_i$. My initial idea was to take minimal element of $A_i$, rearrange $A_i$ so $m_i$ is on main diagonal and then subtract $m_i$ from each element of main diagonal. It will produce extra zero in $A_i$ and it will keep sums of elements in a row/column equal. It will also give $a_{i+1}=a_i - 4m_i$ The only problem is to make sure I can rearrange elements in a way that all elements on the main diagonal of $A_i$ are nonzero. I can not prove it and I do not know if it is true. So my approach can be wrong.

Please share your ideas and approaches. Thanks a lot for your contribution.

Answer 1

HINT:

You want to show that there exist $4$ numbers, each nonzero, any two not in the same row or the same column. So you only look at $0$'s and the ones $>0$, mark them with $*$'s. How to show that there exist $4$ $*$'s like that?

I know a result that says that the maximal number of stars in different rows and columns equals the minimum number of rows and columns that cover all the stars. If you knew this it would be proven, since you cannot cover all the stars with less than $4$ rows or columns ( that's easy in fact)

So it boils down to a combinatorial thing. A $4\times 4$ matrix with some $*$'s in some cells. Can you prove the above statement?

Answer 2

Doubly stochastic matrices are the convex hull of all permutation matrices (the Birkhoff-von Neumann theorem).

A permutation matrix is a matrix that is obtainable from only row and column swaps of an identity matrix, in your case the $4$ by $4$ ID matrix.

For any doubly stochastic matrix $M$, there is a unique set of real numbers $c$ such that $$M = \sum_{k} c_k~P_k$$ and $$\forall k ~ 0 \le c_k \le 1 \text{ and } \sum_k ~ c_k = 1$$ and $P$ is all permutation matrices of the same size as $M$.

For a matrix $n$ by $n$ matrix $M$ and permutation $\omega$, call your $n$ elements selected $S$, as

$$S(M, \omega) = \{M_{i, \omega(i)} ~:~ 1 \le i \le n\}$$

Since the minimum value of $M$ is zero, the minimum value of $S$ is zero. If (for the sake of contradiction) the maximum value of $S$ for any $\omega$ is zero, then each $S$ must contain a zero.

If $\forall \omega ~:~ 0 \in S(M, \omega)$ then

$$\forall \omega ~:~ 0 \in S\left(\sum_{k} c_k~P_k, \omega\right)$$

Since the sum is over non-negative values, and there must be at least one nonzero $c$, then

$$\exists k ~:~ \forall \omega ~:~ 0 \in S\left(P_k, \omega\right)$$

But since $P_k$ is just a permutation of the identity matrix $I$, then

$$\forall \omega ~:~ 0 \in S\left(I, \omega\right)$$

which doesn't hold for the identity permutation, so the max-min value isn't zero.