Solving linear equations

Andrew Thangaraj

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}\]