跳到主要内容

京都大学 情報学研究科 システム科学専攻 2020年8月実施 線形代数

标签：

Author​

思齐塾, 祭音Myyura

Description​

以下の設問に答えよ。ただし, det⁡\det は行列式, TT は転置, 行列の右上の −1-1 は逆行列を意味するものとし, 問題文中の行列およびベクトルの成分, スカラーはすべて実数とする。また, n,m,ln, m, l は正の整数とする。さらに, m×mm \times m 行列 SS , m×lm \times l 行列 TT , l×ml \times m 行列 UU , l×ll \times l 正則行列 VV について, (m+l)×(m+l)(m+l) \times (m+l) 行列 [STUV]\begin{bmatrix} S & T \\ U & V \end{bmatrix} と S−TV−1US-TV^{-1}U が正則であれば,

[STUV]−1=[(S−TV−1U)−1−(S−TV−1U)−1TV−1−V−1U(S−TV−1U)−1V−1+V−1U(S−TV−1U)−1TV−1]\begin{bmatrix} S & T \\ U & V \end{bmatrix}^{-1} = \begin{bmatrix} (S-TV^{-1}U)^{-1} & -(S-TV^{-1}U)^{-1}TV^{-1} \\ -V^{-1}U(S-TV^{-1}U)^{-1} & V^{-1} + V^{-1}U(S-TV^{-1}U)^{-1}TV^{-1} \end{bmatrix}

となる。

(i) 正則な n×nn \times n 行列 AA , nn 次元列ベクトル b,cb, c , スカラー dd について, 以下が成り立つことを示せ。

det⁡[AbcTd]=(det⁡A)×(d−cTA−1b)\det \begin{bmatrix} A & b \\ c^T & d \end{bmatrix} = (\det A) \times (d - c^T A^{-1} b)

(ii) n≥2n \geq 2 とする。 AA を n×nn \times n 正定値対称行列とする。このとき, A−1A^{-1} も n×nn \times n 正定値対称行列となり, スカラー α>0\alpha > 0 , (n−1)(n-1) 次元列ベクトル β\beta , (n−1)×(n−1)(n-1) \times (n-1) 行列 Δ\Delta を用いて,

A−1=[αβTβΔ]A^{-1} = \begin{bmatrix} \alpha & \beta^T \\ \beta & \Delta \end{bmatrix}

と表すことができる。 A~\tilde{A} を行列 AA から最初の行と列を除いた (n−1)×(n−1)(n-1) \times (n-1) 小行列とするとき,

A~−1=Δ−ββTα\tilde{A}^{-1} = \Delta - \frac{\beta\beta^T}{\alpha}

となることを示せ。

(iii) 設問 (ii) の条件に加えて, x=[x1,x2,…,xn]Tx = [x_1, x_2, \dots, x_n]^T , また, xx の (n−1)(n-1) 次元部分ベクトルを x~=[x2,x3,…,xn]T\tilde{x} = [x_2, x_3, \dots, x_n]^T とする。このとき, 二次形式 xTA−1xx^T A^{-1} x は x1x_1 について二次式となるが, その二次式の x1x_1 に関する最小値は x~TA~−1x~\tilde{x}^T \tilde{A}^{-1} \tilde{x} となることを示せ。

题目描述​

以下 det⁡\det 表示行列式，记号 ATA^{\mathrm T} 表示矩阵 AA 的转置， A−1A^{-1} 表示其逆矩阵；题中所有矩阵、向量和标量的分量均为实数， n,m,ln,m,l 均为正整数。

可以使用如下分块逆矩阵公式：设 SS 为 m×mm\times m 矩阵，TT 为 m×lm\times l 矩阵， UU 为 l×ml\times m 矩阵，VV 为可逆的 l×ll\times l 矩阵。若

[STUV]和S−TV−1U\begin{bmatrix} S&T\\ U&V \end{bmatrix} \quad\text{和}\quad S-TV^{-1}U

均可逆，则

[STUV]−1=[(S−TV−1U)−1−(S−TV−1U)−1TV−1−V−1U(S−TV−1U)−1V−1+V−1U(S−TV−1U)−1TV−1].\begin{bmatrix} S&T\\ U&V \end{bmatrix}^{-1} = \begin{bmatrix} (S-TV^{-1}U)^{-1} & -(S-TV^{-1}U)^{-1}TV^{-1} \\[1mm] -V^{-1}U(S-TV^{-1}U)^{-1} & V^{-1} +V^{-1}U(S-TV^{-1}U)^{-1}TV^{-1} \end{bmatrix}.

回答下列问题。

  1. 设 AA 是可逆的 n×nn\times n 矩阵， b,c\boldsymbol{b},\boldsymbol{c} 是 nn 维列向量，dd 是标量。证明
det⁡[AbcTd]=(det⁡A)(d−cTA−1b).\det \begin{bmatrix} A&\boldsymbol{b}\\ \boldsymbol{c}^{\mathrm T}&d \end{bmatrix} = (\det A) \left( d-\boldsymbol{c}^{\mathrm T}A^{-1}\boldsymbol{b} \right).
  1. 设 n≥2n\geq2，AA 是 n×nn\times n 正定实对称矩阵。于是 A−1A^{-1} 也是正定实对称矩阵，并可写为
A−1=[αβTβΔ],A^{-1} = \begin{bmatrix} \alpha&\boldsymbol{\beta}^{\mathrm T}\\ \boldsymbol{\beta}&\Delta \end{bmatrix},

其中 α>0\alpha>0 是标量， β\boldsymbol{\beta} 是 (n−1)(n-1) 维列向量， Δ\Delta 是 (n−1)×(n−1)(n-1)\times(n-1) 矩阵。令 A~\widetilde{A} 为从 AA 删除第一行和第一列所得的 (n−1)×(n−1)(n-1)\times(n-1) 主子矩阵。证明

A~−1=Δ−ββTα.\widetilde{A}^{-1} = \Delta -\frac{\boldsymbol{\beta}\boldsymbol{\beta}^{\mathrm T}}{\alpha}.
  1. 在上一小问的条件下，令
x=[x1,x2,…,xn]T,x~=[x2,x3,…,xn]T.\boldsymbol{x} = [x_1,x_2,\ldots,x_n]^{\mathrm T}, \qquad \widetilde{\boldsymbol{x}} = [x_2,x_3,\ldots,x_n]^{\mathrm T}.

把二次型 xTA−1x\boldsymbol{x}^{\mathrm T}A^{-1}\boldsymbol{x} 视为关于 x1x_1 的二次函数，并保持 x~\widetilde{\boldsymbol{x}} 固定。证明它关于 x1x_1 的最小值为

x~TA~−1x~.\widetilde{\boldsymbol{x}}^{\mathrm T} \widetilde{A}^{-1} \widetilde{\boldsymbol{x}}.

Kai​

解答

(i) の証明

与えられた行列を M=[AbcTd]M = \begin{bmatrix} A & b \\ c^T & d \end{bmatrix} とする。 AA は正則（可逆）であるため、 A−1A^{-1} が存在する。 行列 MM を次のようにブロック行列の積で分解できる。

[AbcTd]=[A0cT1][IA−1b0d−cTA−1b]\begin{bmatrix} A & b \\ c^T & d \end{bmatrix} = \begin{bmatrix} A & 0 \\ c^T & 1 \end{bmatrix} \begin{bmatrix} I & A^{-1}b \\ 0 & d - c^T A^{-1} b \end{bmatrix}

この分解が正しいことを確認する：

[A0cT1][IA−1b0d−cTA−1b]=[A⋅I+0⋅0A(A−1b)+0⋅(d−cTA−1b)cT⋅I+1⋅0cT(A−1b)+1⋅(d−cTA−1b)]=[AbcTd]\begin{bmatrix} A & 0 \\ c^T & 1 \end{bmatrix} \begin{bmatrix} I & A^{-1}b \\ 0 & d - c^T A^{-1} b \end{bmatrix} = \begin{bmatrix} A \cdot I + 0 \cdot 0 & A(A^{-1}b) + 0 \cdot (d - c^T A^{-1} b) \\ c^T \cdot I + 1 \cdot 0 & c^T(A^{-1}b) + 1 \cdot (d - c^T A^{-1} b) \end{bmatrix} = \begin{bmatrix} A & b \\ c^T & d \end{bmatrix}

行列の積の行列式は、各行列の行列式の積に等しいので、

det⁡(M)=det⁡([A0cT1])×det⁡([IA−1b0d−cTA−1b])\det(M) = \det \begin{pmatrix} \begin{bmatrix} A & 0 \\ c^T & 1 \end{bmatrix} \end{pmatrix} \times \det \begin{pmatrix} \begin{bmatrix} I & A^{-1}b \\ 0 & d - c^T A^{-1} b \end{bmatrix} \end{pmatrix}

ブロック三角行列の行列式は、対角ブロックの行列式の積となる。

det⁡[A0cT1]=(det⁡A)×(det⁡1)=det⁡A\det \begin{bmatrix} A & 0 \\ c^T & 1 \end{bmatrix} = (\det A) \times (\det 1) = \det A
det⁡[IA−1b0d−cTA−1b]=(det⁡I)×det⁡(d−cTA−1b)=1×(d−cTA−1b)\det \begin{bmatrix} I & A^{-1}b \\ 0 & d - c^T A^{-1} b \end{bmatrix} = (\det I) \times \det(d - c^T A^{-1} b) = 1 \times (d - c^T A^{-1} b)

ここで、 d−cTA−1bd - c^T A^{-1} b はスカラー（ 1×11 \times 1 行列）なので、その行列式は値自身である。 したがって、

det⁡[AbcTd]=(det⁡A)×(d−cTA−1b)\det \begin{bmatrix} A & b \\ c^T & d \end{bmatrix} = (\det A) \times (d - c^T A^{-1} b)

が示された。

(ii) の証明

AA を n×nn \times n 正定値対称行列とする。 AA を次のように分割する。

A=[abTbA~]A = \begin{bmatrix} a & b^T \\ b & \tilde{A} \end{bmatrix}

ここで、 aa はスカラー、 bb は (n−1)(n-1) 次元の列ベクトル、 A~\tilde{A} は (n−1)×(n−1)(n-1) \times (n-1) の小行列である。 AA が正定値であるため、その主小行列 A~\tilde{A} も正定値であり、したがって正則である。

問題の冒頭で与えられたブロック行列の逆行列の公式を用いる。ここで S=aS=a , T=bTT=b^T , U=bU=b , V=A~V=\tilde{A} と対応させる。

A−1=[abTbA~]−1=[(a−bTA~−1b)−1−(a−bTA~−1b)−1bTA~−1−A~−1b(a−bTA~−1b)−1A~−1+A~−1b(a−bTA~−1b)−1bTA~−1]A^{-1} = \begin{bmatrix} a & b^T \\ b & \tilde{A} \end{bmatrix}^{-1} = \begin{bmatrix} (a-b^T\tilde{A}^{-1}b)^{-1} & -(a-b^T\tilde{A}^{-1}b)^{-1}b^T\tilde{A}^{-1} \\ -\tilde{A}^{-1}b(a-b^T\tilde{A}^{-1}b)^{-1} & \tilde{A}^{-1} + \tilde{A}^{-1}b(a-b^T\tilde{A}^{-1}b)^{-1}b^T\tilde{A}^{-1} \end{bmatrix}

与えられた A−1A^{-1} の分割形式と比較する。

A−1=[αβTβΔ]A^{-1} = \begin{bmatrix} \alpha & \beta^T \\ \beta & \Delta \end{bmatrix}

各ブロックを比較すると、

  1. α=(a−bTA~−1b)−1\alpha = (a-b^T\tilde{A}^{-1}b)^{-1}
  2. β=−A~−1b(a−bTA~−1b)−1=−αA~−1b\beta = -\tilde{A}^{-1}b(a-b^T\tilde{A}^{-1}b)^{-1} = -\alpha \tilde{A}^{-1}b
  3. Δ=A~−1+A~−1b(a−bTA~−1b)−1bTA~−1=A~−1+α(A~−1b)(bTA~−1)\Delta = \tilde{A}^{-1} + \tilde{A}^{-1}b(a-b^T\tilde{A}^{-1}b)^{-1}b^T\tilde{A}^{-1} = \tilde{A}^{-1} + \alpha (\tilde{A}^{-1}b)(b^T\tilde{A}^{-1})

式(2)より、 A~−1b=−1αβ\tilde{A}^{-1}b = -\frac{1}{\alpha}\beta となる。これを式(3)に代入する。

Δ=A~−1+α(−1αβ)(−1αβ)T=A~−1+α(−1αβ)(−1αβT)\Delta = \tilde{A}^{-1} + \alpha \left(-\frac{1}{\alpha}\beta\right) \left(-\frac{1}{\alpha}\beta\right)^T = \tilde{A}^{-1} + \alpha \left(-\frac{1}{\alpha}\beta\right) \left(-\frac{1}{\alpha}\beta^T\right)
Δ=A~−1+α1α2ββT=A~−1+ββTα\Delta = \tilde{A}^{-1} + \alpha \frac{1}{\alpha^2} \beta\beta^T = \tilde{A}^{-1} + \frac{\beta\beta^T}{\alpha}

この式を A~−1\tilde{A}^{-1} について解くと、

A~−1=Δ−ββTα\tilde{A}^{-1} = \Delta - \frac{\beta\beta^T}{\alpha}

が示された。

(iii) の証明

二次形式 Q(x)=xTA−1xQ(x) = x^T A^{-1} x を x1x_1 と x~\tilde{x} を用いて展開する。

x=[x1x~],A−1=[αβTβΔ]x = \begin{bmatrix} x_1 \\ \tilde{x} \end{bmatrix}, \quad A^{-1} = \begin{bmatrix} \alpha & \beta^T \\ \beta & \Delta \end{bmatrix}
Q(x)=[x1x~T][αβTβΔ][x1x~]Q(x) = \begin{bmatrix} x_1 & \tilde{x}^T \end{bmatrix} \begin{bmatrix} \alpha & \beta^T \\ \beta & \Delta \end{bmatrix} \begin{bmatrix} x_1 \\ \tilde{x} \end{bmatrix}
=[x1x~T][αx1+βTx~βx1+Δx~]= \begin{bmatrix} x_1 & \tilde{x}^T \end{bmatrix} \begin{bmatrix} \alpha x_1 + \beta^T \tilde{x} \\ \beta x_1 + \Delta \tilde{x} \end{bmatrix}
=x1(αx1+βTx~)+x~T(βx1+Δx~)= x_1(\alpha x_1 + \beta^T \tilde{x}) + \tilde{x}^T(\beta x_1 + \Delta \tilde{x})
=αx12+x1βTx~+x~Tβx1+x~TΔx~= \alpha x_1^2 + x_1\beta^T \tilde{x} + \tilde{x}^T\beta x_1 + \tilde{x}^T\Delta\tilde{x}

x1βTx~x_1\beta^T \tilde{x} はスカラーなので、その転置 x~Tβx1\tilde{x}^T\beta x_1 と等しい。したがって、

Q(x)=αx12+2(βTx~)x1+x~TΔx~Q(x) = \alpha x_1^2 + 2(\beta^T \tilde{x})x_1 + \tilde{x}^T\Delta\tilde{x}

この式は、 x1x_1 に関する二次関数である。 AA が正定値なので、 A−1A^{-1} も正定値であり、その主小行列である α\alpha は α>0\alpha > 0 である。したがって、この二次関数は下に凸の放物線であり、最小値を持つ。

最小値は、この二次関数を x1x_1 で微分して 0 とおくことで見つけられる。

∂Q(x)∂x1=2αx1+2(βTx~)=0\frac{\partial Q(x)}{\partial x_1} = 2\alpha x_1 + 2(\beta^T \tilde{x}) = 0

これを解くと、最小値を与える x1x_1 の値 x1∗x_1^* は、

x1∗=−βTx~αx_1^* = -\frac{\beta^T \tilde{x}}{\alpha}

となる。 この x1∗x_1^* を Q(x)Q(x) の式に代入して最小値を計算する。

min⁡x1Q(x)=α(−βTx~α)2+2(βTx~)(−βTx~α)+x~TΔx~\min_{x_1} Q(x) = \alpha \left(-\frac{\beta^T \tilde{x}}{\alpha}\right)^2 + 2(\beta^T \tilde{x})\left(-\frac{\beta^T \tilde{x}}{\alpha}\right) + \tilde{x}^T\Delta\tilde{x}
=α(βTx~)2α2−2(βTx~)2α+x~TΔx~= \alpha \frac{(\beta^T \tilde{x})^2}{\alpha^2} - 2\frac{(\beta^T \tilde{x})^2}{\alpha} + \tilde{x}^T\Delta\tilde{x}
=(βTx~)2α−2(βTx~)2α+x~TΔx~= \frac{(\beta^T \tilde{x})^2}{\alpha} - 2\frac{(\beta^T \tilde{x})^2}{\alpha} + \tilde{x}^T\Delta\tilde{x}
=−(βTx~)2α+x~TΔx~= -\frac{(\beta^T \tilde{x})^2}{\alpha} + \tilde{x}^T\Delta\tilde{x}

ここで、 (βTx~)2=(x~Tβ)(βTx~)=x~T(ββT)x~(\beta^T \tilde{x})^2 = (\tilde{x}^T \beta)(\beta^T \tilde{x}) = \tilde{x}^T (\beta\beta^T) \tilde{x} と書けるので、

min⁡x1Q(x)=x~TΔx~−x~TββTx~α=x~T(Δ−ββTα)x~\min_{x_1} Q(x) = \tilde{x}^T\Delta\tilde{x} - \frac{\tilde{x}^T\beta\beta^T\tilde{x}}{\alpha} = \tilde{x}^T \left( \Delta - \frac{\beta\beta^T}{\alpha} \right) \tilde{x}

設問 (ii) の結果から、 A~−1=Δ−ββTα\tilde{A}^{-1} = \Delta - \frac{\beta\beta^T}{\alpha} である。 したがって、二次形式の最小値は、

min⁡x1xTA−1x=x~TA~−1x~\min_{x_1} x^T A^{-1} x = \tilde{x}^T \tilde{A}^{-1} \tilde{x}

となり、題意は示された。

本页目录