# Elementary row operations

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