4
$\begingroup$

Let $S_n$ be the set of all the $n\times n\ (0,1)$-matrices and divide $S_n$ into two sets as follows: $A_n=\{M\in S_n:$ there exist a row and a column of $M$ such that the sum of the row is equal to the sum of the column$\}$ and $B_n=S_n\setminus A_n.$

I have two questions:

$(1)$Is there any estimation for $\dfrac{|A_n|}{|S_n|}$ or $\dfrac{|B_n|}{|S_n|}?$

$(2)$I conjecture that $\lim_{n\rightarrow \infty}\dfrac{|A_n|}{|S_n|}=1,$ is that right?

$\endgroup$
1

1 Answer 1

7
$\begingroup$

For (2), consider a random matrix (each entry independently 0 or 1 with probability 1/2). See this paper (published in Journal of Combinatorics). By virtue of Corollary 2 it suffices to show that if $S_1,\ldots,S_n,T_1,\ldots,T_n$ are binomial random variables Bin$(n,1/2)$, independent except for $\sum_j S_j = \sum_k T_k$ then there are almost surely some $j,k$ with $S_j=T_k$. This is true because any value close to $n/2$ occurs with high probability in both $S_1,\ldots,S_n$ and $T_1,\ldots,T_n$. So the answer to (2) is "yes".

$|B_n|/|S_n|$ must be exponentially small. I don't see a simple way to estimate it.

Here is a lower bound on $|B_n|/|S_n|$ for even $n$: the probability that all the row sums are even and all the column sums are odd, or vice-versa, is exactly $2^{-2n+2}$. I have a cute generation function proof that I'll add if anyone asks, but probably it is a just linear algebra.

ADDED: Since user173856 asked, I'll give the "cute generating function proof". However, I'll first note that if no further generality is needed the simple proof that Kevin gave in the notes is clearly better. The principle is if you have a polynomial $f(x_1,\ldots,x_n,y_1,\ldots,y_n)$ then the sum of $f$ over $\lbrace -1,+1\rbrace^{2n}$ is $2^{2n}$ times the sum of the coefficients of the terms in which the variables all occur to an even power. The others all cancel out. Now $$f(x_1,\ldots,x_n,y_1,\ldots,y_n)=x_1\cdots x_n\prod_{1\le j,k\le n} (1+x_jy_k)$$ counts $n\times n$ 0-1 matrices such that the coefficient of $x_1^{r_1+1}\cdots x_n^{r_n+1}y_1^{c_1}\cdots y_n^{c_n}$ is the number of matrices with row sums $r_1,\ldots,r_n$ and column sums $c_1,\ldots,c_n$. When we sum $f$ over $\lbrace -1,+1\rbrace^{2n}$, the only non-zero terms are when all the variables are $+1$ or all the variables are $-1$. This gives that the number of matrices with odd row sums and even column sums is $$2^{-2n}(2^{n^2}+(-1)^n 2^{n^2}).$$ Divide by the total $2^{n^2}$ to express it as a probability.

$\endgroup$
5
  • 1
    $\begingroup$ For the lower bound: Conditioned on the upper left $(n-1) \times (n-1)$ minor, there is exactly one way to complete the matrix so the row sums are even and the column sums are odd, and the same holds the other way around. $\endgroup$ Dec 30, 2015 at 23:49
  • $\begingroup$ Nice argument Kevin, but you need to worry about the last row and column too. Can you say how often one has to worry about that? Gerhard "Hopefully A Measure Epsilon Problem" Paseman, 2015.12.30 $\endgroup$ Dec 31, 2015 at 0:37
  • $\begingroup$ @Gerhard: Kevin's argument is correct. Assuming $n$ is even, making the final row even implies that the final column is odd. This gives the same $2^{-2n+2}$ probability that I mentioned. $\endgroup$ Dec 31, 2015 at 1:25
  • $\begingroup$ Thank you. My brain was thinking general n. Gerhard "Now Accepting Star Wars Spoilers" Paseman, 2015.12.30 $\endgroup$ Dec 31, 2015 at 5:54
  • $\begingroup$ Brendan Mckay:Thank you very much for your help! You said "I have a cute generation function proof that I'll add if anyone asks", would you please tell me the proof? By the way, can you give a lower bound on $|A_n|/|S_n|$ or a upper bound on $|B_n|/|S_n|$? $\endgroup$
    – user173856
    Dec 31, 2015 at 14:33

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.