[場所1E501（月曜日5限）]
HPに行く
manabaに行く
今回の数学外書輪講は
HPに行く
manabaに行く
今回の数学外書輪講は
- LangのVII 随伴写像
- Matousek の Miniature 7 (Are These Distances Euclidean?)
を読みました。
Are These Distances Euclidean?
正の実数の集合が、$n+1$ 次元ユークリッド空間の $n$ 面体の辺となりうる
ための実数の条件に関する問題です。
例えば、３つの正の実数 $x_1,x_2,x_3$ が与えられた時に、それが、平面上の
３角形の辺となるための必要十分条件は、
２辺の和は残りの１辺の和以上になるという不等式を満たす必要があります。
これを三角不等式といいます。これを具体的に式に書いておけば、
$$x_1+x_2\ge x_3,\ x_1+x_3\ge x_2,\ x_2+x_3\ge x_1$$
となります。
このことを高次元に一般化します。$n$ 次元ユークリッド空間 ${\mathbb R}^n$
の上に、$n+1$ 点 $p_0,p_1,\cdots ,p_n$ を与えて、その間の距離を
$m_{ij}=||p_i-p_j||$ が与えられたとするとき、$m_{ij}$ の取りうる必要十分条件は
どのように与えられるか？という問題です。
$n+1$ 面体の各３角形は存在しないといけませんから、もちろん３角不等式を
満たさないといけません。
しかし、$n\ge 3$ となると、その不等式だけでは十分では在りません。
Matousekの出した例では、
2,2,2,2,3,3 という６つの実数に対して、この数を各辺に持つような
四面体を ${\mathbb R}^3$ に実現することはできないことを述べています。
(もちろん、もっと次元が高いユークリッド空間でもできません。)
しかし、この6つの数は、どの３つを取っても三角不等式を満たしています。
よって、そのような必要十分条件は、以下のようになります。
定理
$||p_i-p_j||=m_{ij}$ とする。
このとき、行列 $G=(g_{ij})$ を $g_{ij}=\frac{1}{2}(m_{0i}^2+m_{0j}^2-m_{ij}^2)$ となる
対称行列とする。このとき、$G$ が半正定値であることと、
そのような点 $p_0,...,p_n$ が存在することは同値である。
証明には、以下の事実を使います。
行列 $A$ が半正定値(positive semi-definite)対称行列であることと、
$A=X^TX$ であることが同値である。
実対称行列が半正定値であるとは、$A$ の固有値が正または0であることを
言います。実対称行列の固有値はいつも実数であることを思い出しましょう。
同値なことは、任意のベクトル ${\bf x}\in {\mathbb R}^n$ に対して、
${\bf x}^TA{\bf x}\ge 0$ となることです。
この定理の証明は、本を見てもらうことにして、
$n=2$ の場合に、定理を当てはめてみると、行列 $G$ は、
$$\begin{pmatrix}x^2&\frac{1}{2}(x^2+y^2-z^2)\\\frac{1}{2}(x^2+y^2-z^2)&y^2\end{pmatrix}$$
となります。この行列が半正定値であることの必要十分条件は、
$\det(G)\ge 0$ かつ、$x^2\ge 0$ です。
後者は、いつでも成り立ちますので、行列式を計算すると、
$$\det(G)=\frac{1}{4}(y+z-x)(x+y-z)(x+z-y)(x+y+z)$$
と因数分解できて、$x,y,z$ はいつでも非負なので、$\det(G)\ge 0$ は
$(y+z-x)(x+y-z)(x+z-y)\ge0$ と同値です。
また、このとき、すぐに、三角不等式は導出できませんが、
この3つの因数のうち、２つが非正であるとすると、
もし、$y+z-x\ge 0,x+y-z\le 0, x+z-y\le 0$ が成り立つとすると、
後半の２つの式の左辺を足すと、
$2x\le 0$ が成り立ち、$x$ が 非負であることと矛盾します。
よって、3つのうち、２つが負になることはありません。
(ほかの２つが負であると仮定しても、文字を入れ替えることによって同じ結論になります)
つまり、$\det(G)\ge 0$ であるなら、
$y+z-x\ge 0, x+y-z\ge 0, x+z-y\ge 0$ が成り立ちます。
よって、$G$ が半正定値な対称行列であることと、三角不等式は
同値となります。
$n=3$ の場合の行列 $G$ を書いておきます。
$m_{0,1}=x, m_{0,2}=y, m_{0,3}=z$
$m_{1,2}=u, m_{2,3}=v, m_{3,1}=w$ とおくと、
$$G=\begin{pmatrix}x^2&\frac{1}{2}(x^2+y^2-u^2)&\frac{1}{2}(x^2+z^2-w^2)\\\frac{1}{2}(x^2+y^2-u^2)&y^2&\frac{1}{2}(y^2+z^2-v^2)\\\frac{1}{2}(x^2+z^2-w^2)&\frac{1}{2}(y^2+z^2-v^2)&z^2\end{pmatrix}$$
となります。
この行列式 $\det(G)$ は、
$$=\frac{1}{4}(x+y-u)(x+y+u)((y+u-x)(u+x-y)z^2+(x^2+z^2-w^2)(y^2+z^2-v^2))-\frac{1}{4}(x(y+z-v)(y+z+v)-y(w+x-z)(w+z-x))^2$$
$$(x^2+z^2-w^2)(y^2+z^2-v^2)=(x+z-w)(w+x+z)(y+z-v)(y+z+v)-2z(v^2x+w^2y-x^2y-xy^2-2xyz-xz^2-yz^2)$$
$$=(x+z-w)(w+x+z)(y+z-v)(y+z+v)+2z(x(y+z-v)(y+z+v)-y(w+x-z)(w+z-x))+2xyz^2$$
上の例では、
$x=u=v=z=2$ かつ、$y=w=3$ として計算をすると、$\det(G)=-81/2$ となり、
やはり、$\det(G)$ が正にならないので、半正定値にはなりません。
Are These Distances Euclidean?
正の実数の集合が、$n+1$ 次元ユークリッド空間の $n$ 面体の辺となりうる
ための実数の条件に関する問題です。
例えば、３つの正の実数 $x_1,x_2,x_3$ が与えられた時に、それが、平面上の
３角形の辺となるための必要十分条件は、
２辺の和は残りの１辺の和以上になるという不等式を満たす必要があります。
これを三角不等式といいます。これを具体的に式に書いておけば、
$$x_1+x_2\ge x_3,\ x_1+x_3\ge x_2,\ x_2+x_3\ge x_1$$
となります。
このことを高次元に一般化します。$n$ 次元ユークリッド空間 ${\mathbb R}^n$
の上に、$n+1$ 点 $p_0,p_1,\cdots ,p_n$ を与えて、その間の距離を
$m_{ij}=||p_i-p_j||$ が与えられたとするとき、$m_{ij}$ の取りうる必要十分条件は
どのように与えられるか？という問題です。
$n+1$ 面体の各３角形は存在しないといけませんから、もちろん３角不等式を
満たさないといけません。
しかし、$n\ge 3$ となると、その不等式だけでは十分では在りません。
Matousekの出した例では、
2,2,2,2,3,3 という６つの実数に対して、この数を各辺に持つような
四面体を ${\mathbb R}^3$ に実現することはできないことを述べています。
(もちろん、もっと次元が高いユークリッド空間でもできません。)
しかし、この6つの数は、どの３つを取っても三角不等式を満たしています。
よって、そのような必要十分条件は、以下のようになります。
定理
$||p_i-p_j||=m_{ij}$ とする。
このとき、行列 $G=(g_{ij})$ を $g_{ij}=\frac{1}{2}(m_{0i}^2+m_{0j}^2-m_{ij}^2)$ となる
対称行列とする。このとき、$G$ が半正定値であることと、
そのような点 $p_0,...,p_n$ が存在することは同値である。
証明には、以下の事実を使います。
行列 $A$ が半正定値(positive semi-definite)対称行列であることと、
$A=X^TX$ であることが同値である。
実対称行列が半正定値であるとは、$A$ の固有値が正または0であることを
言います。実対称行列の固有値はいつも実数であることを思い出しましょう。
同値なことは、任意のベクトル ${\bf x}\in {\mathbb R}^n$ に対して、
${\bf x}^TA{\bf x}\ge 0$ となることです。
この定理の証明は、本を見てもらうことにして、
$n=2$ の場合に、定理を当てはめてみると、行列 $G$ は、
$$\begin{pmatrix}x^2&\frac{1}{2}(x^2+y^2-z^2)\\\frac{1}{2}(x^2+y^2-z^2)&y^2\end{pmatrix}$$
となります。この行列が半正定値であることの必要十分条件は、
$\det(G)\ge 0$ かつ、$x^2\ge 0$ です。
後者は、いつでも成り立ちますので、行列式を計算すると、
$$\det(G)=\frac{1}{4}(y+z-x)(x+y-z)(x+z-y)(x+y+z)$$
と因数分解できて、$x,y,z$ はいつでも非負なので、$\det(G)\ge 0$ は
$(y+z-x)(x+y-z)(x+z-y)\ge0$ と同値です。
また、このとき、すぐに、三角不等式は導出できませんが、
この3つの因数のうち、２つが非正であるとすると、
もし、$y+z-x\ge 0,x+y-z\le 0, x+z-y\le 0$ が成り立つとすると、
後半の２つの式の左辺を足すと、
$2x\le 0$ が成り立ち、$x$ が 非負であることと矛盾します。
よって、3つのうち、２つが負になることはありません。
(ほかの２つが負であると仮定しても、文字を入れ替えることによって同じ結論になります)
つまり、$\det(G)\ge 0$ であるなら、
$y+z-x\ge 0, x+y-z\ge 0, x+z-y\ge 0$ が成り立ちます。
よって、$G$ が半正定値な対称行列であることと、三角不等式は
同値となります。
$n=3$ の場合の行列 $G$ を書いておきます。
$m_{0,1}=x, m_{0,2}=y, m_{0,3}=z$
$m_{1,2}=u, m_{2,3}=v, m_{3,1}=w$ とおくと、
$$G=\begin{pmatrix}x^2&\frac{1}{2}(x^2+y^2-u^2)&\frac{1}{2}(x^2+z^2-w^2)\\\frac{1}{2}(x^2+y^2-u^2)&y^2&\frac{1}{2}(y^2+z^2-v^2)\\\frac{1}{2}(x^2+z^2-w^2)&\frac{1}{2}(y^2+z^2-v^2)&z^2\end{pmatrix}$$
となります。
この行列式 $\det(G)$ は、
$$=\frac{1}{4}(x+y-u)(x+y+u)((y+u-x)(u+x-y)z^2+(x^2+z^2-w^2)(y^2+z^2-v^2))-\frac{1}{4}(x(y+z-v)(y+z+v)-y(w+x-z)(w+z-x))^2$$
$$(x^2+z^2-w^2)(y^2+z^2-v^2)=(x+z-w)(w+x+z)(y+z-v)(y+z+v)-2z(v^2x+w^2y-x^2y-xy^2-2xyz-xz^2-yz^2)$$
$$=(x+z-w)(w+x+z)(y+z-v)(y+z+v)+2z(x(y+z-v)(y+z+v)-y(w+x-z)(w+z-x))+2xyz^2$$
となり、三角不等式のいくつかの式でかけますが、途中でいくつか、マイナス記号が
入っていますので、これらすべて正の数でも、$\det(G)$ が正の値になるとは
限りません。(むしろ、正になっても正定値とも限りませんが。)
$x=u=v=z=2$ かつ、$y=w=3$ として計算をすると、$\det(G)=-81/2$ となり、
やはり、$\det(G)$ が正にならないので、半正定値にはなりません。
0 件のコメント:
コメントを投稿