0248-2010 名情复 数学 P104

线性代数 矩阵分解 马尔可夫链

[1] 正整数 $n$ とする。$n$ 次の正則な正方行列 $A=(A_{ij})$ を，下三角行列 $L$ と上三角行列 $U$ として，$A=LU$ に変換することを考える。次の問いに答えよ。

1. $n=3$ とする。次式を満たす ${\alpha }_{21},{\alpha }_{31},{\alpha }_{32},{\beta }_{21},{\beta }_{31},{\beta }_{32}$ を答えよ。ただし，$A_{11}\ne 0,b_{22}\ne 0$ とする。

$$\left(\begin{array}{ccc}1& 0& 0\\ {\alpha }_{21}& 1& 0\\ {\alpha }_{31}& {\alpha }_{32}& 1\end{array}\right)\left(\begin{array}{ccc}{A}_{11}& A_{12}& A_{13}\\ A_{21}& A_{22}& A_{23}\\ A_{31}& A_{32}& A_{33}\end{array}\right)=\left(\begin{array}{ccc}{A}_{11}& A_{12}& A_{13}\\ 0& b_{22}& b_{23}\\ A_{31}& A_{32}& A_{33}\end{array}\right)$$ $$\left(\begin{array}{ccc}1& 0& 0\\ {\beta }_{21}& 1& 0\\ {\beta }_{31}& {\beta }_{32}& 1\end{array}\right)\left(\begin{array}{ccc}{A}_{11}& A_{12}& A_{13}\\ 0& b_{22}& b_{23}\\ A_{31}& A_{32}& A_{33}\end{array}\right)=\left(\begin{array}{ccc}{A}_{11}& A_{12}& A_{13}\\ 0& b_{22}& b_{23}\\ 0& 0& c_{33}\end{array}\right)=U$$

2. $n=3$ とする。1) の $U$ に対して $A=LU$ が成り立つ $L$ の要素を $A_{ij}(i=1,2,3;j=1,2,3),b_{2j}(j=2,3)$ を用いて表せ。

3. 正整数 $n$ とする。また，$A=LU$ が成り立つ $L,U$ が計算されているとする。このとき，$n$ 次元ベクトル $\mathbf{b}$ に対して，$A\mathbf{x}=\mathbf{b}$ を満たす $\mathbf{x}$ を $L,U$ を用いて計算する方法を説明せよ。ただし，$U$ の対角項はゼロではないとする。

[2] 正整数 $n$ とする。$n$ 次元正方行列 $Q=(Q_{ij})$ が $Q_{ij}\ge 0(i=1,2,\dots ,n;j=1,2,\dots ,n)$ で，かつ $\sum _{j=1}^n{Q}_{ij}=1(i=1,2,\dots ,n)$ のとき，$Q$ を確率行列という。また，$n$ 次元ベクトル $\mathbf{p}=(p_i)$ が $p_i\ge 0(i=1,2,\dots ,n)$ で，かつ $\sum _{i=1}^n{p}_i=1$ のとき，$\mathbf{p}$ を確率ベクトルという。このとき，次の問いに答えよ。

1. ${\mathbf{p}}^{T}Q$ は確率ベクトルとなることを証明せよ。ただし，$(\cdot {)}^T$ は転置を表す。

2. $Q^2=QQ$ は確率行列となることを証明せよ。

---

解答：

[1]
1)
第1の等式より、行列の積を計算して各要素を比較する。
第2行第1列：

$${\alpha }_{21}{A}_{11}+A_{21}=0⟹{\alpha }_{21}=-\frac{A_{21}}{A_{11}}$$

第3行は不変であるため：

$${\alpha }_{31}{A}_{1j}+{\alpha }_{32}{A}_{2j}+A_{3j}=A_{3j}⟹{\alpha }_{31}{A}_{1j}+{\alpha }_{32}{A}_{2j}=0(j=1,2,3)$$

これが任意の $A_{ij}$ で成り立つため、${\alpha }_{31}=0,{\alpha }_{32}=0$ となる。

第2の等式より、同様に積を計算する。
第2行第1列は不変であるため、${\beta }_{21}{A}_{11}+0=0⟹{\beta }_{21}=0$。
第3行について：

$${\beta }_{31}{A}_{11}+A_{31}=0⟹{\beta }_{31}=-\frac{A_{31}}{A_{11}}$$ $${\beta }_{31}{A}_{12}+{\beta }_{32}{b}_{22}+A_{32}=0⟹{\beta }_{32}=-\frac{A_{32}+{\beta }_{31}{A}_{12}}{b_{22}}=-\frac{A_{32}-\frac{A_{31}}{A_{11}}{A}_{12}}{b_{22}}$$ $$\boxed{\begin{array}{rl}{\alpha }_{21}& =-\frac{A_{21}}{A_{11}},{\alpha }_{31}=0,{\alpha }_{32}=0\\ {\beta }_{21}& =0,{\beta }_{31}=-\frac{A_{31}}{A_{11}},{\beta }_{32}=-\frac{A_{32}-\frac{A_{31}}{A_{11}}{A}_{12}}{b_{22}}\end{array}}$$

1)で定義された2つの変換行列をそれぞれ $E_1,E_2$ とおく。

$$E_2{E}_{1}A=U⟹A=E_1^{-1}{E}_2^{-1}U$$

$A=LU$ と比較すると、$L=E_1^{-1}{E}_2^{-1}$ となる。

$$\begin{array}{rl}L& ={\left(\begin{array}{ccc}1& 0& 0\\ {\alpha }_{21}& 1& 0\\ 0& 0& 1\end{array}\right)}^{-1}{\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ {\beta }_{31}& {\beta }_{32}& 1\end{array}\right)}^{-1}\\ & =\left(\begin{array}{ccc}1& 0& 0\\ -{\alpha }_{21}& 1& 0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -{\beta }_{31}& -{\beta }_{32}& 1\end{array}\right)\\ & =\left(\begin{array}{ccc}1& 0& 0\\ -{\alpha }_{21}& 1& 0\\ -{\beta }_{31}& -{\beta }_{32}& 1\end{array}\right)\end{array}$$

1)の結果を代入する。

$$\boxed{L=\left(\begin{array}{ccc}1& 0& 0\\ \frac{A_{21}}{A_{11}}& 1& 0\\ \frac{A_{31}}{A_{11}}& \frac{A_{32}-\frac{A_{31}}{A_{11}}{A}_{12}}{b_{22}}& 1\end{array}\right)}$$

$A\mathbf{x}=\mathbf{b}$ は $LU\mathbf{x}=\mathbf{b}$ と書ける。$U\mathbf{x}=\mathbf{y}$ とおくと、方程式は $L\mathbf{y}=\mathbf{b}$ および $U\mathbf{x}=\mathbf{y}$ の2つのステップに分解される。

$$\boxed{\begin{array}{rl}& \text{Step 1: 前進代入 (Forward substitution) により }L\mathbf{y}=\mathbf{b}\text{ から }\mathbf{y}\text{ を解く。}\\ & y_1=b_1,y_i=b_i-\sum _{j=1}^{i-1}{L}_{ij}{y}_j(i=2,\dots ,n)\\ & \text{Step 2: 後退代入 (Backward substitution) により }U\mathbf{x}=\mathbf{y}\text{ から }\mathbf{x}\text{ を解く。}\\ & x_n=\frac{y_n}{U_{nn}},x_i=\frac{1}{U_{ii}}\left(y_i-\sum _{j=i+1}^n{U}_{ij}{x}_j\right)(i=n-1,\dots ,1)\end{array}}$$

[2]
1)
${\mathbf{v}}^T={\mathbf{p}}^{T}Q$ とおく。その第 $j$ 成分は $v_j=\sum _{i=1}^n{p}_i{Q}_{ij}$ である。
$p_i\ge 0$ かつ $Q_{ij}\ge 0$ であるため、すべての $j$ について $v_j\ge 0$ が成り立つ。
ベクトル $\mathbf{v}$ の全成分の和を計算する。

$$\sum _{j=1}^n{v}_j=\sum _{j=1}^n\left(\sum _{i=1}^n{p}_i{Q}_{ij}\right)=\sum _{i=1}^n\left(p_i\sum _{j=1}^n{Q}_{ij}\right)$$

行列 $Q$ が確率行列であるため、各行の和は $\sum _{j=1}^n{Q}_{ij}=1$ となる。

$$\sum _{j=1}^n{v}_j=\sum _{i=1}^n(p_i\cdot 1)=\sum _{i=1}^n{p}_i=1$$

したがって、非負性および和が1である条件を満たすため、${\mathbf{p}}^{T}Q$ は確率ベクトルとなる。(証明終)

$R=Q^2$ とおく。その $(i,j)$ 成分は $R_{ij}=\sum _{k=1}^n{Q}_{ik}{Q}_{kj}$ である。
$Q_{ik}\ge 0$ かつ $Q_{kj}\ge 0$ より、すべての $i,j$ について $R_{ij}\ge 0$ が成り立つ。
行列 $R$ の第 $i$ 行の成分の和を計算する。

$$\sum _{j=1}^n{R}_{ij}=\sum _{j=1}^n\left(\sum _{k=1}^n{Q}_{ik}{Q}_{kj}\right)=\sum _{k=1}^n\left(Q_{ik}\sum _{j=1}^n{Q}_{kj}\right)$$

行列 $Q$ が確率行列であるため、$\sum _{j=1}^n{Q}_{kj}=1$ となる。

$$\sum _{j=1}^n{R}_{ij}=\sum _{k=1}^n(Q_{ik}\cdot 1)=\sum _{k=1}^n{Q}_{ik}=1$$

非負性および各行の和が1である条件を満たすため、$Q^2$ は確率行列となる。(証明終)

---

本题考察了数值线性代数中的LU分解过程以及概率论中的马尔可夫链状态转移矩阵性质。在进行高斯消元操作时，每一次消元本质上等于左乘一个下三角的初等行变换矩阵。通过记录每一步消元过程中使用的乘数，可以非常自然地构造出对应的下三角矩阵L，这展示了矩阵乘法如何代数化地描述算法过程。解线性方程组时运用LU分解将原本复杂的多维求解任务分离为解两个三角矩阵方程，从而利用前向替换与后向替换大幅度降低计算复杂度。第二题的证明题验证了马尔可夫链中状态概率分布的演化规律，概率向量乘状态转移矩阵得到的新向量依然守恒地保持总概率为1，而转移矩阵的任意次幂表示多步转移概率，也天然满足非负和行和归一化的守恒要求。这种乘法性质奠定了随机过程理论推导的基础。