Sherman–Morrisonの公式

前提知識: 正則行列, 行列式

$A=\begin{pmatrix}2&1\\1&1\end{pmatrix}$ の逆行列は $A^{-1}=\begin{pmatrix}1&-1\\-1&2\end{pmatrix}$ である。左上の成分だけを $2$ から $3$ に変えた行列 $A'=\begin{pmatrix}3&1\\1&1\end{pmatrix}$ の逆行列を、最初から計算し直さずに $A^{-1}$ から求められるだろうか。$A'=A+e_1e_1^{\top}$（$e_1=(1,0)^{\top}$）と書くと、変化分 $e_1e_1^{\top}$ は階数 $1$ の行列である。このような「階数 $1$ の修正」について、次の公式が成り立つ：$A$ が正則で $1+v^{\top}A^{-1}u\ne0$ なら
$$ (A+uv^{\top})^{-1}=A^{-1}-\frac{A^{-1}u\,v^{\top}A^{-1}}{1+v^{\top}A^{-1}u} $$
である。これが Sherman–Morrison の公式 である。上の例では $1+e_1^{\top}A^{-1}e_1=2$、$A^{-1}e_1=(1,-1)^{\top}$ なので
$$ A'^{-1}=\begin{pmatrix}1&-1\\-1&2\end{pmatrix}-\frac12\begin{pmatrix}1&-1\\-1&1\end{pmatrix}=\frac12\begin{pmatrix}1&-1\\-1&3\end{pmatrix} $$
となる。$n$ 次の行列の逆行列を一から求めるには $n^3$ 程度の演算が要るが、この公式なら $A^{-1}$ から $n^2$ 程度の演算で済む。この記事では、行列式の補題、公式とその正則性の判定、Cramer の公式との関係、階数 $k$ の修正への一般化（Woodbury の公式）、正定値行列の修正を証明する。

記号

以下、$K$ は体とし、$K^n$ の元は列ベクトルとする。$u,v\in K^n$ に対し、$uv^{\top}\in M_n(K)$ は $(i,j)$ 成分が $u_iv_j$ の行列で、$u\ne0$ かつ $v\ne0$ なら階数 $1$、そうでなければ零行列である。$v^{\top}u=\sum_iv_iu_i\in K$ はスカラーである。$e_j$ は第 $j$ 成分だけが $1$ の基本ベクトル、$I_n$ は単位行列である。

主定理

まず、階数の小さい修正で行列式がどう変わるかを調べる。

1 の「$\sigma=0$ なら正則でない」は、行列式を使わずにも分かる：$\sigma=0$ なら $1+v^{\top}A^{-1}u=0$ なので $u\ne0$、したがって $x:=A^{-1}u\ne0$ であり、
$$ (A+uv^{\top})x=u+u\,(v^{\top}A^{-1}u)=\sigma u=0 $$
となって、$A+uv^{\top}$ は $0$ でない元を $0$ に写す。

直感と計算量

$A=I_n$、$u=w$ の場合を考えると、公式は $(I_n+wv^{\top})^{-1}=I_n-\frac{wv^{\top}}{1+v^{\top}w}$ である。これは、等比級数 $\frac1{1+t}=1-t+t^2-\cdots$ を形式的に行列に当てはめた
$$ (I_n+wv^{\top})^{-1}=I_n-wv^{\top}+wv^{\top}wv^{\top}-\cdots=I_n-w\bigl(1-v^{\top}w+(v^{\top}w)^2-\cdots\bigr)v^{\top} $$
で、$wv^{\top}wv^{\top}=(v^{\top}w)\,wv^{\top}$ のように積がスカラー $t=v^{\top}w$ の冪にまとまることから予想できる（級数の収束は問わない。この計算は公式を見つける手がかりで、証明は thm-sm-main の掛け算である）。一般の $A$ では $A+uv^{\top}=A(I_n+A^{-1}uv^{\top})$ と分ければこの場合に帰着する。
$A^{-1}$ が分かっているとき、$x:=A^{-1}u$ と $y^{\top}:=v^{\top}A^{-1}$ の計算はそれぞれ $n^2$ 回程度の掛け算、$\sigma=1+v^{\top}x$ は $n$ 回、$A^{-1}-\frac1\sigma xy^{\top}$ は $n^2$ 回程度である。連立 1 次方程式 $(A+uv^{\top})z=b$ を解くだけなら、$A$ についての方程式 $Ap=b$、$Ax=u$ を解いて
$$ z=p-\frac{v^{\top}p}{\sigma}\,x $$
とすればよい（両辺に $A+uv^{\top}$ を掛けると $b+u\,v^{\top}p-\frac{v^{\top}p}{\sigma}\sigma u=b$）。$A$ が対角行列や三角行列のように解きやすい行列なら、$A+uv^{\top}$ が密な行列でも速く解ける。

特別な場合と例

冒頭の例は $i=j=1$、$t=1$、$b_{11}=1$ の場合である。逆に、$A$ の $(1,2)$ 成分に $1$ を足すと（$i=1$、$j=2$）、$1+b_{21}=1+(-1)=0$ なので、$A+e_1e_2^{\top}=\begin{pmatrix}2&2\\1&1\end{pmatrix}$ は正則でない。

階数 $k$ の修正：Woodbury の公式

$u,v$ をそれぞれ $k$ 本並べると、階数 $k$ 以下の修正について同じ形の公式が得られる。

$k=1$ が thm-sm-main である。thm-sm-woodbury を使うと、$n$ 次の逆行列の修正が $k$ 次の逆行列 $S^{-1}$ の計算に帰着する。$k$ が $n$ より小さいときに有効である。同じ公式は、区分けした行列の Schur 補行列を 2 通りに作って比べることでも得られる（ブロック行列 の記事の系「行列式の補題」、Schur補行列）。階数 $k$ の修正を階数 $1$ の修正 $k$ 回に分けて thm-sm-main を繰り返し使ってもよいが、途中の行列が正則でなくなることがあり（たとえば $I_2$ に $-e_1e_1^{\top}$ と $+e_1e_1^{\top}$ を順に足すと、最後の行列 $I_2$ は正則だが途中の $\begin{pmatrix}0&0\\0&1\end{pmatrix}$ は正則でない）、そこから先は ex-sm-counterexamples の 2 行目のように公式が使えない。一度に扱う thm-sm-woodbury の方が条件が簡明である。

正定値行列の修正

実対称な正定値行列（正定値行列）に $uu^{\top}$ を足したり引いたりすると、正定値性は次のように変わる。

2 の境目 $s=1$ では、$\det(A-uu^{\top})=(1-s)\det A=0$ である（lem-sm-det の 2）。

応用

• 逐次最小二乗法：データ $(a_t,b_t)$（$a_t\in\mathbb{R}^n$）が 1 つずつ届くとき、最小二乗法 の正規方程式の係数行列は $G_t=G_{t-1}+a_ta_t^{\top}$ と更新される。$G_{t-1}$ が正定値なら、prop-sm-pd の 1 により $G_t^{-1}$ を $G_{t-1}^{-1}$ から $n^2$ 程度の演算で更新でき、毎回 $n$ 次の方程式を解き直さずに済む。
• 準 Newton 法：Broyden の方法は、近似 Jacobi 行列を毎回階数 $1$ の行列で修正する。その逆行列の更新に thm-sm-main が使われる（準Newton法 の記事の命題「逆行列の更新」）。

条件を外した反例

補足

関連項目

• 前提: 正則行列, 行列式
• 比較: ブロック行列, Schur補行列, Cramerの公式
• 直後に読む: 正定値行列, 最小二乗法, 準Newton法
• 発展: Moore–Penrose逆行列