Small lemma about sums and products

  • Thread starter Tarty
  • Start date
  • #1
7
0
Hey,
I'm trying to prove a larger theorem; in order to complete my proof I need to use the following lemma (or, if it turns out to be false, try a completely different method of proof):

Consider any two sets of n nonzero integers, A and B. If their respective sums and products are equal, then A = B.
i.e if A = {a1, a2, ... aN} and B = (b1, b2, ... bN},
and a1*a2*...*aN = b1*b2*...*bN
and a1 + a2 +... + aN = b1 + b2 + ... bN

then A and B are the same set.

For some reason I'm sure I've seen this theorem before, but I can't for the life of me remember where or whether it was exactly this or slightly different. I'd search it on Google, but then I'd need to know what terms to search for - and if I knew that I would probably know the answer.

So, any ideas/pointers/links to wikipedia articles are very much appreciated.
 

Answers and Replies

  • #2
mathwonk
Science Advisor
Homework Helper
2020 Award
11,154
1,349
have you tried induction?
 
  • #3
Deveno
Science Advisor
906
6
the case |A| = |B| = 2 might be instructive:

let A = {x,y}, B = {a,b}

then x + y = a + b, and xy = ab.

so y = ab/x, and

x + ab/x = a + b, that is:

x^2 + ab = (a+b)x, so

x^2 - (a+b)x + ab = 0

(x - a)(x - b) = 0.

thus x = a, or x = b, in either case, y is the remaining element of B.
 
  • #4
AlephZero
Science Advisor
Homework Helper
6,994
293
Deveno's approach, suggests ths is false if n > 2.

Consider the polynomial
[tex](x-a_1)(x-a_2)\cdots(x-a_n) = x^n + A_{n-1}x^{n-1} \cdots + A_0[/tex]

The sum and product of the a's determine [itex]A_{n-1}[/itex] and [itex]A_0[/itex] but not the other A's.

I conjecture you could find a counterexample that way. But, your conditon that all the a's are nonzero integers imposes some more constraints on the A's ...
 
  • #5
AlephZero
Science Advisor
Homework Helper
6,994
293
Unless you meant to restrict it to positive integers, here's a counter example:

A = -1 2 3 -4
B = 1 -2 -3 4
 
  • #6
134
7
thus x = a, or x = b, in either case, y is the remaining element of B.
&&
AlephZero said:
A = -1 2 3 -4
B = 1 -2 -3 4
In other words, the sets are not necessarily the same.

In Deveno's case, the elements are the same, but the possibility exists that a1=b2 and b1=a2 (the set order is different).

In AlephZero's case, the elements have the same magnitude, but have differing signs (and they could have alternate set ordering as well).
|-1| = |1|
 
  • #7
299
20
This lemma is not even true for the positive integers. Consider the multisets {1, 5, 8} and {2, 2, 10}. Alternatively, if we want to require that all three numbers be distinct, we can consider the sets {1, 9, 10} and {2, 3, 15}.
 
  • #8
uart
Science Advisor
2,776
9
Good counter example Citan. I wonder if the Lemma could be salvaged with the condition that all the factors be positive and non-trivial (that is, we also exclude "1"). Can anyone think of a counter example that doesn't include "1" as one of the factors?

In other words, the sets are not necessarily the same.

In Deveno's case, the elements are the same, but the possibility exists that a1=b2 and b1=a2 (the set order is different).
Matt, sets don't have ordering so that isn't important here.
 
  • #9
uart
Science Advisor
2,776
9
I wonder if the Lemma could be salvaged with the condition that all the factors be positive and non-trivial (that is, we also exclude "1")?

Just to answer my own question. Yes obviously if we just multiply each of the elements in the above counter example by "2" then the sums will increase by a factor of two and the products by eight, so they'll still be equal. So it looks like the proposed lemma is definitely sunk.
 
  • #10
7
0
Oh wow, good catch Citan! (but in fact negative integers are allowable, so even Aleph's counterexample works).

Thanks guys. I guess it's back to the drawing board with the proof. :(
 
  • #11
299
20
Just out of curiosity, what's the larger theorem you're trying to prove?
 
  • #12
7
0
Given two nxn matrices A, B,
The eigenvalues of AB = the eigenvalues of BA.

Essentially I had proved that the trace and determinant of both matrices was the same, and if this lemma were true that's all I would need.
 
Last edited:
  • #13
Deveno
Science Advisor
906
6
actually i thought of a better way:

suppose 0 is an eigenvalue of AB.

then either A or B must be singular.

hence BA is singular, so 0 is an eigenvalue of BA.

suppose λ is a non-zero eigenvalue for AB, with eigenvector v.

then BA(Bv) = B(ABv) = B(λv) = λ(Bv),

so λ is an eigenvalue for BA (with eigenvector Bv,

Bv cannot be 0, since ABv = λv is non-zero).

that's half, the other half is similar.
 
  • #14
299
20
You can actually go farther, and prove that AB and BA have the same eigenvalues with the same multiplicity. For this, it is necessary and sufficient to prove that AB and BA have the same characteristic polynomial. Let Char(AB) = det(λI-AB) be the characteristic polynomial of AB, and similarly for BA. If B is invertible, we have det(B) * Char(AB) = det(B(λI - AB)) = det (λB - BAB) = det ((λI-BA)B) = Char(BA) det(B), and dividing by both sides yields that Char(AB) = Char(BA). Now, note that the coefficients of Char(A) are polynomials in the entries of A, so the map A↦Char(A) is continuous. The invertible matrices are dense in the set of all matrices, so if B is not invertible, there is a sequence of invertible matrices {Bn} such that Bn → B. Then from the previous case we have Char(AB) = lim Char(ABn) = lim Char(BnA) = Char(BA), which completes the proof.
 
  • #15
Deveno
Science Advisor
906
6
The invertible matrices are dense in the set of all matrices

this is a topological fact unlikely to be covered in a linear algebra course (but I do like the way you think).
 

Related Threads on Small lemma about sums and products

Replies
3
Views
628
Replies
8
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
1
Views
4K
Replies
2
Views
794
  • Last Post
Replies
3
Views
1K
  • Last Post
2
Replies
36
Views
14K
Replies
8
Views
805
  • Last Post
Replies
2
Views
2K
Top