1
$\begingroup$

Given a matrix, What is the computational complexity of the fastest algorithm to compute Jordan canonical form for the matrix? suppose the value of elements of the matrix and eigenvalue are complex number.

$\endgroup$
3
  • 6
    $\begingroup$ Have to be a little more specific. If the eigenvalues don't lie in the ground field (eg if the matrix is rational and the eigenvalues are complex irrational) how do you want the eigenvalues specified? $\endgroup$ Jan 24 at 4:48
  • 3
    $\begingroup$ That clarification was helpful but still leaves questions. eg, even if you work in a real/complex RAM (or BSS machine over $\mathbb{C}$), the eigenvalues will almost never be polynomials in the entries of the input matrix M. If $\mathbb{Q}(M)$ denotes the field of rationals adjoin the entries of M, the eigenvalues will in general live in an extension field of $\mathbb{Q}(M)$ of degree n! (where M is n x n). They can be specified in a variety of ways (characteristic polynomial and bounding box, first d digits of accuracy, etc.), but how they are specified can affect complexity. $\endgroup$ Mar 4 at 7:06
  • 3
    $\begingroup$ You might also be in a situation where you don't need to care about the actual values of the eigenvalues, and you can simply ask for combinatorial data to be output such as: the size of the Jordan blocks, and which pairs of Jordan blocks have the same eigenvalue (without specifying what its value is). Is there a particular setting you're interested in? $\endgroup$ Mar 4 at 7:07

Your Answer

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

Browse other questions tagged or ask your own question.