This is motivated by this MO [question](https://mathoverflow.net/questions/117567).


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).



What is $A+A^T$ when $A$ is row-stochastic ?
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.


