Problema de texto de álgebra lineal

Question

Hemos especificado el número de bombillas. Además de la matriz se encuentran los botones. Pulsando el botón de cambio de estado de las bombillas que están conectados al conmutador. Es sabido que para cada conjunto de lámparas que existen en el botón que está conectado con el número impar de bombillas de este conjunto. Demostrar que correctamente presionando los botones podemos apagar todas las lámparas.

Muy agradable tarea, pero duro. Creo que puedo hacer una $Z^n$ espacio de bombillas, pero, ¿cómo demostrar que tenemos una base de esto? O que no es una forma correcta?

Estoy buscando pistas.

Answer 1

Sugerencia: El "número impar de bombillas a partir de un conjunto" puede ser reformulado en términos de un producto escalar sobre $GF(2)$. Si hay un conjunto no vacío de bombillas con incluso del tamaño de las conexiones a todos los botones, esto le daría un no-vector cero en el nullspace de una cierta matriz...

Más consejos: Si usted fijar un orden de las bombillas y representar cualquier conjunto de bombillas como un $\{0,1\}$-vector, entonces el producto escalar de dos vectores (cada uno representa a un conjunto) es igual al tamaño de la intersección de las dos correspondientes conjuntos. En particular, modulo $2$, este producto escalar es cero o distinto de cero de acuerdo a si la intersección es par o impar.