# Constant row-column sum matrices?

1. Given an integer $$T$$ how many $$n\times n$$ matrices in $$\mathbb Z_{\geq0}^{n\times n}$$ we have such that every row and column sum to same $$T$$?

2. Do the set of constant row and column sum matrices form any kind of algebraic structure (it is definitely definable by linear equations) by which I mean closedness, more than permutation invariance at least for special classes etc.)?

• These are the lattice points in the $T$th dilate of the Birkhoff polytope. Look up the “Anand-Dumir-Gupta conjecture.” – Sam Hopkins Jul 18 '19 at 10:38
• The set is obviously closed under addition, and not-quite-so-obviously closed under multiplication, also under multiplication by integer scalars. Every element can be written as an integer linear combination of $n^2-2n+2$ or fewer permutation matrices. – Gerry Myerson Jul 18 '19 at 12:55
• As mentioned by Gerry Myerson, the set forms a semigroup under addition. The semigroup algebra over a field is Cohen-Macaulay, which has some interesting consequences. – Richard Stanley Jul 18 '19 at 17:00
• @Turbo: here's a nice survey-ish paper- home.uni-osnabrueck.de/wbruns/brunsw/pdf-article/1-BRUNS.pdf – Sam Hopkins Jul 18 '19 at 18:53
• The row sums of an $n\times n$ matrix are equal if and only if the all 1's column vector is a right eigenvector. Similarly for equal column sums and the all 1's row vector being a left eigenvector. Hence these properties are preserved under product assuming the row and column sums are not 0. – Richard Stanley Jul 19 '19 at 20:01

If you are looking for a simple formula, you are out of luck except for small $$n$$ or $$T$$. As Sam mentions in a comment, these are the integer points in a dilated Birkhoff polytope. Since the vertices of the polytope are lattice points, the number of matrices is a polynomial of degree $$(n-1)^2$$ in $$T$$ for any fixed $$n$$ (the Ehrhart polynomial) but the polynomial is only known up to $$n=9$$.

This paper and this paper have some stuff about asymptotics. Searching for these buzzwords will get you more interesting things, like this paper.

I commented there's closure under (matrix) multiplication, and OP asked for an explanation, so here goes.

Let $$A,B$$ be $$n\times n$$ constant line-sum matrices with constants $$a,b$$, respectively.

Let $$A$$ have rows $$r_1,r_2,\dots,r_n$$, let $$B$$ have columns $$c_1,c_2,\dots,c_n$$, let $$C=AB$$, and let $$\underline b$$ be the column $$n$$-vector $$\pmatrix{b\cr b\cr\vdots\cr b\cr}$$

Then the entries of the first row of $$C$$ are the dot products $$r_1\cdot c_1,r_1\cdot c_2,\dots,r_1\cdot c_n$$. So, the sum of the entries of the first row of $$C$$ is $$r_1\cdot(c_1+c_2+\cdots+c_n)=r_1\cdot\underline{b}=ab$$

The same argument applies to each row of $$C$$, and a similar argument applies to each column of $$C$$, so $$C$$ is a constant line-sum matrix with constant $$ab$$.

• Thank you very much. – 1.. Jul 19 '19 at 1:19