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]**L. Frank [1958], "Computing eigenvalues of complex matrices by determinant evaluation and by methods of Danilewski and Wielandt,"*J. SIAM*, v. 6, pp. 378-392. MR**21**#2354. MR**0103586 (21:2354)****[E]**R. Hansen [1963], "On the Danilewski method,"*J. ACM*, v. 10, pp. 102-109. MR**27**#5360. MR**0155426 (27:5360)****[I]**N. Herstein [1964],*Topics in Algebra*, Blaisdell, Waltham, Mass. MR**30**#2028. MR**0171801 (30:2028)****[A]**S. Householder [1964],*The Theory of Matrices in Numerical Analysis*, Blaisdell, New York. MR**30**#5475. MR**0175290 (30:5475)****[A]**S. Householder & F. L. Bauer [1959], "On certain methods for expanding the characteristic polynomial,"*Numer. Math.*, v. 1, pp. 29-37. MR**20**#7387. MR**0100962 (20:7387)****[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]**Wayland [1945], "Expansion of determinantal equations into polynomial form,"*Quart. Appl. Math.*, v. 2, pp. 277-306. MR**6**, 218. MR**0011799 (6:218f)****[J]**H. Wilkinson [1965],*The Algebraic Eigenvalue Problem*, Clarendon Press, Oxford. MR**32**#1894. MR**0184422 (32:1894)**

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