BULLETIN OF THE POLISH ACADEMY OF SCIENCES
TECHNICAL SCIENCES
Vol. 56, No. 4, 2008
An algorithm for the calculation of the minimal polynomial
S. BIAAS 1 and M. BIAAS 2
2
1
The School of Banking and Management, 4 Armii Krajowej St., 30-150 Krakw, Poland
Faculty of Management, AGH University of Science and Technology, 30 Mickiewicza St., 30-059 Krakw, Poland
Abstract. This paper gives the simple algorithm for calculation of the degree and coefficients of the minimal polynomial for the complex
matrix A = [aij ]nn .
Key words: matrix, minimal polynomial, characteristic polynomial.
1. Introduction
Example 1. For the matrix A =
We use the standard notation. We denote by Mm,n the set of
m n real or complex matrices. In case n = m we will write
Mn instead of Mn,n .
A complex polynomial f () is called an annihilationy
polynomial for a matrix A Mn if f () 6 0 and f (A) =
0 Mn . The complex polynomial
Ak =
(k)
rank (B) rank of the matrix B,
N = {1, 2, 3, . . .},
I or In unit matrix,
degf (x) degree of the polynomial f (),
empty set.
e-mail:
we have:
(k)
(k)
(k)
a22
2. An algorithm for the calculation of the degree
and the coefficients of the minimal polynomial
For the matrix A = [aij ] Mn we will prove the following
Lemma.
Lemma 1. If the matrix A = [aij ] Mn , the matrix Bk is
defined by (1), then
K = {k N : rank Bk = rank Bk1 } =
6 and n K.
Proof. We see that if
() = det(I A) = n + bn1 n1 + + b1 + b0 ,
then
An + bn1 An1 + + b1 A + b0 I = 0 Mn ,
a(n) = [bn1 a(n1) + + b1 a(1) + b0 a(0) ],
(k = 0, 1, 2, . . .),
a(k) = vecAk (k = 0, 1, 2, . . .),
Bk = [a(0) a(1) a(k) ] (k = 0, 1, 2, . . .)
where a(k) is k + 1-th column of the matrix Bk Mn2 ,k+1 ,
a12
a22
a(k) = [a11 a12 a21 a22 ]T , B0 = [a(0) ] = [1 0 0 1]T ,
1 a11
0 a
12
B1 = [a(0) a(1) ] =
.
0 a21
1
where an 6= 0, is called monic if its leading coefficient
an = 1. The monic polynomial () of least degree for
which (A) = 0 Mn is called the minimal polynomial
of the matrix A Mn .
The properties and the applications of the minimal polynomials in the control theory have been presented in [1, 2].
In this paper the simple algorithm is given for the calculation of the degree and coefficients of the minimal polynomial.
For the matrix A = [aij ] Mn we will use the following
notations:
() = det(I A) charecteristic polynomial of the matrix A,
() minimal polynomial of the matrix A,
vecA = [a11 a12 . . . a1n a21 a22 . . . a2n . . . an1 an2 . . . ann ]T ,
A0 = I Mn ,
Ak = Ak1 A (k = 1, 2, . . .),
(1)
a11
a21
a(0) = [1 0 0 1]T , a(1) = [a11 a12 a21 a22 ]T , . . . ,
f () = an n + an1 n1 + + a1 + a0 ,
(k)
[aij ]
"
rank Bn = rank [a(0) a(1) . . . a(n) ]
= rank [a(0) a(1) . . . a(n1) 0] = rank Bn1 ,
where 0 = [0 0 . . . 0]T Mn2 ,1 . Therefore n K and
K 6= .
Definition 1. A number k0 = min K is called the associated
rank of the matrix A = [aij ] Mn .
Theorem 1. If k0 is the associated rank of the matrix A =
[aij ] Mn and () is the minimal polynomial of this matrix
then:
[email protected]
391
S. Biaas and M.Biaas
1) rank Bk = k + 1 (k = 0, 1, . . . , k0 1),
2) rank Bk = k0 (k k0 ),
3) deg () = k0 ,
for k k0 . This finishes the proof of 2) of the Theorem 1.
Now we prove that if () is the minimal polynomial of
the matrix A then deg () = k0 .
Hence that rankBk0 = rankBk0 1 = k0 it follows that
the set of equations
where the matrix Bk is defined by the relation (1).
Proof. Let Bk = [a(0) a(1) a(k0 1) a(k0 ) a(k0 +1) a(k) ].
First we will prove that rankBk = k + 1 (k =
0, 1, . . . , k0 1). From the definition of k0 it follows that
rankBk0 = rankBk0 1 . For k0 = 1 rankB1 = rankB0 = 1.
However, for k0 > 1 we have:
rankB1 > rankB0 = 1 rankB1 = 2,
with the unknown = [0 1 . . . k0 1 ]T C k0 , has only
one solution and
0 I + 1 A + + k0 1 Ak0 1 + Ak0 = 0 Mn ,
besides
rankB2 > rankB1 = 2 rankB2 = 3,
0 + 1 + + k0 1 k0 1 + k0 ,
is the annihilationy polynomial of the matrix A.
Hence that rankBk = k + 1 (k = 0, 1, . . . , k0 1) it
follows that the set of equations
rankBk0 1 > rankBk0 2 = k0 1 rankBk0 1 = k0 .
Therefore rankBk = k + 1 for k {0, 1, 2, . . . , k0 1}
and rankBk0 = rankBk0 1 = k0 . Hence it follows that
the columns a(0) , a(1) , . . . , a(k0 1) are linear independent
and the column a(k0 ) can be written as the linear combination of the columns a(0) , a(1) , . . . , a(k0 1) , so there exists
= (0 , 1 , . . . , k0 1 ) C k0 such that
(k0 )
0 a(0) + 1 a(1) + + k0 1 a(k0 1) = a0
It denotes that
0 I + 1 A + + k0 1 Ak0 1 + Ak0 = 0 Mn
k0
and the polynomial f () = 0 + 1 + + is the
annihilationy polynomial of the matrix A.
For k > k0 , m = k k0 and any arbitrary numbers
0 , 1 , . . . , m1 C the polynomial g() = f ()(0 +
1 + +m1 m1 +m ) = 0 +1 +. . .+k1 k1 +k
is the annihilationy polynomial of the matrix A, too.
Therefore
0 I + 1 A + + k1 Ak1 + Ak = 0 Mn ,
0 a(0) + 1 a(1) + + k1 a(k1) + a(k) = 0 Mn2 ,1 .
(2)
In the matrix Bk = [a(0) a(1) a(k0 1) a(k0 ) a(k0 +1) a(k) ]
the column a(j) can be multiplied by j (j = 0, 1, . . . , k1)
and added to the column a(k) . Hence and (2) we have
rankBk = rank[a(0) a(1) a(k1) 0] = rankBk1 .
Similary transformation can be used to the matrix Bk1 .
At the end, we have
rankBk = rank[a(0) a(1) a(k0 1) a(k0 ) 0 0]
= rankBk0 = k0
392
Bk0 1 = a(k0 ) ,
(3)
Bk1 = a(k) ,
with the unknown = [0 1 . . . k1 ]T C k , has not the
solutions.
This denotes that the polynomial (3) is the minimal polynomial of the matrix A and deg () = k0 .
Now, we give the algorithm for the calculation of the degree and coefficients of the minimal polynomial of the matrix
A = [aij ] Mn .
Consider the matrix
Bn = [a(0) a(1) . . . a(n) ] Mn2 ,n+1 ,
which is defined in (1).
The elements of the matrix Bn are denoted by bij , therefore Bn = [bij ] Mn2 ,n+1 , where b11 = 1, b12 =
(1)
(n)
(n)
a11 , . . . , b1,n+1 = a11 , . . . , bn2 ,n+1 = ann .
We will calculate the rank of the matrix Bn by Gaussian
elimination, except interchange and cancel of the null
columns.
We obtain
1
b12 . . . b1,n+1
(1)
(1)
0
b22
. . . b2,n+1
(1)
(1)
rankBn = rank
0
b
.
.
.
b
32
3,n+1 ,
... ... ...
...
(1)
(1)
bn2 ,2
(1)
. . . bn2 ,n+1
(1)
(1)
where, for example b22 = b22 , . . . , b2,n+1 = b2,n+1 , bn2 ,2 =
bn2 ,2 b12 .
From the Lemma 1 it follows that n K = {k
N : rankBk = rankBk1 }.
Bull. Pol. Ac.: Tech. 56(4) 2008
An algorithm for the calculation of the minimal polynomial
Therefore there exists r N such
...
rankBn = rank 0
...
that r n and
b12
b13
... ...
...
...
...
...
b1,n+1
b12
(1)
b23
(1)
... ...
...
...
...
...
b2,n+1
b33
(2)
... ...
...
...
...
...
b3,n+1
...
...
... ...
...
...
...
...
(r1)
br,n+1
...
...
br+1,r+2
...
br+2,r+2
...
...
...
...
...
...
...
bn2 ,r+2
(r1)
...
bn2 ,n+1
... ...
...
Bk0 1 = a(k0 ) ,
(4)
T
with the unknown = [0 1 . . . k0 1 ]
one solution and
k0
C , has only
0 + 1 A + + k0 1 Ak0 1 + Ak0 = 0 Mn .
Therefore 0 , 1 , . . . , k0 1 , 1 are the coefficients of the
minimal polynomial of the matrix A. The set of Eq. (4) is
equivalent to the set of equations
= b,
B
where
b11
0 b(1)
22
B= 0
0
... ...
0
0
...
...
b1r
...
...
b2r
b33
(2)
...
b3r
...
...
...
(r1)
brr
...
(1)
(2)
= [0 1 . . . k0 1 ]T , r = k0 .
Example 2. We will calculate
matrix
A = 1
1
In this example we have
b1,r+1
(1)
b2,r+1
, b =
..
(r1)
br,r+1
the minimal polynomial of the
3 2
5 2 .
3
0
10 18 12
2
A = 6 22 12 ,
6 18
8
Bull. Pol. Ac.: Tech. 56(4) 2008
...
(2)
(i1)
...
(r1)
br,r+1 . . .
(1)
(r1)
brr
where bii
6= 0 (i = 1, 2, . . . , r).
From this it follows that rankBj = j (j = 1, 2, . . . , n),
rankBr1 = r, rankBr = r.
Therefore k0 = min K = r and deg () = r = k0 .
Thus, by Gaussian elimination we can compute the degree
of the minimal polynomial of the matrix A.
Hence that det Br1 = det Bk0 1 6= 0 and rankBk0 =
rankBk0 1 = k0 it follows that the set of equations
...
(r1)
. . . br+1,n+1
(r1)
(r1)
. . . br+2,n+1
(r1)
(r1)
36 84 56
A3 = 28 92 56 ,
28 84 48
1 3
10
36
0 3 18 84
0 2
12
56
0 1 6 28
rankB3 = rank 1 5
22
92
0 2 12 56
0 1 6 28
0 3
18
84
1 0
8 48
1 3
10
36
0 3 18 84
0 0
0
0
0 0
0
0
= rank 0 0
0
0 = 2,
0 0
0
0
0 0
0
0
0 0
0
0
0
=
B
"
1
0
0
0
0
# "
#
3
10
, b
,
3
18
k0 = 2,
= [0 1 ]T = [8 6]T .
Therefore, () = 2 6+8. is the minimal polynomial
of the matrix A.
REFERENCES
[1] S. Barnett, Matrices in Control Theory, Van Nostrand Reinhold
Company, London, 1960.
[2] T. Kaczorek, Vectors and Matrices in Automatics and Electrotechnics, WNT, Warszawa, 1998.
393
