[場所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 件のコメント:
コメントを投稿