具体的には
・拡張ユークリッドの互除法によって得られるもの
・解空間はどのように構成出来るか
について色々考えました。必要な知識は
・拡張してないユークリッドの互除法
・行基本変形
・線形代数の基礎すぎる知識(各行が線形独立な行列は正則だよとか)
・線形代数の各種すぎる定義(A+B={x+y ; x∈A,y∈B}とか線形独立とか)
です。線形代数が好きでユークリッドの互除法を拡張したい人にはぴったりなトピックだと思います。
問題
零でない整数a,b,cにたいして、
ax+by=c
の解空間を構成せよ。
考察
ベズーの補題より、gcd(a,b)がcを割り切ることが解の存在性の必要充分条件です。
よくよく考えると、gcd(a,b)=dとおくとax+byはdの倍数なので割り切らない時は解が存在しないので対偶をとると解が存在する条件が「dがcを割り切る」ということが分かります。逆に割り切るならば解が存在することも示したいのですが、これは具体的な解の構成方法を示すことによって示します。以下ではcはdを割り切りc=mdというのを前提に話を進めます。
1.拡張ユークリッドの互除法とは？？
(1.1)ax+by=d
(a,b)に対してgcd(a,b)を求める手続きがユークリッドの互除法です。この手続きを行列の行基本変形に拡張して考えることによって(1)を解くことが出来ます。それが拡張ユークリッドの互除法です。要するに方程式(1.1)を解くアルゴリズムです。
(1 0) (a) = (a)
(0 1) (b) = (b)
に対して、(a,b)に対して行われるユークリッドの互除法は
・片方から片方の定数倍引く
・入れ替える
なのでどちらの操作も同等な基本行列が存在します。そして有限回で終了するのでその有限個の行列を左から掛けていくことによって最終的には右辺のベクトルが(d,0)になってその時の係数行列の１行目の2つの要素が方程式(1.1)の解になっているという訳です。なお、2行目の2つの要素は(ax+by=0)の解となっています。
2.方程式(1.1)の解空間はどんな空間？？
まず(1.1)の解空間を考えます。色々知っている人は斉次なんちゃらと似てると思いますがその通りです。色々しっていなくても必要な知識さえあれば証明できますが、結論から言うと
(x0,y0)を(1.1)の非ゼロな要素,(z0,w0)をax+by=0の非ゼロな解
とすると(1.1)の任意の解は任意の整数kで
(x0 + k*z0 , y0 + k*w0)
と表すことが出来ます。
3.ax+by=c=mdの解空間は？？
結論から言えば
(m*x0 + k*z0, m*y0 + k*w0)
と表すことが出来ます。証明は2と同じ感じでした。
解
入力されたa,b,cに対して,
拡張ユークリッドの互除法によって得られた係数行列の成分を
(x,y)
(z,w)
とする。また、この時d=gcd(a,b)である。
・dがcを割り切らない時は解なし、つまり空集合
・dがcを割り切る時は、m=c/dとして
{ (m*x + k*z , (m*y + k*w) ; k∈整数 }
が解であり、従って割り切るときは必ず解が存在するのでベズーの補題が示されたことになります。
0 件のコメント:
コメントを投稿