jueves, 25 de agosto de 2022

Fotografía matemática compulsiva: matrices y submatrices

$\diamond$

Divisors d'un nombre enter no negatiu. Un exercici de programació amb l'eina GNU MAXIMA

    Si us agrada programar una mica és un bon exercici escriure una senzilla línia d'instruccions amb MAXIMA per escriure la llista de nombres divisors d'un nombre enter no negatiu donat:
    (%i1) for i:1 thru 30 do (if mod(30,i)=0 then print(i));
Obtindrem ràpidament tots el divisors: {1, 2, 3, 5, 6, 10, 15, 30}
Potser convindreu que no té molt d'interès perquè, de fet, el nombre que hem posat és molt petit. Ara bé, i si fos, posem pel cas, 1452 ? Deu n'hi do de la feinada que tindrem si ho fem amb paper i llapis, fins i tot, fent-ho d'una manera exhaustiva amb l'ajut d'un diagrama d'arbre tal com vaig explicar en un article anterior. Modificant la dada, obtindrem el resultat amb un dit i fet
    (%i2) for i:1 thru 1452 do (if mod(1452,i)=0 then print(i));
... 1 2 3 4 6 11 12 22 33 44 66 121 132 242 363 484 726 1452

I encara molt millor si escrivim una funció amb un paràmetre d'entrada per no haver d'escriure cada vegada la instrucció repetitiva:

    (%i3) troba_divisors(n):=(
for i:1 thru n do (if mod(n,i)=0 then print(i))
)$


Funció que farem servir concretant el nombre del qual volem trobar els divisors:

    (%i4) troba_divisors(235456);

Aquest és el resultat del càlcul:
1 2 4 8 13 16 26 32 52 64 104 208 283 416 566 832 1132 2264 3679 4528 7358 9056 14716 18112 29432 58864 117728 235456

Val a dir, però, que MAXIMA disposa ja d'una funció predefinida divisors(). No cal programar-ne un altra. El que m'ha mogut a escriure-la és només per exposar un exercici elemental de programació. La funció predefinida és més eficaç que la que he escrit perquè l'algorisme emprat per MAXIMA és molt millor. Comproveu-ho. Us adonareu que el resultat amb la funció divisors() s'obté molt més ràpidament i, a més, estructurat com una llista:


    (%i5) divisors(235456);

    (%o5){1,2,4,8,13,16,26,32,52,64,104,208,283,416,566,832,
1132,2264,3679,4528,7358,9056,14716,18112,29432,58864,117728,235456}

$\diamond$

La identidad de Bézout

El lema de Bézout

Un resultado básico relacionado con el máximo común divisor de dos números (enteros), distintos de cero, $a,b$ —y lo notaremos de la forma $(a,b)$—, es la denominada identidad de Bezout (lema de Bezout), que dice así:

  Sea $\mathbb{Z} \ni d=(a,b)$, entonces existen dos números enteros $x,y$, no necesariamente únicos, tales que $d=ax+by \quad \quad (1)$.

Ejemplo. Consideremos los números enteros $2$ y $4$. El máximo común divisor de estos dos números es $d=2$, luego, según el lema de Bézout, existen (infinitas) parejas de números $x$ e $y$, tales que $2=2x+4y$. Nos proponemos encontrar cómo son estas infinitas parejas de números $x,y$.

En un caso general, consideremos dos soluciones particulares $x_1,y_1$ y $x_2,y_2$ de la ecuación $d=ax+by$, y que por tanto se sastisfaga $d=a\,x_1+b\,y_1$ y $d=a\,x_2+b\,y_2$. Entonces, como la estructura algebraica que liga los otros infinitos pares de valores es lineal, estas parejas de números enteros están alineadas en una recta cuyas ecuaciones paramétricas son $\left\{\begin{matrix}x-x_1 = \lambda\,(x_2-x_1)\\y-y_1=\lambda\,(y_2-y_1)\end{matrix}\right.\,; \lambda\in \mathbb{Z}$, o, dicho de otro modo, la solución general vendrá dada por $$\left\{\begin{matrix}x=x_1+ \lambda\,(x_2-x_1)\\y=y_1+\lambda\,(y_2-y_1)\end{matrix}\right.\,; \lambda\in \mathbb{Z}\quad \quad (2)$$ donde $x_2-x_1$ e $y_2-y_1$ son, desde luego, números enteros.

Se puede comprobar sin dificultad que, para toda solución particular$x_p,y_p$ de (1), entonces $x_p+kb$ e $y_p-ka$, para cualquier $k\in \mathbb{R}$, también constituye otra solución particular de la misma ecuación; en efecto $a\,(x_p+kb)+b\,(y_p-ka) = a\,x_p+kab+b\,y_p-kab=a\,x_p+b\,y_p$, y, por tanto, $a\,(x_p+kb)+b\,(y_p-ka)=d$. Entonces, podemos escoger los números enteros $x_2-x_1$ e $y_2-y_1$ de los segundos términos de los respectivos segundos miembros de (2) de la forma $x_2-x_1:=\dfrac{b}{d}$ e $y_2-y_1:=-\dfrac{a}{d}$, habida cuenta de que $\dfrac{b}{d} \in \mathbb{Z}$ y $\dfrac{a}{d}\in \mathbb{Z}$ por ser $d=(a,b)$. Así las cosas, podemos escribir las ecuaciones paramétricas (2) de la forma: $$\left\{\begin{matrix} x=x_1+\lambda\,\dfrac{b}{d} \\y=y_1-\lambda\,\dfrac{a}{d} \end{matrix}\right.\,;\lambda\in \mathbb{Z} $$

Resolvamos ahora el ejemplo concreto que nos hemos planteado. Fácilmente, vemos que una solución particular es $x_1=-1$, $y_1=1$ —en efecto, comprobamos que para estos valores de $x$ e $y$ se satisface (1): $2=2\cdot (-1)+4\cdot 1$—, con lo cual, y según lo que hemos razonado arriba, se tiene que $$\left\{\begin{matrix}x=-1+\dfrac{4}{2}\,\lambda\\y=1-\dfrac{2}{2}\,\lambda\end{matrix}\right.\,; \lambda \in \mathbb{Z}$$ esto es $$\left\{\begin{matrix}x=-1+2\,\lambda\\y=1-\lambda\end{matrix}\right.\,; \lambda \in \mathbb{Z}$$ Podemos pues encontrar los infinitos pares de valores $x$ e $y$ que son solución de (1) asignando valores arbitraios al parámetro entero $\lambda$. Así, para $\lambda=0$ se obtiene la solución particular de la que hemos partido: $x=-1$ e $y=1$; para $\lambda=1$, $x=1$ e $y=0$; para $\lambda=2$, $x=3$ e $y=-1$; para $\lambda=-1$, $x=-3$ e $y=2$; para $\lambda=-2$, $x=-5$ e $y=3$, etcétera.

Ecuaciones diofánticas lineales

Una utilidad muy importante de la identidad de Bézout es la de formar parte del proceso de resolución de una ecuación diofántica lineal, $cx+dy=k$, con $c,d,k\in \mathbb{Z}$, para encontrar la solución general, a partir de una solución particular, se procede de una forma muy parecida a la que estamos empleando para encontrar las parejas de valores $x,y$ de la igualdad de Bézout, y lo expongo en este otro artículo (de este mismo cuaderno), mediante un ejemplo práctico.$\diamond$

miércoles, 24 de agosto de 2022

Un sencillo ejercicio sobre bases de numeración

En este sencillo ejercicio, expresaremos $16$ (dado en base $10$) en base $3$.

El conjunto de números con el que debemos expresar una cierta cantidad en base $3$ es $\{0,1,2\}$. Vamos a expresar $16$ en serie de potencias de base $3$. Hecho esto, sabemos que la secuencia de los coeficientes de las potencias (ceros, unos y doses), escritos en el orden de mayor a menor grado del término a que corresponda será la expresión pedida.

Empecemos pues dividiendo $16$ entre $3$. Se obtiene cociente igual a $5$ y resto igual a $1$, por lo que, por el teorema de la división euclídea (t.d.e.), podemos escribir $16=5\cdot 3+1 \quad \quad (1)$; por otra parte, al dividir $5$ entre $3$, obtenemos cociente igual a $1$ y resto igual a $2$, luego por el t.d.e, $5=3\cdot 1+2$, que, sustituido en (1), permite escribir $16=(3\cdot 1+2)\cdot 3+1=3^2+2\cdot 3+1=1\cdot 3^2+2\cdot 3^1+1\cdot 3^0$. En consecuencia, $$16_{10}=121_{3}$$ $\diamond$

lunes, 22 de agosto de 2022

La función indicatriz de Euler, el teorema de Euler-Fermat y el pequeño teorema de Fermat

La función indicatriz de Euler

La función indicatriz de Euler es muy importante en teoría de números. La función indicatriz de Euler de un número entero positivo $m$, y se escribe $\varphi(m)$, proporciona el número de números enteros positivos, menores o iguales que $m$, que son coprimos con $m$. En el lenguaje matemático: $\varphi(m):=\text{cardinal}\left(\{n\in \mathbb{N}: (1\le n \le m) \wedge \text{m.c.d.}(m,n)=1\}\right)$. Se demuestra que dicha cantidad es igual a $\displaystyle \varphi(m):=m\,\prod_{p_i|m}\,\left(1-\dfrac{1}{p_i}\right)$; siendo $\{p_i\}$, el conjunto de números primos que dividen a $m$. Así, por ejemplo $\varphi(9)=9\cdot \left(1-\dfrac{1}{3}\right)=9\cdot \dfrac{2}{3}=6$; en efecto, el conjunto de números naturales que cumplen la condición requerida es $\{1,2,4,5,7,8\}$, y, claro está que $\text{cardinal}\left(\{1,2,4,5,7,8\}\right)=6$

El teorema de Euler-Fermat

La función indicatriz de Euler-Fermat aparece por ejemplo en el teorema de Euler-Fermat: Si $a,m \in \mathbb{N}$ son primos relativos, esto es, $\text{m.c.d.}(a,m)=1)$, entonces $a$ es congruente con $1$ módulo $m$: $a^{\varphi(m)} \equiv 1 (\text{mod}\, m)$, y es de gran importancia en el cálculo de congruencias.

El pequeño teorema de Fermat

El teorema de Euler-Fermat generaliza el pequeño teorema de Fermat. El pequeño teorema de Fermat dice así: dado un número $p$, primo, y un número entero $a$, siendo $a$ y $p$ coprimos, esto es $\text{m.c.d.}(a,p)=1$, entonces $a^{p-1}\equiv 1 (\text{mod}\, p)$, afirmación que es equivalente a $a^p ≡ a (\text{mod}\, p)$. Por ejemplo, si $p=3$ y $a=4$, se tiene que el residuo de la división euclídea de $a^p=4^{3-1}=16$ entre $3$ es $1$, como debe ser; esto es, el residuo de la división $4^3=64$ entre $3$ es igual a $4$.

-oOo-

Observación. Una consecuencia de este teorema es la siguiente: Como al dividir $a^{p-1}$ entre $p$ se obtiene resto igual a $1$, existe un $k\in \mathbb{Z}$ para el cual $a^{p-1}=k\, p +1$, multiplicando por $a$ en cada miembro de la igualdad, se tiene que $a^{p}= k \,p \,a + a$, luego $a^{p} - a$ es múltiplo de $p$ puesto que $k\,a$ és también un número entero.

Ejemplo. Sea $a=9$ y $p=2$ (primo), siendo $(9,2)=1$ y cumpliéndose así las condiciones suficientes del teorema. Comprabamos, en efecto, que $a^p=9^2=81 \mod 2 = 1$, coincidiendo con $a=9 \mod 2 =1$; y, además, $a^p-a \in (\overset{.}{p})$ pues $81-8=72 \in (\overset{.}{2})$.

$\diamond$

Nociones básicas de aritmética modular. Congruencias

La operación módulo, para dos números enteros $a$ y $b$, se define como $a \mod b := \text{residuo}( a \div b)$, entendiendo la división como la división euclídea: dados $a\in \mathbb{Z}$ y $\mathbb{Z}\ni b\neq 0$, entonces $\exists!\,q,r\in \mathbb{Z}$ tales que $a=b\cdot q+r \wedge 0\le r \lt |b|$ . Así por ejemplo, $15 \mod 7 =1$, ya que $8=7\cdot 2+1$; $-6 \mod 7 = 1$ ya que $-6=7\cdot (-1) +1$.

Decimos que dados dos números enteros $m$ y $n$ son congruentes entre sí con respecto a un determinado número entero $p$, y lo escribimos $m \equiv n (\mod p)$ si $m \mod p = n \mod p$, esto es, si las divisiones euclídeas $m \div p$ y $n \div p$ tienen el mismo resto. Así, por ejemplo, $15 \equiv 22 (\mod 7)$ ya que $15 \mod 7 = 1 = 22 \mod 7$. Tambien podemos decir, entre otras muchas cosas, que $15 \equiv -6 (\mod 7)$ ya que $15 \mod 7 = 1 = -6 \mod 7$

Esta operación módulo es muy importante en la teoría elemental de números (o matemática discreta): es necesaria en los cálculos con congruencias y también para entender y probar proposiciones. Como ejemplo práctico podemos subrayar que la matemática discreta es fundamental en el diseño de algoritmos y en programación.

Muchas calculadoras científicas incorporan esta operación, y la secuencia de tecleo suele ser (para el ejemplo que comento): [15 $\rightarrow$ mod $\rightarrow$ 7 $\rightarrow$ = (o EXE)], presentándose el resultado, $1$, en pantalla.

La congruencia cumple dos propiedades básicas. Si $a_1 \equiv a_2 (\mod p)$ y $b_1 \equiv b_2 (\mod p)$, entonces:

  • $a_1+b_1 \equiv a_2 + b_2 \,(\mod p)$
  • $a_{1}\cdot b_{1} \equiv a_{2} \cdot b_{2}\, (\mod p)$

Por ejemplo, $26 \equiv 19 (\mod 7)$, ya que $26 \mod 7 = 5 = 19 \mod 7$, y $27 \equiv 13 (\mod 7)$ puesto que $27 \mod 7 = 6 = 13 \mod 7$. Por tanto:

  • $26+27 \equiv 19+13 (\mod 7)$, esto es, $53 \equiv 32 (\mod 7)$; en efecto: $53 \mod 7 = 4 = 32 \mod 7$
  • $26\cdot 27 \equiv 19\cdot 13 (\mod 7)$, esto es, $702 \equiv 247 (\mod 7)$; en efecto: $702 \mod 7 = 2 = 247 \mod 7$

$\diamond$

jueves, 18 de agosto de 2022

Álgebra de permutaciones

Permutaciones

Consideremos el conjunto de índices $\{1,2,\ldots,n\}$. Entendemos por permutación una aplicación inyectiva del conunto $\{1,2,\ldots,n\}$ sobre sí mismo, de manera que $1\mapsto i_1$, $2\mapsto i_2$, $\ldots$, $n\mapsto i_n$, y notamos dicha permutación de la forma $i=[i_1,i_2,\ldots,i_n]$. Así, por ejemplo, la permutación $i=[2,4,3,1]$ significa que a $1$ le corresponde el $2$; al $2$ el $4$; al $3$ el $3$ y al $4$ el $1$, esto es, $i_1=2$, $i_2=4$,$i_3=3$ y $i_4=4$.

A partir de $n$ índices podemos obtener $n!$ permutaciones distintas.

Podemos componer dos permutaciones $i=[i_1,i_2,\ldots,i_n]$ y $j=[j_1,j_2,\ldots,j_n]$, obteniendo otra permutación de las $n!$ posibles. Esta nueva permutación, $k$, que resulta la notamos de la forma $(j\circ i)_k$, leyéndose $i$ compuesta con $j$, queriendo significar con ello que actúa primero la permutación $i$ y en segundo lugar la permutación $j$ sobre el resultado de la primera; así $(j \circ i)_k=j_{i_k}$

Ejemplo de permutación con $n=4$
Consideremos $i=[2,4,3,1]$ y $j=[4,2,1,3]$. Entonces $j\circ i$ es otra permutación, $k=(j\circ i)_k=j_{i_k}$ y es tal que:
  $k_1=j_{i_1}=j_2=2$
  $k_2=j_{i_2}=j_4=3$
  $k_3=j_{i_3}=j_3=1$
  $k_4=j_{i_4}=j_1=4$
Es decir, $$j \circ i=[2,3,1,4]$$

El grupo de permutaciones $(\mathcal{P}_n,\circ)$

El conjunto de las permutaciones, $\mathcal{P}$, de $n$ índices con la operación composición (o producto) de permutaciones, $(\mathcal{P}_n,\circ)$, tiene estructura de grupo. En efecto, la operación es interna; se cumple la propiedad asociativa $i\circ (j\circ k) = (i \circ j) \circ k$, para cualesquiera permutaciones $i,j$ y $k$; y, existe elemento neutro, que no es otro que $e=[1,2,\ldots,n]$, habida cuenta de que $e\circ i=i\circ e$ para toda permutación $i\in \mathcal{P}_n$, y dada cualquier permutación, $i$, existe para ésta un elemento simétrico, que designaremos por $i'$ y es tal que $i_m=n$ si y sólo si $i'_n=m$, para cualesquiera valores de índices $n,m\in \{1,2,\ldots,n\}$, por lo que $i \circ i' = i' \circ i = e$. Cabe decir, además, que, para cualesquiera permutaciones $i$ y $j$, no se cumple la propiedad conmutativa: $i\circ j \neq j \circ i$ luego dicho grupo no es conmutativo.

Ejemplo de cálculo de la permutación inversa de una permutación dada
Consideremos la permutación $\mathcal{P}_4 \ni i=[4,1,2,3]$. Entonces, como $1$ está en el segundo lugar en la permutación $i$, esto es, $i'_1=2$, ya que $i_2=1$; razonando de la misma manera, deducimos que $i'_2=3$, puesto que $i_3=2$; $i'_3=4$ (ya que $i_4=4$), y $i'_4=1$, pues $i_1=4$. Por consiguiente la permutación inversa de $i=[4,3,2,1]$ es $i'=[2,3,4,1]$.
Comprobemos que $e=[1,2,3,4]=i'\circ i=i'_{i_k}$ donde $k=1,2,3,4$:
  $i'_{i_1}=i'_4=1=e_1$
  $i'_{i_2}=i'_1=2=e_2$
  $i'_{i_3}=i'_2=3=e_3$
  $i'_{i_4}=i'_3=4=e_4$
y también que, $e=[1,2,3,4]=i\circ i'=i_{i'_k}$ donde $k=1,2,3,4$:
  $i_{i'_1}=i_2=1=e_1$
  $i_{i'_2}=i_3=2$
  $i_{i'_3}=i_4=3$
  $i_{i_4}=i_1=4$

Trasposiciones

Llamamos trasposición al intercambio de dos índices ($r$ por $s$, y $s$ por $r$) sin alterar el lugar del resto de los índices, y lo escribimos de la forma $(r,s)$. Ejemplo: $(2,4)=[1,4,3,2]$. Resulta evidente que la inversa de una trasposición es ella misma ya que $(r,s)=(s,r)$.

Teorema. Toda permutación se puede escribir como un producto (composición) de un número finito de trasposiciones.
Ejemplo
Se considera la permutación $[3,4,2,1]$. Veamos cómo escribirla como un producto de trasposiciones.
$[3,4,2,1]=(1,3)\circ [1,4,2,3]=$
  $=(1,3)\circ (2,4) \circ [1,2,4,3]$
    $=(1,3)\circ (2,4) \circ (3,4)\circ [1,2,3,4]$, que podemos escribir también como
      $[3,4,2,1]=(1,3)\circ (2,4) \circ (3,4)$, puesto que la última permutación que resulta (a la derecha) en el paso anterior $[1,2,3,4]$ es el elemento neutro del producto.

(...) $\diamond$