4
$\begingroup$

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!

  • 0
    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?2011-10-15

2 Answers 2

5

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

  • 0
    @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.2011-10-15
2

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.