What is $A+A^T$ when $A$ is row-stochastic ?

Question

This is motivated by this MO question.

If $A\in{\bf M}_n({\mathbb R})$ is row-stochastic (entrywise non-negative, and $\sum_j a_{ij}=1$ for all $i$), then $M:=A+A^T$ is

• symmetric,

• entrywise non-negative.

One finds easily the

• additional property that $$\sum_{i\in I}\sum_{j\in J}m_{ij}\le|I|+|J|$$ for every index subsets $I$ and $J$,

with

• equality in the extremal case: $$\sum_{i,j=1}^nm_{ij}=2n.$$

My question is whether all these four properties imply in turns that $M$ has the form $A+A^T$ for some row-stochastic $A$.

Edit. The answer is Yes when $n=2$ (obvious) or $n=3$ (more interesting).

Answer 1

My answer builds on Brendan McKay's idea. We will show the vertices have the form he describes..

It's obvious that vertices in the polytope of row-stochastic matrices have this form, because each row is independent and the equations for each row form a simplex.

So it's enough to show that vertices in the polytope of symmetric matrices satisfying these conditions have the analogous form. First we are going to show that integer symmetric matrices (with even diagonal entries) satisfying these inequalities have the desired form. Then we are going to show that vertices are always integer matrices.

To show the first thing, use the following algorithm: Whenever any row sums to $1$, remove that row and the corresponding column, and put a $1$ in the corresponding place in the row-stochastic matrix to account for it. Whenever any row sums to $0$, derive a contradiction: that row and all previously removed rows consist of $k+1$ rows and $k+1$ columns that together contribute only $2k$ to $\sum_{i,j} m_{ij}$, so the remaining $n-k-1$ rows and $n-k-1$ columns, when intersected, contribute $2n-2k$, which is more than $(n-k-1)+(n-k-1)$. When this process is complete, every row sums to at least $2$, and the average row sums to $2$, so every row sums to $2$. then you have the adjacency matrix of a graph where every vertex has valence 2 - a union of disjoint cycles. Choose an orientation of each cycle, and complete the stochastic matrix by adding the corresponding oriented adjacency matrix.

So it's enough to show that every vertex has integer entries. Suppose not. Call a pair $I,J$ tight if $\sum_{i\in I} \sum_{j\in J} m_{i,j}=|I|+|J|$. Note that the intersection of two tight pairs is tight, by the following inequality:

$\sum_{i\in I_1} \sum_ {j\in J_1} m_{i,j} + \sum_{i\in I_2} \sum_ {j\in J_2} m_{i,j} \leq \sum_{i\in I_1 \cup I_2} \sum_ {j\in J_1 \cup J_2} m_{i,j} + \sum_{i\in I_1 \cap I_2} \sum_ {j\in J_1 \cap J_2} m_{i,j}$

Call a tight pair integral if $m_{i,j}\subset \mathbb Z$ for all $i,j \in I,J$ (and diagonal entries are even). If some $m_{i,j}$ is not integral, let $I,J$ be a minimal non-integral tight pair. It exists because the set of all indices is always a non-integral tight pair.

There must be at least one non-integral entry in $I \times J$, but the sum of all the entries is an integer, so there is another non-integral entry. Or there is an odd diagonal entry. Assume there are two entries, and that they are not just the same entry reflected around the diagonal. Then you can increase one entry and decrease the other by some small amount $\epsilon$. This will preserve all the equalities and inequalities: If $\epsilon$ is small enough it will preserve all the inequalities that are not currently tight. $m_{i,j}\geq 0$ is not tight for either of these because they are nonzero. Since $I,J$ is a minimal non-integral tight pair, any tight pair containing one contains the other, and so every tight inequality remains tight. Since one could just as well decrease one and increase the other, this shows that $m_{i,j}$ is not a vertex.

The remaining case to consider if the minimal non-integral tight pair has only $m_{i,j}\not \in \mathbb Z$ and $m_{j,i} \not\in \mathbb Z$ and is otherwise integral, or has only an odd diagonal entry and is otherwise non-integral. If $i\neq j$ then $m_{i,j}$ is clearly a half-integer, so either way the total contribution of $m_{i,j}$ and $m_{j,i}$ is odd. But since $J,I$ is also a tight pair, $I\cap J$, $I\cap J$ is also a tight pair, and contains $m_{i,j}$, so it is the same as $I,J$ and $I=J$, so $|I|+|J|$ is even. So the total contribution is even, which means there must be another non-integral or odd diagonal entry, and we are done.

Answer 2

My solution for $n=3$ (upon Suvrit's request):

To begin with, we solve $A+A^T=M$ together with $A{\bf1}={\bf1}$ (no inequality for the moment). This is a linear system in $A$, which consists in $9$ equations in $9$ unknowns. However, it is not Cramer, because the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$ is one-dimensional, spanned by $$\begin{pmatrix} 0 & 1 & -1 \\\\ -1 & 0 & 1 \\\\ 1 & -1 & 0 \end{pmatrix}.$$ In particular, there is a condition for solvability in $A$, but this condition is met by the assumption that $\sum_{i,j}m_{ij}=6$. Notice that $a_{ii}=\frac12m_{ii}$.

Thus there is a solution $A$, and every solution is of the form $A+aB$. There remains to find $a$ so as to satisfy the inequality $A+aB\ge0_n$. For this, let us denote $\mu$ the lower bound of $(a_{12},a_{23},a_{31})$, and $\nu$ that of $(a_{21},a_{13},a_{32})$.

Claim: we have $\nu+\mu\ge0$. This inequality allow us to find an $a$ such that $a_{12}+a,a_{23}+a,a_{31}+a,a_{21}-a,a_{13}-a,a_{32}-a\ge0$, which solves the problem.

Proof of the claim: we have $a_{12}+a_{21}=m_{12}\ge0$, $a_{12}+a_{13}=1-\frac12m_{11}\ge0$ because of the assumption that $m_{ij}\le2$, and finally $$a_{12}+a_{32}=a_{12}+a_{21}+a_{32}+a_{23}-a_{21}-a_{23}=m_{12}+m_{23}+\frac12m_{22}-1.$$ Form the assumption, this is equal to $$2-m_{13}-\frac12(m_{11}+m_{33})\ge0.$$ Finally, every sum $a_{ij}+a_{ji}$, $a_{ij}+a_{ik}$ and $a_{ij}+a_{kj}$ of elements of both sets is non-negative, hence $\mu+\nu\ge0$. Q.E.D.

Adapting this proof to higher $n$ seems difficult, but not impossible. Let us define $$s_A(I,J)=\sum_{i\in I,j\in J}a_{ij}.$$ If $A$ is any solution of $A+A^T=M$ and $A{\bf1}={\bf1}$, where $M$ meets the assumptions above, then for every $I,J$, we have $$s_A(I,J^c)+s_A(J,I^c)=|I|+|J|-s_M(I,J)\ge0.$$ Likewise, $a_{ij}+a_{ji}=m_{ij}\ge0$ for every $i,j$.

We have therefore reduced our question to the following one

Suppose that a matrix $A\in M_n({\mathbb R})$ satisfies $a_{ij}+a_{ji}\ge0$ for every $i,j$, and $s_A(I,J^c)+s_A(J,I^c)\ge0$ for every index sets $I,J$. Is it true that there exists a skew-symmetric matrix $B$, satisfying $B{\bf1}={\bf0}$, such that $A+B$ is entrywise non-negative?

(Remark that for such $B$, one has $s_B(I,J^c)+s_B(J,I^c)\equiv0$.)

A side remark: this set of assumptions about $A$ is redundant. All of them derive from the smaller set of inequalities $$a_{ij}+a_{ji}\ge0,\quad\forall i,j,\qquad s_A(I,I^c)\ge0,\quad\forall I.$$ As a matter of fact, one has $$s_A(I,J^c)+s_A(J,I^c)=s_A(I\setminus J,I\setminus J)+s_A(J\setminus I,J\setminus I)+s_A(I\cap J,(I\cap J)^c)+s_A((I\cup J)^c,I\cup J)$$ and $s_A(K,K)\ge0$ follows from $a_{ij}+a_{ji}\ge0$.