2
$\begingroup$
  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.)?

$\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$ 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$ 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$ 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$ 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$ Jul 19, 2019 at 20:01

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you very much. $\endgroup$
    – Turbo
    Jul 19, 2019 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.