[場所1E503（月曜日5限）]
HPに行く
今回はMiniature 5,6,7についてやりました。
Miniature 5
は、誤り訂正符号についてです。
符号とは送るための情報のことです。
通常、符号を電気信号に乗せて送ると、それを受け取るとき、
送りたかった情報と少々のずれが出てしまう可能性があります。
そのずれは、何かの外的要因かもしれないし、偶然かもしれない。
何らかのノイズということです。
その無意味なノイズを除去するために
符号自身にその誤りを見つける機構を含ませたものを誤り訂正符号
といいます。
除去するアイデアとして、送りたい情報に余分なビット(ビットとは情報のボリュームのこと)
を増やして符号を作り、それを送るのです。
この付け加えたビットのことをparity check bitsといいます。
Matousekの本にあるように、
abcd の4bitの情報をおくるのに、
efg という情報を付け加えて abcdefg
という情報にしたものを符号として送るのです。つまり efg の部分がparity check digits
ということになります。
いまは、このアルファベットを0か1としましょう。
ただ、e=a+b+c、f=a+b+d、g=a+c+d という関係式があるとします。
なので、1011という情報を送る場合には、
1011001という符号にして送るのです。
ここで、上の足し算は、1+0=0+1=1 かつ 1+1=0 という2元体 {\mathbb F}_2
の演算を用いて計算しています。
この7けたの数全体をベクトル空間として{\mathbb F}_2^7 という7次元の
空間とみなします。このとき、G=\begin{pmatrix}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&1&0&1\\0&0&0&1&0&1&1\end{pmatrix}
と行列を定義すると、{\bf v}\in {\mathbb F}_2^4に対して、
G^T{\bf v} を送ることになります。
この G のことを生成行列(Generator matrix)といいます。
このとき、7桁にした、送られる符号全体は、
あるベクトル空間となることが分かります。つまり、
\text{Im}(G^T)\subset {\mathbb F}_2^7
がそのベクトル空間です。
そのベクトル空間を解にもつ、連立一次方程式の係数行列を
parity check matrixといいます。
つまり、送られた符号をこの連立一次方程式にいれてやって
解になれば符号は間違っていないとされ、もし解にならないのなら
符号は間違っているとされます。
ここで少しだけ注意することは、符号が間違っていないとされても
本当に間違っていない符号かどうかは判定できない場合あるということです。
つまり、間違いが複数あるとすると、間違いがありすぎて、結局
合っているという可能性です。そのようなことは確率的には少ないので
この理論では検知できないし無視しようということになるのです。
Miniature 6
は、Odd Distancesですが、この話は、行列の階数を用いたちょっとした応用です。
この話も、次のMiniature 7につづく関連する話でもあります。
このランクの不等式 \text{rank}(AB)\le \text{rank}(A) の不等式の使用は
これで３回目です。
主張する定理は以下です。
定理
お互いの長さが奇数であるような平面上の４点は存在しない。
この定理についてそれほど知っている人は少ないと思いますが、確かに
そうなるようです。
すぐ思いつく平面上の４点は、長方形ですが、そのときでは、
ピタゴラスの定理から、例えば、対角線の長さが5となる。辺の長さが3,4となる
長方形を考えられますが、確かに、全て奇数というわけにはいきません。
一般の四角形にも上の定理のような約束が成り立っているようです。
特に、このような長方形の２倍の長方形を考えることで、全て点の
間の距離が偶数になっている4点は存在するわけです。
この話でうまいところは、
全て奇数となる平面上の4点 {\bf 0},{\bf a}, {\bf b},{\bf c} に対して、
2\langle {\bf a},{\bf b}\rangle=||{\bf a}||^2+||{\bf b}||^2-||{\bf a}-{\bf b}||^2
などを用いて、
行列
\begin{pmatrix}2\langle {\bf a},{\bf a}\rangle&2\langle {\bf a},{\bf b}\rangle&2\langle {\bf a},{\bf c}\rangle\\2\langle {\bf b},{\bf a}\rangle&2\langle {\bf b},{\bf b}\rangle&2\langle {\bf b},{\bf c}\rangle\\2\langle {\bf c},{\bf a}\rangle&2\langle {\bf c},{\bf b}\rangle&2\langle {\bf c},{\bf c}\rangle\end{pmatrix}
のランクの話に帰着させるところと、奇数の2乗は必ず8で割って1余る
という事実を組み合わせることです。
上の行列の 1/2 倍は、グラム行列といいます。
それを Gと書けば、G は、平面上の３点なのだからランクは2以下です。
(GはMiniature 7 にも登場します)
しかし、全て奇数だとすると、この行列は、ランク3になってしまいます。
Miniature 7
は、Are These Distances Euclidean?
ですが、これは、Miniature 6を受けてユークリッド空間の中の
何点かの長さについての問題ですが、
問題は、非負実数 m_{ij} (i,j=0,1,\cdots,n) が、
||{\bf p}_i-{\bf p}_j|| となるような
{\bf p}_i\in {\mathbb R}^n (i=0,1,2,\cdots, n) が存在するための
m_{ij} の条件とは何か？という問題です。
もちろん、m_{ij} は m_{ij}=m_{ji} でかつ、m_{ii}=0 であることは
必要ですが、そのほかに条件はないか？ということです。
n=2 の場合、つまり平面上の3点の場合は、三角不等式が
この問題の答えに相当します。
Miniature 6は、平面上の4点ですが、ここでは、n 次元空間の中の n+1 点です
ので、この問題には直接は関係はありません。
ここで使うのは、半正定値実対称行列 A は、ある実正方行列 X が存在して、
A=X^TX と書けるということです。
ここで、半正定値の行列であるとは、全ての固有値が非負となる
対称行列のことです。(対称行列の固有値は全て実数であるという性質があります。)
逆に、正方実行列 X に対して、X^TX は半正定値実対称行列であることは
すぐ分かるでしょう。
HPに行く
今回はMiniature 5,6,7についてやりました。
Miniature 5
は、誤り訂正符号についてです。
符号とは送るための情報のことです。
通常、符号を電気信号に乗せて送ると、それを受け取るとき、
送りたかった情報と少々のずれが出てしまう可能性があります。
そのずれは、何かの外的要因かもしれないし、偶然かもしれない。
何らかのノイズということです。
その無意味なノイズを除去するために
符号自身にその誤りを見つける機構を含ませたものを誤り訂正符号
といいます。
を増やして符号を作り、それを送るのです。
この付け加えたビットのことをparity check bitsといいます。
Matousekの本にあるように、
abcd の4bitの情報をおくるのに、
efg という情報を付け加えて abcdefg
という情報にしたものを符号として送るのです。つまり efg の部分がparity check digits
ということになります。
いまは、このアルファベットを0か1としましょう。
ただ、e=a+b+c、f=a+b+d、g=a+c+d という関係式があるとします。
なので、1011という情報を送る場合には、
1011001という符号にして送るのです。
ここで、上の足し算は、1+0=0+1=1 かつ 1+1=0 という2元体 {\mathbb F}_2
の演算を用いて計算しています。
この7けたの数全体をベクトル空間として{\mathbb F}_2^7 という7次元の
空間とみなします。このとき、G=\begin{pmatrix}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&1&0&1\\0&0&0&1&0&1&1\end{pmatrix}
と行列を定義すると、{\bf v}\in {\mathbb F}_2^4に対して、
G^T{\bf v} を送ることになります。
この G のことを生成行列(Generator matrix)といいます。
このとき、7桁にした、送られる符号全体は、
あるベクトル空間となることが分かります。つまり、
\text{Im}(G^T)\subset {\mathbb F}_2^7
がそのベクトル空間です。
そのベクトル空間を解にもつ、連立一次方程式の係数行列を
parity check matrixといいます。
つまり、送られた符号をこの連立一次方程式にいれてやって
解になれば符号は間違っていないとされ、もし解にならないのなら
符号は間違っているとされます。
ここで少しだけ注意することは、符号が間違っていないとされても
本当に間違っていない符号かどうかは判定できない場合あるということです。
つまり、間違いが複数あるとすると、間違いがありすぎて、結局
合っているという可能性です。そのようなことは確率的には少ないので
この理論では検知できないし無視しようということになるのです。
Miniature 6
は、Odd Distancesですが、この話は、行列の階数を用いたちょっとした応用です。
この話も、次のMiniature 7につづく関連する話でもあります。
このランクの不等式 \text{rank}(AB)\le \text{rank}(A) の不等式の使用は
これで３回目です。
主張する定理は以下です。
定理
お互いの長さが奇数であるような平面上の４点は存在しない。
この定理についてそれほど知っている人は少ないと思いますが、確かに
そうなるようです。
すぐ思いつく平面上の４点は、長方形ですが、そのときでは、
ピタゴラスの定理から、例えば、対角線の長さが5となる。辺の長さが3,4となる
長方形を考えられますが、確かに、全て奇数というわけにはいきません。
一般の四角形にも上の定理のような約束が成り立っているようです。
特に、このような長方形の２倍の長方形を考えることで、全て点の
間の距離が偶数になっている4点は存在するわけです。
この話でうまいところは、
全て奇数となる平面上の4点 {\bf 0},{\bf a}, {\bf b},{\bf c} に対して、
2\langle {\bf a},{\bf b}\rangle=||{\bf a}||^2+||{\bf b}||^2-||{\bf a}-{\bf b}||^2
などを用いて、
行列
\begin{pmatrix}2\langle {\bf a},{\bf a}\rangle&2\langle {\bf a},{\bf b}\rangle&2\langle {\bf a},{\bf c}\rangle\\2\langle {\bf b},{\bf a}\rangle&2\langle {\bf b},{\bf b}\rangle&2\langle {\bf b},{\bf c}\rangle\\2\langle {\bf c},{\bf a}\rangle&2\langle {\bf c},{\bf b}\rangle&2\langle {\bf c},{\bf c}\rangle\end{pmatrix}
のランクの話に帰着させるところと、奇数の2乗は必ず8で割って1余る
という事実を組み合わせることです。
上の行列の 1/2 倍は、グラム行列といいます。
それを Gと書けば、G は、平面上の３点なのだからランクは2以下です。
(GはMiniature 7 にも登場します)
しかし、全て奇数だとすると、この行列は、ランク3になってしまいます。
Miniature 7
は、Are These Distances Euclidean?
ですが、これは、Miniature 6を受けてユークリッド空間の中の
何点かの長さについての問題ですが、
問題は、非負実数 m_{ij} (i,j=0,1,\cdots,n) が、
||{\bf p}_i-{\bf p}_j|| となるような
{\bf p}_i\in {\mathbb R}^n (i=0,1,2,\cdots, n) が存在するための
m_{ij} の条件とは何か？という問題です。
もちろん、m_{ij} は m_{ij}=m_{ji} でかつ、m_{ii}=0 であることは
必要ですが、そのほかに条件はないか？ということです。
n=2 の場合、つまり平面上の3点の場合は、三角不等式が
この問題の答えに相当します。
Miniature 6は、平面上の4点ですが、ここでは、n 次元空間の中の n+1 点です
ので、この問題には直接は関係はありません。
ここで使うのは、半正定値実対称行列 A は、ある実正方行列 X が存在して、
A=X^TX と書けるということです。
ここで、半正定値の行列であるとは、全ての固有値が非負となる
対称行列のことです。(対称行列の固有値は全て実数であるという性質があります。)
逆に、正方実行列 X に対して、X^TX は半正定値実対称行列であることは
すぐ分かるでしょう。
0 件のコメント:
コメントを投稿