3
$\begingroup$

Let $A$, $B$ be two $n\times n$ real matrices.

Let $A$ be a zero line-sum matrix where each row sum and each column sum equals zero, i.e., $$\sum_{i=1}^{n}a_{ij}=\sum_{j=1}^{n}a_{ij}=0 $$ (it seems there is no name for such matrix, see Name for matrices with vanishing row and column sums).

Let $B$ be a matrix where every entry is non-negative and each row sum and each column sum equals 1, i.e., $$\sum_{i=1}^{n}b_{ij}=\sum_{j=1}^{n}b_{ij}=1, b_{ij}\geq 0 $$ ($B$ is a doubly stochastic matrix).

An index set $S\subset[n]\times[n]$ is a permutation set if $S$ has $n$ elements and if for every $(i,j),(i'j')\in S$, $(i,j)\neq(i',j')$ then $i\neq i;$ and $j\neq j'$.

Now suppose there exists a permutation set $S$ such that $a_{ij}\geq 0$ for every $(i,j)\in S$, $a_{ij}\leq 0$ for every $(i,j)\notin S$ and $\sum_{(i,j)\in S} b_{ij}\geq \sum_{(i,j)\in S'} b_{ij}$ for every permuation set $S'$. Is it true that $\langle A,B\rangle_F\geq 0$?

Note this is obviously true if $B$ is a permutation matrix or if $b_{ij}=1/n$ for every $(i,j)$. These seems like the two extreme cases. But how to prove it in general?

$\endgroup$
4
  • $\begingroup$ A small correction: $B$ is called a doubly stochastic matrix, not a Birkhoff polytope. The Birkhoff polytope is the set of all doubly stochastic matrices (in fixed dimension). $\endgroup$ Commented Jun 14, 2020 at 23:07
  • 1
    $\begingroup$ @JochenGlueck Thanks! I miswrote it because I was thinking about minimizing $\langle A,B\rangle_F$ over a Birkhoff polytope. $\endgroup$
    – Lo Celso
    Commented Jun 14, 2020 at 23:32
  • 2
    $\begingroup$ Going beyond your two examples, a computer might be of help finding potential counterexamples here. Data enters the problem in a very combinatorial way, and it's hard to get an intuition for why the statement should be true in general. So my 2 cents would be to try to finding some genuine counterexamples (e.g using a computer), and only in case of failure to find such, should you have more confidence in the claim, and try proving it. $\endgroup$
    – dohmatob
    Commented Jun 15, 2020 at 8:06
  • $\begingroup$ @dohmatob Thanks for your advice! I used Sage to try the $3 \times3$ case and I found that the Birkhoff polytope, with the additional property I required on $B$ (I let $S=\{(i,i)\}$), has 24 vertices, which is indeed hard to analyze. I have changed the question to a weaker one which I believe is true. $\endgroup$
    – Lo Celso
    Commented Jun 15, 2020 at 17:43

0

You must log in to answer this question.