12.6: Ecuaciones lineales sobre los enteros Mod 2

reducción mod 2

Los métodos que hemos estudiado para resolver sistemas de ecuaciones hasta este punto pueden ser aplicados a sistemas en los que toda la aritmética se realiza sobre otros sistemas algebraicos, incluyendo los enteros módulo 2. El caso mod 2 será particularmente útil en nuestro posterior estudio de la teoría de la codificación.

Al resolver sistemas de ecuaciones con aritmética mod 2, las operaciones de fila elemental siguen siendo fundamentales. Sin embargo, dado que solo hay un elemento distinto de cero, 1, nunca es necesario multiplicar una fila por una constante distinta de cero. Otra gran diferencia es que el número de soluciones posibles es siempre finito. Si tienes ecuaciones\(m\) lineales en\(n\) incógnitas, cada desconocido solo puede tomar uno de dos valores, 0 o 1. Por lo tanto solo hay\(2^n\) posibles\(n\) -tuplas a partir de las cuales dibujar un conjunto de soluciones. Suponiendo\(m \leq n\text{,}\) que normalmente (pero no siempre) tendrá variables\(m\) básicas después de la reducción de filas y la variable\(n-m\) libre. Si este es el caso, y existe alguna solución, habrá\(2^{n-m}\) diferentes soluciones.

Veamos un ejemplo, que se encubre a la forma matricial de inmediato.

\ begin {ecuación*}\ begin {array} {r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {}} x_1 & {} + {} &x_2 & & & {} + {} & x_4 & & & &= 1\\ x_1 & & & & {} + {} &x_3 & & & & {} + {} & x_5& & &= 0\\ & & x_2 & {} + {} &x_3 & & & & & {} + {} &x_6&= 0\\\ end {array}\ end {ecuación*}

La matriz aumentada del sistema es

\ begin {ecuación*}\ left (\ begin {array} {cccccc|c} 1 & 1 & 0 & 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ end {array}\ derecha)\ end {ecuación*}

Los pasos en la reducción de filas de esta matriz siguen. Las entradas en las que “pivotamos” se muestran en negrita para identificar más fácilmente las variables básicas.

\ begin {ecuation*}\ begin {split}\ left (\ begin {array} {cccccc|c} 1 & 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ end {array}\ right) &\ overset {\ textrm {add} R_1\ textrm {a} R_2} {\ text {}\ largoderrow }\ text {}\ left (\ begin {array} {cccccc|c}\ textbf {1} & 1 & 0 & 0 & 0 & 1\\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\ end {array}\ derecha)\\ &\ text {}\ overset {\ textrm {agregar} R_2\ textrm {a} R_1} {\ text {}\ largofila derecha}\ text {}\ left (\ begin {array} {cccccc|c}\ textbf {1} & 0 & 0 & 1 & 0 & 0 & 0\\ 0 &\ textbf {1} & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ end {array}\ derecha)\\ &\ overset {\ textrm {agregar} R_2\ textrm {a} R_3} {\ text {}\ largofila derecha}\ text {}\ left (\ begin {array} {cccccc|c}\ textbf {1} & 0 & 0 & 1 & 0 & 0 & 0 &\\ 0 &\ textbf {1} & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\ end {array}\ right)\ end {split}\ end {equation*}

Observe que en este punto, no podemos pivotar en la tercera fila, tercera columna ya que esa entrada es cero. Por lo tanto pasamos a la siguiente columna, haciendo lo\(x_4\) básico.

\ begin {ecuation*}\ begin {split}\ text {} &\ overset {\ textrm {add} R_3\ textrm {a} R_2} {\ text {}\ longrightarrow}\ text {}\ left (\ begin {array} {cccccc|c}\ textbf {1} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\ textbf {1} & 1 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 &\ textbf {1} & amp; 1 & 1 & 1\\ end {array}\ right)\ end {split}\ end {equation*}

Esto completa la reducción de filas y ahora podemos identificar el conjunto de soluciones. Tenga en cuenta que dado que la suma es resta, los términos se pueden mover a ambos lados de un signo de igual sin ningún cambio en el signo. Las variables básicas son\(x_1\text{,}\)\(x_2\text{,}\) y\(x_4\text{,}\) mientras que las otras tres variables son libres. La solución general del sistema es

\ begin {ecuación*}\ begin {array} {c} x_1 = x_3+x_5\\ x_2 = x_3+x_6\\ x_3 = x_3\\ x_4 = 1+ x_5+x_6\\ x_5 = x_5\\ x_6 = x_6\\ end {array}\ end {ecuación*}

Con tres variables libres, hay\(2^3=8\) soluciones a este sistema. Por ejemplo, uno de ellos se obtiene por fraguado\(x_3=1\text{,}\)\(x_5=1\text{,}\) y\(x_6=0\text{,}\) que produce\((x_1, x_2, x_3, x_4, x_5, x_6) = (0,1,1,0,1,0)\text{.}\)

Podemos verificar nuestra reducción de filas con SaeMath:

H=Matrix(Integers(2),[[1,1,0,1,0,0,1],
   [1,0,1,0,1,0,0],[0,1,1,0,0,1,0]])
H.echelon_form()

Ejercicios

En todos los ejercicios que siguen, los sistemas de ecuaciones han terminado\(\mathbb{Z}_2\text{,}\) y así se debe utilizar la aritmética mod 2 para resolverlos.

Ejercicio\(\PageIndex{1}\)

Resuelva los siguientes sistemas, describiendo completamente los conjuntos de soluciones:

1. \(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} & x_2 & & & = 0 \\ x_1 & & & {}+{} & x_3 & = 0 \\ \end{array} \)
2. \(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} & x_2 & & & & & = 0 \\ & & x_2 & {}+{} & x_3& & & = 0\\ & & & & x_3& {}+{} & x_4 & = 1 \\ x_1 & {}+{} & x_2 & {}+{} & x_3& & & = 1 \\ \end{array} \)

Contestar

1. \(\displaystyle \{(0,0,0),(1,1,1)\}\)
2. \(\displaystyle \{(1,1,1,0)\}\)

Ejercicio\(\PageIndex{2}\)

Este ejercicio proporciona un ejemplo en el que el número de variables básicas es menor que el número de ecuaciones. La única diferencia entre los dos sistemas de abajo son los lados de la derecha. Puede comenzar con una matriz aumentada que tenga dos columnas del lado derecho y hacer la reducción de filas para ambos sistemas al mismo tiempo.

1. \(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & &{}+{} & x_4 &= 1 \\ x_1 & & & {}+{} &x_3 & {}+{} & x_4 &= 0 \\ & & x_2 & {}+{} &x_3 & & &= 1 \\ \end{array}\)
2. \(\displaystyle \begin{array}{r@{}r@{}r@{}r@{}r@{}r@{}r@{}r@{}} x_1 & {}+{} &x_2 & & &{}+{} & x_4 &= 1 \\ x_1 & & & {}+{} &x_3 & {}+{} & x_4 &= 0 \\ & & x_2 & {}+{} &x_3 & & &= 0 \\ \end{array}\)

Contestar

Como se sugiere aquí es la matriz aumentada con ambos lados derechos, y su reducción de fila:

\ begin {ecuation*}\ begin {split}\ left (\ begin {array} {cccc|cc} 1 & 1 & 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0\\ end {array}\ right) &\ text {}\ longrightarrow\ text {}\ left (\ begin {array} {cccc|cc}\ textbf {1} & 0 & 1 & amp; 1 & 0 & 0\\ 0 &\ textbf {1} & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1\\\ end {array}\ derecha)\\ end {split}\ end {ecuación*}

Aquí solo hay dos variables básicas porque el lado izquierdo de la última ecuación es la suma de los lados izquierdos de las dos primeras ecuaciones.

1. Ignorando la última columna de ambas matrices, vemos que la última ecuación del primer sistema se reduce a\(0=0\text{,}\) lo que siempre es cierto, y las dos primeras ecuaciones producen dos variables libres,\(x_3\) y\(x_4\text{.}\) La solución general es el conjunto de cuadruplos\(\{(x_3 +_2 x_4,x_3 +_2 1, x_3, x_4) \mid x_3, x_4 \in \mathbb{Z}_2 \}\text{.}\) La cardinalidad del conjunto de soluciones es 4.
2. Si reemplazamos la quinta columna por la sexta, la última fila indica eso\(0=1\text{,}\) lo que significa que el conjunto de soluciones está vacío.

Ejercicio\(\PageIndex{3}\)

Este ejercicio motiva el concepto de coset en el Capítulo 15.

1. Resuelve el siguiente sistema y prueba que el conjunto de soluciones es una combinación lineal de vectores en\(\mathbb{Z}_{2}^{5}\) y también un subgrupo del grupo\(\mathbb{Z}_{2}^{5}\) bajo adición de mod 2 coordinatewise.
   \ begin {ecuación*}\ begin {array} {r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} x_1 & {} + {} &x_2 & & & & & & & & {} + {} + {} & x_5&= 0\\ x_1 & & & & {+} {} &x_3 & & & & {} + {} & x_5&= 0\\ x_1 & & & & & {} + {} &x_3 & {} + {} & x_4 & & &= 0\\ & & x_2 & {} + {} &x_3 & {} + {} & x_4 & & &= 0\\\ end {array}\ end {ecuación*}
2. Describir el conjunto de soluciones al siguiente sistema, ya que se relaciona con el conjunto de soluciones al sistema en la parte anterior de este ejercicio.
   \ begin {ecuación*}\ begin {array} {r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} r@ {} x_1 & {} + {} &x_2 & & & & & & & & & {} + {} + {} & x_5&= 1\\ x_1 & & & & {+} {} &x_3 & & & & {} + {} & x_5&= 0\\ x_1 & & & & & {} + {} &x_3 & {} + {} & x_4 & & &= 1\\ & & x_2 & {} + {} &x_3 & {} + {} & x_4 & & &= 0\\\ end {array}\ end {ecuación*}

Contestar

1. La reducción de filas produce una solución con una variable libre,\(x_3\).
   \[\begin{aligned} (x_1,\: x_2,\: x_3,\: x_4,\: x_5)&=(x_3,\: x_3,\: x_3,\: 0,\: 0) \\ &=x_3(1,\: 1,\: 1,\: 0,\: 0)\end{aligned}\]
   El conjunto de soluciones tiene solo dos elementos. Lo es\(\{(0,\:0,\:0,\:0,\:0),\:(1,\:1,\:1,\:0,\:0)\}\). Dado que\(\mathbb{Z}_2^5\) es un grupo finito, el conjunto de soluciones es un subgrupo porque está cerrado con respecto a la adición de mod 2 por coordenadas.
2. La matriz aumentada de coeficientes de fila reducida proporciona la solución
   \[\begin{aligned} (x_1,\: x_2,\: x_3,\: x_4,\: x_5)&=(x_3,\: 1+x_3,\: x_3,\:1,\: 0) \\ &=(0,\:1,\:0,\:1,\: 0)+x_3(1,\:1,\:1,\:0,\: 0)\end{aligned}\]
   Por lo tanto, la solución a este sistema es un desplazamiento del conjunto de solución al sistema homogéneo por el vector\((0,\:1,\:0,\:1,\:0)\), que es\(\{(0,\:1,\:0,\:1,\:0),\: (1,\:0,\:1,\:1,\:0)\}\)