Jordan Normal and Rational Normal Form Algorithms
<|reference_start|>Jordan Normal and Rational Normal Form Algorithms: In this paper, we present a determinist Jordan normal form algorithms based on the Fadeev formula: \[(\lambda \cdot I-A) \cdot B(\lambda)=P(\lambda) \cdot I\] where $B(\lambda)$ is $(\lambda \cdot I-A)$'s comatrix and $P(\lambda)$ is $A$'s characteristic polynomial. This rational Jordan normal form algorithm differs from usual algorithms since it is not based on the Frobenius/Smith normal form but rather on the idea already remarked in Gantmacher that the non-zero column vectors of $B(\lambda_0)$ are eigenvectors of $A$ associated to $\lambda_0$ for any root $\lambda_0$ of the characteristical polynomial. The complexity of the algorithm is $O(n^4)$ field operations if we know the factorization of the characteristic polynomial (or $O(n^5 \ln(n))$ operations for a matrix of integers of fixed size). This algorithm has been implemented using the Maple and Giac/Xcas computer algebra systems.<|reference_end|>
@article{parisse2004jordan,
    title={Jordan Normal and Rational Normal Form Algorithms},
    author={Bernard Parisse (IF), Morgane Vaughan (IF)},
    journal={arXiv preprint arXiv:cs/0412005},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0412005},
    primaryClass={cs.SC}
}