Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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