LINEAR ALGEBRA
AND ITS
APPLICATIONS
ELSEVIER Linear Algebra and its Applications 277 (1998) 253 269
On the number of invariant polynomials of
the product of matrices with prescribed
similarity classes
Zhang Yu Lin 1
Departamento de Matem{tlica, Universidade de Coirnbra, 3000 Co#~Thra, Portugal
Received 20 September 1995; accepted 30 September 1997
Submitted by G. de Oliveira
Abstract
We study the possibilities for the number of nontrivial invariant polynomials of the
product of two nonsingular matrices, with prescribed similarity classes, over an algebra-
ically closed field. © 1998 Elsevier Science Inc. All rights reserved.
1. Introduction
Let F be an algebraical ly closed field. For A E F ..... , denote by i (A) the num-
ber of nontr ivial invariant polynomials of A.
In this paper, we study the range of i (XAX I YBY i), when A and B are given
n × n nonsingular matrices over F and X, Y run over the set of nonsingular ma-
trices over F.
Define
R(A) = minrank(A + )J,,),
2~F
where/, , is the n × n identity matrix. In [1], it was proved that
i (A) -- n - R(A) .
Supported by the Fundaca60riente. On leave from Northwest University, Xian, 710069,
People's Republic of China.
0024-3795/98/$19.00 © 1998 Elsevier Science Inc. All rights reserved.
PII: S0024-3795(97) 1 0064-7
254 Z~ E Lin / Linear Algebra and its Applications 277 (1998) 253-269
Thus the study of the range of i(A'B') is equivalent o the study of the range of
R(A'B') with A' and B' similar to A and B, respectively. In this paper, instead of
i(A'B'), we prefer to consider R(AIB').
I fX and Y are n-square invertible matrices over F, then XAX t YBY 1 is sim-
ilar to (y - IX )A(X- I Y)B and to A(X -j Y)B(Y IX), so our problem is equivalent
to studying the range of i(A'B) or i(AB'), with A' and B' similar to A and B, re-
spectively.
Since a square matrix is similar to its transpose, the problem is also equivalent
to studying the range of i(B'A'), with A' and B' similar to A and B, respectively.
For any polynomial f (x ) over F, we denote by d( f ) the degree o f f (x ) . Given
two polynomials f (x ) and g(x), we write f (x ) I g(x) whenever f (x ) divides g(x).
Let cq (x), c~2(x),..., ~n(x) and fli (x), f l2(x),. . . , ft,(x) be the invariant polyno-
mials of A and B, respectively, and let 71 (x, 2), 72(x, 2) , . . . , 7,(x, 2) be the invari-
ant polynomials of 2B -~ . We assume that the invariant polynomials are always
monic and have been ordered so that each one divides the following of its group.
It is easy to see that if fls(x) = (x - bi) (~ (x - b2) ~2... (x - bp) '~, then
E/ ¢ , ) "
Let r (= i(A)) be the number of invariant polynomials of A which are different
from 1. In the same manner, let s := i(B). This means that cq(x) . . . . .
~,_r(x) = 1, and ~, ,.+l(x) has degree at least one. Similarly, ill(x) . . . . .
fl,_~(x) = 1 and/7, ~+l(x) has degree at least one.
Given a monic polynomial f (x ) = x k - akx k I . . . . . a2x - al with degree
k >i 1, we denote by CO <') and C'( f ) the companion matrices of f (x ) , defined by
C(f ) = [e2,e3,...,ek,a] and C'(f) = [al, e, , . . . ,ek_,] ,
where es is the ith column of the k-identity matrix, i E { 1 , . . . , k} and
a=[a l ,a2 , . . . ,ak] t, d=[a~- ,a t . _ l , . . . , a i ] t,
where the superscript " t" means transpose.
Let us define f (x ) := ei+,, ,(x), and gj(x) := fls+,_,(x) for i = 1 , . . . , r and
j = 1 , . . . , s, and let hs(x, 2), i = 1 , . . . , s be the nontrivial invariant polynomials
of 2B -1 .
We take Ks = C( f ) , i= 1 , . . . , r , L i = C'(gj), j= 1 , . . . , s , and define
K = K~ ® • • • • Kr and L = L~ O • • • • L,. The matrices K and L are respectively
similar to A and B.
We say that the pair (A, B) is spectrally complete for the product if for any n-
tuple (21, . . . , 2,) of elements of F satisfying 2~ .. . Jo, = det(AB), there exist ma-
trices A' and B' similar to A and B, respectively, such that A'B' has eigenvalues
(2i , . . •, ,~,).
In [2], Silva characterized all such pairs when F has at least four elements.
The following is the corresponding result when F is algebraically closed.
z. L Zhang I Linear Algebra nd its Applieations 277 (1998) 253~69 255
Theorem 1 [2]. Let A and B be n x n nonsingular matrices, over an algebraically
closed field, with n >~ 2. Then (A,B) is spectrally complete for the product if and
only if i(A) 4- i(B) <~ n and at least one of the following conditions is satisfied."
1. n=2,
2. at least one oJ'the nontrivial invariant polynomials oJ'A or B has degree differ-
ent from two.
The following theorem, proved in [3] will be used in the sequel.
Define
R(A, B) = min {rank(A - cI,,) + rank(B - cl,,)}.
Theorem 2 [3]. Let A and B be n × n matrices over an algebraically closed field
and t c {0, l , . . . ,n} . There exist matrices A r and B' similar to A and B,
respectively, such that
rank(A' - B') : t
if and only if the following conditions are satisfied."
~i(x)ifli+,(x), fli(x)loci+,(x) for i G {1, . . . ,n - t} and t<~R(A,B).
(1)
I f condition (1) is satisfied, we shall say (A, B) is a t-pair. It is easy to check
that the set of integers t E {0, 1 . . . . , n - 1 } for which there exists )o E F, such that
~i(x) lTi+~(x ,,~), 7i(x,2) l~i+,(x), i : 1 . . . . ,n - t (2)
is not empty. So let to be the min imum of this set.
Remark 1. Clearly, to ~> JR(A) - R(B)] and R(A)+ R(B)<<. R(A, 2B-l) .
2. Main result
We are going to prove the following theorem, which is our main result.
Theorem 3. For any n x n nonsingular matrices, A and B, over an algebraically
closed field F, there exist A' and B' similar to A and B, respectively, such that
R(A'B') = t if and only if
to<~t<~ min{n - 1,R(A) +R(B)}. (3)
Lemma 1 (Necessity). For any n x n nonsingular matrices A and B, over an
algebraically closed field F, we have
to <~ R(AB) <<. min{n - 1, R(A) + R(B)}. (4)
256 Z. E L#~ / Linear Algebra and its Applications 277 (1998) 253 269
Proof. For any nonzero 2, /4 C F, we have
R(AB) <~ rank(AB + 21)
= rank(A + 2B tI + [g - [~I)
~< rank(A- [g) + rank().B t + [~I)
= rank(A- [~ I )+ rank(B- l+~/ )
= rank(A- /~ l )+ rank(B+~l ) .
So R(AB) <~ R(A) + R(B).
Denoting by "~" the similarity relation and bearing Theorem 2 in mind, we
have
rain rain rank(AtB t - 2I) = rain rain rank(A t - )~B' i)
A~-A.B~B ),cF 4~A.Br~B )~F
= min rain rank(A t - ).B' 1)
2~F A~A,B~_B
- min min rank(A t - C) = t0.
).~F .4~0~,4,C~2B I
So
R(AB) = minrank(A - )~B ~) >~ to.
/.CI'
So (4) holds. []
To prove the sufficiency, we have to consider several cases.
Remark 2. I fA and B are nonsingular matrices, it is easy to see that there exist
A' and B t similar to A and B, respectively, such that R(A~B I) = 0 if and only ifA
and B I are similar, up to a scalar factor (i.e., there exists ~ E F, so that
B 1 ~ ~A).
Lemma 2. I f A and B are both n × n nonderogator)' matrices, over an
algebraically closed field, then Jot t E {1, . . . ,n 1}, there exist A' and B'
similar to A and B, respectively, such that R(AtB ') = t.
Proof. In this case, A and B are respectively similar to matrices of the forms
A '= ". a~ , B '= 0 ".
". 0 ". 1
1 Lb~ 0
Z. L. Zhang / Linear Algebra and its Applications 277 (1998) 253 269 257
LetX =d iag(c l , . . . , c t i , z o , . . . , zo , Zo) ,wherec , , i= 1 . . . . . t - I and) .o
are any nonzero e lements of F .
Let B" = XB'X t. Then we have
B" =
- * d t
where d, = c,/c,.~ I,
a'~
:¢
A'B" = "
"" dt I
• . / -o
0 A 0
0
1 . . . . . t -2 , andd~ i =c~ t/21' ~ !~ i~ Then
d~
dt 1
where a' I = albl)~o/cl.
Since F is an infinite field, we may choose the cTs and )~o, such that a'~, 2o and
the drs are pai rwise distinct• Then we have
R(A'B") ~ rank(A'B" - zol) -- t. [ ]
Lemma 3. f f A and B are n x n nonsingular matrices, over an algebraically closed
field, and either A or B is nonderogatory, then Jor an), t sati,ffi,ing
to <~ t <~ n - 1
there exist A' and B' similar to A and B, respectie~ely, such that
R(A'B') -- t.
Proof. Wi thout loss of general i ty, we may assume that A is nonderogatory .
Then ./i (x) is the only invar iant po lynomia l of A different f rom one. As before,
258 Z. K Lin / Linear Algebra and its Appfications 277 (1998) 253-269
let gl(x)[ . . .Fg~(x) be the nontrivial invariant polynomials of B, and
hi (x, 2)]- . . Ihs(x, 2) be the nontrivial invariant polynomials of 2B -1.
If s =n, then B is scalar. In this case, it is easy to see that
R(AB) = R(A) = n - 1, and the lemma is trivial.
Now we assume that A is nonderogatory and B is nonscalar. We consider
two cases.
Case 1: There does not exist 2o E F such that hi(x, 20)Ill(x). Then we have
to = R(A) - R(B) + 1 = s. Factorize fi (x) in the following way:
f i (x) = Ii (x)12(x) . . . l,(x), where the degree of li(x) is the same as the degree
of gi(x), i= l , . . . , s . For R(A) -R(B)+ l<~t<~n- 1, we do the following.
Let B' be the following normal form of B
B' =
[c(~) ]
c(~) =
...
c(~.)
ad{g ~ ) I
i 0 ".
" . 1. G2
az 0
b&(~) 1
O ".
"-. 1
h" 0
c,~(e.) l
0 "'.
e3 "'. 1
c2 0
Since B is nonsingular, al, b j , . . . , c I are nonzero. A is similar to the following
matrix
A' =
0
1 ". /~
".. 0 i
1 0 m 1
1 "'. m2
° ' - 0
1 md(~)
1 °. .
°.
0 111
1 "'. n2
"'. 0
1 nd(e,)
z. L. Zhang I Linear Algebra and its Applications 277 (1998) 253 269 259
where the diagonal blocks have Ii (x ) , /2 (x) , . . . , ! , (x) as characterist ic polyno-
mials.
, , - i , ., 2~, 20), where xi, i = 1, ., p and 2o are any Let X = d iag(x l , . . . , x~,, ~o . . . .
nonzero elements of F, p E {0 , . . . , n - 1}.
Then A'XB 'X ~ =
i ' .
! .
* Pd(n)
IP.I(/~ )÷ l
°
~P
*
i , .
o
ao
where the elements denoted with * are in the posit ions
d(g i )+ l , d (g i )+ l , k= 1 , . . . , s - 1.
i= l
The blank places are zero. Because A and B are nonsingular matrices, the , s
and the diagonal elements are all nonzero. The number of the *s equals
JR(A) - R(B) I , so we have at least ]R(A) - R(B)] columns which are l inearly in-
dependent. And we may choose the xls so that the y~s are distinct and also dif-
ferent from 20. We can see that rank(A 'XB 'X 1_ 21)>1 IR(A) -R(B) ] + 1+
p -- i, for 2 E F.
So we have
R(A 'XB 'X ') = ]R(A) - R(B)[ +1+ p- i ,
where
d(go) + . . . + d(gg) <~ p < d(go) + . . . + d(g,+, ) i - O . . . . . s - 1.
(Define d(go) = 0.)
Case 2: There exists ) .oEF such that h l (x , )~o) l J i (x ) . Then we have
to -- ]R(A) - R(B) I ---- s - 1. Factor ize f l (x) in the following way:
J](x) =- l', (x) l" (x) . . . l~(x), where
260 Z. E Lin / L inear A lgebra and its Appl ications 277 (1998) 253 269
r, (x) - - h, (x, ~,,) = (x - a , ) (x - a . ) . . . (x - ~,~,, ~)
and the degree of li(x ) is the same as the degree of hi, i = 1,. . . s.
Clearly, A is similar to
A I ~
a l 1
*°
a2
"°. 1
ad(hx}
, 1
, 0 "'.
: "'. 1
* 0 1
°°°
°°, 1
* 1
* 0 "'.
: "'. 1
* 0
- • . , [! where the diagonal blocks have l' I (x), l'~(x) . . . . (x) as characteristic polyno-
mials. The matrix 2o3 * is similar to a matrix of the following form:
~B'-1=
al 1
° ,
a2
"'° 1
ad{h~l
• 1
• 0 "°"
: ". 1
• 0
°,
, 1
* 0 "'°
: "'. 1
* 0
where the diagonal blocks have hj (x,)L0), h2(x, 20),... , hs(x, 20) as characteristic
polynomials. The inverse of B' ~ is in the form
Z. L. Zhang / Linear Algebra and its' Applications 277 /1998) 253-269 261
B I ~ ~O
1
"~1 t * *
et 2
!
r, q P'I )
0 *
1 "'.
"'. 0 *
1 ,
oo
0
1 ' o ,
•o
1 *
where the diagonal blocks have gt (x) . . . . , g,(x) as characteristic polynomials.
Then we have A'B'
,~0
oo ,
o°
,~o
,k
° .o "A"
t d z • . . . - where the .s are in the positions (y~,=, (gi), ~i~Id(g,)) , t 1, ,s 1. Since
,4 and B are nonsingular, the elements *'s are nonzero. This way we get to col-
umns which are linearly independent. So
262 Z. K Lin / Linear Algebra and its Applications 277 (1998) 253-269
R(A'ff) = min rank(A'B' - 21) = rank(A'B' - 20I) = to = IR(A) - R(B)I.
2cF
For R(A) -R (B) + 1 <<, t<~n- 1, we do the same as we did for Case 1. []
Proof of Theorem 3. Here we assume that A and B are both derogatory. I f one
of them is scalar, the theorem is trivial. Now suppose neither of A and B is
scalar or nonderogatory. The proof goes by induction on n. When n = l, 2, 3, 4,
it can be verified easily.
Suppose n ~> 5 and A and 2B i satisfy (2). From Theorem 2, there are A' and
B' similar to A and B, respectively, such that
rank(A'B' - 2/) = rank(A' - 2(B') 1) = t; then we have that
R(A ' - 1) t.
I f we have equality, the proof is complete. Now suppose R(A'- ;~
(B') l) ~< t - 1, then (A, £B 1) is (t - l)-pair.
Note that, i f t ~< n/2, equality always holds, otherwise there exists l* such that
R(A' - /~(B') -1 ) ~< t - 1. That means/~ is an eigenvalue of A'B' of algebraic mul-
tiplicity at least n - t + 1. Since 2 is an eigenvalue of A'B' of algebraic multiplic-
ity at least n - t, so (n - t + 1) + (n - t) ~< n, i.e., t >/(n + 1)/2, a contradiction.
Henceforth we consider only the case t ~> (n + 1)/2.
Without loss of generality, suppose that d(J]) >1 d(gt) = p with p < n. Let
L '~-L2@.. .®L~. I f d(g~) =d(J]), take K ' - - I£2®. . .OKr . (Bear in mind
the definition of Ki and Li.) I f d~fl) > d(gl) = p, K1 is similar to a matrix of
the form
N
, . .
0
0 1
0
M '
0
where N E F p×p. In this case, take K ~ = M•K2 q~... OKr. Since (A,2B -~) is
( t -1 ) -pa i r , it is not difficult to verify, in any case (K',2L '-1) is also a
(t - 1)-pair.
Case 1: Suppose that d(fl) ~> d(gl) -p ~> 2.
Without loss of generality, suppose that M and N are companion matrices,
and suppose N ¢ aLl 1. Consider the polynomial (b(y) ~- _y2 + (n + 2)y - 2n,
with coefficients in the field of real numbers. Its roots are 2 and n. Since
2 ~ 0. We also have r <~ nip and s <~ nip. Therefore
2n 1
R(K') +R(L') > 2n-2p- - -+ l =-~b(p)+n-p - 1 ~> n-p - 1.
P P
Z L. Zhang / Linear Algebra and its Applications 277 (1998) 253~69 263
So the max imum value t can be attained. On the other hand, from
t/> (n + 1)/2 we can get t - 1 >/IR(K') - R(L')].
Case 1.1: Suppose that n -p >~ t. By the induction assumption, there is
X E F (n-p)x(n-p) such that R(K 'XL 'X -1) = rank(K 'XL 'X -j - )d) = t - 1.
I f d(gl) = d( f l ) , then, by Lemma 2, there is a nonsingular matrix Y E F p×p
such that
R(K1YL1Y i) = rank(K1YL1Y i _ M) = 1.
Then
R(K(Y ®X)L(Y ®X) - I) = rank(K(Y ®X)L(Y ®X) ' - )d) = t.
Now suppose that d(f l ) > d(gl). I f the column [., 0 , . . . , 0] t E F (n-p)x I is a lin-
ear combinat ion of the columns of K'XL 'X -~ , then, by Lemma 2, there is a non-
singular matrix Y E F p×p such that R(NYLI y- l ) = rank(NYLl y- l -21) = 1; if
not, by Lemma 2 again, there is Y E F p×p such that
= 21p I "
In any case,
R(/((r x)L(r
Case 1.2: Suppose
by the induction
®X) - ' ) = rank(K(Y ® X)L( Y O X) - ' - 21) = t.
that n -p < t < n - 1. Since n -p - 1 ~ d(gl). I f the column [* ,0, . . . ,0] t E F I"-pl×l is a
linear combinat ion of the columns of K'XL 'X -~ , then, by lemma 2, there exists
a nonsingular matrix Y E F p×p such that
R(NYL IY - l ) = rank(NYL1Y-' - 2/) = t - (n -p - 1).
Then
R(K(Y ® X)L ( Y ®X) -1) = rank(K(Y ® X)L( Y ® X) -I - )d) = t.
264 Z.Y. Lin / Linear Algebra amt its Applications 277 (1998) 253 269
I f not, by Lemma 2 again, there is Y E F p×f' such that
)d,, i i "
We have R(NYL~Y l) = t - (17 -p - 1). In any case,
R(K(Y@X)L(Y@X) ' )=rank(K(Y@X)L(Y@X) ' -21)=t .
Case 1.3: Suppose that t = n - 1. Because p ~> 2, we have R(A) + R(B) >~ n,
that is i(A) + i(B) <~ n. Assume one of the nontrivial invariant polynomials of A
and B is not of degree 2. By Theorem 1, (A, B) is spectral ly complete for the
product. We may choose 21s such that all o f them are distinct. Then we have
R(A'B') = n - 1.
Assume all the nontr ivial invariant polynomials of A and B are of degree 2.
Without loss of generality, suppose
A =
0 1
a l (12
0
¢/I
and B =
b~
Let X = diag(cl, 1, c> 1,.. , c / /-~/, 1), where the cls are nonzero elements of F
chosen so that the diagonal elements of the matrix
cl 0
:# a l h~l
Cl
XAX I B =
* a l h l
c.
are all distinct. Then we have R(XAX J B) = n - 1.
Case 2: Suppose that d(J]) ~> d(gl) -- 1.
Case 2.1 : d([1) = d(gl) = 1. In this case, A' = a • K' and B' = b (~ L'. Since
R(A) = R(K') and R(B) = R(L'), we have ]R(K') - R(L')] <~ t <~ R(K') + R(L').
Now let IR(K') - R(L')I ~< t ~< n - 2. By the induction assumption there exists
X, such that
R(K'XL 'X ~) = rank(K 'XL 'X -~ -ab l ) - t.
Consequently, R(A'(I OX)B'(1 ~X) ~) = t.
Z. L. Zhang / Liuear Algebra and its Application,s 277 (1998) 253 269 265
Now assume t = ii - I.
R(A) + R(B) >~ n, that means i(A) + i(B) <<. n. According to Theorem 1, the
pair (A ,B) is spectral ly complete for the product. Then we can get
R(A'B') = n - I .
R(A) + R(B) = n- I . F rom R(A) - R(K'), R(B) = R(L'), we have
R(K ' ) + R(L') = n- 1. Again by Theorem 1, (K ' ,L ' ) is spectrally complete
for the product. We may choose ).l . . . . . )~,,_~ C F - {ab} to be distinct and
also conclude that R(A'B' ) = n - 1.
Case 2.2: d( / i ) = q > d(gl ) = 1.
Let w be the number of l inear invariant polynomials of B, and u - d(g,,.~ ~ ).
Note that 2 ~< q ~~ (n - q) - (n - q ) /q , R(L") >~ (n - q - w)
- (n - q - w) /q , we have R(K' ) + R(L") >1 2n - 2q + 2 -2n /q - (q - l )w /q >1
2n - 2q+2 - 2n/q - (q - 1) (q - 1) /q. Notice the fact that the quadrat ic ex-
pression 2q 2 - (n + 5)q + 2n + 1 is nonposit ive for 2 ~ q <~ n/2. We have that
R(K' ) +R(L" )>~ n-q 1, and we can verify that (K' . f iL" 1) is also a
(t - l)-pair.
We are going to use the same technique as we used in Case 1.
Suppose that n-q >~ t. By the induction assumption, there is
X ~ F ('' ,~i~(,, /~ such that R(K 'XL"X ~) = rank(K 'XL"X i _ ill) -- t - 1. Then.
by Lemma 2, there is a nonsingular matrix Y ~ F '/~'~ such that
R(C( J ] )YC(g , ,+] )Y ~) rank(C( j i )YC(g , , _~)Y ] - )d) = 1.
Then
R((C(.[]) + K ' ) (Y + X) (C(g , ,~ , ) + L" ) (Y ~!~ X) ')
= rank(A ' (Y+X)B ' (Y+X) ~ - )d) = t.
Suppose that n - q < t < n - 1. Since R(K ' ) + R(L") ~> n - q - 1, by the in-
duction assumption there exists a nonsingular matrix X ¢ F ~'' '~):~¢" 'f> such that
R(K 'XL"X i) = rank(K 'XL"X- i _ 21) = n q - 1.
Then, by Lemma 2, there exists a nonsingular matrix Y ~ F q'~q such that
R(C( . I ] )YC(g~, )Y ~) = rank(C( . l ) )YC(g , , , ] )Y ~ - )d) - t - (n - q - 1).
Then
R((C(.IL) L~ K')(Y +X)(C(g,,.. i )+ L")(Y, i X) )
= rank(A'(Y +X)B ' (Y ,??X) ~ - )d) = t.
266 Z Y Lin I Linear Algebra and its Applications 277 (1998) 253~69
Suppose that t = n - 1.
1. R(A) +R(B) >~ n, that is the pair (A,B) is spectrally complete for the prod-
uct.
2. R(A) + R(B) = n - 1. We prove this is impossible.
Note that r<~n/q and s~<(n-w) /2+w. Hence n+l =r+s~ 0, a contradiction
because q2 _ (3 + n)q + 2n < 0 for 2 <~ q <~ n/2.
(2). w < q < u.
Note that A and B are similar to
I C(g) o
A'=C( J i )OK 'andB '= 0 ... 0 1
Lit ,
0
respectively, where C(g)c F q×q. Assuming that u > n/2, then R(K')>>. n
-n /q - (q - 1), R(L") = n - w- q - 1. So R(K') + R(L') >>. 2n - w- 1
-q -n /q - (q - 1) ~>2n- (q - l ) -2q -n /q=2n-3q+l_n /q . Notice
the fact that the quadratic expression 2q 2 - (n + 2)q + n ~< 0 for 2 <<. q <~ n/2
and n ~> 4. We have that R(K') + R(L') ~> n - q - 1. It is also easy to check that
IR(K') -R (L ' ) ] ~< ]w+ 1 - 1] <~q- 1 ~~ 3 and u cannot be n/2 because, in this case, as B is nonderogatory, we will
have w=, /2 . So R(L") >~ (n -q) - (w+(n-w) /3 ) and R(K') >1(n -q)
- (n /q -1 ) . We have that R(K ' )+R(L" ) >~2n-2q+l -n /q - (2w+n) /3
>~ 2n- Zq + l - n /q - (2 (q -1) + n)/3 = Zn- Zq- (Zq 2 - 5q + nq + 3n)/3q.
Notice the fact that the quadratic expression 5q 2 - (8 + 2n)q + 3n~<0 for
2<~q<~n/3 and n~>4. We have that R(K ' )+R(L" ) ~>n-q-1 . When
n/3 < q<.n/2, we have r = 2, it is obvious R(K') +R(L ' ) ~> n- q - 1. So in
any case we have R(K ' )+R(L" ) ~>n-q-1 . On the other hand,
]R(K') - R(L")] <~ Iw + (n - w)/u - 11 <~ lu - 2 - (n - u - 2)/21 ~< (n - 1)/2,
the last inequality holds because 2 <<. u << n/2. So the induction assumption
holds for the pair (K', L').
Bear in mind that a square matrix is similar to its transpose, so we may
change the order of A' and B'. Now we reduced our problem to the same type
as Case 1, and we may do the same analysis as we did before.
(3). w < q and u < q.
Note that A and B are similar to
c(f)
. . .
0
0 1
0
K t
and C(gw+l) OL",
Z. L. Zhang / Linear Algebra and its Applications 277 (1998) 253~69 267
respectively, where C( f ) E F ..... . In this case we have that
u />2, q>I3 , w~~(n-u) -n /3 andR(L ' )>~(n-u) -
(w + (n - u - w) /u ) >>, (n - u) - (n/u - 1 + (q - l )(u - 1)/u). We have
R(K ' )+R(L" ) >~2n-2u-n /3 - (n+(q- l ) (u -1 ) ) /u+l . Notice the fact
that the quadrat ic expression 3u 2 - (2n-3q+9)u+3n-3q+3~n-u- 1. When
n/3 < q <~n/2, we have r = 2, it is obvious R(K' ) +R(L ' ) >~ n- u - 1. So in
any case we have R(K ' )+R(L" )>1 n -u -1 . And we can verify that
(K ' , )Z ''-1 ) is also a ( t - 1)-pair.
Again we reduced our problem to the same form as Case 1, and we may do
the same analysis as we did before.
(4). q<~w.
In this case, A and B are similar to
A' -C~I i )~K ' and B'=xqOL" ,
respectively, where xq E F q×q is a scalar matrix. First suppose that
R(K') >~ R(L"). As
IR(A') - R(B')I ~ t <~ R(A') + R(B'),
we have
(q - 1) + R(K') - R(L") <~ t <~ (q - 1) + R(K') + R(L").
That means R(K') - R(L") <~ t - (q - 1) <~ R(K') + R(L"). Note that
t - (q - 1) ~< n - q - 1. By the induction assumption, there exists X such that
R(K 'XL"X J) = rank(K 'XL"X ~ - ) J) = t - (q - 1).
Then R( ( C(Jl ) @ K')(Iq ® X)(xq @ L")(lq @ X) ~ ) = t.
Second, suppose that R(B') > R(A'). That means R(L") > (q - 1)+ R(K') . I f
t - (q - 1) ~> R(L") - R(K' ) , then we may do the same as we did in the first
case. Now consider t - (q - 1) < R(L") - R(K') . As R(L") > R(A'), there must
be one diagonal block in L" whose order is greater or equal to the order of
C(f~). Moving it to the first d iagonal block we can get a matrix similar to B'
of the form
C(g) o
0 . . . 0 1
Ltt!
0
where C(g) ¢ F q×q.
We have R(L"') - R(K' ) = R(L") - R(K') - q. Because t/> ]R(A') - R(B')I =
R(L") - R(K') - (q - 1), by induction assumption there exists X such that
R(L" 'XK 'X ~) ~- rank(L" 'XK 'X -~ - ) J) = t, ~ R(L") - R(K') q.
268 z.Y. Lin / Linear Algebra and its Applications 277 (1998) 253~69
Then by Lemma 2, there exists Y such that
R(C(g)YC( / i )Y i) = rank(C(g)YC( / ] )Y ' - ),I) = t - t~.
Thus we have
R(A'B') t.
Third, suppose that R(A') /> R(B') = R(L") > R(K'). If t - (q - 1) /> R(L")
-R(K ' ) , then we may do the same as we did in the first case. Now consider
t - (q -1 ) ~R(A ' ) -R (B ' )=R(K ' )+(q - I ) R(L ' ) (q - 1 ) - z . As R(L ' )>R(K ' ) ,
there must be one diagonal block in L" whose order is greater or equal to
the order of C(/'i). Then we may get a matrix B', similar to B', of the form
.r : ~ C(g) 0
'~0 ... 0 1
L m
0
where C(g) EF :x: andR(x,~ :+C(g) )=z 1. (If there is a block in L" with
size z + 1, then let B"-.v~/~:~ > + C(g) ~ L".)
Since C(./]) is nonderogatory, by Lemma 3, there is Y ~ F ~l×q such that
R((x,~ : + C(g))YC(. / ])Y ~) - rank((xq - + C(,~))YC(,/])Y ' - 21)
- (q - 1 ) - ( z 1 )=q-z .
On the other hand, by the induction assumption, there is X ~ F ('~ "~(" '~! such
that
R(L"XK 'X ~)rank(L"XK'X i _ 21) -- t - (q - z).
So
R(A'B') t.
Assume that t = n - 1.
1. R(A) + R(B) >~ n, the pair (A,B) is spectrally complete for the product.
2. R(A)+R(B)=n- I , i.e., (q 1 )+R(K ' )+R(L ' ) ,1 -1 . Then
R(K ' ) + R(L" ) = ,, - 9.
That means the pair (K',L") is spectrally complete for the product. We may
choose distinct nonzero elements, ).~ . . . . . 2, ,~, different from the eigenvalues
of C(./])x,~ (we recall that x,~ is a q × q scalar matrix) and satisfying
2~ .. . 2,, q = det K'L". Then it is easy to conclude that R(A'B') n - 1. []
Z, L. Zhang / Linear Al:,,ehra and its Apldication,s 277 (19()8; 253 269 269
Acknowledgements
This paper is wr i t ten under the supervis ion of Professor G .N . de Ol iveira. 1
wou ld like to thank Professor E .M. Sti for his useful suggest ions and the refer-
ees for a very thorough and careful reading o f the original draft.
References
[1] G.N. de Oliveira, E.M. Sfi. J.A. Dias da Silva, On the eigenvalucs of the matrix ,4 ~ A'~.V ]
Linear and Multilinear Algebra 5 (1977) 119 128.
[2] F.C. Silva, The eigenvalues ofthe product of matrices with prescribed similarity classes. Linear
and Multilinear Algebra 34 (1993) 269 277.
[3] F.C. Silwl, The rank of the difference of matrices with prescribed similarity classes, Linear and
M ultilinear Algebra 24 (1988) 51 58.
[4] F.C. Silva, Spectrally complete pairs of matrices, Linear Algebra and Its Applications 108
(1988) 239 262.
[5] F.C. Silva, On the number of invariant polynomials of the matrix ,~,(qX i + B. Linear Algebra
and Its Applications 79 (1986) 1 21.
[6] Zhang Yu Lin. The range of i(XAX i + B) (preprint).
[7] F.C. Silwl, Wasin So, Possible number of invariant polynomials for the difference of two
similarity classes (preprint).