Sistemas de congruencias lineales (parte 2)#
En este capítulo vamos a continuar con el estudio de las congruencias lineales, en esta ocasión aumentaremos el número de variables involucradas. Empezaremos el capítulo con los sistemas de \(2\) congruencias con \(2\) variables y después vamos a ver sistemas de \(n\) congruencias con \(n\) variables.
Veremos cómo resolver sistemas de congruencias lineales de \(2\) variables. Sin embargo, cuando los sistemas empiezan a tener \(3\) o más variables, la notación matricial es de mucha ayuda. Es por eso que utilizaremos algunos resultados de álgebra lineal para desarrollar un método que nos ayude a resolver dichos sistemas. Dejaremos referencias a los resultados usados por si no estas familiarizado o necesitas recordarlo.
Sistemas de congruencias lineales de \(2\) variables#
En esta sección vamos a ver cómo resolver sistemas de \(2\) congruencias lineales que tienen \(2\) variables.
Definición 43 (Sistema de congruencias lineales de 2 variables )
Un sistema de congruencias lineales de \(2\times 2\) es un sistema formado de dos congruencias lineales de la forma
Vamos a ver que el método de eliminación que usamos para un sistema de ecuaciones lineales de \(2\times 2\), lo podemos utilizar para resolver los sistemas de congruencias lineales.
Con el siguiente ejemplo vamos a ilustrar el método de eliminación.
Ejemplo 128
Usa el método de eliminación para resolver el siguiente sistema de congruencias lineales
Solución.
Vamos a eliminar primero la variable \(x\). Multiplicamos la primera congruencia por \(6\) y la segunda congruencia por \(5\), y tendremos que
Luego, restamos las congruencias y simplificamos los resultados módulo \(13\) para obtener
Notemos que como \((6,13) = 1|11\), la congruencia tiene solución. Además el inverso de \(6\) módulo \(13\) es \(11\). Entonces tenemos que
Para encontrar el valor de \(x\), vamos a sustituir el valor de \(y = 4\) en la primera congruencia del sistema. Entonces tenemos que
Nuevamente como \((5,13) = 1|12\), la congruencia tiene solución y además el inverso de \(5\) módulo \(13\) es \(8\). Entonces tenemos que
Así la solución es \(x\equiv 5\pmod{13}\) y \(y\equiv 4\pmod{13}\).
El siguiente teorema nos ayuda a determinar si el sistema de congruencias lineales tiene una solución única.
Teorema 55
El sistema lineal
Demostración. Supongamos que el sistema tiene una solución, digamos \(x\equiv x_0\pmod{m}\) y \(y\equiv y_0\pmod{m}\). Entonces satisface el sistema de congruencias, es decir que
Ahora vamos a multiplicar la primera congruencia por \(d\) y la segunda congruencia por \(b\). Tendremos que
Si restamos las congruencias, obtenemos que
Luego, por el Corolario 10 tenemos que la congruencia tiene una solución única si y sólo si \((\Delta, m) = 1\).
Similarmente, si multiplicamos la primera congruencia por \(-c\) y la segunda congruencia por \(a\) tendremos que
Ahora, si sumamos las congruencias, tenemos que
Nuevamente por el Corolario 10 tenemos que la congruencia tiene una solución única si y sólo si \((\Delta, m) = 1\).
Por lo tanto, el sistema tiene solución única módulo \(m\) si y sólo si \((\Delta, m) = 1\).\(\square\)
El siguiente teorema nos dice cómo son las soluciones del sistema de congruencias lineales cuando este tiene solución.
Teorema 56
Cuando el sistema de congruencias lineales
Demostración. Por hipótesis tenemos que el sistema tiene solución única, entonces \((\Delta, m) = 1\). Por el Teorema 34 tendríamos que \(\Delta\) tiene inverso módulo \(m\). Entonces se cumple que \(\Delta \Delta^{-1}\equiv 1\pmod{m}\).
Ahora vamos a demostrar que \(x_0\equiv \Delta^{-1}(ed-bf)\pmod{m}\) y \(y_0\equiv \Delta^{-1}(af-ce)\pmod{m}\) satisfacen el sistema,
Por otro lado, también tenemos que
Así, \(x\equiv x_0\pmod{m}\), \(y\equiv y_0\pmod{m}\) es la única solución del sistema. \(\square\)
Ejemplo 129
Determina si el siguiente sistema de congruencias lineales tiene solución.
Solución.
Primero vamos a calcular el valor de \(\Delta\).
El sistema no tiene una solución única módulo \(14\), ya que \((2,14) = 2\). Por lo anterior, \(2\) no tiene inverso módulo \(14\) y no podríamos calcular \(\Delta^{-1}\). Entonces, no podemos calcular las soluciones usando las fórmulas del Teorema 56. Sin embargo, sí podemos usar el método de eliminación para buscarlas.
Multiplicamos la primera congruencia por \(7\) y la segunda congruencia por \(4\) y obtenemos que
Luego, si restamos las ecuaciones, tendremos que
Por lo tanto \(y = 1\). En general, \(y = 1 + 7t\) para algún entero \(t\). Ahora sustituimos esto en la primera congruencia y tenemos que
Por lo tanto, \(x = 2\) y en general \(x = 2 + 7t\) para algún entero \(t\).
Como la solución no era única módulo \(14\), las dos soluciones que tendríamos serían \(x = 2\),\(y = 1\) y \(x = 9\), \(y = 8\).
Notemos que las fórmulas obtenidas en el Teorema 56 para \(x_0\) y \(y_0\) y el valor de \(\Delta\) los podemos reescribir en términos de determinantes.
Sistemas de congruencias lineales en forma matricial#
Cuando los sistemas de congruencias lineales son muy grandes es de mucha ayuda usar el lenguaje matricial. En lo que sigue vamos a mostrar los resultados para sistemas de congruencias lineales en general, pero en los ejemplos vamos a trabajar con sistemas pequeños de \(2\times 2\) o \(3\times 3\) para poder mostrarlos.
Lo anterior nos lleva a definir la congruencia entre matrices.
Definición 44 (Matrices congruentes)
Sean \(A\) y \(B\) matrices de tamaño \(n\times k\) donde las entradas son enteros y las entradas de la matriz \(A\) son \(a_{ij}\) y las entradas de la matriz \(B\) son \(b_{ij}\). Diremos que \(A\) es congruente con \(B\) módulo \(m\) si para cada par \((i,j)\) se cumple que \(a_{ij}\equiv b_{ij}\pmod{m}\), en donde \(1\le i\le n\) y \(1\le j\le k.\)
Escribiremos \(A\equiv B\pmod{m}\) si \(A\) es congruente con \(B\) módulo \(m\).
Ejemplo 130
Veamos que las siguientes matrices son congruentes módulo \(13\).
Como podemos observar, se cumplen las siguientes congruencias
Por lo tanto, se cumple que \(A\equiv B\pmod{13}.\)
Vamos a ver que algunas propiedades que ya definimos para congruencias, también son válidas en forma matricial con algunas condiciones extras. Para las siguientes secciones de las notas estaremos usando el producto de matrices. Si no estas familiarizado con esto, puedes revisar el siguiente enlace en donde se explica como hacer el producto de matrices.
Teorema 57
Sean \(A\) y \(B\) matrices de tamaño \(n\times k\), en donde \(A\equiv B\pmod{m}\), sea \(C\) una matriz de tamaño \(k\times p\) y sea \(D\) una matriz de tamaño \(p\times n\), donde todas las entradas de las matrices son enteros. Entonces \(AC\equiv BC\pmod{m}\) y \(DA\equiv DB\mod{m}\).
Demostración. Sean \(a_{ij}\), \(b_{ij}\) las entradas de las matrices \(A\) y \(B\) respectivamente, donde \(1\le i\le n\), \(1\le j\le k\) y \(c_{ij}\) las entradas de la matriz \(C\) para \(1\le i\le k\) y \(1\le j\le p\).
Primero veamos que \(AC\equiv BC\pmod{m}\).
Si hacemos la operación \(AC\) entonces tendríamos que la \((i,j)\)-ésima entrada de la matriz \(AC\) sería \(\sum_{t=1}^{k}a_{it}c_{tj}\). Similarmente si hiciéramos la operación \(BC\) tendríamos que la \((i,j)\)-ésima entrada de la matriz \(BC\) sería \(\sum_{t=1}^{k}b_{it}c_{tj}\), en donde \(1\le i\le n\) y \(1\le j\le k\). Si llegamos a esa expresión habremos terminado.
Por hipótesis tenemos que \(A\equiv B\pmod{m}\) y por la Definición 44 tendríamos que \(a_{it}\equiv b_{it}\pmod{m}\) para toda \(i\) y \(t\). Ahora, usando el Teorema 30 podríamos multiplicar el valor \(c_{tj}\) obteniendo que \(a_{it}c_{tj}\equiv b_{it}c_{tj}\pmod{m}.\) Luego podemos sumar para todos los valores de \(t\) desde \(1\) hasta \(k\) y obtendríamos que
Ahora veamos que \(DA\equiv DB\mod{m}\).
Primero denotemos las entradas de la matriz \(D\) como \(d_{ij}\), donde \(1\le i\le p\) y \(1\le j\le n\). Nuevamente, veamos que la \((i,j)\)-ésima entrada de la matriz \(DA\) es \(\sum_{t=1}^{n}d_{it}a_{tj}\) y la \((i,j)\)-ésima entrada de la matriz \(DB\) sería \(\sum_{t=1}^{n}d_{it}b_{tj}.\)
Similarmente por la Definición 44 tendríamos que \(a_{tj}\equiv b_{tj}\pmod{m}\) para toda \(j\) y \(t\).
En este caso vamos a multiplicar el valor \(d_{it}\) obteniendo que \(d_{it}a_{tj}\equiv d_{it}b_{tj}\pmod{m}.\) Luego podemos sumar para todos los valores de \(t\) desde \(1\) hasta \(n\) y obtendríamos que
Definición 45
El sistema de congruencias lineales módulo \(m\)
Se puede representar usando notación matricial y es equivalente a
Ejemplo 131
El sistema de congruencias lineales
Vamos a presentar algunos resultados previos. Después de ellos vamos a poder resolver sistemas de congruencias lineales como los de la Definición 45.
Definición 46 (Matriz inversa)
Si \(A\) y \(\bar{A}\) son matrices de tamaño de \(n\times n\) con entradas enteras y se cumple que \(\bar{A} A\equiv A\bar{A} \equiv I_n\pmod{m}\) en donde \( I_n = \begin{pmatrix} 1 & 0 & \ldots & 0\\ 0 & 1 & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 1\\ \end{pmatrix}\) es la matriz identidad de tamaño \(n\times n\), entonces decimos que \(\bar{A}\) es la matriz inversa de \(A\) módulo \(m\).
Ejemplo 132
Veamos que la matriz inversa de \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\) es la matriz \(\bar{A} = \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix}\) módulo \(7\).
Vamos a verificar que se cumple la Definición 46.
Por lo tanto \(\bar{A}\) es la inversa de \(A\).
Para matrices de tamaño \(2\times 2\), tenemos el siguiente teorema que nos ayuda a encontrar la matriz inversa fácilmente.
Teorema 58 (Matriz inversa de \(2\times 2\))
Sea \(A = \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}\) con entradas enteras, tales que \(\Delta = det(A) = ad - bc\) es primo relativo con el entero positivo \(m\). Entonces la matriz
Demostración. Para verificar que \(\bar{A}\) es la inversa de \(A\) módulo \(m\), tenemos que verificar que \(A\bar{A} \equiv \bar{A}A \equiv I_2\pmod{m}\). Notemos que como \((\Delta,m) = 1\) entonces \(\Delta \bar{\Delta} \equiv 1\pmod{m}.\)
Veamos lo siguiente
Luego, veamos que
Por lo tanto \(\bar{A}\) es la matriz inversa de \(A\). \(\square\)
Ejemplo 133
Encuentra la matriz inversa de \(A = \begin{pmatrix} 4 & 6 \\ 9 & 2 \\ \end{pmatrix}\) módulo \(13\).
Solución.
Primero vamos a calcular \(\Delta = det(A) = ad - bc = 4\cdot 2 - 6\cdot 9 = 8 - 54 = -46\equiv 6\pmod{13}\). Como \((6,13) = 1\),el inverso de \(6\) módulo \(13\) es \(11\), así tenemos que \(\bar{\Delta} = 11\). Luego, tendríamos que la matriz inversa es
Ya vimos cómo calcular el determinante de una matriz de tamaño \(2\times 2\). Para calcular el determinante de matrices de tamaño \(n\times n\) en donde \(n>2\) podemos consultar las siguientes notas de Álgebra Superior I.
Veamos un ejemplo de cómo calcular el determinante de una matriz de tamaño de \(3\times 3\).
Ejemplo 134
Calcula el determinante de la matriz \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\) módulo \(7\).
Solución.
Recordemos que los signos correspondientes a las entradas de una matriz de \(3\times 3\) son
Primero tenemos que seleccionar una fila o columna de la matriz. En este caso vamos a seleccionar primera fila, es decir
Ahora vamos a calcular lo siguiente, \(sign(1,j)\cdot a_{1j}\cdot det(A_{1j})\), en donde \(sign(1,j)\) es el signo correspondiente a la entrada \(a_{1j}\) de la matriz \(A\) y \(A_{1j}\) es la matriz resultante de tapar la fila \(1\) y la columna \(j\) para \(j = 1,2,3\).
Calculemos las matrices \(A_{1j}.\)
Entonces tendríamos que el determinante es
Finalmente calculamos el valor módulo \(7\). Por lo tanto, tenemos que \(det(A) = -9\equiv 5\pmod{7}.\)
Para encontrar la inversa de matrices de tamaño de \(n\times n\) en donde \(n > 2\), necesitamos los siguientes resultados de álgebra lineal.
Definición 47 (Matriz adjunta)
La matriz adjunta módulo \(m\) de una matriz \(A\) de tamaño \(n\times n\) es la matriz \(C\) de cofactores de tamaño \(n\times n\) donde la \((i,j)\)-ésima entrada es el cofactor \(c_{ji} \equiv (-1)^{i+j}\cdot det(A_{ij}) \pmod{m}\). La matriz \(A_{ij}\), es la matriz obtenida al eliminar la \(i\)-ésima fila y la \(j\)-ésima columna de la matriz \(A\).
La matriz adjunta de una matriz \(A\) la vamos a denotar como \(adj(A)\).
Veamos un ejemplo para ilustrar como calcular la matriz adjunta.
Ejemplo 135
Calcula la matriz adjunta de \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\) módulo \(7\).
Solución.
Primero necesitamos calcular los valores \(c_{ij}\).
Vamos a calcular la entrada \(c_{11}\).
Para obtener \(A_{11}\) vamos a eliminar la fila \(1\) y la columna \(1\), es decir
Calculemos \(c_{12}\).
Obtengamos \(A_{12}\), eliminando la fila \(1\) y la columna \(2\) obteniendo
Continuando este proceso calcularíamos la entrada \(c_{33}\).
\(A_{33}\) la obtenemos eliminando la fila \(3\) y la columna \(3\), así obtenemos que
Así, tenemos los cofactores:
Por lo tanto la matriz adjunta es,
El siguiente teorema nos será de mucha ayuda para llegar a una fórmula que nos ayude a calcular la inversa de una matriz de \(n\times n\). Veremos con un ejemplo que se cumple, sin embargo, puedes consultar mas sobre el tema en el siguiente enlace.
Teorema 59
Si \(A\) es una matriz de tamaño \(n\times n\) con \(det(A)\neq 0\), entonces se cumple que \(A\cdot adj(A) = det(A)\cdot I_n\), en donde \(adj(A)\) es la matriz adjunta de \(A\) e \(I_n\) es la matriz identidad de tamaño \(n\times n\).
Vamos a usar los valores calculados en el Ejemplo 134 y el Ejemplo 135 para ver que se cumple el teorema.
Ejemplo 136
Sea \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\). Verifica que se cumple el Teorema 59.
Solución.
Ya calculamos que \(det(A) = 5\pmod{7}\) y que \(adj(A) \equiv \begin{pmatrix} 2 & 1 & 2 \\ 5 & 3 & 0 \\ 0 & 3 & 2 \\ \end{pmatrix} \pmod{7}.\)
Entonces tendríamos que
Con todo lo anterior, vamos a presentar el teorema que nos brinda una fórmula para calcular la matriz inversa.
Teorema 60 (Matriz inversa módulo \(m\))
Si \(A\) es una matriz de tamaño \(n\times n\) con entradas enteras y \(m\) es un entero positivo tal que \((det(A),m) = 1\), entonces la matriz \(\bar{A} = \bar{\Delta} \cdot adj(A)\) es la matriz inversa de \(A\) módulo \(m\), en donde \(\bar{\Delta}\) es el inverso de \(\Delta = det(A)\) módulo \(m\).
Demostración. Como \((det(A),m) = 1\), sabemos que \(det(A) \neq 0\). Luego por el Teorema 59 tendríamos que
Vamos a ver que se cumple la Definición 46 para \(A\) y para \(\bar{A} = \bar{\Delta} \cdot adj(A)\).
Primero revisemos que pasa con \(A\bar{A}\).
Ahora veamos que pasa con \(\bar{A} A\).
Por lo tanto \(\bar{A} = \bar{ \Delta} \cdot adj(A)\) es la inversa de \(A\) módulo \(m\). \(\square\)
Con el Teorema 60 tenemos lo necesario para encontrar la matriz inversa de una matriz de tamaño \(n\times n\).
Ejemplo 137
Dada la matriz \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\), calcula su matriz inversa módulo \(7\).
Solución.
Vamos a usar Teorema 60 para encontrar la matriz inversa. Ya tenemos los cálculos del determinante y la matriz adjunta los cuales son
Como \((5,7) = 1\), entonces \(\Delta\) tiene inverso, que es \(\bar{\Delta} = 3\).
Luego, la matriz inversa sería
En el Ejemplo 132 puedes comprobar que \(\bar{A}\) sí es la matriz inversa de \(A\).
Por lo tanto, se cumple que \(A\bar{A} \equiv \bar{A} A \equiv I_3 \pmod{7}\).
Observación 18
Con todo el desarrollo anterior podemos utilizar la matriz inversa de \(A\) módulo \(m\), cuando existe, para resolver el sistema
Por lo tanto, encontramos la solución \(X\) que es \(\bar{A}B \pmod{m}.\)
Para terminar esta sección, veamos un ejemplo de un sistema de congruencias de \(3\) congruencias con \(3\) variables.
Ejemplo 138
Resuelve el sistema de congruencias lineales
Solución.
El sistema anterior lo podemos escribir en notación matricial y es equivalente a
Por la observación Observación 18, para resolver el sistema tendríamos que multiplicar por la matriz inversa. Recordemos que en el Ejemplo 137 calculamos la matriz inversa de \(A = \begin{pmatrix} 4 & 5 & 3 \\ 5 & 5 & 2 \\ 3 & 3 & 3 \\ \end{pmatrix}\) la cual es \(\bar{A} = \begin{pmatrix} 6 & 3 & 6 \\ 1 & 2 & 0 \\ 0 & 2 & 6 \\ \end{pmatrix}\). Entonces, tendríamos lo siguiente:
Por lo tanto, tendríamos que \(x_1\equiv 3\pmod{7}\), \(x_2\equiv 0\pmod{7}\) y \(x_3\equiv 2\pmod{7}.\)
Comprobemos estas soluciones.
El método que mostramos para resolver los sistemas de congruencias no es el único. Puedes adaptar métodos de álgebra lineal para resolver este tipo de sistemas, en donde la división es reemplazada por multiplicación por el inverso módulo \(m\).
Código para resolver un sistema de congruencias#
El siguiente código nos servirá para resolver sistemas de congruencias lineales con \(n\) variables y \(n\) congruencias. Para ellos vamos a utilizar el método mostrado en esta sección.
Primero vamos a crear las funciones necesarias para calcular el producto de matrices, el determinante y la matriz adjunta.
Como ejemplo, para estos códigos vamos a usar la matriz del Ejemplo 138
Además, vamos a utilizar listas para representar las matrices, es decir, si tenemos la matriz
A = [[a,b,c], [d,e,f], [g,h,i]]
La siguiente función nos ayuda a calcular el producto entre matrices módulo \(m\).
def matrices_producto(matriz_A,matriz_B,m):
col_A = len(matriz_A[0])
fil_A = len(matriz_A)
col_B = len(matriz_B[0])
fil_B = len(matriz_B)
producto = [[0 for a in range(col_B)] for b in range(fil_A)]
if col_A != fil_B:
return print(f"Las matrices no se pueden multiplicar ya que las columnas de A son diferentes a las filas de B")
else:
for i in range(fil_A):
for j in range(col_B):
for k in range(fil_B):
producto[i][j] += matriz_A[i][k]*matriz_B[k][j]
producto[i][j] %= m
return producto
matriz_A = [[4,5,3],[5,5,2],[3,3,3]]
matriz_B = [[6,3,6],[1,2,0],[0,2,6]]
matrices_producto(matriz_A, matriz_B,7)
[[1, 0, 0], [0, 1, 0], [0, 0, 1]]
La siguiente función nos ayuda a calcular el determinante de una matriz de tamaño de \(n\times n\).
def calcular_determinante(matriz,m):
if len(matriz) != len(matriz[0]):
return print("La matriz no es cuadrada")
if len(matriz) == 2:
return matriz[0][0]*matriz[1][1] - matriz[0][1]*matriz[1][0]
determinante = 0
for columna in range(len(matriz)):
submatriz = [fila[:columna] + fila[columna + 1:] for fila in matriz[1:]]
sign = (-1)**columna
factor = sign * matriz[0][columna] * calcular_determinante(submatriz,m)
determinante += factor
return determinante % m
matriz_A = [[4,5,3],[5,5,2],[3,3,3]]
calcular_determinante(matriz_A,7)
5
La siguiente función nos ayuda a calcular la matriz adjunta de una matriz de tamaño de \(n\times n\).
def calcular_adjunta(matriz,m):
n = len(matriz)
adjunta = []
for i in range(n):
adjunta_fila = []
for j in range(n):
submatriz = [fila[:j] + fila[j+1:] for fila in (matriz[:i] + matriz[i+1:])]
signo = (-1)**(i+j)
cofactor = signo * calcular_determinante(submatriz,m)
cofactor %= m
adjunta_fila.append(cofactor)
adjunta.append(adjunta_fila)
adjunta = [list(fila) for fila in zip(*adjunta)]
return adjunta
matriz_A = [[4,5,3],[5,5,2],[3,3,3]]
calcular_adjunta(matriz_A,7)
[[2, 1, 2], [5, 3, 0], [0, 3, 2]]
La siguiente función nos ayuda a calcular el máximo común divisor y el inverso del determinante módulo \(m\).
def euclides_extendido_ciclos(a,b):
s=[1,0]
t=[0,1]
while b!=0:
q=a//b
r=a%b
nuevo_s=s[-2]-q*s[-1]
nuevo_t=t[-2]-q*t[-1]
s.append(nuevo_s)
t.append(nuevo_t)
a,b=b,r
return s[-2],t[-2],a
def inverso_modn(a,m):
alfa,beta,d = euclides_extendido_ciclos(a,m)
if d == 1:
return alfa,d
La siguiente función nos ayudará a resolver un sistema de congruencias lineales de tamaño \(n\times n\).
def resolver_sis_congr (A,b,m):
determinante = calcular_determinante(A,m)
inverso,d = inverso_modn(determinante,m)
if d == 1:
adjunta_A = calcular_adjunta(A,m)
inversa_A = [[(inverso * a_ij)%m for a_ij in fila] for fila in adjunta_A]
resultado = matrices_producto(inversa_A,b,m)
return resultado
else:
return print(f"El determinante {determinante} no tiene inverso módulo {m}")
Vamos a resolver el siguiente sistema de congruencias con el código realizado.
A = [[4,5,3],[5,5,2],[3,3,3]]
b = [[4], [5], [1]]
resolver_sis_congr(A,b,7)
[[3], [0], [2]]
Ahora, resolvamos el siguiente sistema de congruencias con el código realizado.
A = [[2,5,6],[2,0,1],[1,2,3]]
b = [[3], [4], [1]]
resolver_sis_congr(A,b,7)
[[4], [1], [3]]
Hay que notar que aunque el algoritmo utilizado para resolver los sistemas de congruencias funciona, no es óptimo cuando se trata de matrices grandes, lo que significa que el tiempo de cálculo crece muy rápidamente a medida que aumenta el tamaño de la matriz. Para matrices de tamaño \(2\times 2\) y \(3\times 3\), el código se realiza en un tiempo aceptable. Para matrices de tamaño más grande que \(10\times 10\), el tiempo de ejecución se vuelve muy grande.
Explicación del código#
En este capítulo vimos que podemos crear una lista de listas usando la comprensión de listas dentro de una comprensión de lista, esto nos funcionó para crear una matriz en donde todas sus entradas son ceros.
matriz = [[0 for a in range(n)] for b in range(m)]
Lo que hace el código es ejecutar primero la comprensión de listas interior creando una lista que contiene \(n\) elementos. Luego esta lista se genera \(m\) veces, lo que da como resultado una lista que contiene \(m\) listas, es decir una matriz de \(n\times m\) en donde todas las entradas son cero.
Vimos una nueva forma de seleccionar elementos en una lista.
lista = [1,2,3,4,5,6,7,8]
lista_1 = lista[:4]
lista_2 = lista[4:]
La variable «lista_1» nos regresaría la lista \([1,2,3,4]\). Utilizamos el símbolo : para indicar que queremos seleccionar desde el primer elemento con índice \(0\) hasta el elemento con índice \(3\). Recordemos que Python toma una elemento anterior por la derecha al que le indiquemos.
La variable «lista_2» nos regresaría la lista \([5,6,7,8]\), en este caso utilizamos el símbolo : para indicarle a Python que queremos seleccionar desde el elemento con índice \(4\) hasta el último de la lista.
El uso que le dimos a esta forma de selección fue para quitar elementos intermedios de una lista.
lista = [1,2,3,4,5,6,7,8]
lista_1 = lista[:4]
lista_2 = lista[5:]
lista_3 = lista_1 + lista_2
El valor de la variable «lista_3» sería una lista sin el elemento con el índice \(4\) de la lista original, es decir que tendríamos la lista \([1,2,3,4,6,7,8]\).
También vimos la función zip() la cual nos ayuda a “desempaquetar”. Lo que hace es combinar las listas de una lista de listas, es decir que transpone la matriz. Veamos el siguiente ejemplo que nos ayudará a comprender qué sucede al aplicar esta función a una lista de listas.
matriz = [[a1, a2, a3],[b1, b2, b3], [c1, c2, c3]]
transponer = zip(*matriz)
El resultado de la variable «transponer» sería una lista de tuplas es decir \([(a_1, b_1, c_1), (a_2, b_2, c_2), (a_3, b_3,c_3)]\).
Representado con matrices tendríamos que la matriz
Veamos cómo funciona el código para hacer el producto de matrices.
def matrices_producto(matriz_A,matriz_B,m):
col_A = len(matriz_A[0])
fil_A = len(matriz_A)
col_B = len(matriz_B[0])
fil_B = len(matriz_B)
producto = [[0 for a in range(col_B)] for b in range(fil_A)]
if col_A != fil_B:
return print(f"Las matrices no se pueden multiplicar ya que las columnas de A son diferentes a las filas de B")
else:
for i in range(fil_A):
for j in range(col_B):
for k in range(fil_B):
producto[i][j] += matriz_A[i][k]*matriz_B[k][j]
producto[i][j] %= m
return producto
Definimos una función llamada «matrices_producto» la cual recibe \(3\) argumentos, los dos primeros son matrices que deben estar escritas en forma de listas de listas y el tercero es un valor entero el cual es el módulo.
Enseguida creamos \(4\) variables «col_A», «fil_A», «col_B» y «fil_B» las cuales con ayuda de la funciónlen()nos sirven para saber cuántas filas y columnas tienen las matrices que se introducen en la función.
def matrices_producto(matriz_A,matriz_B,m):
col_A = len(matriz_A[0])
fil_A = len(matriz_A)
col_B = len(matriz_B[0])
fil_B = len(matriz_B)
Creamos la variable «producto» la cual es una lista de comprensión dentro de otra lista de comprensión y genera una matriz la cual contiene puros ceros en sus entradas.
producto = [[0 for a in range(col_B)] for b in range(fil_A)]
Luego creamos un condicional
ifen el cual la condición es, si las columnas de la primer matriz no son iguales a las filas de la segunda matriz, el código nos imprime la leyenda de que las matrices no se pueden multiplicar. En el caso en que las columnas y fila si sean la misma cantidad, pasamos al condicionalelse, el cual contiene tres ciclosfor. El primer ciclo recorre los índices de las filas de la primera matriz, el segundo ciclo recorre los índices de las columnas de la segunda matriz y el tercer ciclo recorre las filas de la segunda matriz. Luego, en la variable «producto[ i ][ j ]» se va guardando la suma del producto entre el elemento de la fila \(i\) y columna \(k\) de la primera matriz por el elemento de la fila \(k\) y columna \(j\) de la segunda matriz. En cada iteración al resultado se le aplica módulo \(m\). Finalmente, la función nos regresa como resultado la matriz «producto».
if col_A != fil_B:
return print(f"Las matrices no se pueden multiplicar ya que las columnas de A son diferentes a las filas de B")
else:
for i in range(fil_A):
for j in range(col_B):
for k in range(fil_B):
producto[i][j] += matriz_A[i][k]*matriz_B[k][j]
producto[i][j] %= m
return producto
Ahora veamos el código para calcular el determinante de una matriz.
def calcular_determinante(matriz,m):
if len(matriz) != len(matriz[0]):
return print("La matriz no es cuadrada")
if len(matriz) == 2:
return matriz[0][0]*matriz[1][1] - matriz[0][1]*matriz[1][0]
determinante = 0
for columna in range(len(matriz)):
submatriz = [fila[:columna] + fila[columna + 1:] for fila in matriz[1:]]
sign = (-1)**columna
factor = sign * matriz[0][columna] * calcular_determinante(submatriz,m)
determinante += factor
return determinante % m
Definimos una función llamada «calcular_determinante» la cual recibe como argumento una matriz, que es una lista de listas y un entero \(m\) el cual es el módulo. Como el determinante es para matrices cuadradas, primero con un condicional
ifrevisamos que el número de columnas de la matriz coincida con el número de filas. Si no son iguales, el código nos imprime que la matriz no es cuadrada.
def calcular_determinante(matriz,m):
if len(matriz) != len(matriz[0]):
return print("La matriz no es cuadrada")
Si la matriz es cuadrada, el código pasa al siguiente bloque, el cual es otro condicional
if, en que se verifica si el tamaño de la matriz es de \(2\times 2\). Si la condición es cierta entonces el código nos regresa el determinante calculado con la fórmula \(\Delta = ad - bc\) y ese es el valor que nos regresa la función.
if len(matriz) == 2:
return matriz[0][0]*matriz[1][1] - matriz[0][1]*matriz[1][0]
Creamos la variable «determinante» con un valor inicial de \(0\). Es donde se va a guardar el valor final de la cuenta.
Si el código pasa a este bloque quiere decir que la matriz es de tamaño mas grande que \(2 \times 2\).
Para calcular el determinante vamos a usar el método mostrado en el curso de Álgebra Superior I.
Al no contar con una fórmula para calcular directamente el determinante de una matriz de tamaño \(n\times n\), lo que hace el código es reproducir el algoritmo mostrado en las notas mencionadas. Esto se logra llamando a la función «calcular_determinante» dentro de la misma función «calcular_determinante».
Es decir, con el ciclo for recorremos las columnas. Luego, con una comprensión de listas, quitamos el índice de la columna en cada lista dentro de la matriz y esto lo hace sin tomar en cuenta la primer lista de la matriz, así reducimos la matriz, guardando este resultado en la variable «submatriz». La variable «sign» calcula el signo y la variable «factor» contiene el calculo sign * matriz[0][columna] * calcular_determinante(submatriz,m), es decir, \((-1)^{i+j}\cdot a_{ij} \cdot det(A_{ij}).\) La matriz \(A_{ij}\) es el valor obtenido en la variable «submatriz», si ésta no es de tamaño \(2\times 2\), entonces el código vuelve a realizar los pasos hasta calcular el valor del primer factor. Esto se repite hasta tener todos los valores calculados y así poder obtener el determinante. Finalmente, lo que nos regresa la función es el valor de determinante módulo \(m\).
determinante = 0
for columna in range(len(matriz)):
submatriz = [fila[:columna] + fila[columna + 1:] for fila in matriz[1:]]
sign = (-1)**columna
factor = sign * matriz[0][columna] * calcular_determinante(submatriz,m)
determinante += factor
return determinante % m
Veamos el código para calcular la matriz adjunta.
def calcular_adjunta(matriz,m):
n = len(matriz)
adjunta = []
for i in range(n):
adjunta_fila = []
for j in range(n):
submatriz = [fila[:j] + fila[j+1:] for fila in (matriz[:i] + matriz[i+1:])]
signo = (-1)**(i+j)
cofactor = signo * calcular_determinante(submatriz,m)
cofactor %= m
adjunta_fila.append(cofactor)
adjunta.append(adjunta_fila)
adjunta = [list(fila) for fila in zip(*adjunta)]
return adjunta
Definimos una función llamada «calcular_adjunta» que recibe dos argumentos, el primero es la matriz y el segundo es el módulo. Creamos dos variables «n» que nos dice el tamaño de la matriz y «adjunta» que es una lista vacía. Notemos que no se verifica que la matriz sea cuadrada ya que como más adelante usamos la función «calcular determinante», de no ser cuadrada nos lo diría esa parte del código.
def calcular_adjunta(matriz,m):
n = len(matriz)
adjunta = []
Comenzamos un ciclo
forcon el cual se recorren las filas de la matriz. Se crea la variable «adjunta_fila» la cual es una lista vacía, en donde vamos a guardar las filas de la matriz adjunta.
Luego empezamos otro ciclofordentro del primer ciclo, con este segundo ciclo recorremos las columnas de la matriz. Como vimos en el Ejemplo 135, tenemos que calcular la matriz de cofactores eliminando la fila \(i\) y la columna \(j\). Eso es lo que logramos con la variable «submatriz», con la instrucciónfila[:j] + fila[j+1:]eliminamos la columna \(j\) y con la instrucciónmatriz[:i] + matriz[i+1:]quitamos la fila \(i\).
Con la variable «signo» calculamos el signo del cofactor.
En la variable «cofactor» calculamos el valor de las entradas de la matriz adjunta multiplicando el signo por el determinante de la submatriz. En este paso aplicamos la función «calcular_determinante», la cual ya vimos cómo funciona, entonces una vez calculado el valor se simplifica módulo \(m\). Este valor se agrega a la lista «adjunta_fila». Una vez que tenemos todos los cofactores de la primera fila, esta lista se guarda en la variable «adjunta», la cual va a ser la lista de listas que forme la matriz.
for i in range(n):
adjunta_fila = []
for j in range(n):
submatriz = [fila[:j] + fila[j+1:] for fila in (matriz[:i] + matriz[i+1:])]
signo = (-1)**(i+j)
cofactor = signo * calcular_determinante(submatriz,m)
cofactor %= m
adjunta_fila.append(cofactor)
adjunta.append(adjunta_fila)
Finalmente cambiamos el valor de la variable «adjunta» con una comprensión de listas. Con la instrucción
list(fila)tomamos cada fila de la matriz creada con la funciónzip(*adjunta)y nos regresa la matriz adjunta.
adjunta = [list(fila) for fila in zip(*adjunta)]
return adjunta
Por último, veamos el código para resolver un sistema de congruencias lineales.
def resolver_sis_congr (A,b,m):
determinante = calcular_determinante(A,m)
if algoritmo_euclides(determinante,m) == 1:
det_inverso = inverso_modn(determinante,m)
adjunta_A = calcular_adjunta(A,m)
inversa_A = [[(det_inverso * a_ij)%m for a_ij in fila] for fila in adjunta_A]
resultado = matrices_producto(inversa_A,b,m)
return resultado
else:
return print(f"El determinante {determinante} no tiene inverso módulo {m}")
Definimos una función llamada «resolver_sis_congr», la cual recibe como argumentos una lista de listas la cual representa una matriz cuadrada, una lista con listas de \(1\) sólo elemento la cual representa la columna de valores independientes del sistema de congruencias y por último un entero positivo el cual es el módulo que se va a trabajar.
Creamos la variable «determinante», en donde aplicamos la función «calcular_determinante» para obtener el determinante de la matriz ingresada en los argumentos.
def resolver_sis_congr (A,b,m):
determinante = calcular_determinante(A,m)
Luego comenzamos un condicional
ifen el cual la condición es que el máximo común divisor del determinante y el módulo \(m\) debe ser igual a \(1\). Si la condición es verdadera el código continua. Primero calcula la variable «det_inverso» en la cual usamos la función «inverso_modn» para encontrar el inverso multiplicativo del determinante. Luego calcula la variable «adjunta_A» en la cual usamos la función «calcular_adjunta» para obtener la matriz adjunta. Después calcula la variable «inversa_A» la cual se calcula con el Teorema 60 el cual nos dice que la matriz inversa se obtiene multiplicando el inverso multiplicativo del determinante por la matriz adjunta. Como estamos multiplicando un número entero por una matriz, necesitamos multiplicar todos los elementos de la matriz. Eso lo logramos con una comprensión de listas. Finalmente, calcula la variable «resultado» que se obtiene de multiplicar la variable «inversa_A» por la variable \(b\) que es el segundo argumento que dimos a la función original y aplicamos módulo \(m\).
if algoritmo_euclides(determinante,m) == 1:
det_inverso = inverso_modn(determinante,m)
adjunta_A = calcular_adjunta(A,m)
inversa_A = [[(det_inverso * a_ij)%m for a_ij in fila] for fila in adjunta_A]
resultado = matrices_producto(inversa_A,b,m)
return resultado
En caso de que el máximo común divisor entre el determinante y el módulo no sea \(1\), el código pasa al condicional
elseque nos arroja un mensaje diciendo que no se puede calcular el inverso del determinante módulo \(m\).
else:
return print(f"El determinante {determinante} no tiene inverso módulo {m}")
Ejercicios de práctica#
Resuelve los siguientes sistemas usando el método de eliminación.
\(5x + 6y\equiv 10\pmod{13}\) y \(6x - 7y\equiv 2\pmod{13}\).
\(7x + 8y\equiv 11\pmod{15}\) y \(5x - 9y\equiv 10\pmod{15}\).
\(x - 2y -z\equiv 6\pmod{11}\), \(2x + 3y + z\equiv 5\pmod{11}\) y \(3x + y + 2z\equiv 2\pmod{11}\).
Resuelve los siguientes sistemas de ecuaciones utilizando la notación matricial.
\(x + 2y + 3z \equiv 1\pmod{7}\), \(x + 2y + 5z \equiv 1\pmod{7}\) y \(x + 4y + 6z \equiv 1\pmod{7}\).
\(x + y + z \equiv 1\pmod{7}\), \(x + y + w \equiv 1\pmod{7}\), \(x + z + w \equiv 1\pmod{7}\) y \(y + z + w \equiv 1\pmod{7}\).