Fraction-free Method for Computing Rational Normal Forms of Square Matrices

Bibliographic Information

Other Title
  • 行列の有理標準形の分数なし計算法
  • ギョウレツ ノ ユウリ ヒョウジュンケイ ノ ブンスウ ナシ ケイサンホウ

Search this article


In this paper, we present a fraction-free algorithm for computing Rational Normal Forms of square matrices over the polynomial ring. The original algorithm is based on Danilevskii's method. Its principal transformations are similar to Gaussian elimination. When they are carried out exactly by computer algebra system, the difficulty lies in that the elements of intermediate matrices extremely swell and it requires much CPU-time to compute g.c.d.s and l.c.m.s for reducing rational expressions. In order to avoid such difficulty, we give a fraction-free algorithm analogous to Bareiss'single-step fraction-free elimination. We implement it on the computer algebra system REDUCE3.5. The experimental result shows the efficiency of our algorithm.


Citations (3)*help

See more


See more


Report a problem

Back to top