Andrew Thangaraj
Aug-Nov 2020
\[\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
Given problem: Find \(v\) such that \(Tv=w\)
is equivalent to
Find \(v\) such that \[STv=Sw,\] where \(S:W\to W\) is an invertible operator.
Find invertible operator \(S\) such that matrix of \(ST\) is of a form suitable for easy solving.
\[Ax=b\ \leftrightarrow\ \begin{bmatrix} 0&2&3\\ 3&-1&4\\ 2&5&1 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_1\\b_2\\b_3 \end{bmatrix}\]
Step 1(a): Permute Row 1 with Row \(j\) (\(j\ge 1\)) to get nonzero pivot at (1,1), if possible
Invertible operator: \(E_1=\begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{bmatrix}\)
\(E_1\times\) matrix: matrix with Rows 1 and 2 interchanged
\[E_1Ax=E_1b\ \leftrightarrow\ \begin{bmatrix} 3&-1&4\\ 0&2&3\\ 2&5&1 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2\\b_1\\b_3 \end{bmatrix}\]
\[E_1Ax=E_1b\ \leftrightarrow\ \begin{bmatrix} 3&-1&4\\ 0&2&3\\ 2&5&1 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2\\b_1\\b_3 \end{bmatrix}\]
Step 1(b): Make pivot value equal to 1
Invertible operator: \(E_2=\begin{bmatrix} 1/3&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix}\)
\(E_2\times\) matrix: matrix with Row 1 divided by 3
\[E_2E_1Ax=E_2E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&2&3\\ 2&5&1 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1\\b_3 \end{bmatrix}\]
\[E_2E_1Ax=E_2E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&2&3\\ 2&5&1 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1\\b_3 \end{bmatrix}\]
Step 1(c): Make all values below pivot 0
Invertible operator: \(E_3=\begin{bmatrix} 1&0&0\\ 0&1&0\\ -2&0&1 \end{bmatrix}\)
\(E_3\times\) matrix: matrix with Row 3 replaced by Row 3 - 2(Row 1)
\[E_3E_2E_1Ax=E_3E_2E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&2&3\\ 0&17/3&-5/3 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1\\b_3-2b_2/3 \end{bmatrix}\]
\[E_3E_2E_1Ax=E_3E_2E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&2&3\\ 0&17/3&-5/3 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1\\b_3-2b_2/3 \end{bmatrix}\]
Step 2(a-b): Make pivot at (2,2) equal to 1
Invertible operator: \(E_4=\begin{bmatrix} 1&0&0\\ 0&1/2&0\\ 0&0&1 \end{bmatrix}\)
\(E_4\times\) matrix: matrix with Row 2 divided by 2
\[E_4\cdots E_1Ax=E_4\cdots E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&1&3/2\\ 0&17/3&-5/3 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1/2\\b_3-2b_2/3 \end{bmatrix}\]
\[E_4\cdots E_1Ax=E_4\cdots E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&1&3/2\\ 0&17/3&-5/3 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1/2\\b_3-2b_2/3 \end{bmatrix}\]
Step 2(c): Make values below pivot 0
Invertible operator: \(E_5=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&-17/3&1 \end{bmatrix}\)
\(E_5\times\) matrix: matrix with Row 3 replaced by Row 3 - (17/3)(Row 1)
\[E_5\cdots E_1Ax=E_5\cdots E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&1&3/2\\ 0&0&-61/6 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1/2\\b_3-2b_2/3-17b_1/6 \end{bmatrix}\]
\[E_5\cdots E_1Ax=E_5\cdots E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&1&3/2\\ 0&0&-61/6 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1/2\\b_3-2b_2/3-17b_1/6 \end{bmatrix}\]
Step 3(a-b): Make pivot at (3,3) equal to 1
Invertible operator: \(E_6=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&-6/61 \end{bmatrix}\)
\(E_6\times\) matrix: matrix with Row 3 replaced by (-6/61)(Row 3)
\[E_6\cdots E_1Ax=E_6\cdots E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&1&3/2\\ 0&0&1 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1/2\\-6b_3/61+4b_2/61+17b_1/61 \end{bmatrix}\]
\[Ax=b\ \leftrightarrow\ \begin{bmatrix} 0&2&3\\ 3&-1&4\\ 2&5&1 \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
\[E_6\cdots E_1Ax=E_6\cdots E_1b\ \leftrightarrow\ \begin{bmatrix} 1&-1/3&4/3\\ 0&1&3/2\\ 0&0&1 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix} b_2/3\\b_1/2\\-6b_3/61+4b_2/61+17b_1/61 \end{bmatrix}\]
Unique solution
\(A\): \(m\times n\) matrix
1: row counter: i=1, column counter: j=1
2: while i <= m and j <= n
3: if a_ij != 0 [pivot at (i,j)]
4: divide Row i by a_ij [make pivot value 1]
5: for k = i+1 to m [make values below pivot 0]
6: Row k = Row k - (a_kj)(Row i)
7: i=i+1, j=j+1 [next row,column if pivot is nonzero]
8: else
9: if (there exists k>i s.t. a_kj != 0)
10: interchange Row i,k [same pivot position]
11: else
12: j=j+1 [next column if no nonzero pivot]
For any matrix \(A\), there are elementary row operations \(E_i\) such that \[\left(\prod_i E_i\right)A=\begin{bmatrix} 0&\cdots&0&1&\ast&\cdots&\ast&\ast&\ast&\cdots&\ast&\ast&\cdots&\cdots\\ 0&\cdots&0&0& 0 &\cdots& 0 & 1 &\ast&\cdots&\ast&\ast&\cdots&\cdots\\ 0&\cdots&0&0& 0 &\cdots& 0 & 0 & 0 &\cdots& 0 & 1 &\cdots&\cdots\\ 0&\cdots&0&0& 0 &\cdots& 0 & 0 & 0 &\cdots& 0 & 0 &\cdots&\cdots\\ \vdots&\vdots&\vdots&\vdots& \vdots &\vdots& \vdots & \vdots & \vdots &\vdots& \vdots & \vdots &\vdots &\vdots\\ \end{bmatrix}\]
rank \(A\) \(=\) number of nonzero pivots
dim null \(A=n-\)rank \(A\)
Basis of null \(A\): found by solving \(Ax=0\) using above form
\[A\in F^{4,7}\to \begin{bmatrix} 1&2&3&4&5&6&7\\ 0&0&1&3&5&0&2\\ 0&0&0&1&7&8&4\\ 0&0&0&0&0&0&0 \end{bmatrix}\]
rank \(A=3\)
dim null \(A=7-3=4\)
\[Ax=0\leftrightarrow\begin{bmatrix} 1&2&3&4&5&6&7\\ 0&0&1&3&5&0&2\\ 0&0&0&1&7&8&4\\ 0&0&0&0&0&0&0 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7 \end{bmatrix}=\begin{bmatrix} 0\\0\\0\\0 \end{bmatrix}\]
variables corresponding to pivots \((x_1,x_3,x_4)\): dependent
remaining variables \((x_2,x_5,x_6,x_7)\): free
\[A\in F^{4,7}\to \begin{bmatrix} 1&2&3&4&5&6&7\\ 0&0&1&3&5&0&2\\ 0&0&0&1&7&8&4\\ 0&0&0&0&0&0&0 \end{bmatrix}\]
Free variables \(=(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0)\) and solve for dependent variables
Basis for null \(A\): \(\{v_1,v_2,v_3,v_4\}\)
\[Ax=b\leftrightarrow\begin{bmatrix} 1&2&3&4&5&6&7\\ 0&0&1&3&5&0&2\\ 0&0&0&1&7&8&4\\ 0&0&0&0&0&0&0 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7 \end{bmatrix}=\begin{bmatrix} 1\\2\\3\\0 \end{bmatrix}\]
Free variables \(=(0,0,0,0)\) and solve for dependent variables
Solution: \(u+\) null \(A\)
\[\{u+a_1v_1+a_2v_2+a_3v_3+a_4v_4:a_i\in\mathbb{R}\}\]
\[Ax=b\leftrightarrow\begin{bmatrix} 1&2&3&4&5&6&7\\ 0&0&1&3&5&0&2\\ 0&0&0&1&7&8&4\\ 0&0&0&0&0&0&0 \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7 \end{bmatrix}=\begin{bmatrix} 1\\2\\3\\4 \end{bmatrix}\]
No solution