東京大学 情報理工学系研究科 コンピュータ科学専攻 2018年2月実施 問題1

Author

kainoj

Description

In this problem, represents the set of real numbers, and represents the set of real column vectors of length . For , denotes its transpose. Let be the identity matrix.

Consider an eigensystem of a real symmetric matrix ,

where and are an eigenvalue and a corresponding eigenvector, respectively.

Let be the maximum of eigenvalues of matrix .

You may use the following facts on the eigenvalues and the eigenvectors of a real symmetric matrix without proofs:

• There are independent eigenvectors that form an orthogonal basis.
• Every eigenvalue is a real number.

Answer the following questions.

(1) Prove that if is an eigenvector of , it is also an eigenvector of for any .

(2) Prove that

(3) Prove that

for any .

(4) Suppose that matrix is also an real symmetric matrix. Prove that

Kai

(1)

Let be an eigenvector with corresponding eigenvalue : . Let .

So is an eigenvector of with corresponding eigenvalue of .

(2)

Let be a unit vector which maximizes . Because is real and symmetric, then it can be diagonalized , where is orthogonal matrix, which columns form orthogonal basis. In following equation, let's substitute :

On the other hand, let be eigenvector corresponding to . Because maximizes , then:

Here we got:

For vector which maximizes . Hence,

and the maximum is reached for eigenvector .

(3)

Let . From question (2) we know that for arbitrary : look at second to the last line of Q2 calculations. Now if we know that fact, we get the inequality trivially:

(4)

Since are symmetric and real, then and for some orthogonal and. From what we obtained in (Q2): let be a~unit vector which maximizes . Then:

Substitute and . Of course , because (the same for ). Combining this and our knowledge form previous questions: