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

标签：

• Kyoto-University
• Householder-Transformation
• Orthogonal-Matrix
• Eigenvalues-and-Eigenvectors
• Matrix-Determinant
• Matrix-Inverse

Author

amongtrees, 空想性錯視, 祭音Myyura

Description

In the questions below, $\mathbb{R}$ denotes the set of all real numbers, $\boldsymbol{a}^T$ stands for the transpose of $\boldsymbol{a}$, $\boldsymbol{A}^{-1}$ is the inverse of a matrix $\boldsymbol{A}$, and $\boldsymbol{I}_{n}$ denotes the identity matrix of size $n \times n$.

Q.1

Let $\boldsymbol{v} \in \mathbb{R}^{n}$ be a nonzero column vector, and define a matrix $\boldsymbol{T}$ as

$$\boldsymbol{T} = \boldsymbol{I}_{n} - 2\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}}$$

Answer the following questions.

(1) Show that $\boldsymbol{T}$ is a symmetric matrix.

(2) Show that $\boldsymbol{T}$ is an orthogonal matrix.

(3) Compute all the eigenvalues of $\boldsymbol{T}$.

(4) Compute the determinant of $\boldsymbol{T}$.

(5) Define a column vector $\boldsymbol{e}_{1} \in \mathbb{R}^{n}$ as

$$\boldsymbol{e}_{1} = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$$

Given a column vector $\boldsymbol{x} \in \mathbb{R}^n$, which is not $\boldsymbol{e}_1$ multiplied by any scalar. Determine $\boldsymbol{v}$ so that $\boldsymbol{Tx}$ becomes $\boldsymbol{e}_1$ multiplied by some scalar, and express it using $\boldsymbol{x}$ and $\boldsymbol{e}_1$.

Q.2

Answer the following questions.

(1) Let $\boldsymbol{P}$ be an arbitrary real matrix of size $n \times n$. Assume that $\boldsymbol{I}_n + \boldsymbol{P}$ is non-singular. Show that the following equation holds.

$$\left (\boldsymbol{I}_n + \boldsymbol{P} \right)^{-1}\boldsymbol{P} = \boldsymbol{P}\left(\boldsymbol{I}_n + \boldsymbol{P}\right)^{-1}$$

(2) Let $\boldsymbol{Q}$ and $\boldsymbol{R}$ be arbitrary real matrices of size $n \times m$ and $m \times n$, respectively. Assume that $\boldsymbol{I}_n + \boldsymbol{QR}$ is non-singular. Show that $\boldsymbol{I}_m + \boldsymbol{RQ}$ is non-singular and that the following equation holds.

$$\left( \boldsymbol{I}_n + \boldsymbol{QR}\right)^{-1}\boldsymbol{Q} = \boldsymbol{Q}\left(\boldsymbol{I}_m + \boldsymbol{RQ}\right)^{-1}$$

题目描述

1. 对非零列向量 $v\in\mathbb R^n$，定义
   $$T=I_n-2\frac{vv^\top}{v^\top v}.$$
   1. 证明 $T$ 对称；2. 证明 $T$ 正交；3. 求全部特征值；4. 求 $\det T$。
   2. 令 $e_1=(1,0,\ldots,0)^\top$。给定不是 $e_1$ 标量倍的 $x$，用 $x,e_1$ 表示一个 $v$，使 $Tx$ 成为 $e_1$ 的标量倍。
2. 回答：
   1. 若 $I_n+P$ 可逆，证明 $(I_n+P)^{-1}P=P(I_n+P)^{-1}$。
   2. 对 $Q\in\mathbb R^{n\times m}$、$R\in\mathbb R^{m\times n}$，若 $I_n+QR$ 可逆，证明 $I_m+RQ$ 可逆且
      $$(I_n+QR)^{-1}Q=Q(I_m+RQ)^{-1}.$$

考点

• Householder 反射：证明对称正交性，分解沿 $v$ 与其正交补的作用，得到特征值、行列式及把向量反射到坐标轴的构造。
• 矩阵逆恒等式：利用矩阵多项式交换及乘法验证证明不同维度矩阵的 push-through identity。

Kai

Q.1

Background: Householder Transformation

(1)

Since $\boldsymbol{I}_n$ is symmetric and $\boldsymbol{v}^T\boldsymbol{v}$ is a scalar, we have:

$$\boldsymbol{T}^T = \left(\boldsymbol{I}_n - 2\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}}\right)^T = \boldsymbol{I}_n^T - 2\frac{\left(\boldsymbol{v}\boldsymbol{v}^T\right)^T}{\boldsymbol{v}^T\boldsymbol{v}} = \boldsymbol{I}_n - 2\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}} = \boldsymbol{T}$$

Thus, $\boldsymbol{T}$ is a symmetric matrix.

(2)

According to (1), we know $\boldsymbol{T}^T = \boldsymbol{T}$, so we have:

$$\begin{aligned} \boldsymbol{T}^T\boldsymbol{T} = \boldsymbol{T}^2 &= \left(\boldsymbol{I}_n - 2\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}}\right)^2 \\ &= \boldsymbol{I}_n -4\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}} + 4\frac{\boldsymbol{v}\left(\boldsymbol{v}^T\boldsymbol{v}\right)\boldsymbol{v}^T}{\left(\boldsymbol{v}^T\boldsymbol{v}\right)^2} \\ &= \boldsymbol{I}_n -4\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}} + 4\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}} \\ &= \boldsymbol{I}_n \end{aligned}$$

Thus, $\boldsymbol{T}$ is an orthogonal matrix.

(3)

The form $\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}}$ is the projection matrix of vector $\boldsymbol{v}$, we can make the following classification discussion:

Case 1: $\boldsymbol{x}$ is orthogonal to $\boldsymbol{v}$

Let $\boldsymbol{x}$ be any non-zero vector such that $\boldsymbol{v}^T\boldsymbol{x} = \boldsymbol{0}$, obviously the subspace of satisfied vectors in $\mathbb{R}^n$ has $n-1$ demensions, and we have:

$$\begin{aligned} \boldsymbol{Tx} &= \left(\boldsymbol{I}_n - 2\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}}\right)\boldsymbol{x} \\ &= \boldsymbol{I}_n\boldsymbol{x} - 2\frac{\boldsymbol{v}\left(\boldsymbol{v}^T\boldsymbol{x}\right)}{\boldsymbol{v}^T\boldsymbol{v}} \\ &= \boldsymbol{x} - 2\frac{\boldsymbol{v}\cdot\boldsymbol{0}}{\boldsymbol{v}^T\boldsymbol{v}} \\ &= \boldsymbol{x} \end{aligned}$$

Thus, $\lambda = 1$ is an eigenvalue with multiplicity $n - 1$;

Case 2: $\boldsymbol{x}$ is parallel to $\boldsymbol{v}$

Let $\boldsymbol{x} = c\boldsymbol{v}$ for some scalar $c\neq 0$, we have:

$$\begin{aligned} \boldsymbol{Tx} &= \left(\boldsymbol{I}_n - 2\frac{\boldsymbol{vv}^T}{\boldsymbol{v}^T\boldsymbol{v}}\right)c\boldsymbol{v} \\ &= c\left(\boldsymbol{I}_n\boldsymbol{v} - 2\frac{\boldsymbol{v}\left(\boldsymbol{v}^T\boldsymbol{v}\right)}{\boldsymbol{v}^T\boldsymbol{v}}\right) \\ &= c\left(\boldsymbol{v} - 2\boldsymbol{v}\right) \\ &= -\boldsymbol{x} \end{aligned}$$

Thus, $\lambda = -1$ is an eigenvalue with multiplicity 1.

(4)

The determinant of a matrix is the product of its eigenvalues.

$$det(\boldsymbol{T}) = 1^{n-1} \times (-1)^1 = -1$$

(5)

We want to find a vector $\boldsymbol{v}$ such that $\boldsymbol{Tx} = k\boldsymbol{e}_1$ for some scalar $k$, where $\boldsymbol{x} \in \mathbb{R}^n$ and $\boldsymbol{x}$ is not a scalar multiple of $\boldsymbol{e}_1$.

Since $\boldsymbol{T}$ is an orthogonal matrix, it preserves the norm of the multiplied vector. Thus, $\left\|\boldsymbol{Tx}\right\| = \left\|\boldsymbol{x}\right\|$, and we have:

$$\left\|k\boldsymbol{e}_1\right\| = \left| k \right| \cdot \left\| \boldsymbol{e}_1 \right\| = \left| k \right| = \left\|\boldsymbol{x}\right\| \Rightarrow k = \pm \left\|\boldsymbol{x}\right\|$$

So we are actually looking for a $\boldsymbol{v}$ such that $\boldsymbol{Tx} = \pm \left\|\boldsymbol{x}\right\| \boldsymbol{e}_1$. From the definition of $\boldsymbol{T}$, we have:

$$\boldsymbol{x} - 2\frac{\boldsymbol{v}\left(\boldsymbol{v}^T\boldsymbol{x}\right)}{\boldsymbol{v}^T\boldsymbol{v}} = \pm \left\|\boldsymbol{x}\right\| \boldsymbol{e}_1$$

Rearranging this equation:

$$\begin{equation} \boldsymbol{x} \mp \left\|\boldsymbol{x}\right\| \boldsymbol{e}_1 = 2\frac{\boldsymbol{v}^T\boldsymbol{x}}{\boldsymbol{v}^T\boldsymbol{v}}\boldsymbol{v} \end{equation}$$

This shows that the vector $\boldsymbol{v}$ must be parallel to $\boldsymbol{x} \mp \left\|\boldsymbol{x}\right\| \boldsymbol{e}_1$. Let's choose $\boldsymbol{v}$ to be just this vector and verify the result. Let $\alpha = \pm \left\|\boldsymbol{x}\right\|$, we have $\boldsymbol{v} = \boldsymbol{x} - \alpha \boldsymbol{e}_1$. Now compute the terms in the equation (1):

$$\begin{aligned} \boldsymbol{v}^T\boldsymbol{v} &= \left(\boldsymbol{x} - \alpha \boldsymbol{e}_1 \right)^T\left(\boldsymbol{x} - \alpha \boldsymbol{e}_1 \right) \\ &= \boldsymbol{x}^T\boldsymbol{x} - 2\alpha \boldsymbol{x}^T\boldsymbol{e}_1 + \alpha^2\boldsymbol{e}_1^T\boldsymbol{e}_1 \\ &= \left\| \boldsymbol{x} \right\|^2 - 2\alpha x_1 + \alpha^2 \\ &= \left\| \boldsymbol{x} \right\|^2 - 2\alpha x_1 + \left\| \boldsymbol{x} \right\|^2 \\ &= 2( \left\| \boldsymbol{x} \right\|^2 - \alpha x_1 ) \\ \\ \boldsymbol{v}^T\boldsymbol{x} &= \left(\boldsymbol{x} - \alpha \boldsymbol{e}_1 \right)^T \boldsymbol{x} \\ &= \boldsymbol{x}^T\boldsymbol{x} - \alpha \boldsymbol{e}_1^T \boldsymbol{x} \\ &= \left\| \boldsymbol{x} \right\|^2 - \alpha x_1 \end{aligned}$$

Thus, equation (1) stands true, which confirms our choice of $\boldsymbol{v}$ is correct. And the different signs influence $\boldsymbol{Tx}$ be of different scalar of $\boldsymbol{e}_1$.

Q.2

(1)

$$\begin{aligned} (\boldsymbol{I}_n+\boldsymbol{P})\boldsymbol{P}(\boldsymbol{I}_n+\boldsymbol{P})^{-1} &= (\boldsymbol{P}+\boldsymbol{P}^2)(\boldsymbol{I}_n+\boldsymbol{P})^{-1}\\ &= \boldsymbol{P}(\boldsymbol{I}_n + \boldsymbol{P})(\boldsymbol{I}_n+\boldsymbol{P})^{-1}\\ &= \boldsymbol{P} \end{aligned}$$

Left-multiplying both sides of the equation by $(\boldsymbol{I}_n+\boldsymbol{P})^{-1}$, we get $\left (\boldsymbol{I}_n + \boldsymbol{P} \right)^{-1}\boldsymbol{P} = \boldsymbol{P}\left(\boldsymbol{I}_n + \boldsymbol{P}\right)^{-1}$.

(2)

Firstly we need prove $\boldsymbol{I}_m+\boldsymbol{RQ}$ is non-singular. Assume it's singular, then there must exist a non-zero vector $\boldsymbol{u} \in \mathbb{R}^m$ such that:

$$(\boldsymbol{I}_m+\boldsymbol{RQ})\boldsymbol{u} = \boldsymbol{0} \Rightarrow \boldsymbol{u} = -\boldsymbol{RQu}$$

Left-multiplying by $\boldsymbol{Q}$ gives:

$$\boldsymbol{Qu} = -\boldsymbol{QRQu} \Rightarrow (\boldsymbol{I}_n + \boldsymbol{QR})\boldsymbol{Qu} = \boldsymbol{0}$$

Since we are given that $\boldsymbol{I}_n + \boldsymbol{QR}$ is non-singular, the only solution to this equation is $\boldsymbol{Qu} = \boldsymbol{0}$. Substituting this back into the initial assumption:

$$\boldsymbol{u} = -\boldsymbol{R\left(Qu\right)} = \boldsymbol{0}$$

This contradicts our assumption that $\boldsymbol{u}$ is a non-zero vector. Thus, $\boldsymbol{I}_m + \boldsymbol{RQ}$ must be non-singular.

Next, we have:

$$\begin{aligned} (\boldsymbol{I}_n + \boldsymbol{QR})\boldsymbol{Q}(\boldsymbol{I}_m + \boldsymbol{RQ})^{-1} &=(\boldsymbol{Q} + \boldsymbol{QRQ})(\boldsymbol{I}_m + \boldsymbol{RQ})^{-1} \\ &= \boldsymbol{Q}(\boldsymbol{I}_m + \boldsymbol{RQ})(\boldsymbol{I}_m + \boldsymbol{RQ})^{-1} \\ &= \boldsymbol{Q} \end{aligned}$$

Similarly left-multiplying both sides of the equation by $(\boldsymbol{I}_n + \boldsymbol{QR})^{-1}$, we get $\left( \boldsymbol{I}_n + \boldsymbol{QR}\right)^{-1}\boldsymbol{Q} = \boldsymbol{Q}\left(\boldsymbol{I}_m + \boldsymbol{RQ}\right)^{-1}$.