Jordan Normal and Rational Normal Form Algorithms

Original · EN

In this paper, we present a determinist Jordan normal form algorithms based on the Fadeev formula: (λ· I-A) · B(λ)=P(λ) · I where B(λ) is (λ· I-A)'s comatrix and P(λ) 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(λ₀) are eigenvectors of A associated to λ₀ for any root λ₀ of the characteristical polynomial. The complexity of the algorithm is O(n⁴) field operations if we know the factorization of the characteristic polynomial (or O(n⁵ (n)) operations for a matrix of integers of fixed size). This algorithm has been implemented using the Maple and Giac/Xcas computer algebra systems.