1
$\begingroup$

Numerous software implementations exist for doing diagonalization of square matrices. However, they are iterative in nature, usually based on some fixed point equation, and returns results with floating point precision. I am interested instead in an algorithm that computes eigenvalues exactly, assuming an underlying data structure designed to exactly represent algebraic numbers.

Consider a symmetric matrix $A$ whose entries are integers $Z$. Then we can rewrite $A = P^{-1} D P$ for some unitary $P$ and diagonal $D$. The entires of $D$ are algebraic. Furthermore, $P$ can be chosen such that its entries are algebraic. $P$ is not unique. I am interested in an exact representation of $P$ that supports exact span checking on its column vectors.

Iteration-based floating point results are not sufficient: the rank can depend on various machine epsilons in examples like the following:

\begin{bmatrix} 1 & 0 \\ 0 & 2^{-100} \end{bmatrix}

An example of a problem I need to solve would be as follows. Fix integer symmetric matrices $A$ and $B$. We wish to compute their eigenvectors: V=$\{v_i\}$ consists of eigenvectors for $A$ and W=$\{w_i\}$ consists of eigenvectors for $B$. For an input member $v$ in V, and a subset $\bar W \subset W$, I want to check whether $v \in \mathbf{span} {\bar W}$

Are there standard algorithms out there that do this efficiently? (Presumably, the entries of the basis vector are represented as lists of rational coefficients for various algebraic numbers?)

$\endgroup$
7
  • $\begingroup$ What do you mean by 'underlying data structure to represent algebraic numbers'? $\endgroup$
    – Kitegi
    Nov 15 '15 at 19:14
  • $\begingroup$ @Farnight. For example, floating points would not be suitable, because they are not exact. The underlying data structure would store things like sqrt(2) as is, without approximation. $\endgroup$
    – Yi Liu
    Nov 15 '15 at 19:46
  • $\begingroup$ What about something like: The third root of $x^5-x-1$? $\endgroup$
    – Kitegi
    Nov 15 '15 at 20:21
  • $\begingroup$ @farnight Thanks for raising that point. I was not clear. The primary operation I was looking for is the ability to quickly check whether two numbers are exactly the same. So, in the case of "third root of $f(x)$ v.s. 11th root of $g(x)$" I guess there could be ambiguity depending on the ordering, and the operation could be slow if the gcd of $f$ and $g$ is high order. $\endgroup$
    – Yi Liu
    Nov 15 '15 at 20:47
  • $\begingroup$ My high level goal is to be able to check whether a given eigenvector $v$ of is in the span of some other set of vectors ${w_i}$. $v$ and any $w_i$ are eigenvectors of integer matrices having the same square shape. I want to do this in a algebraic manner rather than via floating point approximations. $\endgroup$
    – Yi Liu
    Nov 15 '15 at 20:55
0
$\begingroup$

This wikipedia page states "While there is no simple algorithm to directly calculate eigenvalues for general matrices, there are numerous special classes of matrices where eigenvalues can be directly calculated."

https://en.wikipedia.org/wiki/Eigenvalue_algorithm#Direct_calculation

I think this may be what you are asking.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.