A Comparison of Two Proofs of Yamamoto?s Theorem Relating
Eigenvalue moduli and Singular Values of a Matrix
Except where reference is made to the work of others, the work described in this thesis
is my own or was done in collaboration with my advisory committee. This thesis
does not include proprietary or classified information.
Melinda Pell
Certificate of Approval:
Randall R. Holmes
Associate Professor
Mathematics
Tin-Yau Tam, Chair
Professor
Mathematics
Krystyna Kuperberg
Professor
Mathematics
Greg Harris
Associate Professor
Mathematics
Stephen L. McFarland
Dean
Graduate School
A Comparison of Two Proofs of Yamamoto?s Theorem Relating
Eigenvalue moduli and Singular Values of a Matrix
Melinda Pell
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
15 December, 2006
A Comparison of Two Proofs of Yamamoto?s Theorem Relating
Eigenvalue moduli and Singular Values of a Matrix
Melinda Pell
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at their
expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Melinda Pell, daughter of Lonnie and Lucinda Tilley, was born in Oceana, West
Virginia on December 20, 1971. Upon graduation from Oceana High School, Melinda
began college, attending Concord College in Athens, WV. After only a year of school-
ing she and her husband of two years relocated to Georgia. It was some time and a
state later when Melinda returned to her academic adventure in Florida by attending
Florida Community College at Jacksonville. This was also a brief visit in the world of
academia due to relocation of the family in 1994 to Phenix City, Alabama. In 1998, she
decided to return to her scholarly goals. She enrolled at Columbus State University in
Columbus, Georgia where she completed her B.S. (Math) in May, 2002. She began her
graduate study in the Department of Mathematics of Auburn University in August, 2002.
During the 2004-2005 year Melinda was a temporary instructor for the Department of
Mathematics of Columbus State University.
iv
Thesis Abstract
A Comparison of Two Proofs of Yamamoto?s Theorem Relating
Eigenvalue moduli and Singular Values of a Matrix
Melinda Pell
Master of Science, 15 December, 2006
(B.S., Columbus State University, 2002)
39 Typed Pages
Directed by Tin-Yau Tam
We examine two proofs of Yamamoto?s theorem regarding the asymptotic relation-
ship between singular values and eigenvalue moduli of a matrix. The first proof is by T.
Yamamoto in 1967 and makes use of compound matrices. The second is by R. Mathias
in 1990 through utilization of an interlacing theorem for singular values. We compare
the two proofs.
v
Acknowledgments
The author would like to thank Dr. Tin-Yau Tam for his never-ending patience and
excellent guidance throughout the course of this research, Carlos Almada for his generous
contribution of time and assistance. Without the support of her family this task would
have been unattainable, and it is with great sincerity that she sends gratitude out to
them. Her three children have been most patient and kind throughout this experience.
And most of all she would like to express her appreciation to her husband Tommy Pell
for his loving patience and support through the many difficult days and long endless
nights during the trials of this research.
vi
Style manual or journal used Transactions of the American Mathematical Society
(together with the style known as ?aums?). Bibliograpy follows van Leunen?s A Handbook
for Scholars.
Computer software used The document preparation package TEX (specifically
LATEX) together with the departmental style-file aums.sty.
vii
Table of Contents
1 Introduction 1
2 Notations and Theorems 3
3 Yamamoto?s original proof 16
4 Mathias? proof 22
5 Comparing Approaches 28
Bibliography 31
viii
Chapter 1
Introduction
In this thesis, we investigate two proofs of Yamamoto?s theorem which provides
the relationship between eigenvalue moduli and singular values of a square matrix in an
asymptotic way.
Tools such as singular value decomposition, compound matrices, interlacing inequal-
ities for eigenvalues and singular values, and Jordan form are briefly discussed. Some
treatment is provided for developing notions of norms and other features that are neces-
sary for completing the proofs. We denote by Cn?n the vector space of all n?n complex
matrices and Cn the vector space of complex n-tuples. The theorem of Yamamoto [9] is
stated below:
Theorem 1.1 (Yamamoto)
Let A ?Cn?n. Then
limp??[?i(Ap) ]1p = |?i(A)|, i = 1,2,...,n, (1.1)
where ?1(A) ????? ?n(A) ? 0 are the singular values of A and ?1(A),...,?n(A) are the
eigenvalues of A which are arranged in the non-increasing order |?1(A)|?????|?n(A)|
with respect to their moduli.
The case i = 1 of Theorem 1.1 is a special case of Gelfand?s Spectral Radius Theorem
(1941) which may take the following form.
1
Theorem 1.2 (Gelfand)
Let bardblAbardbl := maxbardblxbardbl=1bardblAxbardbl be a matrix norm induced by a vector norm bardbl?bardbl : Cn ? R
where A ?Cn?n. Then
limp??bardblApbardbl1p = ?(A), (1.2)
where ?(A) := |?1(A)| is the spectral radius of A.
We remark that Gelfand?s Theorem is also valid for Hilbert space bounded operators
but the proof requires more advanced tools [2].
In Chapter 2, we will present and briefly discuss some concepts, in order to aid the
reader and clarify any confusion. Then, in Chapter 3 we will focus on the original proof
by Yamamoto [9], and in Chapter 4 we will examine and discuss the more recent proof by
Mathias [3]. Once these proofs are each fully analyzed, a comparison of the two proofs
will be presented in Chapter 5.
We finally remark that very recently Yamamoto?s theorem is extended in the context
of semi-simple Lie group by Tam and Huang [7].
2
Chapter 2
Notations and Theorems
The eigenvalues of A ? Cn?n are the numbers ? such that Ax = ?x, for some
nonzero vector x ? Cn. The vector x is known as an eigenvector corresponding to the
eigenvalue ? for the matrix A. According to the Fundamental Theorem of Algebra, each
A ? Cn?n has n eigenvalues ?1(A),...,?n(A) ? C, counting multiplicities. We order
them in such a way to have
|?1(A)|?|?2(A)|???? ?|?n(A)|.
The spectral radius of A is the largest eigenvalue modulus and is denoted by
?(A) := |?1(A)|.
A matrix A ? Cn?n is said to be Hermitian if A? = A where A? is the complex
conjugate transpose of A. It is said to be positive semi-definite (p.s.d.) if it is Hermitian
and has nonnegative eigenvalues, and it is said to be positive definite (p.d.) if it is
Hermitian and has positive eigenvalues. A matrix U ? Cn?n is said to be unitary if it
satisfies the condition U? = U?1. A matrix A ? Cn?n is said to be nilpotent if Ap = 0
for some p ?N.
3
The singular values ?1(A) ? ?2(A) ? ... ? ?n(A) ? 0 of the matrix A ?Cn?n are
the square roots of the corresponding eigenvalues of the p.s.d. matrix A?A, i.e.,
?i(A) :=
radicalBig
?i(A?A), i = 1,...,n.
One can use AA? to define singular values: ?i(A) := radicalbig?i(AA?) because AB and BA
have the same spectrum.
A norm on a vector space X is a map bardbl ? bardbl : X ? R satisfying the following
properties
1. bardblxbardbl? 0 for all x ? X and bardblxbardbl = 0 if and only if x = 0,
2. (Triangle inequality) bardblx+ybardbl?bardblxbardbl+bardblybardbl, x,y ? X,
3. bardbl?xbardbl = |?|bardblxbardbl for all scalars ? and x ? X.
Example 2.1 Let X = Cn and x ?Cn.
The 2-norm is defined as
bardblxbardbl2 = ?x?x = (
nsummationdisplay
i=1
|xi|2)1/2
and bardbl?bardbl2 is a special case of the p-norms
bardblxbardblp =
parenleftBigg nsummationdisplay
i=1
|xi|p
parenrightBigg1/p
, 1 ? p < ?.
For example bardblxbardbl1 =summationtextni=1|xi| and bardblxbardbl? = max1?i?n|xi|.
Let bardbl?bardbl be a vector norm on Cn. The map bardbl?bardbl : Cn?n ?R:
bardblAbardbl = maxxnegationslash=0bardblAxbardblbardblxbardbl = maxbardblxbardbl=1bardblAxbardbl
4
is called the induced matrix norm on Cn?n (induced by the vector norm bardbl?bardbl). It is easy
to verify that an induced matrix norm is a norm and satisfies
1. bardblAxbardbl?bardblAbardblbardblxbardbl for all A ?Cn?n, x ?Cn.
2. (submultiplicative) bardblABbardbl?bardblAbardblbardblBbardbl, for all A,B ?Cn?n.
3. bardblIbardbl = 1.
Example 2.2 Let A ?Cn?n. Then
1. bardblAbardblp = maxxnegationslash=0bardblAxbardblpbardblxbardblp , 1 ? p < ?.
2. bardblAbardbl1 = max1?j?nsummationtextni=1|aij| (column sum norm).
3. bardblAbardbl? = max1?i?nsummationtextnj=1|aij| (row sum norm) and thus bardblAbardbl1 = bardblA?bardbl?.
4. bardblAbardbl2 is the square root of the largest eigenvalue of A?A (or AA?). It is also called
the largest singular value.
The induced matrix norm bardbl?bardbl2 is a very important norm on Cn?n and is called the
spectral norm. It is well-known [4] that for all A ?Cn?n,
1. bardblA?bardbl2 = bardblAbardbl2, and
2. bardblA?Abardbl2 = bardblAbardbl22.
We will specify which norm we use if there is a need.
Determinants are used often throughout this paper, and it is worthwhile to make
note of the properties they possess. Some useful properties of determinants [1] are:
1. A matrix A ? Cn?n is singular if and only if detA = 0. If A is nonsinuglar, then
det(A?1) = (detA)?1.
5
2. For an upper triangular matrix A the determinant is the product of the diago-
nal entries of A, detA = producttextni=1 aii. This property holds true for lower triangular
matrices as well. A particular case is the identity matrix I, for which detI = 1.
3. The determinant of the product of two matrices A and B is equal to the product
of the determinant of A and the determinant of B, det(AB) = detAdetB.
4. If U ?Cn?n is unitary, then detU = 1.
A Jordan block [4] Jk(?) is a k?k upper triangular matrix of the form
Jk(?) =
?
??
??
??
??
?
? 1
? ...
... 1
?
?
??
??
??
??
?
?Ck?k
which can be expressed as Jk = ?Ik +Nk where Ik is the k?k identity matrix and
Nk =
?
??
??
??
??
?
0 1
0 ...
... 1
0
?
??
??
??
??
?
?Ck?k.
A Jordan matrix J ?Cn?n is a direct sum of Jordan blocks and has the form:
J =
?
??
??
??
??
??
?
Jn1(?1)
Jn2(?2)
...
Jnk(?k)
?
??
??
??
??
??
?
?Cn?n,
where n1 +n2 +???+nk = n. Neither the values ?i and the orders ni need be distinct.
6
Theorem 2.3 (Jordan Canonical Form Theorem)
Let A ?Cn?n. Then there exists a nonsingular matrix M ?Cn?n such that
M?1AM = J,
where J is a Jordan matrix.
The matrix J in the above theorem is called a Jordan form of A and is unique up to
permutation of the Jordan blocks.
We now prove the following classical result which gives a necessary and sufficient
condition for the powers of a given matrix to tend to zero. It will be used in the proof
of Gelfand?s result.
Theorem 2.4 Let B ?Cn?n. Then limp??Bp = 0 if and only if ?(B) < 1.
Proof: (?) Suppose limp??Bp = 0. Let ? be any eigenvalue of B, that is, there exists
a nonzero x ?Cn such that Bx = ?x. Then for any p ?N,
Bpx = ?px.
Now Bp ? 0 implies that ?px ? 0 and thus ?p ? 0. So |?| < 1 for all eigenvalues ? of
B and hence ?(B) < 1.
(?) Let B ?Cn?n such that ?(B) < 1. Let
J :=
?
??
??
??
??
?
J1
J2
...
Jk
?
??
??
??
??
?
7
be a Jordan form of B. Then by Theorem 2.3 there is a nonsingular matrix M ? Cn?n
such that B = MJM?1. Each block Ji ? Cni?ni (i = 1,...,k) can be written as the
sum of ?I for some eigenvalue ? of B and a nilpotent matrix N, namely,
N =
?
??
??
??
??
?
0 1
0 1
... 1
0
?
??
??
??
??
?
?Cni?ni.
Taking the pth power of B yields Bp = MJpM?1 where
Jp =
?
??
??
??
??
?
Jp1
Jp2
...
Jpk
?
??
??
??
??
?
.
To show that Bp ? 0 it suffices to show Jpi ? 0 as p ??. Since each Ji is of the form
?I +N, we need to show that limp??(?I +N)p = 0 under the assumption that |?| < 1.
Now the binomial expansion gives
(?I +N)p = ?p +
parenleftBigg
p
1
parenrightBigg
?p?1N +
parenleftBigg
p
2
parenrightBigg
?p?2N2 +???+
parenleftBigg
p
p?1
parenrightBigg
?1Np?1 +Np.
Since N is nilpotent, Nm = 0 for some m ?N. Then for p ? m we have
(?I +N)p = ?p +
parenleftBigg
p
1
parenrightBigg
?p?1N +
parenleftBigg
p
2
parenrightBigg
?p?2N2 +???+
parenleftBigg
p
m?1
parenrightBigg
?p?m+1Nm?1.
It is sufficient to show that for each j = 1,...,m?1,
limp??
parenleftBigg
p
j
parenrightBigg
?p?j = 0
8
where |?| < 1. Now
limp?? |
parenleftbigp
j
parenrightbig?p?j|
|parenleftbigp?1j parenrightbig?p?1?j| = limp??
vextendsinglevextendsingle
vextendsinglevextendsingle p
p?j?
vextendsinglevextendsingle
vextendsinglevextendsingle= |?| lim
p??
vextendsinglevextendsingle
vextendsinglevextendsingle p
p?j
vextendsinglevextendsingle
vextendsinglevextendsingle= |?| < 1
for any j = 0,...,m? 1. The ratio test implies limp??parenleftbigpjparenrightbig?p?j = 0 and we have the
desired result.
There are other methods of matrix decomposition, two of which are defined in the
following theorems:
Theorem 2.5 [10] (Schur?s Triangularization Theorem)
Let ?1,?2,...,?n be the eigenvalues of A ? Cn?n. Then there exists a unitary matrix
U ?Cn?n such that U?AU is an upper triangular matrix, that is,
U?AU =
?
??
??
??
??
?
?1
?2 *
...
?n
?
??
??
??
??
?
where the order of ?1,...,?n can be arbitrarily fixed.
Theorem 2.6 [10] (Singular Value Decomposition)
Let A ? Cm?n and let ?1,?2,...,?r be the nonzero singular values of A. Then there
exist unitary matrices U ?Cm?m and V ?Cn?n such that
A = U
?
??
?
D 0
0 0
?
??
?V,
where D = diag(?1,?2,...,?r). Thus rankA = r which is the number of nonzero
singular values of A.
9
Due to Theorem 2.6 the singular values remain the same under unitary equivalence, i.e.,
A and UAV have the same singular values if U and V are unitary matrices.
The rank of a matrix also has some important properties that will be needed. They
include [1]:
1. rank(AB) ? rank(A).
2. rank(AB) ? rank(B).
3. rank(A?A) = rank(A).
Suppose A ? Cn?n and 1 ? k ? n. Then the kth compound of A is defined as the
parenleftbign
k
parenrightbig?parenleftbign
k
parenrightbig complex matrix C
k(A) whose elements are defined by
Ck(A)?,? = detA[?|?]. (2.1)
Here A[?|?] is the k ? k submatrix of A obtained by choosing the rows indexed by ?
and the columns indexed by ?, where ?,? ? Qk,n and
Qk,n := {? = (?(1),...,?(k)) : 1 ? ?(1) < ??? < ?(k) ? n}
is the set of increasing sequences of length k chosen from 1,...,n. For example, if n = 3
and k = 2, then
C2(A) =
?
??
??
??
?
detA[1,2|1,2] detA[1,2|1,3] detA[1,2|2,3]
detA[1,3|1,2] detA[1,3|1,3] detA[1,3|2,3]
detA[2,3|1,2] detA[2,3|1,3] detA[2,3|2,3]
?
??
??
??
?
.
In general C1(A) = A and Cn(A) = detA.
Some properties of the compound matrix [8] are listed in the following result.
10
Theorem 2.7 Let A,B ?Cn?n. Then
1. Ck(AB) = Ck(A)Ck(B).
2. [Ck(A)]? = Ck(A?).
3. Ck(A?1) = [Ck(A)]?1 if A is nonsingular.
4. If A is normal, Hermitian, positive definite (or nonnegative) or unitary, then so is
Ck(A).
5. The eigenvalues of Ck(A) are the parenleftbignkparenrightbig numbers ?i1?i2 ????ik for (i1,...,ik) ? Qk,n,
where ?1,...,?n are the eigenvalues of A. In particular the eigenvalue of maximal
modulus of Ck(A) is |?1(Ck(A))| = |?1(A)|???|?k(A)|.
6. The singular values of Ck(A) are the parenleftbignkparenrightbig numbers ?i1?i2 ????ik for (i1,...,ik) ?
Qk,n, where ?1,...,?n are the singular values of A. In particular, the largest
singular value of Ck(A) is ?1(Ck(A)) = ?1(A)????k(A).
Principal submatrices are used in Chapter 4, and the relationship between the eigenvalues
of a matrix A and the principal submatrices of A is described in the following theorem.
Theorem 2.8 [10] (Interlacing Inequalities for Eigenvalues)
Let H be an n?n Hermitian matrix partitioned as
H =
?
??
?
A B
B? C
?
??
?
where A is an m?m principal submatrix of H, 1 ? m ? n. Then
?k(H) ? ?k(A) ? ?k+n?m(H), k = 1,2,...,m.
11
In particular, when m = n?1,
?1(H) ? ?1(A) ? ?2(H) ????? ?n?1(H) ? ?n?1(A) ? ?n(H).
Proof: [10] It is sufficient to prove the m = n ? 1 case. Let ?1 ? ?2 ? ??? ? ?n be
the eigenvalues of H and let ?1 ? ??? ? ?n?1 be the eigenvalues of A. By the Spectral
Theorem of Hermitian matrices, there is a unitary U ?Cn?n such that
H = U?
?
??
??
??
??
??
?
?1
?2
...
?n
?
??
??
??
??
??
?
U.
Then
tI ?H = U?
?
??
??
??
??
??
?
t??1
t??2
...
t??n
?
??
??
??
??
??
?
U,
and thus for t negationslash= ?i, i = 1,2,...,n,
(tI ?H)?1 = U?
?
??
??
??
??
??
?
1
t??1
1
t??2
...
1
t??n
?
??
??
??
??
??
?
U. (2.2)
12
When t negationslash= ?i, i = 1,2,...,n,
(tI ?H)?1 = adj(tI ?H)det(tI ?H), (2.3)
where adjA denotes the adjugate of A ? Cn?n. Upon computation, the (n,n)-entry of
(tI ?H)?1 by using (2.2) is
|u1n|2
t??1 +
|u2n|2
t??2 +???+
|unn|2
t??n
and the (n,n)-entry of adj(tI ?H) is det(tI ?A). Thus by (2.3)
?(t) := det(tI ?A)det(tI ?H) = |u1n|
2
t??1 +
|u2n|2
t??2 +???+
|unn|2
t??n. (2.4)
Assume that ?1 > ?2 > ??? > ?n. Note that ?(t) is continuous whose roots are ?1 ?
... ? ?n?1, which must interlace ?1,...,?n, i.e.,
?i ? [?i+1,?i], i = 1,2,...,n?1.
By continuity argument, we have the same conclusion for ?1 ? ?2 ????? ?n.
Notations: Let 1 ? k ? n?1. We denote by A[k] the submatrix formed by selecting
the first k rows and columns of A. In other words, A[k] is upper-left corner principal
k?k submatrix of A:
13
A[k] =
?
??
??
??
??
??
??
k?k
n?k
n?k
?
??
??
??
??
??
??
Denote by A?k? the submatrix generated by deleting the first k?1 rows and columns
of A. In other words, A?k? is lower-right corner principal (n?k+1)?(n?k+1) submatrix
of A:
A?k? =
?
??
??
??
??
??
??
k?1
k?1
n ? k +1? n ? k +1
?
??
??
??
??
??
??
Notice that the kth entry of the diagonal is a member in each submatrix.
Theorem 2.9 [3] (Interlacing Inequalities for Singular Values)
Let A ?Cn?n be given and let Ap ?Cn?(n?p) (respectively Ap ?C(n?p)?n) denote
a submatrix of A obtained by deleting any p columns (or respectively any p rows) from
A. Then
?i(A) ? ?i(Ap) ? ?i+p(A), i = 1,2,...,n?p.
Proof: [10] It is sufficient to establish the p = 1 case and for definiteness suppose that
A1 is obtained by deleting the last column from A. Then A1 is a submatrix of A and
14
A?1A1 is a principal submatrix of A?A. By Theorem 2.8 we have
?i(A?A) ? ?i(A?1A1) ? ?i+1(A?A).
By taking square roots, we obtain ?i(A) ? ?i(A1) ? ?i+1(A).
Lemma 2.10 [3] Let A ? Cn?n be given, and consider B = (0 | A) ? Cn?(n+p) and
C =
?
??
?
A
0
?
??
??C(n+p)?n obtained by adjoining p zero columns (respectively, rows) to A.
Then
?i(A) = ?i(B) = ?i(C), i = 1,2,...,n.
Proof: The nonzero singular values of A are the square roots of the positive eigenvalues
of A?A or AA?. Now BB? = AA? and C?C = A?A. So ?i(A) = ?i(B) = ?i(C),
i = 1,2,...,n, when zero singular values are also counted.
15
Chapter 3
Yamamoto?s original proof
Recall Yamamoto?s theorem as it was stated earlier in Theorem 1.1:
Let A ?Cn?n. Then
limp??[?i(Ap) ]1p = |?i(A)|, i = 1,2,...,n.
The largest singular value and largest eigenvalue modulus fall under i = 1 case and is
a special case of Gelfand?s Spectral Radius Theorem (Theorem 1.2) where the induced
matrix norm is the spectral norm. We may use the spectral norm and its properties to
achieve our goal in this case. In his proof, Yamamoto [9] first provides the following
lemma in order to establish Gelfand?s result which gives the case k = 1.
Lemma 3.1 Let bardbl?bardbl : Cn?n ? R be a matrix norm induced by a vector norm bardbl?bardbl :
Cn ?R. Given A ?Cn?n, for every p ?N, we have
?(A) ?bardbl Apbardbl1p ?bardbl Abardbl,
where ?(A) is the spectral radius of A.
Proof: Let A ? Cn?n. For any eigenvalue ? of A, let x ? Cn be a unit eigenvector
corresponding to ?. That is, bardblxbardbl = 1 and
Ax = ?x.
16
So we have
Apx = ?px.
By taking the norm of this equality we have bardblApxbardbl = bardbl?pxbardbl. The homogeneous and
sub-multiplicative property yield
bardblAbardblp = bardblAbardblpbardblxbardbl?bardblApbardblbardblxbardbl?bardblApxbardbl = bardbl?pxbardbl = |?p|bardblxbardbl?|?|pbardblxbardbl = |?|p.
By taking the pth-root on both sides we obtain
bardblAbardbl?bardblApbardbl1p ?|?| = ?(A)
since bardblxbardbl = 1. In particular it is true for ? = ?1.
We now have the tools to prove Gelfand?s Spectral Radius Theorem which states
that for any induced matrix norm bardbl?bardbl on Cn?n and any A ?Cn?n,
limp??bardblApbardbl1p = ?(A). (3.1)
Proof: By Lemma 3.1 the sequence {bardblApbardbl1p}p?N is contained in the closed and bounded
interval [?(A),bardblAbardbl]. Let ? be any limit point of the sequence {bardblApbardbl1p}p?N. So there
is a convergent subsequence in [?(A),bardblAbardbl], denoted by {bardblApibardbl 1pi}i?N where 1 ? p1 ?
p2 ????, such that bardblApibardbl 1pi converges to the limit point ? ? [?(A),bardblAbardbl]. We claim that
? = ?(A).
Suppose on the contrary ?(A) < ?. There would exist some positive number ?prime such
that 0 ? ?(A) < ?prime < ?. Then
?(A)
?prime = ?(
A
?prime) < 1
17
which implies
parenleftBigA
?prime
parenrightBigpi
? 0 as pi ?? by Theorem 2.4. So
bardbl
parenleftbiggA
?prime
parenrightbiggpi
bardbl? 0 as pi ??.
Thus, for a fixed constant epsilon1 > 0, there exists a positive integer N(epsilon1) such that
bardbl
parenleftbiggA
?prime
parenrightbiggpi
bardbl < epsilon1
for every i > N(epsilon1). Then
1 < ??prime = 1?prime limi??bardblApibardbl 1pi = limi??bardbl
parenleftbiggA
?prime
parenrightbiggpi
bardbl 1pi < limi??epsilon1 1pi = 1,
a contradiction! So ?(A) = ?. Since ? is arbitrary we have established that there is only
one limit point, ?(A).
Suppose that limp??bardblApbardbl1p were not equal to ?(A). Then there would exist an
epsilon1 > 0 such that for every j ?N, there would exist pj > m with |bardblApjbardbl
1
pj ??(A)|? epsilon1. So
there would exist a subsequence {bardblApjbardbl
1
pj }j?N of {bardblApbardbl1p}p?N such that for all j ?N
|bardblApjbardbl
1
pj ??(A)|? epsilon1. (3.2)
But {bardblApjbardbl
1
pj }j?N is a subsequence of {bardblApbardbl1p}p?N which is contained in the closed and
bounded interval [?(A),bardblAbardbl]. So there is a convergent subsequence of {bardblApjbardbl
1
pj }j?N,
namely {bardblApjkbardbl
1
pjk }k?
N, and this convergent subsequence must converge to the limit
point ?(A) since ?(A) is the only limit point of bardblApbardbl1p, i.e. limk??bardblApjkbardbl
1
pjk = ?(A).
So for the same epsilon1 > 0, there exists N(epsilon1) ?N such that
|bardblApjkbardbl
1
pjk ??(A)| < epsilon1
18
whenever k > N(epsilon1), contradicting (3.2).
Hence we have limp??bardblApbardbl1p = ?(A). When bardbl?bardbl = bardbl?bardbl2 we have the k = 1 case
of Yamamoto?s Theorem as a corollary since bardblAbardbl2 = ?1(A).
Corollary 3.2 Let A ?Cn?n. Then limp??[?1(Ap)]1p = |?1(A)|.
We now prove the remaining cases k = 2,...,n of (1.1).
Proof: The properties of compound matrices allow the use of the k = 1 case (Corollary
3.2) to show the result true for the finishing case. By Theorem 2.7 we have
|?1(Ck(A))| =
kproductdisplay
i=1
|?i(A)|, ?1(Ck(A)) =
kproductdisplay
i=1
?i(A). (3.3)
Apply Corollary 3.2 on the kth compound Ck(A) of A:
limp??[
kproductdisplay
i=1
?i(Ap)]1p =
kproductdisplay
i=1
|?i(A)|. (3.4)
Case 1: A is nilpotent, i.e., |?1(A)| = 0. Then for all j = 2,...,n,
0 = |?1(A)| = limp??[?1(Ap)]1/p ? limp??[?j(Ap)]1/p ? 0.
So
limp??[?j(Ap)]1/p = |?j(A)|.
Case 2: A is not nilpotent, i.e., |?1(A)|negationslash= 0. Let A have k nonzero eigenvalues for
some 1 ? k ? n, i.e., |?1| ? ??? ? |?k| > |?k+1| = ??? = |?n| = 0. Utilizing Theorem
2.5 we have U?AU = T where T is upper triangular with ?1,?2,...,?n on the diagonal.
19
Raising both sides to the power p, we have
(U?AU)p = U?ApU = Tp
and due to the upper triangular form of T we have ?p1,?p2,...,?pn on the diagonal of Tp.
Since k of the eigenvalues are nonzero, rank(Tp) ? k. Notice
rank(Tp) = rank(U?ApU) = rank(Ap).
So there are at least k nonzero singular values of Ap since the rank of a matrix is the
number of nonzero singular values. Then we have for any p,
tproductdisplay
i=1
?i(Ap) > 0, 1 ? t ? k. (3.5)
Then for 1 ? j ? k + 1 we have
limp??[?j(Ap)]1p = limp??
bracketleftBiggproducttextj
i=1 ?i(Ap)producttext
j?1
i=1 ?i(Ap)
bracketrightBigg1
p
=
limp??
bracketleftBigproducttextj
i=1 ?i(Ap)
bracketrightBig1
p
limp??
bracketleftBigproducttextj?1
i=1 ?i(Ap)
bracketrightBig1
p
(nonzero denominator by (3.5))
=
producttextj
i=1|?i(A)|producttext
j?1
i=1 |?i(A)|
(by Corollary 3.2)
= |?j(A)|.
In particular when j = k + 1
limp??[?k+1(Ap)]1p = 0. (3.6)
20
If j > k + 1 we have by (3.6)
0 ? [?j(Ap)]1p ? [?k+1(Ap)]1p ? 0.
So, limp??[?j(Ap)]1p = |?j(A)| = 0. Then for any i = 1,...,n,
limp??[?i(Ap)]1p = |?i(A)|.
21
Chapter 4
Mathias? proof
Mathias [3] provides a different method of proving Yamamoto?s theorem. Like Ya-
mamoto, he also makes use of Gelfand?s Spectral Radius Theorem to show the k = 1
case. Recall Gelfand?s result (Theorem 1.2):
LetbardblAbardbl := maxbardblxbardbl=1bardblAxbardblbe a matrix norm induced by a vector normbardbl?bardbl : Cn ?R
where A ?Cn?n. Then
limp??bardblApbardbl1p = ?(A),
where ?(A) := |?1(A)| is the spectral radius of A.
The proof of Gelfand?s result provided by Mathias proceeds as follows.
Proof: For any eigenvalue ? associated with A ? Cn?n, let x be a unit eigenvector
corresponding to ?. Now
Ax = ?x ? Apx = ?px.
By taking the norm of both sides we obtain:
bardblApbardblbardblxbardbl?bardblApxbardbl = bardbl?pxbardbl = |?|pbardblxbardbl.
Now since bardblxbardbl is a unit vector, we have bardblApbardbl1p ? |?|. In particular this is true for the
largest eigenvalue ?1. So ?(A) ?bardblApbardbl1p. Now define
?A = A
?(A) +epsilon1
22
for an arbitrary epsilon1 > 0. Clearly ?(A) +epsilon1 > 0. Then we have
?( ?A) = ?
parenleftbigg A
?(A) +epsilon1
parenrightbigg
= ?(A)?(A) +epsilon1 < 1
and bardbl ?Apbardbl ? 0 as p ? ? by Theorem 2.4. So in particular there exists an integer
N(epsilon1,A) such that bardbl ?Apbardbl ? 1 whenever p > N(epsilon1,A). This actually provides the upper
bound we need, since
1 ?bardbl ?Apbardbl = bardbl
parenleftbigg A
?(A) +epsilon1
parenrightbiggp
bardbl = bardblA
pbardbl
(?(A) +epsilon1)p.
Thus bardblApbardbl? (?(A) +epsilon1)p and by taking the pth root we obtain
bardblApbardbl1p ? ?(A) +epsilon1.
Now putting all of this together provides a nice small interval around bardblApbardbl1p , that is,
?(A) ?bardblApbardbl1p ? ?(A) +epsilon1.
As epsilon1 ? 0, then p ?? and thus
limp??bardblApbardbl1p = ?(A) = |?1(A)|.
In particular since bardblAbardbl2 = ?1(A) we have
limp??[?1(Ap)]1p = |?1(A)|. (4.1)
23
Our next step is to examine the case k = n for
limp??[?k(Ap)]1p = |?k(A)|. (4.2)
When k = n we consider two possibilities for the matrix A, the singular and nonsingular
cases. Recall that when k = n, we are dealing with the smallest of the singular values
and eigenvalue moduli of A.
Proof: of (4.2).
Case1: A is singular. So detA = producttextni=1 ?i(A) = 0. For each p ? N by Theorem 2.6
there are unitary matrices U and V such that
Ap = UDV = Udiag(?1,?2,...,?n)V.
So we have
0 = |detA|p = |detAp| = |det(UDV)| = |detU||detD||detV| = |detD| =
nproductdisplay
i=1
?i(Ap).
So at least one of each of the eigenvalues and singular values is equal to zero, namely
the smallest ones, |?n(A)| and ?n(Ap), respectively. Then we have
limp??[?n(Ap)]1p = |?n(A)| = 0.
Case 2: Now consider the case when A is nonsingular. Of course nonsingularity
indicates that A has an inverse and we can use this to our advantage as follows:
Ax = ?x ? 1?x = A?1x.
24
Then the smallest eigenvalue of A, with respect to modulus, |?n|, is the reciprocal of the
largest eigenvalue of A?1 with respect to modulus, that is, 1|?n(A)| = ?(A?1). We also
have ?1(A) = [?1(A?A)]12 so that
?1(A?1) =
parenleftbigg 1
[?n(A?A)]
parenrightbigg1
2 = 1
[?n(A?A)]12
= 1?
n(A)
.
By (4.1),
1
limp??[?n(Ap)]1p
= limp??[ 1?
n(Ap)
]1p = limp??[?1(A?p)]1p = |?1(A?1)| = 1|?
n(A)|
.
By reciprocating each side of the equality we obtain
limp??[?n(Ap)]1p = |?n(A)|. (4.3)
So far we have established Yamamoto?s result (1.1) when k = 1 and when k = n. To
show the case for 1 < k < n, Mathias employs Theorem 2.9 and Lemma 2.10 and uses
the properties of principle submatrices. In particular there are two principle submatrices
that we shall consider: A[k], the upper-left corner principal k ?k submatrix of A and
A?k? lower-right corner principal (n?k+1)?(n?k+1) submatrix of A . The last case
of his proof proceeds as follows:
Proof: By Theorem 2.5 there exist a unitary matrix U such that U?AU = T where T
is an upper triangular matrix T having ?1(A),?2(A),...,?n(A) on the diagonal. Then
U?ApU = Tp. (4.4)
25
Since T is an upper triangular matrix,
(T[k])p = (Tp)[k], (T?k?)p = (Tp)?k?. (4.5)
So by Theorem 2.9 and (4.5) we have
?k(Ap) = ?k(Tp) ? ?k((Tp)[k]) = ?k((T[k])p). (4.6)
Hence ?k(Ap) is bounded below by ?k((T[k])p).
In order to construct an upper bound for ?k(Ap) employ Theorem 2.9, Lemma 2.10,
and (4.5) to obtain
?k(Ap) = ?k(Tp) (by unitary invariance (4.4))
= ?1+(k?1)(Tp)
? ?1(L) (by Theorem 2.9)
= ?1((Tp)?k?) (by Lemma 2.10)
= ?1((T?k?)p) (by (4.5)), (4.7)
where L is the submatrix of Tp by deleting the first k ?1 rows of Tp. This establishes
the upper bound we were looking for. Putting (4.6) and (4.7) together we have
?k((T[k])p) ? ?k(Ap) ? ?1((T?k?)p).
By taking the pth root we obtain
[?k((T[k])p)]1p ? [?k(Ap)]1p ? [?1((T?k?)p)]1p.
26
Taking the limit yields
limp??[?k((T[k])p)]1p ? limp??[?k(Ap)]1p ? limp??[?1((T?k?)p)]1p. (4.8)
By applying (4.3) on the principal submatrix T[k] ?Ck?k of T,
limp??[?k((T[k])p)]1p = |?k(T[k])|. (4.9)
Likewise, applying (4.1) on the principal submatrix T[k] ?C(n?k+1)?(n?k+1) of T
limp??[?1((T?k?)p)]1p = |?1(T?k?)|. (4.10)
Then by putting together (4.8), (4.9), ( 4.10) we have bounds on the limit of ?k(Ap):
|?k(T[k])|? limp??[?k(Ap)]1p ?|?1(T?k?)|.
But |?k(T[k])| = |?k(T)| = |?k(A)| and |?1(T?k?)| = |?k(T)| = |?k(A)|. Thus
|?k(A)|? limp??[?k(Ap)1p] ?|?k(A)|
Hence, limp??[?k(Ap)1p] = |?k(A)| for 1 ? k ? n.
27
Chapter 5
Comparing Approaches
About 23 years after T. Yamamoto introduced his proof that
limp??[?i(Ap)]1p = |?i(A)|,
R. Mathias introduced a different proof. The proofs share some common characteristics
but the main ingredient in each is different and that leads to several distinguishing
characteristics. We will consider the development of the proofs by comparing the cases
k = 1 and 1 ? k ? n for each author.
Initially both Yamamoto and Mathias use Gelfand?s Spectral Radius Theorem. They
offer proofs for Gelfand?s result in which both make use of Theorem 2.4. Yamamoto leads
into the theorem by introducing a lemma (3.1) which bounds bardblApbardbl1p by ?(A) and bardblAbardbl.
This is followed by the use of the closed and bounded interval to manipulate subsequences
that show that
limp??bardblApbardbl]1p = ?(A).
Mathias defines a matrix ?A in order to bound bardblApbardbl1p below and above by ?(A) and
?(A) +epsilon1 respectively. Then let epsilon1 ? 0 so that limp??bardblApbardbl1p = ?(A). Both authors use
properties of norms, and the fact that bardblAbardbl = ?1(A). Since Mathias approach is very
different from Yamamoto we will discuss each separately from this point forward.
For Yamamoto the procession from the k = 1 case to the 1 < k ? n case is a natural
step eased by the use of the compound matrix Ck(A). Once the k = 1 case is applied
28
to Ck(A), only a few details need to be checked for the completion of the proof. If A is
nilpotent (|?i(A)| = 0, i = 1,...,n) and the k = 1 case limp??[?1(Ap)]1p = |?1(A)| = 0
to obtain
limp??[?j(Ap)]1p = |?j(A)| = 0
since the eigenvalues and singular values are ordered in non-increasing order. Now when
A is not nilpotent with k nonzero eigenvalues, Yamamoto applies Schur?s Triangulariza-
tion Theorem (Theorem 2.5) and uses the rank argument to show that the number of
nonzero singular values is at least k. Then by manipulation of the product of the first k
singular values he is able to establish that
limp??[?i(Ap)]1p = |?i(A)|, i = 1,...,n
Of course through this final step by necessity he divides the product up in order to
isolate the jth term. The fact that k of the singular values are nonzero guarantees the
denominator is nonzero and then application of Corollary 3.2 transforms the notation to
eigenvalues and the desired result falls out.
In comparison Mathias? method requires him to split up the case where 1 < k ? n.
He establishes the k = n case easily by considering the singular and nonsingular cases.
Using the fact that for a singular matrix ?i(A) = 0 and employing Singular Value
Decomposition (Theorem 2.6) he gets that ?i(Ap) = 0. The invertibility of a nonsingular
matrix allows the use of the k = 1 result to be applied to A?1 to obtain the equality for
the smallest eigenvalue and singular value. He continues with the 1 < k < n case only
after finishing the k = 1 and k = n cases. Now armed with the two limits obtained in
the cases for k = 1 and k = n, Mathias incorporates the use of principal submatrices to
show the desired result is true. Since Schur?s Triangularization Theorem (Theorem 2.5)
29
allows conversion of Ap into an upper triangular matrix through unitary similarity, he
can simplify the process by engaging the Singular Value Interlacing Theorem (Theorem
2.9) as well as Lemma 2.10 to obtain upper and lower bounds on [?i(Ap)]1p. Having
these bounds basically finishes the proof since the triangular form of T together with the
application of the results for k = 1 and k = n gives the desired result.
Clearly the tools needed to finish the proofs for the case(s) where 1 < k ? n are
varied for each approach. Yamamoto?s use of compound matrices reduces the additional
tools he is required to use to properties of nilpotent matrices and Schur?s Triangular-
ization Theorem. The approach Mathias chose to take requires more steps since he has
separate cases for k = n and 1 < k < n. Also he needs to have at hand the benefits of
Schur?s Triangularization Theorem (2.5), Singular Value Decomposition (Theorem 2.5),
properties of principal submatrices as well as the Singular Value Interlacing Theorem
(Theorem 2.9). While the approach of R. Mathias is nice, the original method of Ya-
mamoto is a more elegant approach, since it relies on only a few tools. Mathias? reasoning
is easy to follow and understand, but requires a wider base of knowledge to establish the
result.
30
Bibliography
[1] S. Friedberg, A. Insel, and L. Spence, Linear Algebra, 3rd Ed. , Prentice Hall, New
Jersey, 1997.
[2] P.R. Halmos, A Hilbert Space Problem Book, Springer-Verlag, New York, 1974.
[3] R. Mathias, Two theorems on singular values and eigenvalues, Amer. Math. Monthly,
97:47?50, 1990.
[4] R. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 1985.
[5] R. Horn and C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press,
1991.
[6] P. Nylen and T.Y. Tam, On the spread of a Hermitian matrix and a conjecture of
Thompson, Linear and Multilinear Algebra 37:3?11, 1994.
[7] T.Y. Tam and H. Huang, An extension of Yamamoto?s theorem on the eigenvalues
and singular values of a matrix, J. of Math. Soc. Japan, to appear.
[8] J. Todd, Survey of Numerical Analysis, McGraw-Hill, New York, 1962.
[9] T. Yamamoto, On the extreme values of the roots of matrices, J. Math. Soc. Japan,
19:173?178, 1967.
[10] F. Zhang, Matrix Theory: basic results and techniques, Springer, New York, 1999.
31