NTTデータ数理システム新卒採用試験＜数学＞問題紹介 第五回 ～線形代数～

※試験の設定は2023年度時点の情報であり、2024年度以降は変更の可能性があります。試験内容についてはエントリーされた方にお送りする情報をご確認ください。

こんにちは、シミュレーション & マイニング部の高橋と申します。昨年に引き続き、当社の入社試験問題を紹介する企画の第五回です。今年度はこの記事のみの予定です。

入社試験問題例

2023年度に出題した問題の中から、私が担当した線形代数の問題を紹介します。

問題.
$m$, $n$ を正の整数、$M\in\mathbb{R}^{m\times n}$ とするとき、$MM^{-}M=M$ を満たす $M^{-}\in\mathbb{R}^{n\times m}$ を $M$ の一般化逆行列と呼ぶ。一般化逆行列は常に存在する（一意とは限らない）。
$p$, $q$ を正の整数、$A\in\mathbb{R}^{p\times p}$, $B\in\mathbb{R}^{p\times q}$, $D\in\mathbb{R}^{q\times q}$（ただし $A$, $D$ は対称行列）、
$G\coloneqq D-B^{T}A^{-}B\in\mathbb{R}^{q\times q}$、ブロック行列 $N\coloneqq\begin{pmatrix} A & B\\ B^{T} & D \end{pmatrix}\in\mathbb{R}^{(p+q)\times (p+q)}$ とおく。  
また、ある $H\in\mathbb{R}^{p\times q}$ が存在して $B=AH$ が成り立つとする。  
この設定のもと以下の問いに答えよ。
(1) 次の等式を示せ。
                                    $N=\begin{pmatrix}I_{p} & O_{p\times q}\\B^{T}A^{-} & I_{q}\end{pmatrix}\begin{pmatrix}A & O_{p\times q}\\O_{q\times p} & G\end{pmatrix}\begin{pmatrix}I_{p} & A^{-}B\\O_{q\times p} & I_{q}\end{pmatrix}.$
      ただし $p\times p$ の単位行列を $I_{p}$、$p\times q$ の零行列を $O_{p\times q}$ などと表記した。
(2) $\begin{pmatrix}I_{p} & O_{p\times q}\\B^{T}A^{-} & I_{q}\end{pmatrix}^{-1},\begin{pmatrix}I_{p} & A^{-}B\\O_{q\times p} & I_{q}\end{pmatrix}^{-1}$ を求めよ。結果のみでよい。
(3) $N^{-}$ のひとつを $A$, $B$, $G$ およびそれらの一般化逆行列で表される4成分を持つブロック行列として求めよ。
                                                                               (2023年度 株式会社NTTデータ数理システム 入社試験問題)

この問題の背景には、後述の一般ガウス=マルコフモデルがあります。まずは問題の解答を示し、次に問題背景について見ていきましょう。
なお、この問題は行列の扱いに慣れている人向けの問題で、実際の試験では複数問のうち2問を選択して解けばよいので、行列が苦手だという方も心配ご無用です。

解答

(1)
右辺から計算する。
$\begin{pmatrix}I_{p} & O_{p\times q}\\B^{T}A^{-} & I_{q}\end{pmatrix}\begin{pmatrix}A & O_{p\times q}\\O_{q\times p} & G\end{pmatrix}\begin{pmatrix}I_{p} & A^{-}B\\O_{q\times p} & I_{q}\end{pmatrix}=\begin{pmatrix} A & AA^{-}B\\B^{T}A^{-}A & B^{T}A^{-}AA^{-}B+G\end{pmatrix}.$
ここで以下が成立：
$AA^{-}B=AA^{-}AH=AH=B$,
$B^{T}A^{-}A=(AH)^{T}A^{-}A=H^{T}A^{T}A^{-}A=H^{T}AA^{-}A=H^{T}A=H^{T}A^{T}=(AH)^{T}=B^{T}$,
$B^{T}A^{-}AA^{-}B=B^{T}A^{-}(AA^{-}B)=B^{T}A^{-}B$.
よって、$\begin{pmatrix}I_{p} & O_{p\times q}\\B^{T}A^{-} & I_{q}\end{pmatrix}\begin{pmatrix}A & O_{p\times q}\\O_{q\times p} & G\end{pmatrix}\begin{pmatrix}I_{p} & A^{-}B\\O_{q\times p} & I_{q}\end{pmatrix}=\begin{pmatrix}A & B\\ B^{T} & D\end{pmatrix}=N.$

(2)
対角ブロックをそれぞれ単位行列と仮置きして、非対角ブロックを求めればよい。 
$\begin{pmatrix}I_{p} & O_{p\times q}\\B^{T}A^{-} & I_{q}\end{pmatrix}^{-1}=\begin{pmatrix}I_{p} & O_{p\times q}\\-B^{T}A^{-} & I_{q}\end{pmatrix},\begin{pmatrix}I_{p} & A^{-}B\\O_{q\times p} & I_{q}\end{pmatrix}^{-1}=\begin{pmatrix}I_{p} & -A^{-}B\\O_{q\times p} & I_{q}\end{pmatrix}.$

(3)
$R,S,T\in\mathbb{R}^{(p+q)\times (p+q)}$ （$R$, $T$：正則）とする。  
このとき、$(RST)(T^{-1}S^{-}R^{-1})(RST)=RSS^{-}ST=RST$ より、 $T^{-1}S^{-}R^{-1}$ は $(RST)^{-}$ のひとつ。
また、$\begin{pmatrix}A & O_{p\times q}\\O_{q\times p} & G\end{pmatrix}\begin{pmatrix}A^{-} & O_{p\times q}\\O_{q\times p} & G^{-}\end{pmatrix}\begin{pmatrix}A & O_{p\times q}\\O_{q\times p} & G\end{pmatrix}=\begin{pmatrix}AA^{-}A & O_{p\times q}\\O_{q\times p} & GG^{-}G\end{pmatrix}=\begin{pmatrix}A & O_{p\times q}\\O_{q\times p} & G\end{pmatrix}$
より、$\begin{pmatrix}A^{-} & O_{p\times q}\\O_{q\times p} & G^{-}\end{pmatrix}$ は $\begin{pmatrix}A & O_{p\times q}\\O_{q\times p} & G\end{pmatrix}^{-}$ のひとつ。  
以上より、$N^{-}$ のひとつは
$\begin{pmatrix}I_{p} & A^{-}B\\O_{q\times p} & I_{q}\end{pmatrix}^{-1}\begin{pmatrix}A^{-} & O_{p\times q}\\O_{q\times p} & G^{-}\end{pmatrix}\begin{pmatrix}I_{p} & O_{p\times q}\\B^{T}A^{-} & I_{q}\end{pmatrix}^{-1}$
$=\begin{pmatrix}I_{p} & -A^{-}B\\O_{q\times p} & I_{q}\end{pmatrix}\begin{pmatrix}A^{-} & O_{p\times q}\\O_{q\times p} & G^{-}\end{pmatrix}\begin{pmatrix}I_{p} & O_{p\times q}\\-B^{T}A^{-} & I_{q}\end{pmatrix}$
$=\begin{pmatrix}A^{-}+A^{-}BG^{-}B^{T}A^{-} & -A^{-}BG^{-}\\ -G^{-}B^{T}A^{-} & G^{-}\end{pmatrix}.$

問題背景

ここからは数理統計学に詳しい学生さん向けの内容となりますが、興味のある方はぜひお読みください。
前述の通り、本問は一般ガウス=マルコフモデルと関係があります。
このモデルの母数推定問題に一般化逆行列の性質が応用可能であることをご紹介します。
まず、一般ガウス=マルコフモデルを導入します。

 $p$ 個の目的変数 $Y_{i}(i = 1,\dots,p)$ をそれぞれ $q$ 個の説明変数 $X_{i,j}(j = 1,\dots,q)$ と未知母数 $\beta_{j}(j = 1,\dots,q)$ の線形結合および誤差項 $\varepsilon _{i}$ の和で表す。
これは $\bm{Y}\coloneqq(Y_{1},\dots,Y_{p})^{T}$, $\bm{X}\coloneqq\{X_{i,j}\}_{i,j}$, $\bm{\beta}\coloneqq(\beta_{1},\dots,\beta_{q})^{T}$, $\bm{\epsilon}\coloneqq(\epsilon_{1},\dots,\epsilon_{p})^{T}$
とおけば、$\bm{Y}=\bm{X\beta}+\bm{\epsilon}$ と書ける。
ただし、$\bm{\epsilon}$ に以下の仮定をおく：
$\sigma^{2} >0$：未知母数、$\bm{J}\in\mathbb{R}^{p\times p}$：対称・各要素は非負実数 について
$\rm{E}[\bm{\epsilon}]=\bm{O}_{p\times 1}$, $\rm{Cov}[\bm{\epsilon}, \bm{\epsilon}]=\sigma^{2}\bm{J}$.

このモデルを一般ガウス=マルコフモデルと呼び、$(\bm{Y},\bm{X\beta},{\sigma}^{2}\bm{J})$ と表記します。
これを見て重回帰分析の設定を思い出した方も多いと思います。
これは正しく、通常の重回帰分析で扱うモデルは、ガウス=マルコフモデルと呼ばれ、一般ガウス=マルコフモデルで $\bm{X}$ をフルランク、$\bm{J}=I_{p}$ としたもの：$(\bm{Y},\bm{X\beta},{\sigma}^{2}I_{p})$ に相当します。
逆に、一般ガウス=マルコフモデルは、ガウス=マルコフモデルを $\bm{X}$ のランク落ちや $\{\epsilon_{i}\}_{i}$ が相関を持つことなどを許容して一般化したものに相当します。

さて、この一般ガウス=マルコフモデルの母数推定問題に対して、一般化逆行列の性質が応用可能であることをご紹介します。
以下の事実が知られています。

一般ガウス=マルコフモデル $(\bm{Y},\bm{X\beta},{\sigma}^{2}\bm{J})$ を考える。
$\bm{C_{1}}\in\mathbb{R}^{p\times p}$, $\bm{C_{2}}\in\mathbb{R}^{p\times q}$, $\bm{C_{3}}\in\mathbb{R}^{q\times p}$, $\bm{C_{4}}\in\mathbb{R}^{q\times q}$ について
                        $\begin{pmatrix}\bm{J} & \bm{X}\\ \bm{X}^{T} & \bm{O}_{q\times q}\end{pmatrix}^{-}=\begin{pmatrix}\bm{C_{1}} & \bm{C_{2}}\\ \bm{C_{3}} & -\bm{C_{4}}\end{pmatrix}$
が満たされるとする。このとき、以下の結果が成り立つ。
・ $\hat{\bm{\beta}}\coloneqq\bm{C_{3}}\bm{Y}=\bm{C_{2}}^{T}\bm{Y}$ とおく。
     また、$\bm{p}\in\mathbb{R}^{q\times 1}$ について $\bm{p}^{T}\bm{\beta}$ が推定可能である（すなわち線形不偏推定量を持つ）とする。
     このとき、$\bm{p}^{T}\bm{\beta}$ の最良線形不偏推定量は $\bm{p}^{T}\hat{\bm{\beta}}$ である。
・ $\bm{p},\bm{q}\in\mathbb{R}^{q\times 1}$ について $\bm{p}^{T}\bm{\beta}$, $\bm{q}^{T}\bm{\beta}$ が推定可能であるとする。
     このとき、$\hat{\bm{\beta}}$ の分散共分散行列は、次の式が成立するという意味で、$\sigma^{2}\bm{C_{4}}$ である。
     ・ $\rm{Cov}[\bm{p}^{T}\hat{\bm{\beta}}, \bm{q}^{T}\hat{\bm{\beta}}]=\sigma^{2}\bm{p}^{T}\bm{C_{4}}\bm{q}$.
・ $\rm{E}[\bm{Y}^{T}\bm{C_{1}Y}]=Tr(\bm{JC_{1}})\sigma^{2}$.

すなわち、$\bm{C_{1}}$, $\bm{C_{2}}$, $\bm{C_{3}}$, $\bm{C_{4}}$ さえ求まれば、最良線形不偏推定量、$\hat{\bm{\beta}}$ の分散共分散行列（と便宜的にみなせるもの）、$\sigma^{2}$ の不偏推定量 $\hat{\sigma}^{2}$ が構成できることになります。

この事実をガウス=マルコフモデルに適用してみます。
具体的には、$p>q$ の場合のガウス=マルコフモデル：$(\bm{Y},\bm{X\beta},{\sigma}^{2}I_{p})$ に対する上記推定量を考えることにします。（注：この設定では $\bm{X}$, $\bm{J}=I_{p}$ がフルランクであることから $\hat{\bm{\beta}}$ は一意に定まり、$\bm{\beta}$ の最良線形不偏推定量となります。また、$\hat{\bm{\beta}}$ の分散共分散行列も $\sigma^{2}\bm{C_{4}}$ と一意に定まります。）
ご興味のある方は計算し、以下の結果が導出できることをご確認ください。（$\bm{C_{1}}$, $\bm{C_{2}}$, $\bm{C_{3}}$, $\bm{C_{4}}$ の計算に本問(3)の結果を利用することができます。その際、本問の問題文で与えられている仮定が満たされていることも確認してみてください。） 
・ $\hat{\bm{\beta}}=(\bm{X}^{T}\bm{X})^{-1}\bm{XY}$,
・ $\rm{Cov}[\hat{\bm{\beta}}, \hat{\bm{\beta}}]=\sigma^{2}(\bm{X}^{T}\bm{X})^{-1}$,
・ $\hat{\sigma}^{2}=(p-q)^{-1}\bm{Y}^{T}(\bm{Y}-\bm{X}\hat{\bm{\beta}})=(p-q)^{-1}(\bm{Y}-\bm{X}\hat{\bm{\beta}})^{T}(\bm{Y}-\bm{X}\hat{\bm{\beta}})$.

応募者募集！

アカリク NTTデータ数理システム 求人情報ページ