Archivo de la etiqueta: matrices equivalentes

Álgebra Lineal I: Teorema de reducción gaussiana

Por Julio Sampietro

Introducción

Llegamos a uno de los resultados más importantes del álgebra lineal: el teorema de reducción gaussiana. Como mencionamos en una entrada previa, el teorema nos proporcionará un algoritmo que nos permitirá resolver muchos problemas prácticos: resolver sistemas lineales, invertir matrices, así como temas que veremos más adelante, como determinar la independencia lineal de vectores.

El teorema nos dice que cualquier matriz puede llevarse a una en forma escalonada reducida con solo una cantidad finita de operaciones elementales. La prueba además nos dice cómo hacerlo de una manera más o menos sencilla. Aparte de la demostración, damos una receta un poco más coloquial de cómo trabajar con el algoritmo y finalmente damos un ejemplo, muy importante para aclarar el procedimiento.

Sugerencia antes de empezar

El algoritmo que veremos es uno de esos resultados que es fácil de seguir para una matriz en concreto, pero que requiere de un buen grado de abstracción para entender cómo se demuestra en general. Una fuerte recomendación es que mientras estés leyendo la demostración del siguiente teorema, tengas en mente alguna matriz muy específica, y que vayas realizando los pasos sobre ella. Puedes usar, por ejemplo, a la matriz $$A=\begin{pmatrix} 0 & 0 & 4 & -2 \\ 0 & 3 & -1 & 0 \\ 0& -3 & 5 & -2 \end{pmatrix}.$$

El teorema de reducción gaussiana

Teorema. Cualquier matriz $A\in M_{m,n}(F)$ puede llevarse a una en forma escalonada reducida realizando una cantidad finita de operaciones elementales en sus filas.

Demostración: Daremos una demostración algorítmica. Sea $A\in M_{m,n}(F)$ cualquier matriz. Para auxiliarnos en el algoritmo, vamos a tener registro todo el tiempo de las siguientes dos variables:

  • $X$ es la columna que «nos toca revisar».
  • $Y$ es la cantidad de «filas no triviales» que hemos encontrado.

La variable $X$ empieza siendo $1$ y la variable $Y$ empieza siendo $0$.

Haremos los siguientes pasos:

Paso 1. Revisaremos la columna $X$ a partir de la fila $Y+1$ (osea, al inicio $Y=0$, así que revisamos toda la columna). Si todas estas entradas son iguales a $0$, entonces le sumamos $1$ a $X$ (avanzamos hacia la derecha) y si $X<n$, volvemos a hacer este Paso 1. Si $X=n$, vamos al paso 7.

Paso 2. En otro caso, existe alguna entrada distinta de cero en la columna $X$, a partir de la fila $Y+1$. Tomemos la primera de estas entradas. Supongamos que sucede en la fila $i$, es decir, que es la entrada $a_{iX}$. Al número en esta entrada $a_{iX}$ le llamamos $x$.

Paso 3. Hacemos un intercambio entre la fila $i$ y la fila $Y+1$. Puede pasar que $i=Y+1$, en cuyo caso no estamos haciendo nada. Independientemente del caso, ahora el número en la entrada $(X,Y+1)$ es $x\neq 0$.

Paso 4. Tomamos la fila $Y+1$ y la multiplicamos por el escalar $1/x$. Esto hace que ahora sea la primer entrada en su fila distinta de cero, y además que sea igual a $1$.

Paso 5. De ser necesario, hacemos transvecciones para hacer el resto de las entradas de la columna $X$ iguales a $0$. Esto lo podemos hacer pues, si por ejemplo la entrada $a_{iX}\neq 0$, entonces la transvección que a la $i$-ésima fila le resta $a_{iX}$ veces la $(Y+1)$-ésima fila hace que la entrada $(i,X)$ se anule.

Paso 6. Le sumamos $1$ a $Y$ (para registrar que encontramos una nueva fila no trivial) y le sumamos $1$ a $X$ (para avanzar a la columna de la derecha). Si $X<n$, vamos al Paso 1. Si $X=n$, vamos al Paso 7.

Paso 7. Reportamos la matriz obtenida como $A_{red}$, la forma escalonada reducida de $A$.

Mostremos que en efecto obtenemos una matriz escalonada reducida. El Paso 3 garantiza que las únicas filas cero están hasta abajo. El Paso 4 garantiza que todos los pivotes son iguales a 1. El ir recorriendo las columnas de izquierda a derecha garantiza que los pivotes quedan «escalonados», es decir de abajo hacia arriba quedan de izquierda a derecha. El Paso 5 garantiza que cada pivote es la única entrada no cero de su columna.

$\square$

El procedimiento descrito en el teorema se llama reducción gaussiana.

Como vimos en la entrada anterior realizar una operación elemental es sinónimo de multiplicar por una matriz elemental. Como el teorema nos dice que podemos obtener una matriz en forma escalonada reducida realizando una cantidad finita de operaciones elementales, se sigue que podemos obtener una matriz en forma escalonada reducida multiplicando por la izquierda por un número finito de matrices elementales. Al asociar todas estas matrices elementales en un único producto, obtenemos la demostración del siguiente corolario.

Corolario. Para cualquier matriz $A\in M_{m,n}(F)$ podemos encontrar una matriz $B\in M_{m}(F)$ que es un producto finito de matrices elementales y que satisface qu $A_{red}=BA$.

Un tutorial de reducción gaussiana más relajado

Si bien el teorema nos da la manera formal de hacer el algoritmo, el proceso es en realidad bastante intuitivo una vez que se entiende. Para esto explicamos en unos cuantos pasos en términos más sencillos como hacer la reducción:

  1. Buscamos la primer columna de la matriz que no tenga puros ceros.
  2. Una vez encontrada, buscamos la primer entrada (de arriba hacia abajo) que no sea cero.
  3. Pasamos el renglón con esa entrada hasta arriba haciendo un cambio de renglones.
  4. Multiplicamos por el inverso de esa entrada a todo el renglón, para quedarnos así con un $1$ hasta arriba.
  5. Sustraemos múltiplos del primer renglón a todos los otros renglones para que todo lo que esté abajo del $1$ sea cero.
  6. Buscamos la siguiente columna tal que no sea cero abajo del primer renglón.
  7. Repetimos los pasos anteriores, solo que en lugar de pasar nuestro renglón «hasta arriba» solo lo colocamos en el segundo lugar, y así sucesivamente.

Un ejemplo de reducción gaussiana

La mejor manera de entender el algoritmo de reducción gaussiana es con un ejemplo. Usemos el algoritmo para reducir la matriz

\begin{align*}
A=\begin{pmatrix} 0 & 1 & 2 & 3 &4\\ -1 & 0 &1 & 2 &3 \\ 0 & 1 & 1 & 1 &1\\ 3 & 1 &-1 & 0 & 2\end{pmatrix}\in M_{4,5}(\mathbb{R}).
\end{align*}

Aplicando los pasos en orden: Primero identificamos la primer columna que no sea idénticamente cero, y vemos que la primera columna no tiene puros ceros. La primer entrada que no es cero está en el segundo renglón. Así cambiamos el primer y segundo renglón de lugar para subir esa entrada y obtener

\begin{align*}
A_1=\begin{pmatrix} -1 & 0 &1 & 2 &3 \\ 0 & 1 & 2 & 3 &4\\ 0 & 1 & 1 & 1 &1\\ 3 & 1 &-1 & 0 & 2\end{pmatrix}.
\end{align*}

Ahora que la primer entrada del primer renglón es distinta de cero, multiplicamos el primer renglón por $\frac{1}{-1}=-1$ y obtenemos

\begin{align*}
A_2=\begin{pmatrix} 1 & 0 &-1 & -2 &-3 \\ 0 & 1 & 2 & 3 &4\\ 0 & 1 & 1 & 1 &1\\ 3 & 1 &-1 & 0 & 2\end{pmatrix}.
\end{align*}

Ahora queremos quitar el $3$ del último renglón. Para esto, multiplicamos por $-3$ el primer renglón y lo sumamos al último y nos queda

\begin{align*}
A_3&=\begin{pmatrix} 1 & 0 &-1 & -2 &-3 \\ 0 & 1 & 2 & 3 &4\\ 0 & 1 & 1 & 1 &1\\ 3-3 & 1-3\cdot 0 &-1-3\cdot (-1) & 0-3\cdot (-2) & 2-3\cdot (-3)\end{pmatrix}\\ &=\begin{pmatrix} 1 & 0 &-1 & -2 &-3 \\ 0 & 1 & 2 & 3 &4\\ 0 & 1 & 1 & 1 &1\\ 0 & 1&2 & 6 & 11\end{pmatrix}.
\end{align*}

Ya tenemos entonces nuestra primera columna en forma escalonada reducida, pasemos a la segunda. Ya tenemos un $1$ en la segunda entrada de la segunda columna, por lo que no hace falta hacer un cambio de renglón o multiplicar por un inverso. Basta entonces con cancelar las otras entradas de la columna, para eso sustraemos el segundo renglón del tercero y cuarto, para obtener

\begin{align*}
A_4&= \begin{pmatrix} 1 & 0 & -1 & -2 & -3 \\ 0 & 1 & 2 & 3 &4 \\ 0-0 & 1-1 & 1-2 & 1-3 & 1-4\\ 0 -0 & 1-1& 2-2 & 6-3 & 11-4\end{pmatrix}\\
&= \begin{pmatrix}
1 & 0 &-1 & -2 &-3\\ 0 & 1 & 2 & 3 &4 \\ 0 & 0 & -1 & -2 & -3\\ 0 & 0 & 0 &3 & 7\end{pmatrix}.
\end{align*}

Seguimos entonces con la tercera columna, y observamos que la entrada $(3,3)$ es $-1$, entonces la transformamos en un $1$ multiplicando el tercer renglón por $\frac{1}{-1}=-1$.

\begin{align*}
A_5=\begin{pmatrix}
1 & 0 &-1 & -2 &-3\\ 0 & 1 & 2 & 3 &4 \\ 0 & 0 & 1 & 2 & 3\\ 0 & 0 & 0 &3 & 7\end{pmatrix}.
\end{align*}

Ahora tenemos que cancelar las entradas de la tercer columna, para eso sumamos $-2$ veces el tercer renglón al segundo y una vez el tercer renglón al primero:

\begin{align*}
A_6&=\begin{pmatrix}
1+0 & 0+0 &-1+1 & -2+2 &-3+3\\ 0-2\cdot 0 & 1-2\cdot 0 & 2-2\cdot 1 & 3-2\cdot2 &4-2\cdot3 \\ 0 & 0 & 1 & 2 & 3\\ 0 & 0 & 0 &3 & 7\end{pmatrix}\\
&= \begin{pmatrix}
1 & 0 &0 & 0 &0\\ 0 & 1 & 0 & -1 &-2 \\ 0 & 0 & 1 & 2 & 3\\ 0 & 0 & 0 &3 & 7\end{pmatrix}.
\end{align*}

Ahora pasamos a la siguiente columna. En la entrada $(4,4)$ tenemos un $3$, pero queremos un $1$, entonces multiplicamos el último renglón por $\frac{1}{3}$:

\begin{align*}
A_7= \begin{pmatrix}
1 & 0 &0 & 0 &0\\ 0 & 1 & 0 & -1 &-2 \\ 0 & 0 & 1 & 2 & 3\\ 0 & 0 & 0 &1 & \frac{7}{3}\end{pmatrix}.\end{align*}

Finalmente, cancelamos las entradas restantes de los otros renglones sustrayendo dos veces el último renglón del penúltimo y sumándolo una vez al segundo para obtener

\begin{align*}
A_8=\begin{pmatrix}1 & 0 &0 &0 &0 \\ 0 & 1& 0 & 0 & \frac{1}{3}\\ 0 & 0 &1 & 0 &-\frac{5}{3}\\ 0 & 0 & 0 & 1 & \frac{7}{3} \end{pmatrix}.
\end{align*}

Y así termina nuestro algoritmo, y nuestra matriz está en forma escalonada reducida. Las dos cosas más importantes de $A_8$ son que

  • Está en forma escalonada reducida y
  • es equivalente a $A$, es decir, el sistema de ecuaciones $AX=0$ y el sistema de ecuaciones $A_8 X =0$ tienen exactamente las mismas soluciones.

De hecho, todas las matrices $A,A_1, A_2, \ldots, A_8$ son equivalentes entre sí, pues difieren únicamente en operaciones elementales. Esta propiedad es muy importante, y precisamente es la que nos permite aplicar el algoritmo de reducción gaussiana a la resolución de sistemas lineales.

Una aplicación a un sistema de ecuaciones

Usemos el ejemplo anterior para resolver un sistema de ecuaciones:

Problema. Resolver en los reales el sistema lineal homogéneo $AX=0$ donde $A$ es la matriz ejemplo de la sección anterior.

Solución: Los sistemas $AX=0$ y $A_{red}X=0$ son equivalentes, por lo que basta resolver $A_{red}X=0$ con $A_{red}$ la matriz en forma escalonada reducida que encontramos (es decir, $A_8$). Este sistema queda planteado por las siguientes ecuaciones lineales:

\begin{align*}
\begin{cases}
x_1=0\\
x_2+\frac{x_5}{3}=0\\
x_{3}-\frac{5}{3}x_5=0\\
x_4+\frac{7}{3}x_5=0.
\end{cases}.
\end{align*}

Ya hemos resuelto sistemas de este estilo. Aquí $x_5$ es la variable libre y $x_1,x_2,x_3,x_4$ son variables pivote. Fijando $x_5$ igual a cualquier número real $t$, obtenemos que las soluciones son de la forma

\begin{align*}
\left(0, -\frac{1}{3}t, \frac{5}{3} t, – \frac{7}{3}t, t\right), \hspace{2mm} t\in \mathbb{R}.
\end{align*}

$\triangle$

Más adelante…

El algoritmo de reducción gaussiana es crucial para muchos de los problemas que nos encontramos en álgebra lineal. Por ahora, las aplicaciones principales que veremos es cómo nos permite resolver sistemas de ecuaciones lineales de la forma $AX=b$ y cómo nos permite encontrar inversas de matrices. Sin embargo, más adelante usaremos reducción gaussiana para determinar la dimensión de espacios vectoriales, conjuntos generados, para determinar si ciertos vectores son linealmente independientes, para determinar el rango de una matriz y varias otras cosas más.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  • Aplica el algoritmo de reducción gaussiana a la matriz $$\begin{pmatrix} 1 & 1 & 2 & 2 & 3 & 3 \\ 0 & 0 & 4 & 4 & 5 & 5 \\ 0 & 0 & 0 & 0 & 6 & 6 \end{pmatrix}.$$ Para su sistema lineal asociado, encuentra todas las variables pivote y libres y resuélvelo por completo.
  • Aplica el algoritmo de reducción gaussiana a la matriz $$\begin{pmatrix} 0 & 8 \\ 0 & 2 \\ -1 & 5 \\ 2 & 3 \\ 5 & 0 \\ 3 & 1\end{pmatrix}.$$
  • Considera las matrices $A_1$, $A_4$ y $A_8$ de la sección con el ejemplo del algoritmo de reducción gaussiana. Toma una solución no trivial de $A_8X=0$ y verifica manualmente que también es solución de los sistemas lineales $A_1X=0$ y de $A_4X=0$.
  • Encuentra la matriz $B$, producto de matrices elementales tal que $BA=A_{red}$ con $A$ la matriz que usamos en el ejemplo. Para ello, tendrás que multiplicar todas las matrices correspondientes a las operaciones elementales que usamos.
  • Explica qué es lo que garantiza que el algoritmo de reducción gaussiana en efecto hace una cantidad finita de operaciones elementales.
  • Aplica el algoritmo de reducción gaussiana a la matriz $$A=\begin{pmatrix} 0 & 2 & 1 & 0 \\ 1 & 1 & 0 & 1\end{pmatrix}.$$ Si haces los pasos correctamente, llegarás a una matriz del estilo $$A_{red}=\begin{pmatrix} 1 & 0 & a & b \\ 0 & 1 & c & d \end{pmatrix}.$$ Toma el bloque $B$ de $2\times 2$ de la izquierda de $A$, es decir $B=\begin{pmatrix} 0 & 2 \\ 1 & 1\end{pmatrix}$. Toma el bloque $C$ de $2\times 2$ de la derecha de $A_{red}$, es decir, $C=\begin{pmatrix} a & b \\ c & d \end{pmatrix}.$ ¿Qué matriz obtienes al hacer el producto $BC$? ¿Y el producto $CB$? ¿Por qué crees que pasa esto?

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104721 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM»