シュタイニッツ交換補題

シュタイニッツ交換補題は、例えば有限次元ベクトル空間の任意の2つの基底が同じ数の要素を持つことを示すために使用される線型代数の基本定理である。この結果はドイツの数学者エルンスト・シュタイニッツにちなんで名付けられている。この結果はしばしばシュタイニッツ・マクレーン交換補題と呼ばれ、サンダース・マクレーン による シュタイニッツの補題のマトロイドへの一般化^[1]も認識されている。^[2]

および をベクトル空間 の有限部分集合とします。が線型独立なベクトルの集合であり が を張る場合、次のようになります。 ${\displaystyle U}$${\displaystyle W}$${\displaystyle V}$${\displaystyle U}$${\displaystyle W}$ ${\displaystyle V}$

1. ; ${\displaystyle |U|\leq |W|}$

2.が を張るような集合が存在する。 ${\displaystyle W'\subseteq W}$${\displaystyle |W'|=|W|-|U|}$${\displaystyle U\cup W'}$${\displaystyle V}$

および と仮定します。 であること、および を必要に応じて並べ替えると、この集合がを張ることを示します。について帰納法で進めます。 ${\displaystyle U=\{u_{1},\dots ,u_{m}\}}$${\displaystyle W=\{w_{1},\dots ,w_{n}\}}$${\displaystyle m\leq n}$${\displaystyle w_{j}}$${\displaystyle \{u_{1},\dotsc ,u_{m},w_{m+1},\dotsc ,w_{n}\}}$${\displaystyle V}$${\displaystyle m}$

基本ケースでは、がゼロであると仮定します。この場合、ベクトル は存在せず、集合は仮説によって 張られるため、主張は成り立ちます。${\displaystyle m}$${\displaystyle u_{i}}$${\displaystyle \{w_{1},\dotsc ,w_{n}\}}$${\displaystyle V}$

帰納的ステップでは、命題が に対して真であると仮定します。帰納的仮説により、が を張るようにを並べ替えることができます。 であるため、次のような 係数が存在することになります。${\displaystyle m-1}$${\displaystyle w_{i}}$${\displaystyle \{u_{1},\ldots ,u_{m-1},w_{m},\ldots ,w_{n}\}}$${\displaystyle V}$${\displaystyle u_{m}\in V}$${\displaystyle \mu _{1},\ldots ,\mu _{n}}$

${\displaystyle u_{m}=\sum _{i=1}^{m-1}\mu _{i}u_{i}+\sum _{j=m}^{n}\mu _{j }w_{j}}$。

の少なくとも1つは非ゼロでなければなりません。そうでないと、この等式は の線形独立性と矛盾するからです。したがって となります。必要に応じて順序を変更することで、 が非ゼロであると仮定できます。したがって、 ${\displaystyle \mu_{j}}$${\displaystyle \{u_{1},\ldots ,u_{m}\}}$${\displaystyle m\leq n}$${\displaystyle \mu _{m}w_{m},\ldots ,\mu _{n}w_{n}}$${\displaystyle \mu_{m}}$

${\displaystyle w_{m}={\frac {1}{\mu _{m}}}\left(u_{m}-\sum _{j=1}^{m-1}\mu _{j}u_{j}-\sum _{j=m+1}^{n}\mu _{j}w_{j}\right)}$。

言い換えると、は の範囲内にあります。この範囲には各ベクトル が含まれるため、帰納的仮説により が含まれます。 ${\displaystyle w_{m}}$${\displaystyle \{u_{1},\ldots ,u_{m},w_{m+1},\ldots ,w_{n}\}}$${\displaystyle u_{1},\ldots ,u_{m-1},w_{m},w_{m+1},\ldots ,w_{n}}$${\displaystyle V}$

シュタイニッツ交換補題は計算数学、特に線型代数と組合せアルゴリズムにおける基本的な結果である。^[3]

• Julio R. Bastida, Field extensions and Galois Theory、Addison–Wesley Publishing Company (1984)。

• Mizar システムの証明: http://mizar.org/version/current/html/vectsp_9.html#T19