Archivo de la etiqueta: algoritmo

Álgebra Superior II: El algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

Introducción

En entradas anteriores estudiamos los conceptos de máximo común divisor y de mínimo común múltiplo. Ahora nos enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar iteradas veces el algoritmo de la división en ciertos números específicos, comenzando con dos enteros $a$ y $b$ para encontrar su máximo común divisor de dos enteros positivos $a$ y $b$.

Lo primero que haremos es explicar el procedimiento mediante el cual podemos encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo de la división. En la siguiente sección daremos la demostración de por qué funciona este procedimiento. Hacia el final de la entrada también veremos que este mismo procedimiento nos permite también escribir al máximo común divisor de dos enteros $a$ y $b$ como combinación lineal de ellos, es decir, de la forma $ra+sb$ con $r$ y $s$ números enteros.

El procedimiento del algoritmo de Euclides

Sean $a, b$ cualesquiera enteros positivos, con $a \neq b$ y $a > b.$ Por el algoritmo de la división, sabemos que siempre existen $q, r \in \mathbb{Z}$ tales que podemos escribir $$a = bq + r, \enspace \text{con} \quad \quad 0 \leq r < b. $$

Luego, como $b$ y $r$ son enteros, también existen $q_1$ y $r_1$ tales que $$b = rq_1 + r_1,\enspace \text{con} \quad \quad 0 \leq r_1 < r.$$

Y como $r$ y $r_1$ son enteros, existen $q_2$ y $r_2 \in \mathbb{Z}^+$ tales que $$r = r_1q_2 + r_2,\enspace \text{con} \quad \quad 0 \leq r_2 < r_1.$$

Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos $b>r>r_1>r_2>\ldots \geq 0$, de modo que debe existir una $i$ tal que $r_i=0$. De esta forma, en el penúltimo paso tendremos que existen $q_{i-1}$ y $r_{i-1}$ enteros tales que $$r_{i-3} = r_{i-2}q_{i-1} + r_{i-1}, \enspace \text{con} \quad \quad 0 \leq r_{i-1} < r_{i-2}.$$

Y en el último paso tendríamos $q_i \in \mathbb{Z}^+$ y $r_i = 0$ tales que
$$r_{i-2} = r_{i-1}q_i + 0, \enspace \text{con} \quad \quad 0 = r_i < r_{i-1} .$$

Lo que nos dice el algoritmo de Euclides es que el último residuo no cero, en este caso $r_{i-1}$ es el máximo común divisor de $a$ y $b$.

Este procedimiento es particularmente útil cuando $a$ y $b$ son números tan grandes, tanto que determinar el máximo común divisor de ellos no sea inmediato. Aunque se comience con números muy grandes, el algoritmo de Euclides encuentra el MCD de manera rápida.

Ejemplo del algoritmo de Euclides

A continuación veremos el algoritmo de Euclides en acción.

Problema. Encuentra el máximo común divisor de $3456$ y $6524$.

Solución. Observamos que $6524 > 3456$. Así, $$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
Aplicando nuevamente el algoritmo de la división, obtenemos
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
Aplicando una vez más el algoritmo de la división, se tiene
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
Siguiendo este procedimiento,
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Como el último residuo no cero es $4$, entonces $(6524, 3456)=4$.

$\square$

Observación. Aunque el algoritmo de Euclides requiere que los números $a$ y $b$ sean positivos, cuando ocurre el caso de que uno de ellos o los dos fueran negativos, no hay un gran obstáculo. Basta sacar el valor absoluto de ambos números al inicio, ya que los divisores de un número negativo son los mismos que los de su valor absoluto.

Veamos un ejemplo que usa esta observación.

Ejemplo. Obtén el máximo común divisor de $-100$ y $45$.

Solución. Como uno de los números es negativo, antes que nada sacamos valores absolutos: $|-100| = 100$ y $|45| = 45.$ Le aplicamos el algoritmo de Euclides a estos números:
$$ 100 = 45 \cdot 2 + 10, \quad \quad 0 \leq 10 < 45. $$
$$ 45 = 10 \cdot 4 + 5, \quad \quad 0 \leq 5 < 10. $$
$$10 = 5 \cdot 2 + 0.$$

Notemos que el último residuo no cero es $5$. Por lo tanto, $(-100, 45) = 5.$

$\square$

Demostración de la validez del algoritmo de Euclides

Ahora, veamos la demostración de que el algoritmo de Euclides funciona. El resultado clave para demostrarlo es la siguiente proposición.

Proposición. Sean $a,b \in \mathbb{Z}^+, $ tales que $a = bq + r.$ Entonces $(a,b) = (b,r).$

Demostración. Sean $a,b \in \mathbb{Z}^+$. Sea $d=(a,b)$ el máximo común divisor de $a$ y $b$, y sea $f=(b,r)$ el máximo común divisor de $b$ y $r$.

Tenemos que $d\mid a$. Además, $d \mid b,$ por lo que $d\mid bq$. Así, $d\mid a-bq=r$. De este modo, $d$ es un divisor común de $b$ y de $r$, de modo que $d\mid f$.

Por otro lado, $f\mid b$, de donde $f\mid bq$. Además, $f\mid r$. De este modo, $f\mid bq+r=a$. Concluimos entonces que $f$ es divisor común de $a$ y $b$. Pero entonces $f\mid d$.

Por propiedades de divisibilidad, tenemos entonces que $|f|=|d|$, pero como ambos son números no negativos concluimos entonces que $f=d$, como queríamos.

$\square$

Ya con este resultado demostrado, enunciemos formalmente el algoritmo de Euclides y demos su demostración.

Teorema. Empecemos tomando dos enteros positivos $a$ y $b$, con $a\geq b$. Usando el algoritmo de la división, definimos sucesivamente los números $r_0,r_1,\ldots,r_i$ y $q_0,q_1,\ldots,q_i$ de manera que se cumpla

\begin{align*}
b=aq_0+r_0\\
a=r_0q_1+r_1
\end{align*}

con $0\leq r_0<a$, y $0\leq r_1 < r_0$ y para $j=2,\ldots,i$ que se cumpla

\begin{align*}
r_{j-2}=r_{j-1}q_j+r_{j},
\end{align*}

con $0\leq r_j < r_{j-1}.$

Como $b\geq a > r_0 > r_1 > r_2 > \ldots > r_i$, entonces podemos suponer que $r_i=0$. Entonces $(a,b)=r_{i-1}$.

Demostración. Por la proposición anterior, tenemos que $(a,b)=(b,r_0)$. También por esa misma proposición, tenemos que $(b,r_0)=(r_0,r_1)$. Y, de hecho, aplicando repetidametne la proposición tenemos que:

$$(r_0,r_1)=(r_1,r_2)=\ldots=(r_{i-1},r_i)=(r_{i-1},0)=r_{i-1}.$$

La penúltima igualdad es porque $r_i=0$ y la última porque $(n,0)=n$ para cualquier entero positivo $n$.

$\square$

Máximo común divisor como combinación lineal entera

Una última consecuencia del algoritmo de Euclides es que nos ayuda a poner al máximo común divisor de dos números $a$ y $b$ como combinación lineal entera de ellos dos.

Una forma práctica de encontrar la combinación lineal correspondiente es mediante el siguiente procedimiento. Tomaremos como ejemplo el algoritmo de Euclides que ya habíamos hecho para encontrar $(6524,3456)$.

$$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Lo que haremos es la siguiente tabla, en donde en la columna izquierda ponemos todos los residuos que vamos encontrando. Además, completaremos la primera fila con $1,0$ y la segunda con $0,1$.

$6524$$1$$0$
$3456$$0$$1$
$3068$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Vamos a ir llenando la tabla con lo que ya sabemos del algoritmo de Euclides. Por el algoritmo de Euclides, sabemos que $3456$ cabe $1$ vez en $6524$. Por esta razón, restamos $1$ vez la segunda fila de la primera, para obtener $1-0=1$ y $0-1=-1$. Estos son los números que van en la fila $3$, columnas $2$ y $3$:

$6524$$1$$0$
$3456$$0$$1$
$3068$$\mathbf{1}$$\mathbf{-1}$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

De nuevo, $3068$ cabe una vez en $3456$, así que de nuevo restamos una vez el tercer renglón del segundo. Nos queda $0-1=-1$ y $1-(-1)=2$ para las nuevas entradas:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$\mathbf{-1}$$\mathbf{2}$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Ahora cambia un poco, pues $388$ ya sabemos que cabe $7$ veces en $3068$ (por lo que hicimos del algoritmo de Euclides). Así, para la nueva fila restamos siete veces la cuarta fila de la tercera, para obtener como nuevos números $1-7\cdot (-1)=8$ y $-1-7\cdot (2)=-15$. La tabla queda así:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$\mathbf{8}$$\mathbf{-15}$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Siguiendo este procedimiento repetidamente, llegamos a la siguiente tabla:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$8$$-15$
$36$$-9$$17$
$28$$89$$-168$
$8$$-98$$185$
$4$$383$$-723$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Los últimos dos números que pusimos en la tabla nos dan la respuesta de cómo poner a $4$ como combinación lineal entera de $6524$ y de $3456$:

$$4=383 \cdot 6524 – 723 \cdot 3456.$$

Verifica que en efecto las cuentas son correctas, y que esta expresión final es válida.

¿Cómo se demuestra que este procedimiento siempre funciona? Se puede mostrar inductivamente que, de hecho, para cada uno de los renglones con entradas $a,b,c$ se cumple que $a=6524b+3456c$. Esto queda como uno de los problemas de tarea moral.

Más adelante…

Esta entrada termina nuestra exploración introductoria al mundo de la aritmética de los números enteros. Sin embargo, todavía hay otros lugares a los que nos llevará el algoritmo de la división. Hasta ahora hemos discutido mucho el caso de la divisibilidad, es decir, cuando el residuo de la división de un número entre otro es igual a cero. Pero también podemos encontrar estructuras matemáticas muy ricas si estudiamos al resto de los posibles residuos. A partir de la siguiente entrada hablaremos del anillo de enteros módulo $n$, lo cual nos ayudará a formalizar estas ideas.

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  1. Usa el algoritmo de Euclides para encontrar el máximo común divisor de las siguientes parejas de números, y para escribirlo como combinación lineal entera de ellos.
    1. $15$ y $35$
    2. $18$ y $92$
    3. $201$ y $153$
    4. $328$ y $528$
  2. ¿Cómo usarías el algoritmo de Euclides para encontrar el máximo común divisor de los números $91$, $105$ y $119$? Es decir, debes encontrar el mayor entero $d$ que divida a estos tres números de manera simultánea.
  3. Hay otra forma de encontrar el máximo común divisor de dos números si conocemos su factorización en números primos. Imagina que tenemos dos números $n$ y $m$ y que, conjuntamente, usan los números primos distintos $p_1,p_2,\ldots, p_k$ en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como:
    \begin{align*} m=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \\ n=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\ \end{align*}
    1. Demuestra que la máxima potencia de $p_1$ que divide tanto a $m$ como a $n$ es $p_1^{\text{min}(\alpha_1,\beta_1)}$
    2. Demuestra que el máximo común divisor de $m$ y $n$ es $$p_1^{\text{min}(\alpha_1,\beta_1)} p_2^{\text{min}(\alpha_2,\beta_2)}\cdots p_k^{\text{min}(\alpha_k,\beta_k)}.$$
  4. Demuestra un resultado análogo al del inciso anterior para el mínimo común múltiplo y úsa ambos resultados para dar otra demostración de que $(m,n)[m,n]=mn$.
  5. Verifica que, en efecto, el método explicado en la entrada ayuda a escribir al máximo común divisor de dos enteros como combinación lineal de ellos.

Entradas relacionadas

Álgebra Lineal II: Proceso de Gram-Schmidt en espacios euclideanos

Por Leonardo Ignacio Martínez Sandoval

Introducción

En la entrada anterior recordamos algunas de las aplicaciones que pueden tener las bases ortogonales y ortonormales. Esto nos da la pista de que siempre es bueno intentar conseguir una base ortonormal. ¿Es esto siempre posible? En el primer curso de Álgebra Lineal vimos que si tenemos en espacio euclideano, entonces sí. Esto está explicado a detalle en la entrada del Proceso de Gram-Schmidt.

Esta entrada está escrita únicamente en formato de recordatorio. Enunciamos los resultados principales, pero las demostraciones y más ejemplos se encuentran en otras entradas.

Teorema de Gram-Schmidt

El teorema de Gram-Schmidt asegura que dado un conjunto de vectores linealmente independientes en un espacio vectorial real con un producto interior dado, podemos encontrar otros vectores que ahora sean ortonormales, que generen lo mismo y que además «apunten hacia un lado similar» a los vectores originales. Además, asegura que estos vectores son únicos. El resultado concreto es el siguiente.

Teorema. Sea $V$ un espacio vectorial real con producto interior $\langle \cdot, \cdot \rangle$. Sean $v_1,\ldots,v_d$ vectores linealmente independientes. Entonces, existen únicos vectores ortonormales $e_1,\ldots,e_d$ tales que para toda $k\in\{1,2,\ldots,d\}$ se tiene que $$\text{span}(e_1,\ldots,e_k)= \text{span}(v_1,\ldots,v_k)$$ y $\langle e_k, v_k \rangle >0$.

Muy a grandes rasgos, esta forma de escribir el teorema permite hacer inducción en $d$. Al pasar a un nuevo $d$, podemos usar hipótesis inductiva para construir $e_1,\ldots,e_{d-1}$. Así, sólo hay que ver cómo construir $e_d$ para que sea ortogonal a todos los anteriores y para que tenga norma $1$. Para encontra a un buen candidato, se debe poner a $e_d$ en términos de los $e_1,\ldots,e_{d-1}$ y $v_d$, y se debe suponer que cumple lo deseado. Al hacer algunos productos interiores esto nos dice que $e_d$ forzosamente se construye definiendo

$$f_d=v_d-\sum_{i=1}^{d-1}\langle v_d, e_i\rangle e_i$$

y tomando $e_d=\frac{f_d}{\norm{f_d}}$.

En los detalles de la prueba se ve que este $e_d$ en efecto cumple todo lo deseado.

Si estamos en un espacio euclideano, entonces tenemos una base finita. Podemos usar esta en la hipótesis del teorema de Gram-Schmidt para concluir lo siguiente.

Corolario. Todo espacio euclideano tiene una base ortonormal.

Algoritmo de Gram-Schmidt

La demostración del teorema de Gram-Schmidt a su vez da un algorimo para encontrar de manera explícita la base ortonormal buscada. Es un algoritmo que poco a poco va contruyendo los vectores. Supongamos que nos dan los vectores $v_1,\ldots,v_n$.

Para empezar, normalizamos $v_1$ para obtener $e_1=\frac{v_1}{\norm{v_1}}$. De aquí en adelante procedemos recursivamente. Si ya construimos $e_1,\ldots,e_k$, entonces podemos construir $e_{k+1}$ a través de la fórmula que pusimos, es decir, primero definimos

$$f_{k+1}=v_{k+1}-\sum_{i=1}^{k}\langle v_{k+1}, e_i\rangle e_i,$$

para luego tomar $e_{k+1}$ como la normalización de $f_{k+1}$, es decir, como $\frac{e_{k+1}}{\norm{e_{k+1}}.$ Seguimos de esta manera hasta terminar.

El siguiente diagrama da una idea un poco más visual de cómo vamos haciendo las operaciones. Comenzamos con los vectores $v_1,\ldots,v_d$ de la fila superior. Luego, vamos construyendo a los $e_i$ y $f_i$ en el orden indicado por las flechas: $e_1,f_2,e_2,\ldots,f_{d-1},e_{d-1},f_d,e_d$. Para construir un $f_i$ usamos la fórmula con productos interiores. Para construir el $e_i$ correspondiente, normalizamos.

Intuición geométrica

Ya tenemos el lenguaje para entender mucho mejor el proceso de Gram-Schmidt. Si te das cuenta, cuando tomamos $$f_{k+1}=v_{k+1}-\sum_{i=1}^{k}\langle v_{k+1}, e_i\rangle e_i$$ justamente estamos aprovechando la descomposición

$$v_{k+1}= \left(\sum_{i=1}^{k}\langle v_{k+1}\right)+ f_{k+1}$$

de $v_{k+1}$ como suma de un elemento en espacio generado por $e_1,\ldots, e_k$ y uno en su ortogonal. El elemento del espacio generado lo obtenemos a través de la fórmula que sale de la descomposición de Fourier que vimos en la entrada anterior. El hecho de que $f_{k+1}$ esté en el ortogonal es lo que hace que cada nuevo vector sea ortogonal a los anteriores. Al final hay que normalizar $f_{k+1}$ para que la base sea ortonormal y no sólo ortogonal. Habría dos formas de hacerlo. Una es tomar $\frac{f_{k+1}}{\norm{f_{k+1}}}$. La otra es tomar $-\frac{f_{k+1}}{\norm{f_{k+1}}}$. El producto escalar positivo que pedimos es lo que nos da la unicidad.

Ejemplo de aplicación del algoritmo de Gram-Schmidt

Hagamos un ejemplo muy sencillo. Será sólo de práctica y como recordatorio. Hay ejemplos más interesantes en la entrada Problemas de bases ortogonales, Fourier y proceso de Gram-Schmidt.

Es sencillo verificar que $\langle (a,b,c), (x,y,z)\rangle =4ax+3by+2cz$ es un producto interior en $\mathbb{R}^3$. Vamos a ortonormalizar la base $(1,1,1)$, $(0,1,1)$, $(0,0,1)$.

En la notación del algoritmo, tenemos entonces $v_1=(1,1,1)$, $v_2=(0,1,1)$ y $v_3=(0,0,1)$. El primer paso es tomar $e_1=\frac{v_1}{\norm{v_1}}$. La norma de $v_1$ con este producto interior es $\sqrt{4+3+2}=3$. De este modo, $e_1=\left(\frac{1}{3}, \frac{1}{3} , \frac{1}{3} \right)$.

Teniendo $e_1$, podemos definir $f_2$ con la fórmula dada:

\begin{align*}
f_2&=v_2-\langle v_2, e_1 \rangle e_1\\
&=(0,1,1)-\left(4\cdot 0\cdot \frac{1}{3}+3\cdot 1 \cdot \frac{1}{3} + 2 \cdot 1 \cdot \frac{1}{3}\right)\left(\frac{1}{3},\frac{1}{3},\frac{1}{3} \right)\\
&=(0,1,1)-\frac{5}{3} \left(\frac{1}{3},\frac{1}{3},\frac{1}{3} \right)\\
&=\left(-\frac{5}{9},\frac{4}{9},\frac{4}{9}\right).
\end{align*}

De aquí, debemos normalizar $f_2$. Su norma es $$\sqrt{ \frac{100}{81}+\frac{48}{81}+\frac{32}{81} } = \frac{\sqrt{180}}{9}=\frac{2\sqrt{5}}{3}=\frac{10}{3\sqrt{5}}.$$ De este modo, $$e_2=\left(-\frac{\sqrt{5}}{6},\frac{2\sqrt{5}}{15},\frac{2\sqrt{5}}{15}\right)$$

Teniendo $e_1$ y $e_2$, podemos definir $f_3$ con la fórmula dada:

\begin{align*}
f_3&=v_3-\langle v_3, e_1 \rangle e_1 – \langle v_3, e_2 \rangle e_2\\
&=(0,0,1)-\frac{2}{3} \left(\frac{1}{3}, \frac{1}{3} , \frac{1}{3} \right) – \frac{4\sqrt{5}}{15} \left(-\frac{\sqrt{5}}{6},\frac{2\sqrt{5}}{15},\frac{2\sqrt{5}}{15}\right)\\
&=(0,0,1)-\left(\frac{2}{9}, \frac{2}{9} , \frac{2}{9} \right)-\left(-\frac{2}{9},\frac{8}{45},\frac{8}{45}\right)\\
&=\left(0, -\frac{2}{5},\frac{3}{5}\right).
\end{align*}

De aquí, debemos normalizar $f_3$. Su norma es $$\sqrt{\frac{12}{25}+\frac{18}{25}}=\frac{\sqrt{6}}{\sqrt{5}}=\frac{6}{\sqrt{30}}.$$ De este modo, $$e_3=\left( 0, -\frac{\sqrt{30}}{15}, \frac{\sqrt{30}}{10}\right).$$

Hemos encontrado la base ortonormal buscada $e_1,e_2,e_3$.

$\square$

Más adelante…

Con esta entrada-recordatorio terminamos la segunda unidad del curso. A partir de ahora es importante que recuerdes que todo espacio euclideano tiene una base ortonormal. También es útil que recuerdes cómo se obtiene, así que asegúrate de practicar el proceso de Gram-Schmidt.

Todo lo que hemos mencionado tiene su análogo en espacios vectoriales sobre los complejos con un producto interior hermitiano. Asegúrate de entender las diferencias y de realizar los ejercicios que te permitirán entender los resultados correspondientes.

En la siguiente unidad desarrollaremos la teoría necesaria para poder enunciar y demostrar tanto el teorema espectral real, como el teorema espectral complejo.

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  1. Haz la demostración del teorema de Gram-Schmidt a partir del esquema comentado en la entrada. En caso de que se te dificulte, revisa los detalles en la entrada de blog correspondiente.
  2. Para verificar que todo esté en orden, verifica que los vectores $e_1,e_2,e_3$ del ejemplo en efecto son una base ortonormal con el producto interior dado.
  3. En el teorema de Gram-Schmidt, ¿es importante el orden en el que elijamos $v_1$ hasta $v_n$? ¿Cambia el conjunto resultante si cambiamos el orden? ¿Es conveniente tomar algún otro orden para simplificar las cuentas?
  4. Aplica el proceso de Gram-Schmidt a los vectores \begin{align*}(1,1,1,1)\\ (0,1,1,1)\\ (0,0,1,1)\\ (0,0,0,1)\end{align*} en $\mathbb{R}^4$ con el producto interior canónico (el producto punto).
  5. Enuncia y demuestra un teorema de Gram-Schmidt para espacios vectoriales sobre $\mathbb{C}$ con un producto interior hermitiano. Obtén el corolario correspondiente para los espacios hermitianos. Aplica este proceso a los vectores $(1+i,1+i,1+i),(0,1+i,1+i),(0,0,1+i)$ de $\mathbb{C}^3$ con el producto hermitiano canónico para obtener una base ortonormal.

Entradas relacionadas

Álgebra Lineal I: Reducción gaussiana para determinar inversas de matrices

Por Ayax Calderón

Introducción

En entradas anteriores hablamos de las matrices en forma escalonada reducida y de cómo cualquier matriz puede ser llevada a esta forma usando el algoritmo de reducción gaussiana. Usamos esto para resolver sistemas de ecuaciones lineales arbitrarios, es decir, de la forma $AX=b$. en esta ocasión estudiaremos cómo ver si una matriz es invertible y cómo determinar inversas de matrices mediante el algoritmo de reducción gaussiana.

Inversas de matrices elementales

Recordemos que una matriz $A\in M_n(F)$ es invertible si existe una matriz $B$ tal que $AB=BA=I_n$. Dicha matriz $B$ es única, se conoce como la matriz inversa de $A$ y se denota por $A^{-1}$.

Es importante observar que las matrices elementales son invertibles, puesto que las operaciones elementales se pueden revertir (esto también nos dice que la inversa de una matriz elemental también es una matriz elemental). Por ejemplo, si la matriz $E$ se obtiene de $I_n$ intercambiando los renglones $i$ y $j$, entonces $E^{-1}$ se obtiene de $I_n$ haciendo la misma operación, por lo que $E^{-1}=E$. Por otro lado, si $E$ se obtiene de sumar $\lambda$ veces el renglón $j$ al renglón $i$ en $I_n$, entonces E^{-1} se obtiene de sumar $-\lambda$ veces el renglón $j$ al renglón $i$ en $I_n$. El argumento para reescalamientos queda como tarea moral.

Debido a su importancia, enunciaremos este resultado como una proposición.

Proposición. Las matrices elementales son invertibles y sus inversas también son matrices elementales. Como consecuencia, cualquier producto de matrices elementales es invertible.

Algunas equivalencias de matrices invertibles

Hasta el momento sólo tenemos la definición de matrices invertibles para verificar si una matriz es invertible o no. Esto es poco práctico, pues dada una matriz, tendríamos que sacar otra «de la nada».

El siguiente resultado empieza a decirnos cómo saber de manera práctica cuándo una matriz cuadrada es invertible. También habla de una propiedad importante que cumplen las matrices invertibles.

Teorema. Para una matriz $A\in M_n(F)$ las siguientes afirmaciones son equivalentes:
(a) $A$ es invertible.
(b) $A_{red}=I_n$.
(c) $A$ es producto de matrices elementales.

Demostración. Para empezar, notemos que el producto de matrices invertibles es invertible , pues cualquier matriz elemental es invertible y las matrices invertibles son estables bajo productos. Esto prueba que (c) implica (a).

Ahora, supongamos que (a) se satisface. Recordemos que para una matriz $A\in M_{m,n}(F)$ podemos encontrar una matriz $B\in M_m(F)$ que es producto de matrices elementales y tal que $A_{red}=BA$. Como $A$ es invertible (por hipótesis) y $B$ es invertible (por la proposición de la sección anterior), entonces $BA$ es invertible y por consiguiente $A_{red}$ también lo es. En particular, todos los renglones de $A_{red}$ son distintos de cero y por lo tanto $A_{red}$ tiene $n$ pivotes, uno en cada columna. Como $A_{red}$ está en forma escalonada reducida, necesariamente $A_{red}=I_n$. Esto prueba que (a) implica (b).

Finalmente, supongamos que $(b)$ se satisface. Entonces existe una matriz $B$, la cual es producto de matrices elementales y tal que $BA=I_n$. Por la proposición anterior $B$ es invertible y $B^{-1}$ es producto de matrices elementales. Como $BA=I_n$, tenemos que $A=B^{-1}BA=B^{-1}$ y así $A$ es producto de matrices elementales, de manera que (b) implica (c).

$\square$

Ya podemos responder de manera práctica la pregunta «¿$A$ es invertible?». Para ello, basta aplicarle reducción gaussiana a $A$. Por el teorema anterior, $A$ es invertible si y sólo si la forma escalonada reducida obtenida es $I_n$. Por supuesto, esto aún no nos dice exactamente quién es la inversa.

Invertibilidad y sistemas de ecuaciones

La siguiente proposición expresa las soluciones del sistema $AX=b$ cuando $A$ es una matriz cuadrada e invertible. Para facilitar las cosas hay que tener un algoritmo para encontrar la inversa de una matriz. Más adelante veremos uno de estos algoritmos basado en reducción gaussiana.

Proposición. Si $A\in M_n(F)$ es una matriz invertible, entonces para todo $b\in F^n$ el sistema $AX=b$ tiene una única solución, dada por $X=A^{-1}b$.

Demostración. Sea $X$ una solución del sistema. Multiplicando la igualdad $AX=b$ por la izquierda por $A^{-1}$ obtenemos $A^{-1}(AX)=A^{-1}b$. Como
\begin{align*}
A^{-1}(AX)=(A^{-1}A)X
=I_nX=X,
\end{align*}
concluimos que $X=A^{-1}b$, por lo tanto el sistema tiene a lo más una solución. Para ver que esta es en efecto una solución, calculamos
\begin{align*}
A(A^{-1}b)=(AA^{-1})b=I_nb=b.
\end{align*}

$\square$

A continuación presentamos un resultado más, que relaciona matrices invertibles con que sus sistemas lineales correspondientes tengan soluciones únicas.

Teorema. Sea $A\in M_n(F)$ una matriz. Las siguientes afirmaciones son equivalentes:
(a) $A$ es invertible.
(b) Para toda $b\in F^n$ el sistema $AX=b$ tiene una única solución $X\in F^n$.
(c) Para toda $b\in F^n$ el sistema $AX=b$ es consistente.

Demostración. Ya demostramos que (a) implica (b). Es claro que (b) implica (c) pues si el sistema tiene una única solución, en particular tiene una solución.

Así, supongamos que que (c) se satisface. Sea $A_{red}$ la forma escalonada reducida de $A$. Por una proposición ya antes mencionada en esta entrada sabemos que existe una matriz $B$ la cual es producto de matrices elementales (por lo tanto invertible) y tal que $A_{red}=BA$. Deducimos que el sistema $A_{red}X=Bb$ tiene al menos una solución para todo $b\in F^n$ (pues si $AX=b$, entonces $A_{red}X=BAX=Bb$).

Ahora, para cualquier $b’\in F^n$ podemos encontrar $b$ tal que $b’=Bb$, tomando $b=B^{-1}b’$. Aquí estamos usando que $B$ es invertible por ser producto de matrices elementales. Concluimos que el sistema $A_{red}X=b$ es consistente para cada $b\in F^n$, pero entonces cualquier renglón de $A_{red}$ debe ser distinto de cero (si la fila $i$ es cero, entonces escogiendo cada vector $b$ con la $i-$ésima coordenada igual a $1$ se obtiene un sistema inconsistente) y, como en la demostración del teorema anterior, se tiene que $A_{red}=I_n$. Usando el teorema anterior concluimos que $A$ es invertible.

$\square$

Hasta ahora, al tomar un matriz cuadrada $A$ y proponer una inversa $B$, la definición de invertibilidad nos exige mostrar ambas igualdades $AB=I_n$ y $BA=I_n$. Finalmente tenemos las herramientas necesarias para mostrar que basta mostrar una de estas igualdades para que ambas se cumplan.

Corolario. Sean $A,B\in M_n(F)$ matrices.
(a) Si $AB=I_n$, entonces $A$ es invertible y $B=A^{-1}$.
(b) Si $BA=I_n$, entonces $A$ es invertible y $B=A^{-1}$.

Demostración. (a) Para cada $b\in F^n$ el vector $X=Bb$ satisface
\begin{align*}
AX=A(Bb)
=(AB)b=b,
\end{align*}
por lo tanto el sistema $AX=b$ es consistente para cada $b\in M_n(F)$. Por el teorema anterior, $A$ es invertible. Multiplicando la igualdad $AB=I_n$ por la izquierda por $A^{-1}$ obtenemos $B=A^{-1}AB=A^{-1}$, y así $B=A^{-1}$.
(b) Por el inciso (a), sabemos que $B$ es invertible y $A=B^{-1}$, pero entonces $A$ es invertible y $A^{-1}=B$.

$\square$

Determinar inversas usando reducción gaussiana

El corolario anterior nos da una manera práctica de saber si una matriz es invertible y, en esos casos, determinar inversas de matrices. En efecto, $A$ es invertible si y sólo si podemos encontrar una matriz $X$ tal que $AX=I_n$ y de aquí $X=A^{-1}$.

La ecuación $AX=I_n$ es equivalente a los siguientes sistemas lineales:
\begin{align*}
AX_1=e_1, \hspace{2mm}, AX_2=e_2, \hspace{2mm} \dots , \hspace
{2mm} AX_n=e_n.
\end{align*}
donde $e_i$ es la $i-$ésima columna de $I_n$ y $X_i$ denota la $i-$ésima columna de $X$. Ya sabemos cómo resolver sistemas lineales usando reducción gaussiana. Esto nos da una manera práctica de calcular $X$: si al menos uno de estos sistemas es inconsistente, entonces $A$ no es invertible; si todos son consistentes, entonces las soluciones $X_1,\ldots,X_n$ son las columnas de la inversa.

En la práctica, uno puede evitar resolver $n$ sistemas lineales considerando el siguiente truco:

En lugar de tomar $n$ matrices aumentadas $[A| e_i]$ considera sólo la matriz aumentada $[A|I_n]$, en la cual agregamos la matriz $I_n$ a la derecha de $A$ (de manera que $[A|I_n]$ tiene $2n$ columnas). Finalmente sólo hay que encontrar la forma escalonada reducida $[A’|X]$ de la matriz de $n\times 2n \hspace{2mm} [A|I_n]$. Si $A’$ resulta ser distinto de $I_n$, entonces $A$ no es inverible. Si $A’=I_n$, entonces la inversa de $A$ es simplemente la matriz $X$.

Ejemplo de determinar inversas

Para ilustrar lo anterior resolveremos el siguiente ejemplo práctico.

Ejemplo. Calcula la inversa de la matriz
\begin{align*}
A= \begin{pmatrix}
1 & 5 & 1\\
2 & 11 & 5\\
9 & -3 & 0
\end{pmatrix}.
\end{align*}

Solución. Aplicamos reducción gaussiana a la matriz extendida
\begin{align*}
[A|I_3]= \begin{pmatrix}
1 & 5 & 1 & 1 & 0 &0\\
2 & 11 & 5 & 0 & 1 & 0\\
9 & -3 & 0 & 0 & 0 & 1
\end{pmatrix}
\end{align*}
\begin{align*}
R_2 -2R_1\begin{pmatrix}
1 & 5 & 1 & 1 & 0 &0\\
0 & 1 & 3 & -2 & 1 & 0\\
9 & -3 & 0 & 0 & 0 & 1
\end{pmatrix}
\end{align*}
\begin{align*}
R_3 -9R_1\begin{pmatrix}
1 & 5 & 1 & 1 & 0 &0\\
0 & 1 & 3 & -2 & 1 & 0\\
0 & -48 & -9 & -9 & 0 & 1
\end{pmatrix}
\end{align*}

\begin{align*}
R_1 -5R_2\begin{pmatrix}
1 & 0 & -14 & 11 & -5 &0\\
0 & 1 & 3 & -2 & 1 & 0\\
0 & -48 & -9 & -9 & 0 & 1
\end{pmatrix}
\end{align*}
\begin{align*}
R_3 +48R_2\begin{pmatrix}
1 & 0 & -14 & 11 & -5 &0\\
0 & 1 & 3 & -2 & 1 & 0\\
0 & 0 & 135 & -105 & 48 & 1
\end{pmatrix}
\end{align*}
\begin{align*}
\frac{1}{135}R_3\begin{pmatrix}
1 & 0 & -14 & 11 & -5 &0\\
0 & 1 & 3 & -2 & 1 & 0\\
0 & 0 & 1 & -\frac{7}{9} & \frac{16}{45} & \frac{1}{135}
\end{pmatrix}
\end{align*}
\begin{align*}
R_1+14R_3\begin{pmatrix}
1 & 0 & 0 & \frac{1}{9} & -\frac{1}{45} &\frac{14}{135}\\
0 & 1 & 3 & -2 & 1 & 0\\
0 & 0 & 1 & -\frac{7}{9} & \frac{16}{45} & \frac{1}{135}
\end{pmatrix}
\end{align*}
\begin{align*}
R_2-3R_3\begin{pmatrix}
1 & 0 & 0 & \frac{1}{9} & -\frac{1}{45} &\frac{14}{135}\\
0 & 1 & 0 & \frac{1}{3} & -\frac{1}{15} & -\frac{1}{45}\\
0 & 0 & 1 & -\frac{7}{9} & \frac{16}{45} & \frac{1}{135}
\end{pmatrix}
\end{align*}
De donde
\begin{align*}
A^{-1}=\begin{pmatrix}
\frac{1}{9} & -\frac{1}{45} &\frac{14}{135}\\
\frac{1}{3} & -\frac{1}{15} & -\frac{1}{45}\\
-\frac{7}{9} & \frac{16}{45} & \frac{1}{135}
\end{pmatrix}.
\end{align*}

$\square$

En el ejemplo anterior hicimos el algoritmo de reducción gaussiana «a mano», pero también pudimos haber usado una herramienta en línea, como la calculadora de forma escalonada reducida de eMathHelp.

Tarea moral

Los siguientes ejercicios te ayudarán a repasar los conceptos vistos en esta entrada.

  • ¿Cuál sería la operación elemental inversa a aplicar un reescalamiento por un factor $c\neq 0$ en el renglón de una matriz?
  • Encuentra la inversa de la matriz
    \begin{align*}
    \begin{pmatrix}
    1 & 2 & 1\\
    2 & 0 & 2\\
    1 & 2 & 0
    \end{pmatrix}.
    \end{align*}
    mediante reducción gaussiana.
  • Resuelve el sistema de ecuaciones
    \begin{align*}
    \begin{cases}
    x+2y+2z=1\\
    2x+y+2z=4\\
    2x+2y+z=5
    \end{cases}
    \end{align*}
  • Sea $A\in M_n(F)$ una matriz tal que $A_{red}\neq I_n$. Explica por qué $A$ no es invertible.
  • Cuando $A$ no es invertible, la matriz $[A|I_n]$ tiene forma escalonada reducida $[A_{red}|X]$, con $A_{red}\neq I_n$. ¿Qué sucede si en este caso haces la multiplicación $AX$? ¿Y la multiplicación $XA$?
  • Demuestra la primera proposición de esta entrada para operaciones elementales sobre las columnas.

Más adelante…

En esta entrada vimos cómo el algoritmo de reducción gaussiana nos permite saber si una matriz es invertible o no. También nos da una forma práctica de determinar inversas. Hay otras formas de hacer esto mediante determinantes. Sin embargo, el método que describimos es bastante rápido y flexible.

Ya que entendemos un poco mejor a las matrices invertibles, el siguiente paso es usarlas para desarrollar nuestra teoría de álgebra lineal. Las matrices invertibles se corresponden con transformaciones lineales que se llaman isomorfismos, las cuales detectan cuándo dos espacios vectoriales son «el mismo».

También más adelante refinaremos el concepto de ser invertible y no. Esta es una clasificación en sólo dos posibilidades. Cuando definamos y estudiamos el rango de matrices y transformaciones lineales tendremos una forma más precisa de decir «qué tanta información guarda una transformación».

Entradas relacionadas

Álgebra Lineal I: Más ejemplos de reducción gaussiana

Por Ayax Calderón

Introducción

En esta entrada veremos varios ejemplos que nos ayudarán a comprender que la reducción gaussiana es una herramienta muy poderosa a la hora de resolver sistemas de ecuaciones lineales.

Problemas resueltos

Problema. Implementa el algoritmo de reducción gaussiana en la matriz
\begin{align*}
A=\begin{pmatrix}
0 & 2 & 1 & 1 & 2\\
1 & 1 & 0 & 2 & 1\\
-3 & 1 & 1 & 0 & 2\\
1 & 1 & 1 & 1 & 1\end{pmatrix}
\end{align*}

Solución. Para este problema usaremos la siguiente notación para indicar las operaciones elementales que estamos efectuando :

  • $R_i \leftrightarrow R_j$ para intercambiar el renglón $i$ con el renglón $j$.
  • $kR_i$ para multiplicar el renglón $i$ por el escalar $k$.
  • $R_i + kR_j$ para sumarle $k$ veces el renglón $j$ al renglón $i$.


\begin{align*}
A=&\begin{pmatrix}
0 & 2 & 1 & 1 & 2\\
1 & 1 & 0 & 2 & 1\\
-3 & 1 & 1 & 0 & 2\\
1 & 1 & 1 & 1 & 1\end{pmatrix}\\
R_1 \leftrightarrow R_2
& \begin{pmatrix}
1 & 1 & 0 & 2 & 1\\
0 & 2 & 1 & 1 & 2\\
-3 & 1 & 1 & 0 & 2\\
1 & 1 & 1 & 1 & 1\end{pmatrix}\\
R_4 – R_1
&\begin{pmatrix}
1 & 1 & 0 & 2 & 1\\
0 & 2 & 1 & 1 & 2\\
-3 & 1 & 1 & 0 & 2\\
0 & 0 & 1 & -1 & 0\end{pmatrix}\\
R_3 + 3R_1
&\begin{pmatrix}
1 & 1 & 0 & 2 & 1\\
0 & 2 & 1 & 1 & 2\\
0 & 4 & 1 & 6 & 5\\
0 & 0 & 1 & -1 & 0\end{pmatrix}\\
\frac{1}{2}R_2
& \begin{pmatrix}
1 & 1 & 0 & 2 & 1\\
0 & 1 & \frac{1}{2} & \frac{1}{2} & 1\\
0 & 4 & 1 & 6 & 5\\
0 & 0 & 1 & -1 & 0\end{pmatrix}\\
R_3 – 4R_2
&\begin{pmatrix}
1 & 1 & 0 & 2 & 1\\
0 & 1 & \frac{1}{2} & \frac{1}{2} & 1\\
0 & 0 & -1 & 4 & 1\\
0 & 0 & 1 & -1 & 0\end{pmatrix}
\end{align*}
\begin{align*}
R_1 – R_2
& \begin{pmatrix}
1 & 0 & -\frac{1}{2} & \frac{3}{2} & 0\\
0 & 1 & \frac{1}{2} & \frac{1}{2} & 1\\
0 & 0 & -1 & 4 & 1\\
0 & 0 & 1 & -1 & 0\end{pmatrix}\\
-1\cdot R_3
&\begin{pmatrix}
1 & 0 & -\frac{1}{2} & \frac{3}{2} & 0\\
0 & 1 & \frac{1}{2} & \frac{1}{2} & 1\\
0 & 0 & 1 & -4 & -1\\
0 & 0 & 1 & -1 & 0\end{pmatrix}\\
R_4 – R_3
& \begin{pmatrix}
1 & 0 & -\frac{1}{2} & \frac{3}{2} & 0\\
0 & 1 & \frac{1}{2} & \frac{1}{2} & 1\\
0 & 0 & 1 & -4 & -1\\
0 & 0 & 0 & 3 & 1\end{pmatrix}\\
R_2 – \frac{1}{2} R_3
& \begin{pmatrix}
1 & 0 & -\frac{1}{2} & \frac{3}{2} & 0\\
0 & 1 & 0 & \frac{5}{2} & \frac{3}{2}\\
0 & 0 & 1 & -4 & -1\\
0 & 0 & 0 & 3 & 1\end{pmatrix} \\
R_1 + \frac{1}{2}R_3
& \begin{pmatrix}
1 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2}\\
0 & 1 & 0 & \frac{5}{2} & \frac{3}{2}\\
0 & 0 & 1 & -4 & -1\\
0 & 0 & 0 & 3 & 1\end{pmatrix}
\end{align*}
\begin{align*}
\frac{1}{3} R_4
&\begin{pmatrix}
1 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2}\\
0 & 1 & 0 & \frac{5}{2} & \frac{3}{2}\\
0 & 0 & 1 & -4 & -1\\
0 & 0 & 0 & 1 & \frac{1}{3}\end{pmatrix}\\
R_3 + 4R_4
& \begin{pmatrix}
1 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2}\\
0 & 1 & 0 & \frac{5}{2} & \frac{3}{2}\\
0 & 0 & 1 & 0 & \frac{1}{3}\\
0 & 0 & 0 & 1 & \frac{1}{3}\end{pmatrix} \\
R_2 – \frac{5}{2}R_4
& \begin{pmatrix}
1 & 0 & 0 & -\frac{1}{2} & -\frac{1}{2}\\
0 & 1 & 0 & 0 & \frac{2}{3}\\
0 & 0 & 1 & 0 & \frac{1}{3}\\
0 & 0 & 0 & 1 & \frac{1}{3}\end{pmatrix} \\
R_1 + \frac{1}{2}R_4
& \begin{pmatrix}
1 & 0 & 0 & 0 & -\frac{1}{3}\\
0 & 1 & 0 & 0 & \frac{2}{3}\\
0 & 0 & 1 & 0 & \frac{1}{3}\\
0 & 0 & 0 & 1 & \frac{1}{3}\end{pmatrix}\\
=&A_{red}
\end{align*}

$\square$

Problema. Resuelve el siguiente sistema homogéneo.
\begin{align*}
\begin{cases}
x+2y-3z &=0\\
2x+5y+2z &=0\\
3x-y-4z &=0
\end{cases}
\end{align*}

Solución. La matriz asociada al sistema anterior es
\begin{align*}
\begin{pmatrix}
1 & 2 & -3\\
2 & 5 & 2\\
3 & -1 & -4
\end{pmatrix}
\end{align*}
Para resolver el sistema $AX=0$ nos bastará con encontrar $A_{red}$, pues el sistema $A_{red}X=0$ es equivalente al sistema $AX=0$.
\begin{align*}
&\begin{pmatrix}
1 & 2 & -3\\
2 & 5 & 2\\
3 & -1 & -4
\end{pmatrix}\\
R_2 -2R_1
&\begin{pmatrix}
1 & 2 & -3\\
0 & 1 & 8\\
3 & -1 & -4
\end{pmatrix}\\
R_3 – 3R_1
&\begin{pmatrix}
1 & 2 & -3\\
0 & 1 & 8\\
0 & -7 & 5
\end{pmatrix}\\
R_1 – 2R_2
&\begin{pmatrix}
1 & 0 & -19\\
0 & 1 & 8\\
0 & -7 & 5
\end{pmatrix}\\
R_3 + 7R_2
&\begin{pmatrix}
1 & 0 & -19\\
0 & 1 & 8\\
0 & 0 & 61
\end{pmatrix}\\
R_2 – \frac{8}{61}R_3
&\begin{pmatrix}
1 & 0 & -19\\
0 & 1 & 0\\
0 & 0 & 61
\end{pmatrix}\\
R_1 + \frac{19}{61}R_3
&\begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 61
\end{pmatrix}\\
\frac{1}{61}R_3
&\begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{pmatrix}\\
&=A_{red}
\end{align*}

De lo anterior se sigue que para resolver el sistema $AX=0$ basta con resolver el sistema
\begin{align*}
\begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{pmatrix} \begin{pmatrix}
x\\
y\\
z
\end{pmatrix}= \begin{pmatrix}
0\\
0\\
0
\end{pmatrix}.
\end{align*}
Pero este sistema es el sistema

\begin{align*}
\begin{cases} x = 0\\ y = 0 \\ z = 0. \end{cases}
\end{align*}

De esta forma, $x=y=z=0$ es la (única) solución al sistema original.

$\square$

Problema. Determina las soluciones fundamentales del sistema homogéneo $AX=0$, donde $A$ es la matriz
\begin{align*}
A=\begin{pmatrix}
1 & -2 & 1 & 0\\
-2 & 4 & 0 & 2\\
-1 & 2 & 1 & 2
\end{pmatrix}.
\end{align*}

Solución. Sea $AX=0$ el sistema
\begin{align*}
\begin{pmatrix}
1 & -2 & 1 & 0\\
-2 & 4 & 0 & 2\\
-1 & 2 & 1 & 2
\end{pmatrix} \begin{pmatrix}
x\\
y\\
z\\
w \end{pmatrix} = \begin{pmatrix}
0\\
0\\
0 \end{pmatrix}
\end{align*}

Para este problema nuevamente nos interesa llevar la matriz asociada al sistema a su forma escalonada reducida.

Aunque es muy importante saber cómo se hacen estos procedimientos, es cierto que también existen herramientas que nos ayudan a hacer estos cálculos de manera más rápida. En esta ocasión usaremos una calculadora de forma reducida escalonada disponible en línea, la cual nos indica que la forma escalonada reducida de la matriz $A$ es
\begin{align*}
A_{red}=\begin{pmatrix}
1 & -2 & 0 & -1\\
0 & 0 & 1 & 1\\
0 & 0 & 0 & 0
\end{pmatrix}.
\end{align*}

De esta forma, el sistema del problema es equivalente al sistema $A_{red}X=0$
\begin{align*}
\begin{pmatrix}
1 & -2 & 0 & -1\\
0 & 0 & 1 & 1\\
0 & 0 & 0 & 0
\end{pmatrix} \begin{pmatrix}
x\\
y\\
z\\
w \end{pmatrix} = \begin{pmatrix}
0\\
0\\
0 \end{pmatrix}
\end{align*}
Las variables pivote son $x$ y $z$. Las variables libres son $y$ y $w$.

Como se mencionó en una entrada anterior, para encontrar las soluciones fundamentales hay que expresar a las variables pivote en términos de las variables libres. En el sistema anterior podemos notar que
\begin{align*}
\begin{cases}
x =2y+w\\
z=-w.
\end{cases}
\end{align*}
por lo que
\begin{align*}
\begin{pmatrix}
x\\
y\\
z\\
w
\end{pmatrix}&=\begin{pmatrix}
2y+w\\
y\\
-w\\
w
\end{pmatrix}\\
&=y\begin{pmatrix}
2\\
1\\
0\\
0
\end{pmatrix} + w \begin{pmatrix}
1\\
0\\
-1\\
1
\end{pmatrix}
\end{align*}
siendo los vectores columna de la última igualdad las soluciones fundamentales del sistema $AX=0$, es decir que con estas soluciones se pueden generar todas las demás.

$\square$

Hasta ahora hemos visto ejemplos de reducción gaussiana de matrices de tamaño muy concreto y entradas muy concretas. Sin embargo, otra habilidad importante es aprender a usar reducción gaussiana en una matriz de tamaño arbitrario, con algunas entradas específicas. Veamos un ejemplo de cómo hacer esto.

Problema. Sea $n>2$ un número entero. Resuelve en números reales el sistema
\begin{align*}
x_2=\frac{x_1+x_3}{2}, x_3= \hspace{2mm} \frac{x_2+x_4}{2}, \hspace{2mm} \dots , \hspace{2mm}, x_{n-1}=\frac{x_{n-2}+x_n}{2}.
\end{align*}

Solución. Este es un sistema lineal homogéneo de ecuaciones. Esto se puede verificar multiplicando cada ecuación por $2$ e igualándola a $0$. Por ejemplo, la primer ecuación se puede escribir como $x_1-2x_2+x_3=0$. Transformando el resto de las ecuaciones, obtenemos que el sistema se puede escribir en forma matricial como $AX=0$, donde$A$ es la matriz en $M_{n-2,n}(F)$ dada por
\begin{align*}
\begin{pmatrix}
1 & -2 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\
0 & 1 & -2 & 1 & 0 & \cdots & 0 & 0 & 0 \\
0 & 0 & 1 & -2 & 1 & \cdots & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & -2 & \cdots & 0 & 0 & 0 \\
& \vdots & & \vdots & & \ddots & & \vdots &\\
0 & 0 & 0 & 0 & 0 & \cdots & -2 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & \cdots & 1 &- 2 & 1
\end{pmatrix}.
\end{align*}

Esta matriz se ve algo intimidante, pero igual se le puede aplicar reducción gaussiana. Hagamos esto.

Afortunadamente, en cada fila ya tenemos un pivote y están «escalonados». Basta con hacer transvecciones para asegurar que en cada columna de un pivote, el pivote es la única entrada no cero. Haremos los primeros pasos para encontrar un patrón de qué va sucediendo.

En el primer paso, sumamos dos veces la fila $2$ a la primer fila. Al hacer esto obtenemos:

\begin{align*}
\begin{pmatrix}
1 & 0 & -3 & 2 & 0 & \cdots & 0 & 0 & 0 \\
0 & 1 & -2 & 1 & 0 & \cdots & 0 & 0 & 0 \\
0 & 0 & 1 & -2 & 1 & \cdots & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & -2 & \cdots & 0 & 0 & 0 \\
& \vdots & & \vdots & & \ddots & & \vdots &\\
0 & 0 & 0 & 0 & 0 & \cdots & -2 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & \cdots & 1 &- 2 & 1
\end{pmatrix}.
\end{align*}

Con esto la segunda columna ya queda lista. El el siguiente paso, multiplicamos por 3 (y 2) la tercer fila y se lo sumamos a la primera fila (y segunda, respectivamente). Obtenemos:

\begin{align*}
\begin{pmatrix}
1 & 0 & 0 & -4 & 3 & \cdots & 0 & 0 & 0 \\
0 & 1 & 0 & -3 & 2 & \cdots & 0 & 0 & 0 \\
0 & 0 & 1 & -2 & 1 & \cdots & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & -2 & \cdots & 0 & 0 & 0 \\
& \vdots & & \vdots & & \ddots & & \vdots &\\
0 & 0 & 0 & 0 & 0 & \cdots & -2 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & \cdots & 1 &- 2 & 1
\end{pmatrix}.
\end{align*}

Para el siguiente paso, ahora hay que multiplicar por 4 (3, 2) la cuarta fila y sumárselo a la primera (segunda, tercera, respectivamente), y obtenemos:

\begin{align*}
\begin{pmatrix}
1 & 0 & 0 & 0 & -5 & 4 & \cdots & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & -4 & 3 & \cdots & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & -3 & 2 &\cdots & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & -2 & 1 & \cdots & 0 & 0 & 0 \\
& \vdots & & \vdots & & & \ddots & & \vdots &\\
0 & 0 & 0 & 0 & 0 & 0 & \cdots & -2 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 &\cdots & 1 &- 2 & 1
\end{pmatrix}.
\end{align*}

El patrón es ahora claro. Conforme arreglamos la columna $j$, luego la columna $j+1$ tiene a los números $-(j+1), -j, \ldots, -3, -2$ y la columna $j+2$ tiene a los números $j,j-1,j-2,\ldots,1,-2,1$. Esto puede demostrarse formalmente por inducción. Al arreglar la columna $n-2$, la matriz queda en la siguiente forma escalonada reducida:

\begin{align*}
\begin{pmatrix}
1 & 0 & 0 & 0 & 0 & \cdots & 0 & -(n-1) & n-2 \\
0 & 1 & 0 & 0 & 0 & \cdots & 0 & -(n-2) & n-3 \\
0 & 0 & 1 & 0 & 0 & \cdots & 0 & -(n-3) & n-4 \\
0 & 0 & 0 & 1 & 0 & \cdots & 0 & -(n-4) & n-5 \\
& \vdots & & \vdots & & \ddots & & \vdots &\\
0 & 0 & 0 & 0 & 0 & \cdots & 0 & -3 & 2\\
0 & 0 & 0 & 0 & 0 & \cdots & 1 & -2 & 1
\end{pmatrix}.
\end{align*}

Estamos listos para resolver el sistema asociado. Las variables libres son $x_{n-1}$ y $x_n$, que podemos darles valores arbitrarios $a$ y $b$. Las variables pivote son todas las demás, y de acuerdo a la forma de la matriz anterior, están dadas por

\begin{align*}
x_1&=(n-1)a – (n-2) b\\
x_2&=(n-2)a – (n-3) b\\
x_3&=(n-3)a – (n-4) b\\
&\vdots\\
x_{n-2}&=2a- b.
\end{align*}

Esto determina todas las soluciones.

$\square$

Entradas relacionadas