Ask Your Question
1

comparing sets of roots of charpoly

asked 2016-11-24 14:15:42 -0500

Laurent B gravatar image

updated 2016-11-24 17:03:35 -0500

tmonteil gravatar image

I am missing something about how to compare list of roots. During a small algorithm I need to know wether a matrix has or not complex eigenvalues. I did the following

   A=matrix(QQ,[[1,2,1],[6,-1,0],[-1,-2,-1]])
   a=(B.charpoly()).roots(ring= QQ, multiplicities=False)
   b=(B.charpoly()).roots(ring= QQbar, multiplicities=False)

then a is the list [-4,0,3] and b is the list [3,0,-4]. I don't get the following :

set(a)==set(b)

return false while

set([-4,0,3])==set([3,0,-4])

return true.

Any help, either on the first pb (knowing that a QQ matrix has complex eigenvalues) or on the second would be greatly appreciated. Cheers.

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
1

answered 2016-11-24 17:00:49 -0500

tmonteil gravatar image

Regarding your second question, the problem is that Sage breaks (by lack of choice) an important Python rule: two objects that are equal must have the same hash (the hash function maps a (hashable) Python object into an int). Python sets use hash to avoid repetitions: if two objects have different hash, they take two different "slots" in the set, if they have the same hash, then Python asks if they are equal to decide whether they have to take two different "slots" in the set. Hashing is a way to avoid long equality tests.

The problem is that Sage considers as equal some objects of different nature (type) for which it is very hard to construct an efficient transversally-consistent hash function.

Note that positive integers are their own hashes. So, if Sage was consistent, every algebraic numbers that is actually a positive integer should have itself (as a Python int) as a hash. Unfortunately, some integers can be roots of polynomials of high degree, and we do not want Sage to check whether the number is an integer when computing the hash, precisely because the hash function is a shortcut that aims to be fast.

Here is an illustration:

sage: a = QQbar(2).sqrt()^2
sage: a
2.000000000000000?
sage: hash(a)
8966545466098104078
sage: a.is_integer()
True
sage: a
2
sage: hash(a)
8966545466098104078
sage: b = 2
sage: hash(b)
2
sage: a == b
True
sage: hash(a) == hash(b)
False

Note the timings:

sage: a = QQbar(2).sqrt()^2
sage: %time hash(a)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 681 µs
8966545466098104078
sage: %time a.is_integer()
CPU times: user 16 ms, sys: 8 ms, total: 24 ms
Wall time: 19.4 ms
True

In particular:

sage: set([2,QQbar(2)])
{2, 2}
sage: set([2]) == set([QQbar(2)])
False

Of course, a trivial hash function (sending every object to 0) would be consistent, but useless since then Python will have to do a lot of equality testing.

What are the options ?

  • be trivially consistent (constant hash function), but accept to be very slow by postponing eveything to equality tests,
  • stay fast in computing nontrivial hashes but inconsistent when the objects have different parents (e.g. integers vs algebraic numbers),
  • compute consistent nontrivial hashes by checking integrity of algebraic numbers, but it is a very slow operation in general (see the previous timings in a simple example),
  • be very clever and figure out a formula to compute a nontrivial hash for algebraic numbers that gives consistent hash for integers and rationals, even when those are described by a huge polynomial (it would be a very nice resut, good luck to find one!),
  • have "typed sets", that accept only elements of the same type (raise an error otherwise). We could do this in Sage, but i am pretty sure that it will be an impossible change for Python sets. This might be an interesting option.

Now, regarding your first question, a matrix defined over QQ always has complex eigenvalues, because the field of complex numbers is algebaically closed. So, i guess, looking at your attempts, that you are trying to know whether there are non-rational eigenvalues.

What you can do is to transform the rational roots into algebraic roots:

sage: set([QQbar(x) for x in a]) == set(b)
True

A second option is not to discard multiplicities when you compute the rational roots. You only have rational eigenvalues if, and only if, the sum of the multiplicities of the rational roots is equal to the dimension:

sage: A.charpoly().roots(ring=QQ)
[(3, 1), (0, 1), (-4, 1)]
sage: sum(r[1] for r in A.charpoly().roots(ring=QQ)) == A.dimensions()[0]
True
edit flag offensive delete link more

Comments

A huge thanks for the explanation ! I get it know and I will be able to adapt it properly. Regarding the first question, actually I want to know if the (rational) Matrix is diagonalizable in $R$ so I need to distinguish between real algebraic eigenvalues and non reals algebraic ones so I took your idea with ring=RR. Thanks a lot, Cheers,

Laurent B gravatar imageLaurent B ( 2016-11-25 04:36:33 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2016-11-24 14:15:42 -0500

Seen: 49 times

Last updated: Nov 24 '16