# For what integers can this matrix be generated?

We call a positive integer $n$ "good" if there exists a $n \times n$ matrix such that:

1) Each element is either $0$ or $1$.

2) Sum of elements in each row is distinct.

3) Sum of elements in each column is the same of that in all other columns.

For example 2 is good:

$$\begin{matrix}0&0\\1&1\end{matrix}$$

Find the set $\mathbb G$ of good numbers.

I have already tried it on small values of $n$, it seems that such a matrix exists for all $n$ ( that's at least for the values I tried ), is that right? And I'm looking for a concrete proof. Any help would be appreciated. Thanks in advance!

-
Maybe you could prove that there are such matrices for all n by using induction? –  Per Alexandersson Oct 15 '11 at 17:05
First of all, there exists a 2x2 matrix: 0 0 _newline_ 1 1 I thought of using induction, but how can I expand a nxn valid matrix to a (n + 1)x(n + 1) valid one? –  Chris Oct 15 '11 at 17:08

If $n$ is even, form pairs of rows such that their numbers of $1$s add up to $n$: $(0,n), (1,n-1),\dotsc(n/2-1,n/2+1)$. In each pair, arrange the $1$s such that they don't overlap. Then each pair contributes $1$ to the sum of each column, and the rows sums are all different.

If $n$ is odd, use the pairs $(1,n-1),(2,n-2),\dotsc,((n-1)/2,(n+1)/2)$, and then add a full row of $1$s.

[Examples for odd $n$ as requested:]

$n=3$:

$$\pmatrix{1&0&0\\0&1&1\\1&1&1}$$

$n=5$:

$$\pmatrix{1&0&0&0&0\\0&1&1&1&1\\1&1&0&0&0\\0&0&1&1&1\\1&1&1&1&1}$$

-
Very elegant solution! –  Per Alexandersson Oct 15 '11 at 17:21
Nice solution! :D Thanks a lot. But, when n is odd, could you clarify more? It would help if you demonstrated when n = 3. Thanks -- again -- in advance! :) –  Chris Oct 15 '11 at 17:30
@Abody97: Sorry, the description of the odd case was wrong; I've fixed it and provided two examples. –  joriki Oct 15 '11 at 18:23
@joriki: Thanks again! But the example for n = 5 doesn't match the description. Well anyway, the idea is clear. –  Chris Oct 15 '11 at 18:52
@Abody97: Why does it not match the description? Because $(2,n-2)$ is the same as $((n-1)/2,(n+1)/2)$ for $n=5$? I think it's usual to write general terms like that; it's implicit that for small values of $n$ the overlapping ones only occur once. –  joriki Oct 15 '11 at 19:27

Let's see, each row has sum at most $n.$ Thus, the total sum of all entries must be $1+2+3+\dots+n = n(n+1)/2,$ if we do not allow an empty row. However, allowing an empty row yields that all possible sums for a $n \times n$ matrix is in the interval $[n(n-1)/2,n(n+1)/2]$. This interval contains $n$ numbers, so one of them must be divisible by $n,$ say the number $m = cn.$ Thus, each column must have $c$ non-zero entries.

This is easily done, by just rearranging entries in each row, as we may move them between columns without changing rows.

-