Introduction to Clustering Large and High-Dimensional Data
Focusing on a few of the most important clustering algorithms, this book provides a detailed account of these major models in an information retrieval context.
TABLE OF CONTENTS Introduction to Clustering Large and High-Dimensional Data
Chapter 10: Appendix Optimization And Linear Algebra Background
This Chapter collects some basic optimization and linear algebra results.
10.1. Eigenvalues of a Symmetric Matrix
In this section we collect a number of well-known facts concerning a symmetric n by n matrix M with real entries.
Proposition 10.1.1. Let v 1 and v 2 be eigenvectors of M with the corre sponding real eigenvalues ? 1 and ? 2 . If ? 1 ? ? 2 , then 
.
Proof
Since 
one has 
, and 
. Due to the assumption ? 1 ? ? 2 ? 0, this yields 
, and completes the proof.
Proposition 10.1.2. If ? be an eigenvalue of M, then ? is real.
Proof: Suppose that ? = ? + i ? , and x is an eigenvector corresponding to ?, i.e.
Since ? = ? + i ? is a complex number the vector x = v + i w, where v and w are real vectors of dimension n. The condition x ? 0 implies x 2 = v 2 + w 2 > 0. Separating the real and imaginary parts in (10.1.1) we get
and the left multiplication of the first equation by w T and the left multiplication of the second equation by v T yield
Since v T M w ? w T M v = 0 one has ?
Copyright Jacob Kogan 2007 under license agreement with Books24x7
