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

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} \]