Elementary row operations

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\}\)
    • 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\)
  • Linear equation: \(Ax=b\)
    • Solution depends on whether \(A\) is injective, surjective

General 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

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.

\(3\times3\) example

\[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

  • permute Row 1 and Row 2

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

\(3\times3\) example

\[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

  • Divide Row 1 by 3

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

\(3\times3\) example

\[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

  • Row 3 = Row 3 - 2(Row 1)

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

\(3\times3\) example

\[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

  • Divide Row 2 by 2

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

\(3\times3\) example

\[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

  • Row 3 = Row 3 - (17/3)(Row 2)

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

\(3\times3\) example

\[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

  • Multiply Row 3 by -6/61

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

\(3\times3\) example: summary

\[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

Elementary row operations (in general)

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

Result of elementary row operations

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

Example: dimension of range and null

\[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

Example: \(Ax=0\) or find basis of null \(A\)

\[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

  • \((x_2,x_5,x_6,x_7)=(0,0,0,1)\)
    • \((x_1,x_3,x_4)=(-21,10,-4)\)
    • \(v_1=(-21,0,10,-4,0,0,1)\)
  • \((x_2,x_5,x_6,x_7)=(0,0,1,0)\)
    • \((x_1,x_3,x_4)=(-46,24,-8)\)
    • \(v_2=(-46,0,24,-8,0,1,0)\)
  • \((x_2,x_5,x_6,x_7)=(0,1,0,0)\)
    • \((x_1,x_3,x_4)=(-25,16,-7)\)
    • \(v_3=(-25,0,16,-7,1,0,0)\)
  • \((x_2,x_5,x_6,x_7)=(1,0,0,0)\)
    • \((x_1,x_3,x_4)=(-2,0,0)\)
    • \(v_4=(-2,1,0,0,0,0,0)\)

Basis for null \(A\): \(\{v_1,v_2,v_3,v_4\}\)

Example: \(Ax=b\)

\[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

  • \((x_2,x_5,x_6,x_7)=(0,0,0,0)\)
    • \((x_1,x_3,x_4)=(10,-7,3)\)
    • \(u=(10,0,-7,3,0,0,0)\)
    • called particular solution

Solution: \(u+\) null \(A\)

\[\{u+a_1v_1+a_2v_2+a_3v_3+a_4v_4:a_i\in\mathbb{R}\}\]

Example: \(Ax=b\)

\[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

Quiz