1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Small lemma about sums and products

  1. Oct 11, 2011 #1
    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.
     
  2. jcsd
  3. Oct 11, 2011 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    have you tried induction?
     
  4. Oct 11, 2011 #3

    Deveno

    User Avatar
    Science Advisor

    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.
     
  5. Oct 12, 2011 #4

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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 ...
     
  6. Oct 12, 2011 #5

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Unless you meant to restrict it to positive integers, here's a counter example:

    A = -1 2 3 -4
    B = 1 -2 -3 4
     
  7. Oct 12, 2011 #6
    &&
    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|
     
  8. Oct 12, 2011 #7
    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}.
     
  9. Oct 14, 2011 #8

    uart

    User Avatar
    Science Advisor

    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?

    Matt, sets don't have ordering so that isn't important here.
     
  10. Oct 14, 2011 #9

    uart

    User Avatar
    Science Advisor

    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.
     
  11. Oct 14, 2011 #10
    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. :(
     
  12. Oct 15, 2011 #11
    Just out of curiosity, what's the larger theorem you're trying to prove?
     
  13. Oct 16, 2011 #12
    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: Oct 16, 2011
  14. Oct 16, 2011 #13

    Deveno

    User Avatar
    Science Advisor

    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.
     
  15. Oct 16, 2011 #14
    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.
     
  16. Oct 16, 2011 #15

    Deveno

    User Avatar
    Science Advisor

    this is a topological fact unlikely to be covered in a linear algebra course (but I do like the way you think).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Small lemma about sums and products
Loading...