Computing Characteristic Polynomials of an Integer Matrix in Maple
Simon Lo, Simon Fraser University
Abstract: Let A be an n by n matrix of integers. We have already presented a Maple implementation of a modular method for computing the characteristic polynomial of A using the Hessenberg matrix approach, and we found that the implementation using double precision floats was always faster than the implementation using integers. We present two improvements to improve the running times. The first improvement is to use a output sensitive probabilistic version of the modular algorithm that would eliminate the use of a bound for the largest coefficient. The second improvement is to first try to find a permutation of the rows and columns of A to convert A into block upper triangular matrix where it would be easier to compute the characteristic polynomial. The permutation can be found by finding the strongly connected components (SCC) of a directed graph G, where G is the graph whose adjancency matrix is A. We have also implemented an algorithm by Tarjan to compute the SCC of a directed graph in Maple in linear time. Our approach of finding permutations into block upper triangular matrix could also be used to compute other related problems, such as computing the determinant.