LA-04 — Systems, Gaussian elimination, rank

Why this matters for ML

Resolver $A\mathbf{x}=\mathbf{b}$ es el esqueleto de la regresión lineal (las normal equations son un sistema). El rank te dice si tus features son redundantes o si un modelo tiene solución única. Los cuatro subespacios fundamentales (column space, null space) explican cuándo un problema de ML tiene solución y cuántas.

Concepts covered

• Sistema lineal $A\mathbf{x}=\mathbf{b}$
• Gaussian elimination, row echelon form (REF) y reduced (RREF)
• Pivots
• Rank
• Column space y null space (kernel)
• Existencia y unicidad de soluciones

Intuition first

🎬 3Blue1Brown E.o.L.A. cap. 7 ("Inverse matrices, column space and null space"). Piensa en $A\mathbf{x}=\mathbf{b}$ como "¿qué input $\mathbf{x}$ aterriza en $\mathbf{b}$ tras la transformación $A$?".

Theory & key results

Sistema: $m$ ecuaciones, $n$ incógnitas ↔ $A\mathbf{x}=\mathbf{b}$ con $A\in\mathbb{R}^{m\times n}$.

Gaussian elimination: con tres row operations (intercambiar filas, escalar una fila, sumar múltiplo de una fila a otra) llevas $A$ a forma triangular (REF) y luego a RREF. No cambian el conjunto solución.

Pivots: las primeras entradas no nulas de cada fila en REF. El número de pivots = rank.

Rank $r$: número de filas (o columnas) linealmente independientes = dimensión del column space. Intuición ML: cuántas "direcciones de información" reales hay.

Column space $C(A)$: span de las columnas de $A$ = todos los $\mathbf{b}$ alcanzables. $A\mathbf{x}=\mathbf{b}$ tiene solución ⟺ $\mathbf{b}\in C(A)$.

Null space $N(A)$: todos los $\mathbf{x}$ con $A\mathbf{x}=\mathbf{0}$. Su dimensión es $n-r$ (rank–nullity theorem). Si $N(A)\neq{\mathbf{0}}$, hay infinitas soluciones (o ninguna).

Existencia y unicidad (para $A$ cuadrada $n\times n$):

• $r=n$ (full rank): solución única para todo $\mathbf{b}$; $A$ invertible.
• $r<n$: null space no trivial → o infinitas soluciones o ninguna, según $\mathbf{b}$.

Worked example

Resolver $$\begin{cases} x + 2y = 5\ 3x + 4y = 6 \end{cases}, \quad A=\begin{bmatrix}1&2\3&4\end{bmatrix}.$$ Fila2 ← Fila2 − 3·Fila1: $\begin{bmatrix}1&2\0&-2\end{bmatrix}$, lado derecho $(5, -9)$. Dos pivots → rank 2 → solución única. Back-substitution: $-2y=-9\Rightarrow y=4.5$; $x=5-2(4.5)=-4$. Solución $(-4, 4.5)$.

Notebook exercises (by hand)

1. Lleva a RREF $\begin{bmatrix}1&1&2\2&2&4\end{bmatrix}$ y da su rank. ¿Qué notas de la fila 2?
2. Para $A$ del ej. anterior, describe $C(A)$ y $N(A)$.
3. ¿Cuántas soluciones tiene $A\mathbf{x}=\mathbf{b}$ si $A$ es $3\times3$ con rank 2? Depende de $\mathbf{b}$: explica ambos casos.
4. Verifica el rank–nullity theorem ($r + \dim N(A) = n$) en un ejemplo $3\times3$ de rank 2.
5. Resuelve por eliminación: $x+y+z=6,\ 2y+5z=-4,\ 2x+5y-z=27$.
6. Si dos feature columns de tu dataset son idénticas, ¿qué le pasa al rank y por qué eso complica ajustar un modelo lineal?

Python lab

import numpy as np
from numpy.linalg import matrix_rank, solve

A = np.array([[1.,2.],[3.,4.]]); b = np.array([5.,6.])
print("rank:", matrix_rank(A))       # 2 -> full rank
print("solución:", solve(A, b))      # [-4. , 4.5]

# sistema singular (columnas dependientes)
S = np.array([[1.,1.,2.],[2.,2.,4.],[0.,1.,1.]])
print("rank singular:", matrix_rank(S))   # < 3

# null space vía SVD (pequeño adelanto de LA-09)
U, s, Vt = np.linalg.svd(S)
null = Vt[np.isclose(s, 0)].T if np.any(np.isclose(s,0)) else "trivial"
print("null space:\n", null)

Implementa tu propia Gaussian elimination sobre una matriz aumentada y compárala con np.linalg.solve — es el mejor ejercicio del módulo.

Examen final 📝

Intenta cada nivel antes de abrir las soluciones.

🟡 Medio

1. Resuelve por eliminación: $x+2y=4,\ 3x-y=5$.
2. Da el rank de $\begin{bmatrix}1&2&3\2&4&6\1&1&1\end{bmatrix}$ llevándola a REF.

🟠 Medio-difícil

3. Para $A=\begin{bmatrix}1&2&1\2&4&2\end{bmatrix}$: describe $C(A)$ (column space) y encuentra una base de $N(A)$ (null space).
4. Un sistema $A\mathbf x=\mathbf b$ con $A$ de $3\times3$ tiene $\text{rank}(A)=2$. Da un $\mathbf b$ para el que haya infinitas soluciones y explica cuándo no habría ninguna.

🔴 Difícil

5. Demuestra el rank–nullity theorem en un caso concreto $3\times3$ de rank 2 (construye la matriz, calcula rank y $\dim N(A)$, verifica $r+\dim N(A)=n$) y explícalo conceptualmente.
6. En regresión lineal, $\hat{\mathbf w}=(X^\top X)^{-1}X^\top\mathbf y$ requiere que $X^\top X$ sea invertible. Muestra que $\text{rank}(X^\top X)=\text{rank}(X)$ y concluye qué condición sobre las feature columns garantiza solución única.