An Efficient Algorithm For Computing Minimal Polynomials Of Polynomial Matrices

The minimal polynomial of a square matrix is a basic concept in linear algebra and its computation has important applications in automatic control, solving sparse linear equations, compution of the determinant and other fields. Firstly, this paper describes the history and state of the research to the minimal polynomial and the characteristic polynomial and then gives the main methods and its computational complexities for computing the characteristic polynomial and of a constant matrix, the characteristic polynomial of a polynomial matrix and the minimal polynomial of a polynomial. Finally, we present an efficient algorithm for computing the minimal polynomial of a polynomial matrix. It determines the coefficient polynomials term by term from lower to higher degree. By using a random vector and randomly shifting, this algorithm requires no condition on input matrix. Comparison with other algorithms in both theoretical complexity analysis and computational tests are given to show its effectiveness. Considering that our algorithm also released the restrictions added on the input matrix in CHTB method and it is of lower computational complexity comparing with CHACM method, our algorithm is one of the good candidates for the computation of the minimal polynomial of a polynomial matrix.