ヴァンデルモンド行列式｜公式と証明

各行が等比数列になっている行列をヴァンデルモンド行列といいます。第 $i$ 行は $1,x_i,x_i^2,\dots$ と並びます。

この行列の行列式は、成分をどれだけ増やしても、差の積というきれいな形に閉じます。

$$\det V=\prod _{i<j}(x_j-x_i)$$

$n$ 次なら $n(n-1)/2$ 個の差を掛けるだけです。展開すれば $n!$ 項ある式が、この形にまとまります。

<svg viewBox="0 0 460 220" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<text x="230" y="22" font-size="11" fill="#9a9a9a" text-anchor="middle">各行が 1 から始まる等比数列になっています</text>
	<rect x="80" y="45" width="200" height="130" fill="none" stroke="#c8c8c8" stroke-width="1"></rect>
	<text x="110" y="75" font-size="13" fill="#1f1f1f" text-anchor="middle">1</text>
	<text x="170" y="75" font-size="13" fill="#1b81e0" text-anchor="middle">x<tspan font-size="9" dy="3">1</tspan></text>
	<text x="240" y="75" font-size="13" fill="#1b81e0" text-anchor="middle">x<tspan font-size="9" dy="3">1</tspan><tspan font-size="9" dy="-7">2</tspan></text>
	<text x="110" y="115" font-size="13" fill="#1f1f1f" text-anchor="middle">1</text>
	<text x="170" y="115" font-size="13" fill="#1b81e0" text-anchor="middle">x<tspan font-size="9" dy="3">2</tspan></text>
	<text x="240" y="115" font-size="13" fill="#1b81e0" text-anchor="middle">x<tspan font-size="9" dy="3">2</tspan><tspan font-size="9" dy="-7">2</tspan></text>
	<text x="110" y="155" font-size="13" fill="#1f1f1f" text-anchor="middle">1</text>
	<text x="170" y="155" font-size="13" fill="#1b81e0" text-anchor="middle">x<tspan font-size="9" dy="3">3</tspan></text>
	<text x="240" y="155" font-size="13" fill="#1b81e0" text-anchor="middle">x<tspan font-size="9" dy="3">3</tspan><tspan font-size="9" dy="-7">2</tspan></text>
	<line x1="295" y1="110" x2="330" y2="110" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="333,110 324,106 324,114" fill="#9a9a9a"></polygon>
	<text x="398" y="98" font-size="12" fill="#1f1f1f" text-anchor="middle">(x2 - x1)(x3 - x1)</text>
	<text x="398" y="122" font-size="12" fill="#1f1f1f" text-anchor="middle">(x3 - x2) を掛ける</text>
	<text x="230" y="200" font-size="11" fill="#9a9a9a" text-anchor="middle">行列式は、すべての組の差を掛け合わせた形になります</text>
</svg>

ヴァンデルモンド行列とは

$n$ 個の数 $x_1,\dots ,x_n$ を並べて、第 $i$ 行に $x_i$ の $0$ 乗から $n-1$ 乗までを置いた行列です。

$$V=\left(\begin{array}{ccccc}1& x_1& x_1^2& \cdots & x_1^{n-1}\\ 1& x_2& x_2^2& \cdots & x_2^{n-1}\\ ⋮& ⋮& ⋮& & ⋮\\ 1& x_n& x_n^2& \cdots & x_n^{n-1}\end{array}\right)$$

転置した形で定義する流儀もあります。行列式は転置で変わらないので、公式はどちらでも同じです。

$x_i$ を節点と呼びます。多項式にいくつかの点で値を指定する場面から自然に現れる行列です。

行列式の公式

行列式は、節点のすべての組についての差の積になります。

$$\det V=\prod _{1\le i<j\le n}(x_j-x_i)$$

$3$ 次なら 3 個、$4$ 次なら 6 個の差を掛けます。掛ける順序は $j>i$ に固定しておかないと、符号が変わってしまいます。

例：3 次で確かめる

節点を $1$、$2$、$3$ とします。

$$V=\left(\begin{array}{ccc}1& 1& 1\\ 1& 2& 4\\ 1& 3& 9\end{array}\right)$$

サラスの方法で計算します。右下がりは $18$、$4$、$3$ で合計 $25$、右上がりは $2$、$12$、$9$ で合計 $23$ です。

差は $2$ になります。公式のほうは $(2-1)(3-1)(3-2)=1\cdot 2\cdot 1=2$ で、一致しています。

例：符号が混ざる場合

節点を $2$、$5$、$-1$ の順に取ります。順序を変えても公式は同じ形です。

$$V=\left(\begin{array}{ccc}1& 2& 4\\ 1& 5& 25\\ 1& -1& 1\end{array}\right)$$

公式に入れると $(5-2)(-1-2)(-1-5)=3\cdot (-3)\cdot (-6)=54$ です。

負の差が 2 つあるので、掛け合わせると正に戻ります。行列式を直接計算しても $54$ になります。

例：4 次では差が 6 個になる

節点を $1$、$2$、$3$、$4$ とします。差の組は $6$ 通りです。

$$(2-1)(3-1)(4-1)(3-2)(4-2)(4-3)=1\cdot 2\cdot 3\cdot 1\cdot 2\cdot 1=12$$

$4$ 次の行列式を定義どおりに展開すれば $24$ 項ありますが、答は $12$ という小さな数にまとまります。

節点が等間隔なら、差の積は階乗の積の形になります。$1$ から $n$ までを節点に取ると、$\det V=1!\cdot 2!\cdots (n-1)!$ です。

0 になるのは同じ節点があるとき

差の積なので、$\det V=0$ となるのは、どれか 2 つの節点が等しいときに限られます。

そのとき行列には同じ行が 2 つ並びます。行列式が $0$ になるのは当然です。

裏を返せば、節点がすべて異なれば $V$ は正則です。この言い換えが、あとで補間の話につながります。

証明：多項式と見て根を数える

$x_n$ だけを変数 $t$ と見て、$\det V$ を $t$ の多項式として扱います。最後の行だけに $t$ が入るので、次数は $n-1$ 以下です。

$t=x_1,\dots ,x_{n-1}$ のいずれかに一致すると、同じ行が 2 つできて行列式は $0$ になります。$n-1$ 個の根が分かったことになります。

したがって $(t-x_1)\cdots (t-x_{n-1})$ で割り切れます。次数が $n-1$ なので、残りは定数倍です。

その定数は $t^{n-1}$ の係数で、余因子展開すると $n-1$ 次のヴァンデルモンド行列式そのものです。あとは帰納法で結論が出ます。

証明：列を引いて次数を落とす

もうひとつの筋は、列に手を入れる方法です。右の列から順に、ひとつ左の列の $x_1$ 倍を引きます。

第 1 行はすべて $0$ になり、左上の $1$ だけが残ります。ほかの行では、第 $j$ 列に $x_i^{j-2}(x_i-x_1)$ が並びます。

各行から共通因数 $(x_i-x_1)$ をくくり出すと、$n-1$ 次のヴァンデルモンド行列が現れます。ここでも帰納法が使えます。

例：3 次で列操作をなぞる

節点 $1$、$2$、$3$ の行列で実際にやってみます。第 3 列から第 2 列の $1$ 倍を、第 2 列から第 1 列の $1$ 倍を引きます。

$$\left(\begin{array}{ccc}1& 1& 1\\ 1& 2& 4\\ 1& 3& 9\end{array}\right)\to \left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 2\\ 1& 2& 6\end{array}\right)$$

第 1 行で展開すると、右下の 2 次の行列式だけが残ります。値は $6-4=2$ です。

その 2 次の行列は、第 1 行が $1\cdot (1,2)$、第 2 行が $2\cdot (1,3)$ という形をしています。共通因数 $1$ と $2$ をくくり出せば、節点 $2$、$3$ のヴァンデルモンド行列が出てきます。

くくり出した $1\cdot 2$ が $(x_2-x_1)(x_3-x_1)$ に、残った行列式 $3-2$ が $(x_3-x_2)$ にあたります。

多項式補間との対応

$n$ 個の点 $(x_i,y_i)$ を通る $n-1$ 次以下の多項式を探します。係数を $a_0,\dots ,a_{n-1}$ と置くと、条件は連立一次方程式になります。

$$Va=y$$

この係数行列がヴァンデルモンド行列です。節点がすべて異なれば正則なので、解がただ一つ決まります。

$n$ 点を通る $n-1$ 次以下の多項式が一通りに決まる、という事実の中身がこれです。

例：3 点を通る 2 次式を求める

点 $(1,1)$、$(2,3)$、$(3,7)$ を通る 2 次以下の多項式を求めます。

$$\left(\begin{array}{ccc}1& 1& 1\\ 1& 2& 4\\ 1& 3& 9\end{array}\right)\left(\begin{array}{c}{a}_0\\ a_1\\ a_2\end{array}\right)=\left(\begin{array}{c}1\\ 3\\ 7\end{array}\right)$$

第 2 式から第 1 式を引くと $a_1+3a_2=2$、第 3 式から第 2 式を引くと $a_1+5a_2=4$ です。

差を取って $a_2=1$、そこから $a_1=-1$、$a_0=1$ が決まります。求める多項式は $p(x)=x^2-x+1$ です。

$x=1,2,3$ を入れると $1$、$3$、$7$ に戻ります。係数行列の行列式が $2$ で $0$ でなかったので、この答以外にはありません。

<svg viewBox="0 0 460 220" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<text x="230" y="22" font-size="11" fill="#9a9a9a" text-anchor="middle">3 点を通る 2 次以下の多項式は、ただ 1 つに決まります</text>
	<line x1="70" y1="190" x2="410" y2="190" stroke="#c8c8c8" stroke-width="1"></line>
	<line x1="80" y1="40" x2="80" y2="195" stroke="#c8c8c8" stroke-width="1"></line>
	<polyline points="91,177 133,173 176,163 219,147 261,126 304,100 347,68 368,49" fill="none" stroke="#1b81e0" stroke-width="1.5"></polyline>
	<circle cx="133" cy="173" r="3.5" fill="#1f1f1f"></circle>
	<circle cx="240" cy="138" r="3.5" fill="#1f1f1f"></circle>
	<circle cx="347" cy="68" r="3.5" fill="#1f1f1f"></circle>
	<text x="133" y="207" font-size="11" fill="#9a9a9a" text-anchor="middle">1</text>
	<text x="240" y="207" font-size="11" fill="#9a9a9a" text-anchor="middle">2</text>
	<text x="347" y="207" font-size="11" fill="#9a9a9a" text-anchor="middle">3</text>
	<text x="152" y="170" font-size="11" fill="#1f1f1f">(1, 1)</text>
	<text x="252" y="135" font-size="11" fill="#1f1f1f">(2, 3)</text>
	<text x="300" y="60" font-size="11" fill="#1f1f1f">(3, 7)</text>
	<text x="392" y="60" font-size="11" fill="#1b81e0" text-anchor="end">y = x² - x + 1</text>
</svg>

例：ラグランジュ基底で同じ答を出す

連立方程式を解くかわりに、基底を先に作る道もあります。節点 $1$、$2$、$3$ に対する基底は次の 3 つです。

$$L_1(x)=\frac{(x-2)(x-3)}{2},L_2(x)=-(x-1)(x-3),L_3(x)=\frac{(x-1)(x-2)}{2}$$

それぞれ、自分の節点で $1$、ほかの節点で $0$ になります。$L_1(1)=\frac{(-1)(-2)}{2}=1$、$L_1(2)=0$ という具合です。

値を重みにして足します。

$$p(x)=1\cdot L_1(x)+3\cdot L_2(x)+7\cdot L_3(x)$$

展開すると $x^2-x+1$ になり、さきほどと同じ答です。$x^2$ の係数は $\frac{1}{2}-3+\frac{7}{2}=1$ と数えられます。

例：節点が重なると解けなくなる

節点を $1$、$2$、$1$ と取ってしまった場合を見ます。公式の差の積に $(1-1)$ が現れるので、行列式は $0$ です。

第 1 行と第 3 行が同じ並びになっているので、これは当たり前です。

$x=1$ での値を 2 通り指定してしまえば、そもそも問題として無理があります。異なる値を指定すれば解なし、同じ値なら解が無数にあります。

逆行列とラグランジュ基底

$V$ の逆行列の列には、ラグランジュ基底多項式の係数が並びます。

$$L_j(x)=\prod _{i\ne j}\frac{x-x_i}{x_j-x_i}$$

$L_j$ は $x_j$ で $1$、ほかの節点で $0$ になる多項式です。補間多項式は ${\sum }_j{y}_j{L}_j(x)$ と書けます。

連立方程式を解く道と、基底を先に作る道は、同じ答に行き着きます。逆行列を明示的に書き下したものがラグランジュの公式だと見られます。

数値計算では条件数が悪い

理論の上ではきれいですが、数値計算では扱いにくい行列です。節点の数が増えると条件数が急に大きくなり、桁落ちが起きます。

原因は基底の選び方にあります。$1,x,x^2,\dots$ は互いに似た形をしていて、区別がつきにくくなるからです。

実際の補間では、ニュートンの差分商やラグランジュの形で直接組み立てます。ヴァンデルモンド行列を作って解く方法は、次数が上がると避けられます。

例：節点が近いと行列式が急に小さくなる

節点を $1$、$1.01$、$1.02$ と、ごく近くに取ってみます。

差はそれぞれ $0.01$、$0.02$、$0.01$ です。積を取ると $2\times 10^{-6}$ になります。

成分はどれも $1$ の近くにあり、行列そのものは小さくも大きくもありません。それでも行列式だけが極端に小さくなります。

節点の間隔が $10$ 分の $1$ になると、$3$ 次では行列式が $1000$ 分の $1$ になります。逆行列の成分はその逆数で効くので、わずかな誤差が大きく増幅されます。

節点が重なるときの拡張

同じ節点で値と微分係数を指定したい場合には、合流型と呼ばれる拡張があります。重なった行を、微分した行に置き換える形です。

こうすると行列式は $0$ にならず、エルミート補間の問題が解けるようになります。もとの公式も、極限の形で引き継がれます。

他の話題とのつながり

離散フーリエ変換の行列は、節点を $1$ の $n$ 乗根に取ったヴァンデルモンド行列です。差の積が $0$ にならないことが、変換が可逆であることを保証します。

行列式の計算そのものは余因子展開やサラスの方法の記事に、$3$ 次までの具体的な計算はそちらにあります。連立方程式の可解性は、連立一次方程式の解の構造の記事とつながります。

よくある誤り

参考文献