Opened 2 years ago

Closed 17 months ago

#30518 closed defect (fixed)

eigenvectors over QQbar are incorrectly conjugated

Reported by: Markus Wageringel Owned by:
Priority: blocker Milestone: sage-9.3
Component: number fields Keywords:
Cc: Vincent Delecroix Merged in:
Authors: Vincent Delecroix Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: c227dad (Commits, GitHub, GitLab) Commit: c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed
Dependencies: #31628 Stopgaps:

Status badges

Description (last modified by Vincent Delecroix)

Eigenvectors over QQbar could get incorrectly conjugated. In the following example from devel, the eigenvectors of a matrix over QuadraticField(-1) are computed in two ways, one of which incorrectly returns the conjugate of some eigenvectors.

By converting the matrix to QQbar first:

sage: K.<i> = QuadraticField(-1)
sage: m = matrix(K, 4, [2,4*i,-i,0, -4*i,2,-1,0, 2*i,-2,0,0, 4*i+4, 4*i-4,1-i,-2])
sage: sorted([(e, matrix.column(vs)) for e, vs, _ in m.change_ring(QQbar).eigenvectors_right()])
[(
    [  1   0]
    [1*I   0]
    [  0   0]
-2, [  0   1]
),
 (
                      [           1.000000000000000? + 0.?e-16*I]
                      [           0.?e-16 - 1.000000000000000?*I]
                      [           0.?e-16 - 6.605551275463989?*I]
-0.6055512754639893?, [1.000000000000000? + 1.000000000000000?*I]
),
 (
                    [           1.000000000000000? + 0.?e-17*I]
                    [           0.?e-17 - 1.000000000000000?*I]
                    [          0.?e-17 + 0.6055512754639893?*I]
6.605551275463989?, [1.000000000000000? + 1.000000000000000?*I]
)]

Supposedly, this result is correct. In contrast, computing the eigenvectors directly, without first converting to QQbar, leads to some eigenvectors getting conjugated:

sage: sorted([(QQbar(e), matrix.column(QQbar, vs)) for e, vs, _ in m.eigenvectors_right()])
[(
    [1 0]
    [I 0]
    [0 0]
-2, [0 1]
),
 (
                      [                                        1]
                      [           0.?e-54 + 1.000000000000000?*I]
                      [           0.?e-53 + 6.605551275463989?*I]
-0.6055512754639893?, [1.000000000000000? - 1.000000000000000?*I]
),
 (
                    [                                        1]
                    [           0.?e-53 + 1.000000000000000?*I]
                    [          0.?e-52 - 0.6055512754639893?*I]
6.605551275463989?, [1.000000000000000? - 1.000000000000000?*I]
)]

Note that the QuadraticField constructor automatically sets an embedding.

sage: K.coerce_embedding()
Generic morphism:
  From: Number Field in i with defining polynomial x^2 + 1 with i = 1*I
  To:   Complex Lazy Field
  Defn: i -> 1*I

Change History (35)

comment:1 Changed 19 months ago by Samuel Lelièvre

Possibly related:

  • #31551: Incorrect conversion from ℚ[-i] to SR

comment:2 in reply to:  1 Changed 19 months ago by Marc Mezzarobba

Replying to slelievre:

Possibly related:

  • #31551: Incorrect conversion from ℚ[-i] to SR

Unlike #31551, this happens with Sage 9.2 too. (The root cause may nevertheless be the same.)

comment:3 Changed 19 months ago by Marc Mezzarobba

The fix now at #31551 does not solve this issue.

comment:4 Changed 19 months ago by Vincent Delecroix

I think this is better illustrated with

sage: for e, vs, _ in m.change_ring(QQbar).eigenvectors_right():
....:     for v in vs:
....:         print(m*v == e*v)
True
True
True
True
sage: for e, vs, _ in m.eigenvectors_right():
....:     for v in vs:
....:         print(m*v == e*v)
True
True
False
False

comment:5 Changed 19 months ago by Vincent Delecroix

The problem somehow comes from line 6638 in matrix2.pyx

m = hom(eigval.parent(), e.parent(), e)

What happens here is that the eigenvalue is quadratic over QQ (not over the base field QQ[i]) and that the above code does not construct the embedding that preserves the one of the base field. This can be reproduced as follows

sage: K.<i> = QuadraticField(-1)
sage: L = K.extension(x^2 - 6*x - 4, 'a1')
sage: eigval = L.gen()
sage: eigval_conj = eigval.galois_conjugates(QQbar)
sage: f0 = hom(eigval.parent(), QQbar, eigval_conj[0])
sage: f1 = hom(eigval.parent(), QQbar, eigval_conj[1])
sage: f0(i)  # wrong embedding!!
0.?e-54 - 1.000000000000000?*I
sage: f1(i)  # wrong embedding!!
0.?e-54 - 1.000000000000000?*I

comment:6 Changed 19 months ago by Vincent Delecroix

Could be fixed by

sage: H = Hom(eigval.parent(), QQbar)
sage: f0 = H(eigval_conj[0], base_map=QQbar.coerce_map_from(K))
sage: f0(i)
0.?e-54 + 1.000000000000000?*I

But maybe hom should consider the embedding of the base by default when it exists?

comment:7 Changed 19 months ago by Vincent Delecroix

Authors: Vincent Delecroix
Branch: u/vdelecroix/30518
Commit: 852c89e335056d10cdefa6e25d9266c22b406e04
Status: newneeds_review

New commits:

fddaa2c#31151 support both embeddings in NumberFieldElement_gaussian
852c89e30518: choose coerce embedding for the base when it exists

comment:8 Changed 19 months ago by git

Commit: 852c89e335056d10cdefa6e25d9266c22b406e04cf668005799173205566b30be5bf0559752f14c9

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

cf6680030518: choose coerce embedding for the base when it exists

comment:9 Changed 19 months ago by Vincent Delecroix

Description: modified (diff)
Summary: eigenvectors over QQbar are incorrectly conjugatedhomomorphism of extension fields do not preserve canonical embeddings of the base

comment:10 Changed 19 months ago by Vincent Delecroix

Status: needs_reviewneeds_work

This is actually only a "partial" fix. It solves the following (that also used to fail)

sage: K.<i> = QuadraticField(-1, embedding=QQbar.gen())
sage: m = matrix(K, 4, [2,4*i,-i,0, -4*i,2,-1,0, 2*i,-2,0,0, 4*i+4, 4*i-4,1-i,-2])
sage: for e, vs, _ in m.eigenvectors_right():
....:     for v in vs:
....:         print(m*v == e*v)
True
True
True
True

But since

sage: K.<i> = QuadraticField(-1)                                                   
sage: QQbar.coerce_map_from(K) is None
True

the original example of the ticket is not solved.

comment:11 Changed 19 months ago by Vincent Delecroix

Authors: Vincent Delecroix
Branch: u/vdelecroix/30518
Commit: cf668005799173205566b30be5bf0559752f14c9
Dependencies: #31558
Description: modified (diff)
Summary: homomorphism of extension fields do not preserve canonical embeddings of the baseeigenvectors over QQbar are incorrectly conjugated

comment:12 Changed 19 months ago by Vincent Delecroix

As a start, you can review #31558.

comment:13 Changed 18 months ago by Samuel Lelièvre

Not fixed in Sage 9.3.rc2, in which #31551 and #31558 were merged.

comment:14 in reply to:  13 Changed 18 months ago by Vincent Delecroix

Replying to slelievre:

Not fixed in Sage 9.3.rc2, in which #31551 and #31558 were merged.

See 10.

comment:15 Changed 18 months ago by Vincent Delecroix

To my mind, the following should raise an error

sage: K.<i> = QuadraticField(-1)
sage: QQbar(i)

(as there is no specified embedding in QQbar)

comment:16 Changed 18 months ago by Vincent Delecroix

Authors: Vincent Delecroix
Branch: u/vdelecroix/30518
Commit: 0b387f7f9b9189e3cffefb7c8ba8ea81eefb4b0e
Dependencies: #31558
Status: needs_workneeds_review

New commits:

0b387f730518: raise errors in eigenspace/eigenvector in more cases

comment:17 Changed 18 months ago by Vincent Delecroix

patchbot is green! please review.

comment:18 Changed 18 months ago by Marc Mezzarobba

But QuadraticField(-1) has a coerce_embedding into CC. So it seems to me that the issue with the original example is that the conversion to QQbar ignores the embedding. If it did not do that, the conversion could be declared as a coercion, even if with the coerce_embedding going to CC.

comment:19 Changed 18 months ago by Vincent Delecroix

To my mind, the way number fields handle their coercions is far beyond the scope of this ticket. Even though I definitely agree that it is problematic. As soon as QQbar.has_coerce_map_from(K) answers True the eigenvalue/eigenvector code will work.

The minimal fix I provided turns wrong answers to errors. Together with 31551 and #31558, wrong answers are turned into right answers when coerce embeddings to the algebraic closure are available.

Version 0, edited 18 months ago by Vincent Delecroix (next)

comment:20 Changed 18 months ago by Marc Mezzarobba

Reviewers: Marc Mezzarobba

Ok, I tried to fix the problematic conversion and make it a coercion in #31628. You can set the present ticket to positive_review on my behalf if you want, or merge in my branch and adapt the tests.

comment:21 Changed 18 months ago by Vincent Delecroix

Dependencies: #31628
Status: needs_reviewneeds_work

comment:22 Changed 18 months ago by git

Commit: 0b387f7f9b9189e3cffefb7c8ba8ea81eefb4b0ec227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

43511e4fix conversion from QQ[-i] to QQbar
cf5228bnew implicit coercions to QQbar and AA
6430356#31628 one more test
c227dad30518: additional test for eigenvectors over nf

comment:23 Changed 18 months ago by Vincent Delecroix

Status: needs_workneeds_review

comment:24 Changed 18 months ago by Vincent Delecroix

Actually, some of my changes made sense (were more generic, only relying on the existence of algebraic closure and not assuming that it was QQbar). I opened #31631.

comment:25 Changed 18 months ago by Marc Mezzarobba

I am not sure I understand: do you want to drop your original fix (0b387f7) from this ticket and recycle it in #31631? That's fine with me, but we could also keep 0b387f7 and just update it to use number fields with no complex embedding.

comment:26 Changed 18 months ago by Vincent Delecroix

I want to drop it here (since it is not necessary anymore). However, going through .algebraic_closure (instead of hard coding QQbar) and checking coercion to the algebraic closure make sense. The reason why I opened #31631. I also would like to add examples related to finite field, reason why I opened an independent ticket.

comment:27 Changed 18 months ago by Marc Mezzarobba

Status: needs_reviewpositive_review

comment:28 Changed 18 months ago by Marc Mezzarobba

Ok, thanks!

comment:29 Changed 18 months ago by Matthias Köppe

Priority: majorblocker

comment:30 Changed 18 months ago by Samuel Lelièvre

Does the fix here provide inspiration for these somewhat similar issues?

comment:31 Changed 18 months ago by Volker Braun

Branch: u/vdelecroix/30518c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed
Resolution: fixed
Status: positive_reviewclosed

comment:32 Changed 18 months ago by Volker Braun

Commit: c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed
Resolution: fixed
Status: closednew

comment:33 Changed 18 months ago by Vincent Delecroix

Branch: c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bedu/vdelecroix/30518
Commit: c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed
Status: newneeds_review

(back to needs review as its dependency has been hopefully fixed)


New commits:

43511e4fix conversion from QQ[-i] to QQbar
cf5228bnew implicit coercions to QQbar and AA
6430356#31628 one more test
c227dad30518: additional test for eigenvectors over nf

comment:34 Changed 18 months ago by Vincent Delecroix

Status: needs_reviewpositive_review

Move to positive review since its dependency has been fixed.

comment:35 Changed 17 months ago by Volker Braun

Branch: u/vdelecroix/30518c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.