Encontrar todos los subconjuntos de este conjunto de vectores linealmente dependientes

Question

He vectores en la forma

(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) 

Necesito encontrar todos lineal dependiente de subconjuntos $Z_2$.

Por ejemplo 1,2,5 y 3,6,7.

EDICIÓN (después de @rschwieb)

La respuesta para la presentan los vectores: 521 642 763 6541 7432 75431 765321

Yo lo hice por la fuerza bruta. Me refiero a que me escribió programa para iterar a través de todas las variantes de $${7 \choose 3} {7 \choose 4} {7 \choose 5} {7 \choose 6} {7 \choose 7}$$ 99 en total.

Pero pensé que sólo lo que de alguna forma existen para este tipo de tarea. Por ahora estoy tratando de implementar http://en.wikipedia.org/wiki/Quadratic_sieve . Código incorporado en todo el programa. Pienso poner aquí entonces yo me organizo bien.

Answer 1

Nos deja denotar con $M$ (transponer) de su matriz, $$M= \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$ Como rschwieb ya se ha señalado, un vector $v$ $Mv=0$ resuelve el problema.

El uso elemental de fila de operación (módulo 2), se puede llevar fácilmente en el escalonada $$M' = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$

Ahora, es fácil ver que los vectores $$v = \begin{pmatrix} \alpha \\ \alpha +\beta +\gamma \\ \gamma \\ \beta +\gamma \\ \alpha \\ \beta \\ \gamma \\ \end{pmatrix} $$ parámetros $\alpha$, $\beta$, $\gamma$ están en el núcleo de $M'$ y por lo tanto en el núcleo de $M$. Configuración $\alpha =0,1$, $\beta=0,1$, y $\gamma=0,1$, se obtiene el $2^3=8$ soluciones. La solución con $\alpha=\beta=\gamma=0$ es trivial, así que hay 7 soluciones no triviales.

Answer 2

Si considero que lo que escribió como una matriz de $M$, cada subconjunto linealmente dependiente será descubierto por la búsqueda de un vector distinto de cero $x$ tal que $xM=0$.

Desde $x$ 7 desconocida binario de las entradas, podemos ver el sistema de ecuaciones en siete incógnitas $xM=0$, y en qué casos. Que sería de $2^7$ posibilidades de $x$, sin embargo algunos de ellos serán descartados por el sistema de ecuaciones, por lo que este es menos trabajo de 'fuerza bruta'.

FYI si el formato de su pregunta más educadamente (e incluir una pregunta en el cuerpo de tu post) y se incluyen los trabajos parciales que usted ha hecho, usted va a obtener más ayuda más rápido.