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