7 Responses to “Really equal? Naturally!”

1. Nadav Says:
   January 3rd, 2010 at 4:47 pm

   Solution:
   Denote the set by S.

   For Naturals:

   First, lets notice that if S has the property, so does tS for every scalar t. Also, S+t has the property, because each partition is into two sets of equal size N.
   Second, we notice that for every element x in S, sum(S-x) = sum(A) + sum(B) = 2 * sum(A) and it’s an even number.
   Therefore, sum(S) is even iff x is even - which is correct for every element x. Therefore all elements of S has the same parity.
   Now, first we take S and subtract min(S) from it. it will still have the property, still be all natural numbers, and now has a 0 element.
   Since 0 is even, all elements are even, and so we can divide by 2 - again and again. if not all elements were 0, sometime, one of them will become odd, and this is a contradiction.
   Therefore, they were all 0 - so all of S elements were equal.

   For Integers:

   Simply subtract min(S), and now all of S’s elements are non-negatives and integers.

   For Rationals:

   Simply multiply S by LCM(denominators of S) - now they’re all integers.

   For Reals and Complex:

   Since Q is a field, and we know that every set of rational numbers that have the property are all equal, we can write the following:
   Let M be a 2N+1 x 2N+1 matrix, such that - the main diagonal is all 0’s. every Row has exactly N 1’s and N (-1)’s.
   Then the dimension of the Nullspace of this matrix is 1: only vectors of type (x,x,x…,x)
   So Rank(M) = 2N

   but if Rank(M) = 2N in Q, it’s also the rank of the matrix in any other superfield of Q, such as R and C.
   So the only vectors in the nullspace of this matrix are (x,…,x) in those fields too.

2. yaniv Says:
   January 3rd, 2010 at 5:34 pm

   Nadav,

   Good solution. In the last part (the proof for the reals/complex) you use an assertion (without proof) that the rank is the same over Q and over R. The assertion is of course true (I prove it below for other readers). But then the construction of the matrix is not necessary and a more elegant solution exists (again, see below).

   The Missing Proof that the Rank Does not Change:
   Let T be a set of m vectors from Qn, independent over Q. Then T is also independent over R. Otherwise, let a1,…,am (in R) be the non-trivial coefficients than make the sum 0. Let e1,…,ek be a basis for the extension field Q(a1,…,am). Then in at least one coordinate, we have a non-trivial sum over Q that is 0. Contradiction.

   A More Elegant Solution (no need to talk about matrices):
   Let S be our set of reals. As S is finite, take a finite-degree extension field of Q that contains all the elements of S. Take a basis, e1,…,en of this extension field. Now, our property holds for S i.f.f. it holds for the projection of the elements of S onto each of the coordinates defined by e1 and en, and it does hold for each coordinate, as it holds for Q.

3. Dan Says:
   January 3rd, 2010 at 10:46 pm

   Seems to me that you’re forcing field extensions on what could be done with elementary-er linear algebra (not that there’s anything wrong with field extensions).

   A More Elementary Proof that the Rank Does not Change:
   The rank of the matrix can be defined as the maximal number K, such that there exists a K x K on minor which is non singular. Clearly, singularity does not change when the field is extended, as it can be defined over any field as “Determinant = 0″, and the determinant does not change. Thus the rank does not change either.

   Good to see you updating again!

4. yaniv Says:
   January 4th, 2010 at 10:51 am

   Dan,

   Great to hear from you!

   I agree that with the matrix-solution field extensions are a little overkill (although I still like it better). I wrote it like that so as to use the same argument as in the more elegant matrix-less solution. I think that the matrix-less solution with the field extension is definitely more elegant.

   And I will indeed start to update again, I have tons of new stuff to post…

5. pitboss Says:
   January 9th, 2010 at 1:05 am

   Hah, I was trying to prove that the rank of the matrix is 2N all day, because I proceeded directly to the general case… This was quite an unpleasant experience I can assure you But the problem was worth it.

6. rouli Says:
   January 11th, 2010 at 12:53 am

   Good one.
   My solution to the private case is quite similar to Nadav’s, but much less elegant, so I’ll avoid writing it over here.
   I still try to understand the solution to the general case (it’s been a few years since my last encounter with extension fields).

   Is there a set of naturals, not all equal, that exhibit this behavior when for each division set A doesn’t need to be the same size as set B?

7. yaniv Says:
   January 11th, 2010 at 10:22 am

   Hi Rouli,

   If you drop the condition that the two sets have equal size then the claim is no longer true. Take the set {1,1,1,3,3}.

Leave a Reply

Name (required)

Mail (will not be published) (required)

Website

Notify me of followup comments via e-mail