京都大学 情報学研究科 知能情報学専攻 2021年8月実施 情報学基礎 F1-1

Author

Isidore

Description

設問1

以下で定義される実行列 \(A\) と \(B\)、および実数ベクトル \(x\) に関して、以下の問いに答えよ。 ここで、 \(\|x\|\) は \(x\) の長さを表す。

\[ A = \begin{pmatrix} 1 & -\sqrt{3} \\ \sqrt{3} & 1 \end{pmatrix}, \quad B = \begin{pmatrix} r & 0 \\ 0 & r \end{pmatrix}, \quad x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \quad \|x\| > 0 \]

(1) \(A^3\) を求めよ。

(2) \(A^{-1}\) を求めよ。

(3) \(A^{15}\) を求めよ。

(4) \(\lim_{n \to \infty} \|(AB)^n x\|\) を求めよ。ここで、 \(n\) は自然数とする。

設問2

\(m \times n\) (\(m > n\)) の実行列 \(A\) と以下で定義される行列 \(B\) と \(C\) を考える。ここで、 \(T\) は転置を表すものとする。 また、内積 \((a, b)\) を以下で定義する。 ここで、 \(a\) と \(b\) は \(l\) 次元ベクトル、 \(a_k\) は \(a\) の \(k\) 番目の要素、 \(b_k\) は \(b\) の \(k\) 番目の要素とする。

\[ B = A^T A, \quad C = A A^T, \quad (a, b) = \sum_{k=1}^l a_k b_k \]

以下の問いに答えよ。必要であれば、実対称行列に関する以下の性質を使用せよ：

• 実対称行列の固有値は全て実数である。
• 実対称行列のどの固有値に対しても、実ベクトルからなる固有ベクトルをとることができる。

(1) \(B\) と \(C\) がともに実対称行列であることを示せ。

(2) \(B\) の全ての固有値が非負であることを示せ。

(3) 実対称行列は直交行列で対角化できる。\(B\) を対角化する直交行列の列ベクトルは、いずれも \(B\) の固有ベクトルである。 これらのうち正の固有値 \(\lambda_i, \lambda_j\) に対応する固有ベクトルを \(p_i, p_j\) とし、\(q_i\) と \(q_j\) を

\[ q_i = \frac{1}{\sqrt{\lambda_i}} A p_i, \ q_j = \frac{1}{\sqrt{\lambda_j}} A p_j \]

で与えられるベクトルとする。 \(q_i, q_j\) が \(C\) の固有ベクトルであって対応する固有値はそれぞれ \(\lambda_i, \lambda_j\) であること、および

\[ (q_i, q_j) = \begin{cases} 0 & (i \neq j) \\ 1 & (i = j) \end{cases} \]

であることを示せ。また、

\[ p_i = \frac{1}{\sqrt{\lambda_i}} A^T q_i \]

であることを示せ。

Kai

設問1

(1)

\[ A = \begin{pmatrix} -8 & 0 \\ 0 & -8 \\ \end{pmatrix} \]

(2)

\[ A^{-1} = \frac{1}{4} \begin{pmatrix} 1 & \sqrt{3} \\ -\sqrt{3} & 1 \\ \end{pmatrix} \]

(3)

\[ A^{15}=(A^3)^5=(-8E)^5=-2^{15}E \]

(4)

Let the required value denote \(I\), and we have

\[ I = \lim_{n \rightarrow \infty}\|(AB)^nx\| = \lim_{n \rightarrow \infty}\|(-8r^3E)^{\frac{n}{3}}x\| \]

Obviously, the limit converges if and only if

\[ -8r^3 \in [-1, 1] \]

Hence, when \(r \in (-\frac{1}{2}, \frac{1}{2})\), we have

\[ I = 0 \]

Particularly, when \(r=\pm \frac{1}{2}\), we have

\[ I = \lim_{n \rightarrow \infty}\|(-1)^{\frac{n}{3}}x\| = \|x\| = \sqrt{x_1^2+x_2^2} \]

設問2

(1)

Obviously, as \(A\) is a real matrix, \(B\) and \(C\) are both real matrices. Also,

\[ \begin{aligned} B^T &= (A^T A)^T = A^T (A^T)^T = A^T A = B\\ C^T &= (A A^T)^T = (A^T)^T A^T = A A^T = C \end{aligned} \]

hence \(B\) and \(C\) are real symmetric matrices.

(2)

Consider B's eigenvalue, we have

\[ A^TAx=\lambda x \]

hence,

\[ x^TA^TAx = \lambda x^Tx \]

hence,

\[ \lambda = \frac{x^TA^TAx}{x^Tx} = \frac{\|Ax\|}{\|x\|} \geq 0 \]

(3)

Consider the eigenvalue \(\lambda_i\) with its eigenvector \(p_i\), we have

\[ A^TAp_i=\lambda_ip_i \]

Left-multiply by \(\frac{1}{\sqrt{\lambda_i}}A\), we have

\[ \frac{1}{\sqrt{\lambda_i}}AA^TAp_i = \sqrt{\lambda_i}Ap_i \\ AA^T(\frac{1}{\sqrt{\lambda_i}}Ap_i) = \lambda_i(\frac{1}{\sqrt{\lambda_i}}Ap_i) \]

since \(q_i = \frac{1}{\sqrt{\lambda_i}}Ap_i\), we have

\[ Cq_i = \lambda_i q_i \]

Similarly, we have \(Cq_j = \lambda_j q_j\) for a different eigenvalue \(\lambda_j\). Therefore, \(q_i\) and \(q_j\) are eigenvectors of C corresponding to eigenvalues \(\lambda_i\) and \(\lambda_j\).

Now we consider the inner product of \(q_i\) and \(q_j\)

\[ q_i^Tq_j = \frac{1}{\sqrt{\lambda_i \lambda_j}}(Ap_i)^T(Ap_j) = \frac{\sqrt{\lambda_j}}{\sqrt{\lambda_i}}p_i^Tp_j \]

Obviously, if \(i \neq j\), as \(B\) is a real symmetric matrix, \(p_i^Tp_j = 0\). If \(i = j\), \(p_i^Tp_j = 1\) Therefore, we have

\[ q_i^Tq_j = \begin{cases} 0 & \text{if } i \neq j \\ 1 & \text{if } i = j \end{cases} \]

Finally, insert \(q_i = \frac{1}{\sqrt{\lambda_i}}Ap_i\) to \(\frac{1}{\sqrt{\lambda_i}}A^Tq_i\), we immediately have

\[ \frac{1}{\sqrt{\lambda_i}}A^Tq_i = \frac{1}{\sqrt{\lambda_i}}A^T\frac{1}{\sqrt{\lambda_i}}Ap_i = \frac{1}{\lambda_i}A^TAp_i = p_i \]

Q.E.D