Opened 14 months ago

Closed 6 months ago

#30518 closed defect (fixed)

eigenvectors over QQbar are incorrectly conjugated

Reported by: gh-mwageringel Owned by:
Priority: blocker Milestone: sage-9.3
Component: number fields Keywords:
Cc: vdelecroix 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 vdelecroix)

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 follow-up: Changed 7 months ago by slelievre

Possibly related:

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

comment:2 in reply to: ↑ 1 Changed 7 months ago by mmezzarobba

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 7 months ago by mmezzarobba

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

comment:4 Changed 7 months ago by vdelecroix

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 7 months ago by vdelecroix

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 7 months ago by vdelecroix

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 7 months ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/30518
  • Commit set to 852c89e335056d10cdefa6e25d9266c22b406e04
  • Status changed from new to needs_review

New commits:

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

comment:8 Changed 7 months ago by git

  • Commit changed from 852c89e335056d10cdefa6e25d9266c22b406e04 to cf668005799173205566b30be5bf0559752f14c9

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 7 months ago by vdelecroix

  • Description modified (diff)
  • Summary changed from eigenvectors over QQbar are incorrectly conjugated to homomorphism of extension fields do not preserve canonical embeddings of the base

comment:10 Changed 7 months ago by vdelecroix

  • Status changed from needs_review to needs_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 7 months ago by vdelecroix

  • Authors Vincent Delecroix deleted
  • Branch u/vdelecroix/30518 deleted
  • Commit cf668005799173205566b30be5bf0559752f14c9 deleted
  • Dependencies set to #31558
  • Description modified (diff)
  • Summary changed from homomorphism of extension fields do not preserve canonical embeddings of the base to eigenvectors over QQbar are incorrectly conjugated

comment:12 Changed 7 months ago by vdelecroix

As a start, you can review #31558.

comment:13 follow-up: Changed 7 months ago by slelievre

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

comment:14 in reply to: ↑ 13 Changed 7 months ago by vdelecroix

Replying to slelievre:

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

See 10.

comment:15 Changed 7 months ago by vdelecroix

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 7 months ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/30518
  • Commit set to 0b387f7f9b9189e3cffefb7c8ba8ea81eefb4b0e
  • Dependencies #31558 deleted
  • Status changed from needs_work to needs_review

New commits:

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

comment:17 Changed 7 months ago by vdelecroix

patchbot is green! please review.

comment:18 Changed 7 months ago by mmezzarobba

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 7 months ago by vdelecroix

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.

Last edited 7 months ago by vdelecroix (previous) (diff)

comment:20 Changed 7 months ago by mmezzarobba

  • Reviewers set to 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 7 months ago by vdelecroix

  • Dependencies set to #31628
  • Status changed from needs_review to needs_work

comment:22 Changed 7 months ago by git

  • Commit changed from 0b387f7f9b9189e3cffefb7c8ba8ea81eefb4b0e to c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed

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 7 months ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:24 Changed 7 months ago by vdelecroix

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 7 months ago by mmezzarobba

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 7 months ago by vdelecroix

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 7 months ago by mmezzarobba

  • Status changed from needs_review to positive_review

comment:28 Changed 7 months ago by mmezzarobba

Ok, thanks!

comment:29 Changed 6 months ago by mkoeppe

  • Priority changed from major to blocker

comment:30 Changed 6 months ago by slelievre

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

comment:31 Changed 6 months ago by vbraun

  • Branch changed from u/vdelecroix/30518 to c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:32 Changed 6 months ago by vbraun

  • Commit c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed deleted
  • Resolution fixed deleted
  • Status changed from closed to new

comment:33 Changed 6 months ago by vdelecroix

  • Branch changed from c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed to u/vdelecroix/30518
  • Commit set to c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed
  • Status changed from new to needs_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 6 months ago by vdelecroix

  • Status changed from needs_review to positive_review

Move to positive review since its dependency has been fixed.

comment:35 Changed 6 months ago by vbraun

  • Branch changed from u/vdelecroix/30518 to c227dad03dbef66c5ab1b2ba3c3cd9e7155c8bed
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.