5
$\begingroup$

Preparing my Linear Algebra lecture I like the determinant free approach of Axler because the proof that operators $T$ on an $n$-dimensional complex vector space have eigenvalues is so simple:

Fix any non-zero vector $x$, observe that $x,T(x),\ldots,T^n(x)$ are linearly dependent to get a non-trivial linear combination $\sum\limits_{k=0}^nc_k T^k(x)=p(T)=0$, factorize the polynomial, and conclude that at least one factor $\lambda_k-T$ is not injective just because compositions of injective maps are injective.

The existence of a single eigenvalue is enough to prove the spectral theorem for normal operators by induction. However, I also try to mention the algorithmic aspects, and to make this proof an algorithm you really have to find all zeros of $p$. This is in contrast to the usual determinant approach where you only need one zero of the characteristic polynomial to get an eigenvalue.

Assume you have an oracle telling you one zero of a complex polynomial each time you ask. Is there a determinant free argument similar to Axler's which would lead to an eigenvalue?

Of course, without asking the oracle $n$ times, but if one quesion isn't enough perhaps at least considerably less than $n$ calls.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ Without using the oracle you can find the minimal polynomial of $T$ by looking for the first linear dependence among $I, T, T^2,\dotsc,T^r$ (minimal $r$). Alternatively find the first linear dependence among $x, T(x),\dotsc, T^r(x)$, for a fixed (arbitrary) nonzero $x$. Either way, the resulting polynomial has the property that all roots are eigenvalues. So, only one oracle call is needed at that point. (In practice it seems to me that the oracle goes the other way: to find a root of a polynomial, you look for an eigenvalue of the companion matrix.) $\endgroup$
    – Zach Teitler
    Commented May 4, 2020 at 18:25
  • $\begingroup$ Minimality is a great concept. Shame on me that I missed that. $\endgroup$
    – Jochen Wengenroth
    Commented May 4, 2020 at 18:49
  • $\begingroup$ @ZachTeitler Of course, I would like to accept your comment as an answer. $\endgroup$
    – Jochen Wengenroth
    Commented May 5, 2020 at 5:47

1 Answer 1

Reset to default
3
$\begingroup$

Using minimality can help.

Without using the polynomial-root oracle you can find the minimal polynomial of $T$ by looking for the first linear dependence among $I, T, T^2, \dotsc, T^r$ (for the minimal $r$—starting with just $I,T$ and increasing $r$ until you find a linear dependence). Alternatively, find the first linear dependence among $x, T(x), \dotsc, T^r(x)$ for a fixed (arbitrary) nonzero $x$. Either way, the resulting polynomial will have the property that all its roots are eigenvalues of $T$. So, only one call to the oracle is needed at that point.

(In practice, it seems to me that it probably goes the other way: to find a root of a polynomial, one looks for an eigenvalue of the companion matrix. But pedagogically it makes sense.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ I would actually go one step further and DEFINE eigenvalues as the zeros of the minimal polynomial, which I would introduce just as above asap. One can then easily prove the "if and only if"-theorem connecting this to the usual definition involving eigenvectors. In this way, one focuses on the central problem of finding zeros, instead of sweeping it under the rug. Consequently, one should move forward to the Frobenius normal form from there and can discuss the Jordan Form as special case when the minimal polynomial factors completely. $\endgroup$
    – thomashennecke
    Commented Aug 13, 2021 at 21:06
  • $\begingroup$ This ties in neatly with computations over the rational numbers and their finite extensions that can actually be performed in practice. I think Axler falls short of his own title by relegating the minimal polynomial to the back of the book without using it in this context, even though it is natural to introduce it while talking about eigenvalues from the start. Here, I refer to the second edition, I do not know the later ones. $\endgroup$
    – thomashennecke
    Commented Aug 13, 2021 at 21:11
  • $\begingroup$ Section 1.5 of Householders "The theory of matrices in numerical analysis" contains a proof of the minimal polynomial having degree at most $n$. I learned an explicit constructive variant of it from Harald Löwe, TU Braunschweig. $\endgroup$
    – thomashennecke
    Commented Jun 25, 2022 at 21:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .