math - ベクトルのすべての線形従属サブセットを見つける

Question

私はそのような形でベクトルを持っています

(1 1 1 0 1 0)
(0 0 1 0 0 0)
(1 0 0 0 0 0) 
(0 0 0 1 0 0) 
(1 1 0 0 1 0) 
(0 0 1 1 0 0) 
(1 0 1 1 0 0) 

Z2 上のすべての線形従属サブセットを見つける必要があります。

たとえば、1,2,5 と 3,6,7 です。

Answer 1

OK、私の 5 セント、ブルート フォース、IINM は、一連のベクトルのすべてのサブセットを反復処理しています。したがって、代わりに、各ベクトルのシングルトン セットが明らかに線形独立している下から移動します。

次のステップでは、シングルトン セットごとに、セット内の残りのベクトルをそれぞれ追加してリストを作成し、そのようなペアのどれが独立しているかを確認します。繰り返しの努力。

3 番目のステップでは、独立したペアごとに、残りのベクトルをそれぞれ追加してトリプルを作成し、新しいベクトルの独立性をテストし、既にテストしたトリプルにマークを付けます。

これにより、ブルートフォースよりも大幅に節約でき、最悪の場合、すべての独立したベクトルのセットになります。