From: israel@math.ubc.ca (Robert Israel) Newsgroups: sci.math.symbolic Subject: Re: What is the algorithm behind the minpoly(..) call in Maple? Date: 2 Aug 1996 00:40:18 GMT In article , masjhd@bath.ac.uk (James Davenport) writes: |> Dhaval M Shah wrote |> >> I would like to know the basic algorithm behind the minpoly(...) call of |> >> the Maple in the linalg(package). |> Maple don't tell me what the algorithm is, so I can't really help you. |> However, the algorithm is probably the obvious one: |> start from the characteristic polynomial, and try crossing out the repeated |> factors. Good guess, but not correct. From looking at the code, it seems that the method essentially this: Suppose we want the minimal polynomial of n by n matrix A. Consider the (n+1) by n^2 matrix B, where the k'th row of B is A^(k-1) with its entries rearranged into a row. Reduce to row echelon form, row by row. When a row is reduced to all 0, it means that the corresponding power of A is written as a linear combination of the preceding powers. The coefficients give you the minimal polynomial. To keep track of the operations performed, adjoin an identity matrix to the right of B. Then the coefficients of the minimal polynomial can be read off from the entries on the right in that row. e.g. consider [ 2 1 -3 ] [ ] A := [ 2 3 -6 ] [ ] [ 1 1 -2 ] Then [ 1 0 0 0 1 0 0 0 1 1 0 0 0 ] [ ] [ 2 1 -3 2 3 -6 1 1 -2 0 1 0 0 ] B := [ ] [ 3 2 -6 4 5 -12 2 2 -5 0 0 1 0 ] [ ] [ 4 3 -9 6 7 -18 3 3 -8 0 0 0 1 ] where the first row comes from the identity matrix, the second from A, the third from A^2, the fourth from A^3. Subtract 2*(row 1) from row 2, then 3*(row 1) + 2*(row 2) from row 3, and the result is [ 1 0 0 0 1 0 0 0 1 1 0 0 0 ] [ ] [ 0 1 -3 2 1 -6 1 1 -4 -2 1 0 0 ] [ ] [ 0 0 0 0 0 0 0 0 0 1 -2 1 0 ] [ ] [ 4 3 -9 6 7 -18 3 3 -8 0 0 0 1 ] Note that all of the part of row 3 that came from A^2 is now 0. Therefore I - 2* A + A^2 = 0, and the minimal polynomial of A is 1 - 2*t + t^2. The actual implementation works row by row, not actually calculating a row of B until it's needed. So in this case you'd never get to the 4th row. Robert Israel israel@math.ubc.ca Department of Mathematics (604) 822-3629 University of British Columbia fax 822-6074 Vancouver, BC, Canada V6T 1Y4