An algorithm for the exact reduction of a matrix to Frobenius form using modular arithmetic. I

Author:
Jo Ann Howell

Journal:
Math. Comp. **27** (1973), 887-904

MSC:
Primary 65F30

DOI:
https://doi.org/10.1090/S0025-5718-1973-0378381-9

MathSciNet review:
0378381

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper is in two parts. Part I contains a description of the Danilewski algorithm for reducing a matrix to Frobenius form using rational arithmetic. This algorithm is modified for use over the field of integers modulo *p*. The modified algorithm yields exact integral factors of the characteristic polynomial. A description of the single-modulus algorithm is given. Part II contains a description of the multiple-modulus algorithm. Since different moduli may yield different factorizations, an algorithm is given for determining which factorizations are not correct factorizations over the integers of the characteristic polynomial.

**[B]**A. Chartres [1964],*Controlled Precision Calculations and the Danilewski Method*, Brown University, Division of Applied Mathematics Report.**[A]**Danilewski [1937], "On a numerical solution of Vekua's equation,"*Mat. Sb.*, v. 2, pp. 169-171. (Russian)**[W]**Werner L. Frank,*Computing eigenvalues of complex matrices by determinant evaluation and by methods of Danilewski and Wielandt*, J. Soc. Indust. Appl. Math.**6**(1958), 378–392. MR**0103586****[E]**Eldon R. Hansen,*On the Danilewski method*, J. Assoc. Comput. Mach.**10**(1963), 102–109. MR**0155426**, https://doi.org/10.1145/321150.321158**[I]**I. N. Herstein,*Topics in algebra*, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1964. MR**0171801****[A]**Alston S. Householder,*The theory of matrices in numerical analysis*, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1964. MR**0175290****[A]**Alston S. Householder and Friedrich L. Bauer,*On certain methods for expanding the characteristic polynomial*, Numer. Math.**1**(1959), 29–37. MR**0100962**, https://doi.org/10.1007/BF01386370**[J]**A. Howell, [1972],*An Algorithm for the Exact Reduction of a Matrix to Frobenius Form Using Modular Arithmetic*, University of Texas at Austin Center for Numerical Analysis, Report CNA-39, Austin, Texas.**1.**Michael T. McClellan [1971],*The Exact Solution of Linear Equations with Polynomial Coefficients*, University of Wisconsin Computer Sciences Department, Technical Report #136, Madison, Wisconsin.**[D]**L. Slotnick [1963],*Modular Arithmetic Computing Techniques*, Westinghouse Electric Corporation, Technical Report ASD-TDR-63-280, Baltimore; Clearinghouse for Federal Scientific and Technical Information, Report No. AD410534, Springfield, Virginia 22151.**[H]**Harold Wayland,*Expansion of determinantal equations into polynomial form*, Quart. Appl. Math.**2**(1945), 277–306. MR**0011799**, https://doi.org/10.1090/S0033-569X-1945-11799-8**[J]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1973-0378381-9

Keywords:
Modular arithmetic,
residue arithmetic,
modulus,
Frobenius form,
Danilewski method,
characteristic polynomial,
similarity transformation,
prime number,
Chinese Remainder Theorem

Article copyright:
© Copyright 1973
American Mathematical Society