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

标签：

• Tokyo-University
• Eigenvalues-and-Eigenvectors
• Rayleigh-Quotient
• Positive-Semidefinite-Matrix

Author

kainoj

Description

In this problem, $\mathbb{R}$ represents the set of real numbers, and $\mathbb{R}^N$ represents the set of real column vectors of length $N$. For $\boldsymbol{v} \in \mathbb{R}^N$, $\boldsymbol{v}^\top$ denotes its transpose. Let $I$ be the $N \times N$ identity matrix.

Consider an eigensystem of a real $N \times N$ symmetric matrix $A$,

$$A\boldsymbol{x} = \lambda \boldsymbol{x},$$

where $\lambda$ and $\boldsymbol{x}$ are an eigenvalue and a corresponding eigenvector, respectively.

Let $\lambda_{\text{max}}(M)$ be the maximum of eigenvalues of matrix $M$.

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

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

Answer the following questions.

(1) Prove that if $\boldsymbol{x}$ is an eigenvector of $A$, it is also an eigenvector of $A + \mu I$ for any $\mu \in \mathbb{R}$.

(2) Prove that

$$\lambda_{\text{max}}(A) = \max \{\boldsymbol{v}^\top A\boldsymbol{v} \mid \boldsymbol{v} \in \mathbb{R}^N, \, \boldsymbol{v}^\top \boldsymbol{v} = 1\}.$$

(3) Prove that

$$\boldsymbol{v}^\top \big(\lambda_{\text{max}}(A)I - A\big)\boldsymbol{v} \geq 0$$

for any $\boldsymbol{v} \in \mathbb{R}^N$.

(4) Suppose that matrix $B$ is also an $N \times N$ real symmetric matrix. Prove that

$$\lambda_{\text{max}}(A + B) \leq \lambda_{\text{max}}(A) + \lambda_{\text{max}}(B).$$

Kai

(1)

Let $x$ be an eigenvector with corresponding eigenvalue $\lambda$: $Ax = \lambda x$. Let $\mu \in \mathbb{R}$.

$$(A + \mu I)x = Ax + \mu x = \lambda x + \mu x = (\lambda + \mu)x$$

So $x$ is an eigenvector of $(A + \mu I)$ with corresponding eigenvalue of $\lambda + \mu$.

(2)

Let $v \in \mathbb{R^N}$ be a unit vector which maximizes $v^T A v$. Because $A$ is real and symmetric, then it can be diagonalized $A = Q^T \Lambda Q$, where $Q$ is orthogonal matrix, which columns form orthogonal basis. In following equation, let's substitute $y = Qv$:

$$\begin{aligned} v^T A v &= v^T Q^T \Lambda Q v = y^T \Lambda y \\ &= \sum_{i=1}^{N}\lambda_i y_i^2\\ &\leq \: \sum_{i=1}^{N} \lambda_{max}(A) \: y_i^2 = \lambda_{max}(A) \: \sum_{i=1}^{N} y_i^2\\ &= \lambda_{max}(A) \: y^T y = \lambda_{max}(A) \: v^T Q^T Q v\\ &= \lambda_{max}(A) \end{aligned}$$

On the other hand, let $x_{max}$ be eigenvector corresponding to $\lambda_{max}(A)$. Because $v$ maximizes $v^T A v$, then:

$$v^T A v \geq x_{max}^T (A x_{max} ) = x_{max}^T x_{max} \: \lambda_{max}(A) = \lambda_{max}(A)$$

Here we got:

$$\lambda_{max}(A) \leq v^T A v \leq \lambda_{max}(A)$$

For vector $v$ which maximizes $v^T A v$. Hence,

$$\lambda_{max}(A) = \max \{v^T A v | v\in\mathbb{R}^N, v^T v = 1\}$$

and the maximum is reached for eigenvector $x_{max}$.

(3)

Let $v\in\mathbb{R}^N$. From question (2) we know that $v^T A v\leq \lambda_{max}(A) v^T v$ for arbitrary $v$: look at second to the last line of Q2 calculations. Now if we know that fact, we get the inequality trivially:

$$\begin{aligned} v^T(\lambda_{max}(A) I - A) v = \lambda_{max}(A) v^T v - v^T A v \geq 0 \end{aligned}$$

(4)

Since $A, B$ are symmetric and real, then $A = Q^T\Lambda_A Q$ and $B = P^T\Lambda_B P$ for some orthogonal $Q$and$P$. From what we obtained in (Q2): let $w$ be a~unit vector which maximizes $w^T(A+B)w$. Then:

$$\begin{aligned} \Lambda_{max}(A+B) &= w^T(A+B)w \\ &= w^T A w + w^T B w \\ &= w^T Q^T \Lambda_A Q w + w^T P^T \Lambda_B P w = (*) \end{aligned}$$

Substitute $y = Qw$ and $z = Pw$. Of course $y^T y = z^T z = 1$, because $y^T y = w^TQ^TQw = w^T w = 1$ (the same for $z$). Combining this and our knowledge form previous questions:

$$\begin{aligned} (*) &= y^T \Lambda_A y + z^T \Lambda_B z \\ &\leq \lambda_{max}(A) \: y^T y + \lambda_{max}(B) \: z^T z \\ &= \lambda_{max}(A) + \lambda_{max}(B) \end{aligned}$$