東京大学 新領域創成科学研究科 メディカル情報生命専攻 2025年1月実施 問題7

标签：

• 东京大学
• 豪斯霍尔德变换
• QR 分解

Author

KardeniaPoyu, 祭音Myyura

Description

長さ $1$ の $3$ 次元実縦ベクトル $\boldsymbol{u} \in \mathbb{R}^3$ ($\|\boldsymbol{u}\| = \sqrt{\boldsymbol{u}^T \boldsymbol{u}} = 1$) に対し、$3 \times 3$ 実行列 $R_u \in \mathbb{R}^{3 \times 3}$ を $R_u = I - 2\boldsymbol{u}\boldsymbol{u}^T$ と定義する。ここで、$I \in \mathbb{R}^{3 \times 3}$ は $3 \times 3$ 単位行列、$\boldsymbol{u}^T$ は $\boldsymbol{u}$ の転置を表す。以下の問に数学的導出も含め答えよ。

(1) 任意のベクトル $\boldsymbol{x} \in \mathbb{R}^3$ に対し、$\boldsymbol{y} = R_u \boldsymbol{x}$ と置くとき、ベクトル $\boldsymbol{x} - \boldsymbol{y}$ はある実数 $a \in \mathbb{R}$ を用いて $\boldsymbol{x} - \boldsymbol{y} = a\boldsymbol{u}$ と書けることを示せ。

(2) $\boldsymbol{y}$ と $\boldsymbol{x}$ の長さは等しい ($\|\boldsymbol{y}\| = \|\boldsymbol{x}\|$) ことを示せ。

(3) ベクトル $\boldsymbol{x} = (x_1, x_2, x_3)^T \in \mathbb{R}^3$ が $1$ つ与えられているとする。$\boldsymbol{y} = R_u \boldsymbol{x}$ がある実数 $b \in \mathbb{R}$ を用いて $\boldsymbol{y} = (b, 0, 0)^T$ の形になるような $\boldsymbol{u}$ を全て求めよ。

(4) ベクトル $\boldsymbol{x} = (x_1, x_2, x_3)^T \in \mathbb{R}^3$ が $1$ つ与えられているとする。$\boldsymbol{y} = R_u \boldsymbol{x}$ がある実数 $c \in \mathbb{R}$ を用いて $\boldsymbol{y} = (x_1, c, 0)^T$ の形になるような $\boldsymbol{u}$ を全て求めよ。

(5) $A = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix} \in \mathbb{R}^{3 \times 3}$ とする。$B = R_u R_v A$ がある実数 $d, e, f, g, h, i \in \mathbb{R}$ を用いて $B = \begin{pmatrix} d & e & f \\ 0 & g & h \\ 0 & 0 & i \end{pmatrix}$ の形になるような、長さ $1$ のベクトルの組 $(\boldsymbol{u}, \boldsymbol{v})$ を $1$ つ求めよ。またこのときの $B$ を答えよ。

题目描述

对单位三维实列向量 $\boldsymbol u\in\mathbb R^3$，

$$\|\boldsymbol u\|=\sqrt{\boldsymbol u^T\boldsymbol u}=1,$$

定义 Householder 矩阵

$$R_u=I-2\boldsymbol u\boldsymbol u^T\in\mathbb R^{3\times3}.$$

要求给出数学推导并回答：

1. 对任意 $\boldsymbol x\in\mathbb R^3$，令 $\boldsymbol y=R_u\boldsymbol x$，证明存在 $a\in\mathbb R$ 使

   $$\boldsymbol x-\boldsymbol y=a\boldsymbol u.$$

2. 证明反射保持长度：

   $$\|\boldsymbol y\|=\|\boldsymbol x\|.$$

3. 给定 $\boldsymbol x=(x_1,x_2,x_3)^T$，求所有单位向量 $\boldsymbol u$，使某个 $b\in\mathbb R$ 满足

   $$R_u\boldsymbol x=(b,0,0)^T;$$

   需涵盖输入向量的退化情形。

4. 对同一 $\boldsymbol x$，求所有单位向量 $\boldsymbol u$，使某个 $c\in\mathbb R$ 满足

   $$R_u\boldsymbol x=(x_1,c,0)^T.$$

5. 给定

   $$A=\begin{pmatrix}0&1&0\\0&0&1\\1&0&1\end{pmatrix},$$

   求一组单位向量 $(\boldsymbol u,\boldsymbol v)$，使

   $$B=R_uR_vA =\begin{pmatrix}d&e&f\\0&g&h\\0&0&i\end{pmatrix}$$

   为上三角矩阵，并写出相应的具体 $B$。

Kai

(1)

定義より、$\boldsymbol{y} = R_u\boldsymbol{x} = (I - 2\boldsymbol{u}\boldsymbol{u}^T)\boldsymbol{x} = \boldsymbol{x} - 2\boldsymbol{u}(\boldsymbol{u}^T\boldsymbol{x})$ である。 これを移項すると、

$$\boldsymbol{x} - \boldsymbol{y} = 2(\boldsymbol{u}^T\boldsymbol{x})\boldsymbol{u}$$

となる。ここで、$\boldsymbol{u}^T\boldsymbol{x}$ はベクトルの内積であり、実数のスカラー値である。 したがって、$a = 2\boldsymbol{u}^T\boldsymbol{x} \in \mathbb{R}$ とおけば、

$$\boldsymbol{x} - \boldsymbol{y} = a\boldsymbol{u}$$

と書けることが示された。

English:

By definition, $\boldsymbol{y} = R_u\boldsymbol{x} = (I - 2\boldsymbol{u}\boldsymbol{u}^T)\boldsymbol{x} = \boldsymbol{x} - 2\boldsymbol{u}(\boldsymbol{u}^T\boldsymbol{x})$. Rearranging this equation yields:

$$\boldsymbol{x} - \boldsymbol{y} = 2(\boldsymbol{u}^T\boldsymbol{x})\boldsymbol{u}$$

Here, $\boldsymbol{u}^T\boldsymbol{x}$ is the inner product of two vectors, which evaluates to a real scalar. Therefore, by letting $a = 2\boldsymbol{u}^T\boldsymbol{x} \in \mathbb{R}$, we can express this as:

$$\boldsymbol{x} - \boldsymbol{y} = a\boldsymbol{u}$$

This completes the proof.

(2)

$\|\boldsymbol{y}\|^2 = \boldsymbol{y}^T \boldsymbol{y} = (R_u \boldsymbol{x})^T (R_u \boldsymbol{x}) = \boldsymbol{x}^T R_u^T R_u \boldsymbol{x}$ を計算する。 まず、$R_u$ の転置は $R_u^T = (I - 2\boldsymbol{u}\boldsymbol{u}^T)^T = I - 2\boldsymbol{u}\boldsymbol{u}^T = R_u$ であり、$R_u$ は対称行列である。 次に、$R_u^T R_u = R_u^2$ を計算すると、

$$\begin{aligned} R_u^2 &= (I - 2\boldsymbol{u}\boldsymbol{u}^T)(I - 2\boldsymbol{u}\boldsymbol{u}^T) \\ &= I - 4\boldsymbol{u}\boldsymbol{u}^T + 4\boldsymbol{u}(\boldsymbol{u}^T\boldsymbol{u})\boldsymbol{u}^T \end{aligned}$$

仮定より $\|\boldsymbol{u}\| = 1$、すなわち $\boldsymbol{u}^T\boldsymbol{u} = 1$ であるため、

$$R_u^2 = I - 4\boldsymbol{u}\boldsymbol{u}^T + 4\boldsymbol{u}(1)\boldsymbol{u}^T = I$$

となり、$R_u$ は直交行列であることがわかる。 ゆえに、$\|\boldsymbol{y}\|^2 = \boldsymbol{x}^T I \boldsymbol{x} = \boldsymbol{x}^T \boldsymbol{x} = \|\boldsymbol{x}\|^2$ となる。 ノルムは非負であるため、$\|\boldsymbol{y}\| = \|\boldsymbol{x}\|$ が示された。

English:

Calculate $\|\boldsymbol{y}\|^2 = \boldsymbol{y}^T \boldsymbol{y} = (R_u \boldsymbol{x})^T (R_u \boldsymbol{x}) = \boldsymbol{x}^T R_u^T R_u \boldsymbol{x}$. First, note that $R_u^T = (I - 2\boldsymbol{u}\boldsymbol{u}^T)^T = I - 2\boldsymbol{u}\boldsymbol{u}^T = R_u$, meaning $R_u$ is a symmetric matrix. Next, we calculate $R_u^T R_u = R_u^2$:

$$\begin{aligned} R_u^2 &= (I - 2\boldsymbol{u}\boldsymbol{u}^T)(I - 2\boldsymbol{u}\boldsymbol{u}^T) \\ &= I - 4\boldsymbol{u}\boldsymbol{u}^T + 4\boldsymbol{u}(\boldsymbol{u}^T\boldsymbol{u})\boldsymbol{u}^T \end{aligned}$$

By assumption, $\|\boldsymbol{u}\| = 1$, which means $\boldsymbol{u}^T\boldsymbol{u} = 1$. Thus:

$$R_u^2 = I - 4\boldsymbol{u}\boldsymbol{u}^T + 4\boldsymbol{u}(1)\boldsymbol{u}^T = I$$

This shows $R_u$ is an orthogonal matrix. Therefore, $\|\boldsymbol{y}\|^2 = \boldsymbol{x}^T I \boldsymbol{x} = \boldsymbol{x}^T \boldsymbol{x} = \|\boldsymbol{x}\|^2$. Since norms are non-negative, it follows that $\|\boldsymbol{y}\| = \|\boldsymbol{x}\|$.

(3)

(2) より $\|\boldsymbol{y}\| = \|\boldsymbol{x}\|$ であるため、$\boldsymbol{y} = (b, 0, 0)^T$ ならば $b^2 = \|\boldsymbol{x}\|^2$、すなわち $b = \pm \|\boldsymbol{x}\|$ である。 (1) より $\boldsymbol{x} - \boldsymbol{y} = a\boldsymbol{u}$ であり、$\boldsymbol{u}$ は長さ 1 のベクトルであるため、$\boldsymbol{x} - \boldsymbol{y} \neq \boldsymbol{0}$ のとき、$\boldsymbol{u}$ は $\boldsymbol{x} - \boldsymbol{y}$ と平行な単位ベクトルとなる。すなわち、$\boldsymbol{u} = \pm \frac{\boldsymbol{x} - \boldsymbol{y}}{\|\boldsymbol{x} - \boldsymbol{y}\|}$ である。 以下の3つの場合に分けて求める。

(i) $\boldsymbol{x} \neq \pm \|\boldsymbol{x}\| (1, 0, 0)^T$ の場合： $\boldsymbol{x} - \boldsymbol{y} \neq \boldsymbol{0}$ となるため、公式に代入して、

$$\boldsymbol{u} = \pm \frac{\boldsymbol{x} \mp \|\boldsymbol{x}\| (1, 0, 0)^T}{\|\boldsymbol{x} \mp \|\boldsymbol{x}\| (1, 0, 0)^T\|} \quad (\text{複号任意})$$

(ii) $\boldsymbol{x} = k (1, 0, 0)^T \ (k \neq 0)$ の場合：

• $b = k$ のとき、$\boldsymbol{y} = \boldsymbol{x}$ となる。このとき $R_u \boldsymbol{x} = \boldsymbol{x} \implies 2\boldsymbol{u}(\boldsymbol{u}^T \boldsymbol{x}) = \boldsymbol{0} \implies \boldsymbol{u}^T \boldsymbol{x} = 0$。ゆえに $u_1 = 0$ を満たす任意の単位ベクトル $\boldsymbol{u} = (0, u_2, u_3)^T$（ただし $u_2^2 + u_3^2 = 1$）。
• $b = -k$ のとき、$\boldsymbol{x} - \boldsymbol{y} = 2k (1, 0, 0)^T \neq \boldsymbol{0}$ となるため、$\boldsymbol{u} = \pm (1, 0, 0)^T$。

(iii) $\boldsymbol{x} = \boldsymbol{0}$ の場合： $b = 0$ となり、$\boldsymbol{y} = \boldsymbol{0}$。$R_u \boldsymbol{0} = \boldsymbol{0}$ は常に成り立つため、任意の単位ベクトル $\boldsymbol{u}$ が解となる。

English:

From (2), $\|\boldsymbol{y}\| = \|\boldsymbol{x}\|$. If $\boldsymbol{y} = (b, 0, 0)^T$, then $b^2 = \|\boldsymbol{x}\|^2$, which implies $b = \pm \|\boldsymbol{x}\|$. From (1), $\boldsymbol{x} - \boldsymbol{y} = a\boldsymbol{u}$. Since $\boldsymbol{u}$ is a unit vector, when $\boldsymbol{x} - \boldsymbol{y} \neq \boldsymbol{0}$, $\boldsymbol{u}$ must be a unit vector parallel to $\boldsymbol{x} - \boldsymbol{y}$. Thus, $\boldsymbol{u} = \pm \frac{\boldsymbol{x} - \boldsymbol{y}}{\|\boldsymbol{x} - \boldsymbol{y}\|}$. We find all solutions by considering three cases:

(i) If $\boldsymbol{x} \neq \pm \|\boldsymbol{x}\| (1, 0, 0)^T$: Here, $\boldsymbol{x} - \boldsymbol{y} \neq \boldsymbol{0}$. Substituting $\boldsymbol{y}$, we get:

$$\boldsymbol{u} = \pm \frac{\boldsymbol{x} \mp \|\boldsymbol{x}\| (1, 0, 0)^T}{\|\boldsymbol{x} \mp \|\boldsymbol{x}\| (1, 0, 0)^T\|} \quad (\text{signs are independent})$$

(ii) If $\boldsymbol{x} = k (1, 0, 0)^T$ for $k \neq 0$:

• For $b = k$, we have $\boldsymbol{y} = \boldsymbol{x}$. This gives $R_u \boldsymbol{x} = \boldsymbol{x} \implies 2\boldsymbol{u}(\boldsymbol{u}^T \boldsymbol{x}) = \boldsymbol{0} \implies \boldsymbol{u}^T \boldsymbol{x} = 0$. Hence, any unit vector with $u_1 = 0$ is a solution: $\boldsymbol{u} = (0, u_2, u_3)^T$ (where $u_2^2 + u_3^2 = 1$).
• For $b = -k$, we have $\boldsymbol{x} - \boldsymbol{y} = 2k (1, 0, 0)^T \neq \boldsymbol{0}$. Hence, $\boldsymbol{u} = \pm (1, 0, 0)^T$.

(iii) If $\boldsymbol{x} = \boldsymbol{0}$: Here $b = 0$ and $\boldsymbol{y} = \boldsymbol{0}$. Since $R_u \boldsymbol{0} = \boldsymbol{0}$ holds trivially, any unit vector $\boldsymbol{u}$ is a solution.

The candidate directions are also sufficient: whenever $\|x\|=\|y\|$ and $x\ne y$,

$$(x-y)^Tx=\frac{\|x-y\|^2}{2},\qquad \left(I-2\frac{(x-y)(x-y)^T}{\|x-y\|^2}\right)x=y.$$

The same identity applies in (4).

(4)

$\boldsymbol{y} = (x_1, c, 0)^T$ とする。(1) より、

$$\boldsymbol{x} - \boldsymbol{y} = \begin{pmatrix} 0 \\ x_2 - c \\ x_3 \end{pmatrix} = a\boldsymbol{u}$$

である。$\boldsymbol{x}-\boldsymbol{y}\ne\boldsymbol0$ の場合に限り、これにより $u_1=0$ である。 また $\|\boldsymbol{y}\| = \|\boldsymbol{x}\|$ より、$x_1^2 + c^2 = x_1^2 + x_2^2 + x_3^2$ となるため、$c = \pm \sqrt{x_2^2 + x_3^2}$ である。

(i) $\boldsymbol{x} - \boldsymbol{y} \neq \boldsymbol{0}$ の場合（すなわち $c \neq x_2$ または $x_3 \neq 0$）： $\boldsymbol{u}$ は $\boldsymbol{x} - \boldsymbol{y}$ を正規化したものになるため、

$$\boldsymbol{u} = \pm \frac{\boldsymbol{x} - \boldsymbol{y}}{\|\boldsymbol{x} - \boldsymbol{y}\|} = \pm \frac{1}{\sqrt{(x_2 - c)^2 + x_3^2}} \begin{pmatrix} 0 \\ x_2 - c \\ x_3 \end{pmatrix}$$

（ただし $c = \pm \sqrt{x_2^2 + x_3^2}$）。

(ii) $\boldsymbol{x} - \boldsymbol{y} = \boldsymbol{0}$ の場合（すなわち $x_3 = 0$ かつ $c = x_2$）： $\boldsymbol{x} = \boldsymbol{y} = (x_1, x_2, 0)^T$ となる。(3) と同様に $R_u \boldsymbol{x} = \boldsymbol{x} \implies \boldsymbol{u}^T\boldsymbol{x} = 0 \implies x_1 u_1 + x_2 u_2 = 0$。 これと $\|\boldsymbol{u}\| = 1$ を満たす任意の単位ベクトル $\boldsymbol{u}$ が解となる。

English:

Let $\boldsymbol{y} = (x_1, c, 0)^T$. From (1), we have:

$$\boldsymbol{x} - \boldsymbol{y} = \begin{pmatrix} 0 \\ x_2 - c \\ x_3 \end{pmatrix} = a\boldsymbol{u}$$

If $\boldsymbol{x}-\boldsymbol{y}\ne\boldsymbol0$, this implies $u_1=0$. Additionally, from $\|\boldsymbol{y}\| = \|\boldsymbol{x}\|$, we get $x_1^2 + c^2 = x_1^2 + x_2^2 + x_3^2$, which gives $c = \pm \sqrt{x_2^2 + x_3^2}$.

(i) If $\boldsymbol{x} - \boldsymbol{y} \neq \boldsymbol{0}$ (i.e., $c \neq x_2$ or $x_3 \neq 0$): $\boldsymbol{u}$ is obtained by normalizing $\boldsymbol{x} - \boldsymbol{y}$:

$$\boldsymbol{u} = \pm \frac{\boldsymbol{x} - \boldsymbol{y}}{\|\boldsymbol{x} - \boldsymbol{y}\|} = \pm \frac{1}{\sqrt{(x_2 - c)^2 + x_3^2}} \begin{pmatrix} 0 \\ x_2 - c \\ x_3 \end{pmatrix}$$

(where $c = \pm \sqrt{x_2^2 + x_3^2}$).

(ii) If $\boldsymbol{x} - \boldsymbol{y} = \boldsymbol{0}$ (i.e., $x_3 = 0$ and $c = x_2$): Here $\boldsymbol{x} = \boldsymbol{y} = (x_1, x_2, 0)^T$. Similar to (3), $R_u \boldsymbol{x} = \boldsymbol{x} \implies \boldsymbol{u}^T\boldsymbol{x} = 0 \implies x_1 u_1 + x_2 u_2 = 0$. Any unit vector $\boldsymbol{u}$ satisfying this equation and $\|\boldsymbol{u}\| = 1$ is a solution.

(5)

この問題は、ハウスホルダー変換を用いて行列 $A$ の QR分解を行うプロセスに相当する。

ステップ1：行列 $A$ の第1列目を変換する $\boldsymbol{v}$ を求める $A$ の第1列 $\boldsymbol{a}_1 = (0, 0, 1)^T$ を、(3) の結果を利用して $(d, 0, 0)^T$ の形に変換する。 $\|\boldsymbol{a}_1\| = 1$ より $d = 1$ と選ぶと、$\boldsymbol{y}_1 = (1, 0, 0)^T$ となる。 公式より、

$$\boldsymbol{v} = \frac{\boldsymbol{a}_1 - \boldsymbol{y}_1}{\|\boldsymbol{a}_1 - \boldsymbol{y}_1\|} = \frac{1}{\sqrt{(-1)^2 + 0^2 + 1^2}} \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix}$$

このとき、$R_v$ を計算すると以下のようになる（これは1行目と3行目を入れ替える置換行列となる）。

$$R_v = I - 2\boldsymbol{v}\boldsymbol{v}^T = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$

$$R_v A = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$

ステップ2：$R_v A$ の第2列目を変換する $\boldsymbol{u}$ を求める $R_v A$ の第2列 $\boldsymbol{a}_2^{(1)} = (0, 0, 1)^T$ を、第1成分を変えずに $(0, g, 0)^T$ の形に変換する。これは (4) に対応する。 $\boldsymbol{x} = (0, 0, 1)^T$ とし、$g = 1$ と選ぶと $\boldsymbol{y}_2 = (0, 1, 0)^T$ となる。 公式より、

$$\boldsymbol{u} = \frac{\boldsymbol{x} - \boldsymbol{y}_2}{\|\boldsymbol{x} - \boldsymbol{y}_2\|} = \frac{1}{\sqrt{0^2 + (-1)^2 + 1^2}} \begin{pmatrix} 0 \\ -1 \\ 1 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} 0 \\ -1 \\ 1 \end{pmatrix}$$

このとき、$R_u$ を計算すると以下のようになる（これは2行目と3行目を入れ替える置換行列となる）。

$$R_u = I - 2\boldsymbol{u}\boldsymbol{u}^T = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$

最後に $B = R_u (R_v A)$ を計算する。

$$B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

これは指定された上三角行列の形を満たしている。

解答：

• $\boldsymbol{v} = \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix}$
• $\boldsymbol{u} = \frac{1}{\sqrt{2}} \begin{pmatrix} 0 \\ -1 \\ 1 \end{pmatrix}$
• $B = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$

English:

This problem corresponds to the process of QR decomposition of matrix $A$ using Householder transformations.

Step 1: Find $\boldsymbol{v}$ to transform the first column of $A$ We transform the first column of $A$, $\boldsymbol{a}_1 = (0, 0, 1)^T$, into the form $(d, 0, 0)^T$ using the method from (3). Since $\|\boldsymbol{a}_1\| = 1$, we can choose $d = 1$, giving $\boldsymbol{y}_1 = (1, 0, 0)^T$. Using the formula:

$$\boldsymbol{v} = \frac{\boldsymbol{a}_1 - \boldsymbol{y}_1}{\|\boldsymbol{a}_1 - \boldsymbol{y}_1\|} = \frac{1}{\sqrt{(-1)^2 + 0^2 + 1^2}} \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix}$$

Calculating $R_v$, we get a permutation matrix that swaps the 1st and 3rd rows:

$$R_v = I - 2\boldsymbol{v}\boldsymbol{v}^T = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$

$$R_v A = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$

Step 2: Find $\boldsymbol{u}$ to transform the second column of $R_v A$ Next, we transform the second column of $R_v A$, which is $\boldsymbol{a}_2^{(1)} = (0, 0, 1)^T$, into $(0, g, 0)^T$ without changing the first component, using the method from (4). Here $\boldsymbol{x} = (0, 0, 1)^T$. Choosing $g = 1$ gives $\boldsymbol{y}_2 = (0, 1, 0)^T$. Using the formula:

$$\boldsymbol{u} = \frac{\boldsymbol{x} - \boldsymbol{y}_2}{\|\boldsymbol{x} - \boldsymbol{y}_2\|} = \frac{1}{\sqrt{0^2 + (-1)^2 + 1^2}} \begin{pmatrix} 0 \\ -1 \\ 1 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} 0 \\ -1 \\ 1 \end{pmatrix}$$

Calculating $R_u$, we get another permutation matrix that swaps the 2nd and 3rd rows:

$$R_u = I - 2\boldsymbol{u}\boldsymbol{u}^T = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$

Finally, we calculate $B = R_u (R_v A)$:

$$B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

This is exactly in the desired upper triangular form.

Final Answer:

• $\boldsymbol{v} = \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix}$
• $\boldsymbol{u} = \frac{1}{\sqrt{2}} \begin{pmatrix} 0 \\ -1 \\ 1 \end{pmatrix}$
• $B = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$