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$?
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.)?
$\begingroup$
$\endgroup$
11
-
3$\begingroup$ These are the lattice points in the $T$th dilate of the Birkhoff polytope. Look up the “Anand-Dumir-Gupta conjecture.” $\endgroup$– Sam HopkinsCommented Jul 18, 2019 at 10:38
-
$\begingroup$ 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. $\endgroup$– Gerry MyersonCommented Jul 18, 2019 at 12:55
-
2$\begingroup$ 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. $\endgroup$– Richard StanleyCommented Jul 18, 2019 at 17:00
-
2$\begingroup$ @Turbo: here's a nice survey-ish paper- home.uni-osnabrueck.de/wbruns/brunsw/pdf-article/1-BRUNS.pdf $\endgroup$– Sam HopkinsCommented Jul 18, 2019 at 18:53
-
2$\begingroup$ 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. $\endgroup$– Richard StanleyCommented Jul 19, 2019 at 20:01
|
Show 6 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
answered Jul 18, 2019 at 11:32
$\begingroup$
$\endgroup$
1
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$.
answered Jul 19, 2019 at 1:17