2004/12/02 by Bernard Parisse, Parisse, Bernard, Morgane Vaughan +1 · 1 citation
Computer Science · #FOS: Computer and information sciences #MSC2000 15A21 68W30 #Matrix Theory and Algorithms #Numerical Methods and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.SC
paper · pdf · doi:10.48550/arxiv.cs/0412005
arxiv created 2004/12/02 · openalex publication_date 2004/12/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(λ0) are eigenvectors of A associated to λ0 for any root λ0 of the characteristical polynomial. The complexity of the algorithm is O(n4) field operations if we know the factorization of the characteristic polynomial (or O(n5 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.