# Solving linear equations

Aug-Nov 2020

## Recap

• Vector space $V$ over a scalar field $F$
• $F$: real field $\mathbb{R}$ or complex field $\mathbb{C}$ in this course
• Linear map $T:V\to W$ preserves linear combinations
• null $T=\{v\in V:Tv=0\}$, range $T=\{Tv:v\in V\}$
• Fundamental theorem of linear maps
• dim null $T$ + dim range $T$ = dim $V$
• $m\times n$ matrix $A$ represents a linear map $T:F^n\to F^m$
• colspace$(A) =$ range $T$, null$(A) =$ null $T$
• Invertible operators are isomorphisms
• Finite-dimensional vector spaces are isomorphic to $F^n$
• Linear maps are isomorphic to matrices

## Linear equations

$Ax=b$

$A=\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\vdots&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn} \end{bmatrix},\ x=\begin{bmatrix} x_1\\x_2\\\vdots\\x_n \end{bmatrix},\ b=\begin{bmatrix} b_1\\b_2\\\vdots\\b_m \end{bmatrix}$

$A\in F^{m,n}$: given,$\quad$ $b\in F^m$: given,$\quad$ $x\in F^n$: to be solved

$T:F^n\to F^m$, linear map represented by $A$ w.r.t. standard bases

$e^{(n)}_j$: vector with 1 at $j$-th position, length $n$

$Te^{(n)}_j=j$-th column of $A$

For $w=(b_1,\ldots,b_m)\in W$, find all $v=(x_1,\ldots,x_n)\in V$ such that $Tv=w$

$w=b_1e^{(m)}_1+\cdots+b_me^{(m)}_m$,$\quad$ $v=x_1e^{(n)}_1+\cdots+x_ne^{(n)}_n$

homogeneous: $b=(0,\ldots,0)$ or $w=0$; find null $T$

## Example 1

$\begin{bmatrix} 1&2&3\\ 0&4&5\\ 0&0&6 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_1\\b_2\\b_3 \end{bmatrix}$

$T$: $(1,0,0)\to (1,0,0)$, $(0,1,0)\to (2,4,0)$, $(0,0,1)\to (3,5,6)$

range $T=\text{span}\{(1,0,0),(2,4,0),(3,5,6)\}=\mathbb{R}^3$, null $T=\{0\}$

$T$: invertible map

Unique solution for every $b$

## Example 2

$\begin{bmatrix} 1&2&3&7&8\\ 0&4&5&9&10\\ 0&0&6&11&12 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5 \end{bmatrix}=\begin{bmatrix} b_1\\b_2\\b_3 \end{bmatrix}$

range $T=\mathbb{R}^3$, dim null $T=2$

$T$: surjective, not injective

Infinitely many solutions for every $b$

## Example 3

$\begin{bmatrix} 1&2&3\\ 0&4&5\\ 0&0&0 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_1\\b_2\\b_3 \end{bmatrix}$

$T$: $(1,0,0)\to (1,0,0)$, $(0,1,0)\to (2,4,0)$, $(0,0,1)\to (3,5,0)$

range $T=\text{span}\{(1,0,0),(0,1,0)\}$, dim null $T=1$

$T$: not surjective, not injective

Infinitely many solutions if $(b_1,b_2,b_3)\in$ range $T$ or $b_3=0$

No solution if $b_3\ne0$

## Example 4

$\begin{bmatrix} 1&2&3\\ 0&4&5\\ 0&0&6\\ 0&0&7 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_1\\b_2\\b_3\\b_4 \end{bmatrix}$

dim range $T=3$, dim null $T=0$

$T$: not surjective, injective

Unique solution if $(b_1,\ldots,b_4)\in$ range $T$ or $7b_3=6b_4$

No solution if $7b_3\ne 6b_4$

## General $3\times3$ case

$\begin{bmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33} \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_1\\b_2\\b_3 \end{bmatrix}$

Gaussian elimination through elementary row operations

$\begin{bmatrix} a'_{11}&a'_{12}&a'_{13}\\ 0&a'_{22}&a'_{23}\\ 0&0&a'_{33} \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b'_1\\b'_2\\b'_3 \end{bmatrix}$