Tao R. Finite Automata and Application to Cryptography
Подождите немного. Документ загружается.
4.4 Canonical Diagonal Matrix Polynomial 133
C
jk
= P
k
C
jk
,j=0, 1,...,h.
C
k
(z)=
h
j=0
C
jk
z
j
is said to be obtained from C
k
(z) by Rule R
a
using P
k
,
denoted by
C
k
(z)
R
a
[P
k
]
−→ C
k
(z).
Rule R
b
:Letk 0, C
k
(z) ∈ M
m,n
(F [z]) and C
k
(z)=
h
j=0
C
jk
z
j
.If
the last m − r
k+1
rows of C
0k
are 0 in the case of r
k+1
<m, C
k+1
(z)=
I
−1
m,r
k+1
C
k
(z) ∈ M
m,n
(F [z]) is said to be obtained from C
k
(z) by Rule R
b
,
denoted by
C
k
(z)
R
b
[r
k+1
]
−→ C
k+1
(z).
An R
a
R
b
transformation sequence
C
k
(z)
R
a
[P
k
]
−→ C
k
(z),C
k
(z)
R
b
[r
k+1
]
−→ C
k+1
(z),k=0, 1,...,t− 1 (4.40)
is said to be elementary, if for any k,0 k t − 1, P
k
is in the form
P
k
=
E
r
k
0
P
k1
P
k2
,
and the first r
k+1
rows of C
0k
is linearly independent over F ,wherer
0
=0.
Notice that if (4.40) is an elementary R
a
R
b
transformation sequence,
then r
j
r
j−1
for j =2,...,t.
The R
a
R
b
transformation sequence (4.40) is said to be terminating,if
the last m − r
t
rows of C
t
(z) are 0 in the case of r
t
<mand the first r
t
rows
of C
0t
are linearly independent over F .
From the definitions of R
a
and R
b
transformations, we have the following.
Lemma 4.4.1. If (4.40) is an R
a
R
b
transformation sequence, then
C
t
(z)=I
−1
m,r
t
P
t−1
I
−1
m,r
t−1
P
t−2
...I
−1
m,r
1
P
0
C
0
(z).
Lemma 4.4.2. Let (4.40) be an elementary R
a
R
b
transformation sequence.
Let m
1
= r
1
, m
j
= r
j
− r
j−1
, j =2,...,t. Then there exists an m × m
invertible matrix polynomial
¯
P (z) such that degrees of elements in columns
r
k
+1 to r
k+1
of
¯
P (z) are at most t − k − 1 for k =0, 1,...,t− 1,and
P
−1
0
I
m,r
1
P
−1
1
I
m,r
2
...P
−1
t−2
I
m,r
t−1
P
−1
t−1
I
m,r
t
=
¯
P (z)DIA
m,m
(E
m
1
,zE
m
2
,...,z
t−1
E
m
t
,z
t
E
m−r
t
),
where r
0
=0, r
i
= r
i
, i =1,...,t− 1,andr
t
= m.
134 4. Relations Between Transformations
Proof. It is easy to verify that for any k,1 k t,
I
m,r
1
I
m,r
2
...I
m,r
k
= DIA
m,m
(E
m
1
,zE
m
2
,...,z
k−1
E
m
k
,z
k
E
m−r
k
).
Denote
P
j
=
⎡
⎢
⎢
⎢
⎣
E
m
1
.
.
.
E
m
j
P
j1
···P
jj
P
j,j+1
⎤
⎥
⎥
⎥
⎦
,j=1,...,t− 1.
Clearly, P
−1
j
is in the form
P
−1
j
=
⎡
⎢
⎢
⎢
⎣
E
m
1
.
.
.
E
m
j
P
j1
···P
jj
P
j,j+1
⎤
⎥
⎥
⎥
⎦
,j=1,...,t− 1.
Let
P
j
(z)=
⎡
⎢
⎢
⎢
⎣
E
m
1
.
.
.
E
m
j
z
j
P
j1
···zP
jj
P
j,j+1
⎤
⎥
⎥
⎥
⎦
,j=1,...,t− 1. (4.41)
It is easy to see that
I
m,r
1
I
m,r
2
...I
m,r
k
P
−1
k
= P
k
(z)I
m,r
1
I
m,r
2
...I
m,r
k
,k=1,...,t− 1.
Using this observation, it is easy to prove, by induction on k, the following
proposition
I
m,r
1
P
−1
1
I
m,r
2
P
−1
2
...I
m,r
k
P
−1
k
= P
1
(z)P
2
(z) ...P
k
(z)I
m,r
1
I
m,r
2
...I
m,r
k
holds for k =1, 2,...,t− 1. This yields
P
−1
0
I
m,r
1
P
−1
1
I
m,r
2
P
−1
2
...I
m,r
t−1
P
−1
t−1
I
m,r
t
= P
−1
0
P
1
(z)P
2
(z) ...P
t−1
(z)I
m,r
1
I
m,r
2
...I
m,r
t−1
I
m,r
t
=
¯
P (z)DIA
m,m
(E
m
1
,zE
m
2
,...,z
t−1
E
m
t
,z
t
E
m−r
t
),
where
¯
P (z)=P
−1
0
P
1
(z)P
2
(z) ...P
t−1
(z).
From (4.41), the determinant of P
j
(z) is a nonzero constant for any j,1
j t − 1. It follows immediately that the determinant of P
−1
0
P
1
(z)P
2
(z) ...
P
t−1
(z) is a nonzero constant. Therefore,
¯
P (z) is invertible.
Partition P
1
(z) ... P
j
(z)into[P
j1
(z), ..., P
j,j+1
(z)], where P
jk
(z)has
m
k
columns for k =1,...,j. From (4.41), it is easy to prove by induction
on j that degrees of elements of P
jk
(z)areatmostj − k +1 for any k, j,
4.4 Canonical Diagonal Matrix Polynomial 135
1 k j +1 and 1 j t − 1. It follows immediately that degrees
of elements in columns r
k
+1 to r
k+1
of
¯
P (z)areatmostt − k − 1for
k =0, 1,...,t− 1.
Theorem 4.4.1. Let (4.40) be an elementary R
a
R
b
transformation se-
quence. Let m
1
= r
1
,m
j
= r
j
− r
j−1
,j=2,...,t. Then there exists an
m × m invertible matrix polynomial
¯
P (z) such that degrees of elements in
columns r
k
+1 to r
k+1
of
¯
P (z) are at most t − k − 1 for k =0, 1,...,t− 1,
and
C
0
(z)=
¯
P (z)DIA
m,m
(E
m
1
,zE
m
2
,...,z
t−1
E
m
t
,z
t
E
m−r
t
)C
t
(z),
where r
0
=0, r
i
= r
i
, i =1,...,t− 1,andr
t
= m.
Proof. From Lemma 4.4.1,
C
t
(z)=I
−1
m,r
t
P
t−1
I
−1
m,r
t−1
P
t−2
...I
−1
m,r
1
P
0
C
0
(z).
Thus
C
0
(z)=P
−1
0
I
m,r
1
P
−1
1
I
m,r
2
...P
−1
t−2
I
m,r
t−1
P
−1
t−1
I
m,r
t
C
t
(z).
Using Lemma 4.4.2, it follows immediately that there exists an m× m invert-
ible matrix polynomial
¯
P (z) such that degrees of elements in columns r
k
+1
to r
k+1
of
¯
P (z)areatmostt − k − 1fork =0, 1,...,t− 1, and
C
0
(z)=
¯
P (z)DIA
m,m
(E
m
1
,zE
m
2
,...,z
t−1
E
m
t
,z
t
E
m−r
t
)C
t
(z).
Corollary 4.4.1. Let (4.40) be a terminating and elementary R
a
R
b
trans-
formation sequence. Let m
1
= r
1
,m
j
= r
j
−r
j−1
,j=2,...,t.Thenthereex-
ists an m×m invertible matrix polynomial
¯
P (z) such that degrees of elements
in columns r
k
+1 to r
k+1
of
¯
P (z) are at most t − k − 1 for k =0, 1,...,t− 1,
and
C
0
(z)=
¯
P (z)DIA
m,r
t
(E
m
1
,zE
m
2
,...,z
t−1
E
m
t
)
¯
Q(z), (4.42)
where r
0
=0,r
i
= r
i
,i=1,...,t− 1,r
t
= m, and
¯
Q(z) is the first r
t
rows
of C
t
(z).
Corollary 4.4.2. Let (4.40) be a terminating and elementary R
a
R
b
trans-
formation sequence. Then the rank of C
0
(z) is r
t
.
Proof.Letr be the rank of C
0
(z). Since
¯
P (z) is invertible, from (4.42),
the rank of C
(z)=DIA
m,r
t
(E
m
1
, zE
m
2
, ..., z
t−1
E
m
t
)
¯
Q(z)isr.Itis
easy to see that any k-order minor of C
(z) equals 0 if k>r
t
.Onthe
other hand, since
¯
Q(0) is row independent, there exists a nonzero r
t
-order
minor
¯
Q(1,...,r
t
; j
1
,...,j
r
t
; z)of
¯
Q(z). It follows that the r
t
-order minor
C
(1,...,r
t
; j
1
,...,j
r
t
; z) is nonzero. Thus r
t
is the rank of C
(z). It follows
that r = r
t
.
136 4. Relations Between Transformations
4.4.2 Relations Between R
a
R
b
Transformation and Canonical
Diagonal Form
Given C
0
(z)inM
m,n
(F [z]) with rank r, there exist P (z) ∈ GL
m
(F [z]),
Q(z) ∈ GL
n
(F [z]), r nonnegative integers a
1
,...,a
r
,andr polynomials
f
1
(z),...,f
r
(z) such that
C
0
(z)=P (z)DIA
m,n
(z
a
1
f
1
(z),...,z
a
r
f
r
(z), 0,...,0)Q(z), (4.43)
0 a
1
··· a
r
, f
j
(z) | f
j+1
(z)forj =1,...,r − 1, and f
j
(0) =0for
j =1,...,r.
Let (4.40) be a terminating and elementary R
a
R
b
transformation se-
quence. From Corollaries 4.4.1 and 4.4.2, we can construct an m×m invertible
matrix polynomial
¯
P (z) such that (4.42) holds, that is,
C
0
(z)=
¯
P (z)DIA
m,r
(E
m
1
,zE
m
2
,...,z
t−1
E
m
t
)
¯
Q(z),
where m
1
= r
1
, m
j
= r
j
− r
j−1
, j =2,...,t,and
¯
Q(z) is the first r rows
of C
t
(z). Denote b
i
= k − 1forr
k−1
<i r
k
,1 k t, i =1,...,r.
Then DIA
m,r
(E
m
1
,zE
m
2
,...,z
t−1
E
m
t
)=DIA
m,r
(z
b
1
,z
b
2
,...,z
b
r
). It fol-
lows that
C
0
(z)=
¯
P (z)DIA
m,r
(z
b
1
,z
b
2
,...,z
b
r
)
¯
Q(z). (4.44)
Notice that
¯
Q(z)hasr rows and rank r and
¯
Q(0) is row independent.
Thus there exist
¯
M(z)∈GL
r
(F [z]),
¯
R(z)∈GL
n
(F [z]), and r polynomials
g
1
(z),...,g
r
(z) such that
¯
Q(z)=
¯
M(z)DIA
r,n
(g
1
(z),...,g
r
(z))
¯
R(z),
g
j
(z) | g
j+1
(z)forj =1,...,r − 1, and g
j
(0) =0forj =1,...,r.From
(4.44), it follows that
C
0
(z)=
¯
P (z)DIA
m,r
(z
b
1
,z
b
2
,...,z
b
r
)
¯
M(z)DIA
r,n
(g
1
(z),...,g
r
(z))
¯
R(z).
(4.45)
Since P , Q,
¯
P and
¯
R are invertible, from (4.43) and (4.45), D
af
and
D
b
¯
M(z)D
g
are equivalent
1
and their determinant factors are the same, where
D
af
= DIA
m,n
(z
a
1
f
1
(z),...,z
a
r
f
r
(z), 0,...,0),
D
b
= DIA
m,r
(z
b
1
,z
b
2
,...,z
b
r
),
D
g
= DIA
r,n
(g
1
(z),...,g
r
(z)).
1
A(z)andB(z)inM
m,n
(F [z]) are equivalent if and only if there exist P
(z)in
GL
m
(F [z]) and Q
(z)inGL
n
(F [z]) such that A(z)=P
(z)B(z)Q
(z).
4.4 Canonical Diagonal Matrix Polynomial 137
Lemma 4.4.3. For any A(z) ∈ GL
n
(F [z]) and any r n,let
d
i
1
,...,i
r
=gcd{A(i
1
,...,i
r
; j
1
,...,j
r
; z), 1 j
1
< ···<j
r
n},
d
j
1
,...,j
r
=gcd{A(i
1
,...,i
r
; j
1
,...,j
r
; z), 1 i
1
< ···<i
r
n}.
Then d
i
1
,...,i
r
and d
j
1
,...,j
r
are nonzero constants.
Proof. Using Laplace expansion theorem, for any t<n,wehave
A(i
1
,...,i
t+1
; j
1
,...,j
t+1
; z)
=
t+1
k=1
(−1)
t+1+k
a
i
t+1
j
k
(z)A(i
1
,...,i
t
; j
1
,...,j
k−1
,j
k+1
,...,j
t+1
; z)
= a(z)d
i
1
,...,i
t
for some a(z) ∈ F [z], where a
ij
(z) is the element at row i and column j
of A(z). Thus d
i
1
,...,i
t+1
= a(z)d
i
1
,...,i
t
for some a(z) ∈ F [z]. It follows that
d
i
1
,...,i
n
= a(z)d
i
1
,...,i
r
for some a(z) ∈ F [z]. Therefore, |A(z)| = a(z)d
i
1
,...,i
r
for some a(z) ∈ F [z]. Since A(z) ∈ GL
n
(F [z]), |A(z)| isanonzeroelement
in F .Thusd
i
1
,...,i
r
is a nonzero element in F .
Similarly, expanding A(i
1
,...,i
t+1
; j
1
,...,j
t+1
; z)bythe(t + 1)-th col-
umn, we can prove that d
j
1
,...,j
r
is a nonzero element in F .
Lemma 4.4.4. For any i, 1 i r, we have a
1
+ ···+ a
i
= b
1
+ ···+ b
i
.
Proof. Consider the (1,...,i; j
1
,...,j
i
) minor of D
b
¯
M(z)D
g
, j
i
r. Notic-
ing the shape of matrices, this minor is equal to z
b
1
+···+b
i
¯
M(1,...,i; j
1
,...,j
i
;
z) g
j
1
(z) ...g
j
i
(z). Consider the set
S = {
¯
M(1,...,i; j
1
,...,j
i
; z), 1 j
1
< ···<j
i
r}.
Denote the greatest common divisor of polynomials in S by d(z). From
Lemma 4.4.3, d(z) is a nonzero constant. By ϕ
1,...,i
(z) we denote the greatest
common divisor of all (1,...,i; j
1
,...,j
i
)minorsofD
b
¯
M(z)D
g
for 1 j
1
<
···<j
i
r. It follows that
ϕ
1,...,i
(z)=z
b
1
+···+b
i
ϕ
1,...,i
(z),
for some ϕ
1,...,i
with ϕ
1,...,i
(0) =0.
On the other hand, for any 1 k
1
< ···<k
i
m and 1 j
1
< ···<
j
i
n, k
i
>ror j
i
>r,the(k
1
,...,k
i
; j
1
,...,j
i
) minor of D
b
¯
M(z)D
g
is 0. For any 1 k
1
< ··· <k
i
r and 1 j
1
< ··· <j
i
r,the
(k
1
,...,k
i
; j
1
,...,j
i
) minor of D
b
¯
M(z)D
g
has a factor z
b
k
1
+···+b
k
i
. Clearly,
b
k
1
+ ···+ b
k
i
b
1
+ ···+ b
i
holds. Thus the multiplicity of z in the i-order
determinant factor of D
b
¯
M(z)D
g
is b
1
+ ···+ b
i
. Notice that the determinant
138 4. Relations Between Transformations
factors of D
af
and of D
b
¯
M(z)D
g
are the same. Since the i-order determinant
factor of D
af
is z
a
1
+···+a
i
f
1
(z) ...f
i
(z)andf
j
(0) =0foranyj,1 j i,
we have z
a
1
+···+a
i
= z
b
1
+···+b
i
.
Lemma 4.4.5. For any i, 1 i r, we have f
1
(z) ...f
i
(z)=g
1
(z) ...g
i
(z).
Proof. Similar to the discussion in the proof of Lemma 4.4.4, the (j
1
, ...,
j
i
;1,..., i) minor of D
b
¯
M(z)D
g
equals z
b
j
1
+···+b
j
i
¯
M(j
1
,...,j
i
;1,...,i; z)
g
1
(z) ...g
i
(z)ifj
i
r. Consider the set
S
= {
¯
M(j
1
,...,j
i
;1,...,i; z), 1 j
1
< ···<j
i
r},
and denote the greatest common divisor of polynomials in S
by d
(z). From
Lemma 4.4.3, d
(z) is a nonzero constant. By ψ
1,...,i
(z) we denote the greatest
common divisor of all (j
1
,...,j
i
;1,...,i)minorsofD
b
¯
M(z)D
g
for 1 j
1
< ···
<j
i
r. It follows that
ψ
1,...,i
(z)=z
b
g
1
(z) ...g
i
(z)
for some nonnegative integer b.
On the other hand, for any 1 k
1
< ···<k
i
n and 1 j
1
< ···<
j
i
m, k
i
>ror j
i
>r,the(j
1
,...,j
i
; k
1
,...,k
i
) minor of D
b
¯
M(z)D
g
is 0. For any 1 k
1
< ··· <k
i
r and 1 j
1
< ··· <j
i
r,the
(j
1
,...,j
i
; k
1
,...,k
i
) minor of D
b
¯
M(z)D
g
has a factor g
k
1
(z) ...g
k
i
(z)which
has the factor g
1
(z) ...g
i
(z). Thus the non z factor in the i-order determinant
factor of D
b
¯
M(z)D
g
is g
1
(z) ...g
i
(z). Notice that the determinant factors of
D
af
and of D
b
¯
M(z)D
g
are the same. Since the i-order determinant factor of
D
af
is z
a
1
+···+a
i
f
1
(z) ...f
i
(z)andf
j
(0) =0foranyj,1 j i,wehave
f
1
(z) ...f
i
(z)=g
1
(z) ...g
i
(z).
Lemma 4.4.6. a
j
= b
j
and f
j
(z)=g
j
(z) for j =1,...,r.
Proof. From Lemmas 4.4.4 and 4.4.5.
Theorem 4.4.2. Let DIA
m,n
(z
a
1
f
1
(z),...,z
a
r
f
r
(z), 0,...,0) be the canon-
ical diagonal form of C
0
(z) ∈ M
m,n
(F [z]), where f
j
(0) =0,j=1,...,r.
Let (4.40) be a terminating and elementary R
a
R
b
transformation sequence,
and
¯
Q(z) the first r rows of C
t
(z).
(a) There exists
¯
P (z) ∈ GL
m
(F [z]) such that degrees of elements in
columns r
k
+1 to r
k+1
of
¯
P (z) are at most t − k − 1 for k =0, 1,...,t− 1,
and
C
0
(z)=
¯
P (z)DIA
m,r
(z
a
1
,...,z
a
r
)
¯
Q(z),
where r
0
=0,r
i
= r
i
,i=1,...,t− 1, and r
t
= m.
(b) DIA
r,n
(f
1
(z),...,f
r
(z)) is the canonical diagonal form of
¯
Q(z).
Proof. (a) From Corollaries 4.4.1 and 4.4.2, and Lemma 4.4.6.
(b) From Lemma 4.4.6 and Corollary 4.4.2.
4.4 Canonical Diagonal Matrix Polynomial 139
4.4.3 Relations of Right-Parts
From now on, we denote
D(z)=DIA
r,r
(z
a
1
,...,z
a
r
)
with 0 a
1
··· a
r
= t − 1. Let m
i
=maxj [∃k(1 k r & a
k
=
a
k+1
= ···= a
k+j−1
= i − 1)], i =1,...,t.Then
D(z)=DIA
r,r
(E
m
1
,zE
m
2
,...,z
t−1
E
m
t
).
Lemma 4.4.7. For any L(z) ∈ M
r,r
(F [z]),
¯
Q(z), Q
∗
(z) ∈ M
r,n
(F [z]),as-
sume that
L(z)D(z)Q
∗
(z)=D(z)
¯
Q(z) (4.46)
and Q
∗
(0) is row independent. If L(z)=L
0
+ zL
1
+ z
2
L
2
+ ···+ z
t−1
L
t−1
+
z
t
L
t
(z) and for any h, 0 h<t, L
h
is partitioned into blocks L
h
=
[L
hij
]
1i,jt
with m
i
× m
j
L
hij
,thenL
hij
=0whenever i − j>h.
Proof. Denote D(z)
¯
Q(z)=A
0
+ zA
1
+ z
2
A
2
+ ···+ z
t−1
A
t−1
+ z
t
A
t
(z)
and D(z)Q
∗
(z)=A
∗
0
+ zA
∗
1
+ z
2
A
∗
2
+ ···+ z
t−1
A
∗
t−1
+ z
t
A
∗
t
(z). For any k,
0 k<t, partition A
k
and A
∗
k
into t blocks
A
k
=
⎡
⎢
⎣
A
1,k+1
.
.
.
A
t,k+1
⎤
⎥
⎦
,A
∗
k
=
⎡
⎢
⎣
A
∗
1,k+1
.
.
.
A
∗
t,k+1
⎤
⎥
⎦
,
where A
i,k+1
and A
∗
i,k+1
have m
i
rows, i =1,...,t.SinceD(z)=DIA
r,r
(E
m
1
, zE
m
2
, ..., z
t−1
E
m
t
), we have A
ij
= A
∗
ij
=0foranyi, j,1 j<i t.
Since Q
∗
(0) is row independent, rows of A
∗
11
, ..., A
∗
tt
are linearly independent.
For any k,0 k<t, we prove, by induction on k, the proposition P (k):
L
hij
=0ift i j + h +1, 1 j k − h +1 and 0 h k. Basis : k =0.
Comparing constant terms in two sides of (4.46), we have
L
0
⎡
⎢
⎢
⎢
⎣
A
∗
11
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
A
11
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
.
It follows immediately that
⎡
⎢
⎣
L
021
.
.
.
L
0t1
⎤
⎥
⎦
A
∗
11
=0.
140 4. Relations Between Transformations
Noticing that A
∗
11
is row independent, we have L
0i1
=0foranyi,2 i t.
Thus P (0) holds. Induction step : Suppose that P (k − 1) holds and k<t.
That is, L
hij
=0fort i j + h +1, 1 j k − h and 0 h k − 1.
Comparing coefficients of z
k
in two sides of (4.46), we have
L
k
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
11
0
0
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ L
k−1
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
12
A
∗
22
0
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ ···+ L
1
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
1k
.
.
.
A
∗
kk
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ L
0
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
1,k+1
.
.
.
A
∗
k+1,k+1
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
1,k+1
.
.
.
A
k+1,k+1
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
It follows immediately that
⎡
⎢
⎢
⎢
⎣
A
k+1,k+1
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
= L
(k)
k
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
11
0
0
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ L
(k)
k−1
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
12
A
∗
22
0
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ ···+ L
(k)
1
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
1k
.
.
.
A
∗
kk
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ L
(k)
0
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
1,k+1
.
.
.
A
∗
k+1,k+1
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
where
L
(k)
h
=
⎡
⎢
⎢
⎣
L
h,k+1,1
... L
h,k+1,t
L
h,k+2,1
... L
h,k+2,t
... ... ...
L
ht1
... L
htt
⎤
⎥
⎥
⎦
,h=0, 1,...,k.
From the induction hypothesis, this yields
⎡
⎢
⎢
⎢
⎣
A
k+1,k+1
0
.
.
.
0
⎤
⎥
⎥
⎥
⎦
4.4 Canonical Diagonal Matrix Polynomial 141
= L
(k)
k
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
A
∗
11
0
0
0
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ L
(k)
k−1
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0
A
∗
22
0
0
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ ···+ L
(k)
1
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0
.
.
.
A
∗
kk
0
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
+ L
(k)
0
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0
.
.
.
0
A
∗
k+1,k+1
0
.
.
.
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
Since rows of A
∗
11
, ..., A
∗
k+1,k+1
are linear independent, we have L
h,i,k−h+1
=
0fort i k +2and 0 h k.FromP (k − 1), this yields P (k).
From P (t − 1), L
hij
=0forany0 h<tand i − j>h.
Lemma 4.4.8. For any L(z) ∈ M
r,r
(F [z]),
¯
Q(z), Q
∗
(z) ∈ M
r,n
(F [z]),
assume that (4.46) holds and Q
∗
(0) is row independent. Then there exists
R(z) ∈ M
r,r
(F [z]) such that
¯
Q(z)=R(z)Q
∗
(z).
Proof. Denote L(z)=L
0
+zL
1
+z
2
L
2
+···+z
t−1
L
t−1
+z
t
L
t
(z). Partition
L
k
into blocks (L
kij
)
1i,jt
with m
i
× m
j
L
kij
, k =0, 1,...,t− 1. Partition
z
k
L
k
D(z)intoblocks(L
kij
(z))
1i,jt
with m
i
×m
j
L
kij
(z), k =0, 1,...,t−1.
From Lemma 4.4.7, it is easy to see that
L
kij
(z)=
z
k+j−1
L
kij
, if i − j k,
0, otherwise.
It follows that for any k,0 k t − 1,
z
k
L
k
D(z)=D(z)R
k
(z),
where
R
k
(z)=[R
kij
(z)]
1i,jt
,
R
kij
(z)=
z
k+j−i
L
kij
, if i − j k,
0, otherwise.
Clearly, there exists a matrix polynomial R
t
(z) such that
z
t
L
t
(z)D(z)=D(z)R
t
(z).
Let
R(z)=
t−1
k=0
R
k
(z)+R
t
(z).
142 4. Relations Between Transformations
We then have
L(z)D(z)=D(z)R(z).
Using (4.46), this yields
D(z)R(z)Q
∗
(z)=D(z)
¯
Q(z).
It follows that R(z)Q
∗
(z)=
¯
Q(z).
Lemma 4.4.9. For any R(z),R
(z) ∈ M
r,r
(F [z]) and
¯
Q(z),Q
∗
(z) ∈
M
r,n
(F [z]),if
Q
∗
(z)=R(z)
¯
Q(z),
¯
Q(z)=R
(z)Q
∗
(z) (4.47)
hold and
¯
Q(0) or Q
∗
(0) are row independent, then
R
(z)R(z)=R(z)R
(z)=E
r
,
therefore, R(z) and R
(z) are invertible.
Proof. Suppose that
¯
Q(0) is row independent. From (4.47), we have
¯
Q(z)=R
(z)R(z)
¯
Q(z).
Let T (z)=E
r
− R
(z)R(z). Denote T (z)=T
0
+ zT
1
+ ···+ z
t
T
t
.Thenwe
have
(T
0
+ zT
1
+ ···+ z
t
T
t
)
¯
Q(z)=0. (4.48)
We prove T
i
=0foranyi,0 i t by induction on i. Denote
¯
Q(z)=
Q
0
+ zQ
1
+ ···+ z
s
Q
s
. In the case of i = 0, from (4.48), we have T
0
Q
0
=0.
Since Q
0
=
¯
Q(0) is row independent, we obtain T
0
= 0. Suppose that we
have proven T
j
=0for0 j i − 1 t − 1. Using (4.48), we have T
i
Q
0
=0.
Since Q
0
is row independent, we obtain T
i
= 0. We conclude T (z)=0.It
immediately follows that R
(z)R(z)=E
r
. Therefore, R(z)R
(z)=E
r
.
The proof is similar in the case where Q
∗
(0) is row independent.
For any C(z)∈M
m,n
(F [z]) with rank r, P (z)∈GL
m
(F [z]) and Q(z)∈
GL
n
(F [z]), if P
−1
(z) C(z) Q
−1
(z) is the canonical diagonal form of C(z),
say DIA
m,n
(z
a
1
f
1
(z), ..., z
a
r
f
r
(z), 0, ..., 0), with f
j
(0) =0,j =1,...,r,
DIA
r,n
(f
1
(z), ..., f
r
(z)) Q(z) is called a right-part of C(z).
Notice that the constant term of a right-part of C(z) is row independent.
Theorem 4.4.3. Given C
0
(z) in M
m,n
(F [z]) with rank r, assume that
Q
∗
(z) is a right-part of C
0
(z) and DIA
m,n
(z
a
1
f
1
(z),...,z
a
r
f
r
(z), 0,...,0) is
the canonical diagonal form of C
0
(z), where 0 a
1
··· a
r
,f
j
(z) | f
j+1
(z)
for j =1,...,r− 1, and f
j
(0) =0for j =1,...,r.Let(4.40), i.e.,
C
k
(z)
R
a
[P
k
]
−→ C
k
(z),C
k
(z)
R
b
[r
k+1
]
−→ C
k+1
(z),k=0, 1,...,t− 1