MATH347

MATH347 L8: Row echelon forms

New concepts:
- Row echelon form
- Elementary matrices
- Matrix inverse

How to determine number of solutions?

Use similarity transformations to reduced row echelon form:
- All zero rows are below non-zero rows
- First non-zero entry on a row is called the leading entry
- In each non-zero row, the leading entry is to the left of lower leading entries
- Each leading entry equals 1 and is the only non-zero entry in its column
Row echelon form:
- Allow additional non-zero elements in a column, above the leading entry
>>

A=[1 2 3; 0 1 1; 1 2 3]; rref(A)
$(\begin{array}{ccc} 1 & 0.0 & 1 \\ 0.0 & 1 & 1 \\ 0.0 & 0.0 & 0.0 \end{array})$
>>

Interpretation of reduced echelon forms

After carrying out rref on bordered matrix $[\begin{array}{lll} 𝑨 & | . & 𝒃 \end{array}]$ , if:

there is a row with $[\begin{array}{llllll} 0 & 0 & \dots & 0 & | . & 1 \end{array}] \Rightarrow$ No solutions
the result is of form $[\begin{array}{lll} 𝑰 & | . & 𝒄 \end{array}] \Rightarrow$ Unique solution
there is no row of form $[\begin{array}{llllll} 0 & 0 & \dots & 0 & | . & 1 \end{array}]$ , and there is a row of all zeros $[\begin{array}{llllll} 0 & 0 & \dots & 0 & | . & 0 \end{array}] \Rightarrow$ Infinitely many solutions

Examples

[\begin{array}{llllll} 1 & - 1 & 0 & 1 & | . & 2 \\ 0 & 0 & 1 & - 1 & | . & 1 \\ 0 & 0 & 0 & 0 & | . & 0 \end{array}] \Rightarrow Infinitely many solutions

[\begin{array}{lllll} 1 & 2 & - 4 & | . & - 4 \\ 0 & 3 & - 1 & | . & 2 \\ 0 & 0 & 8 & | . & 8 \end{array}] \sim [\begin{array}{lllll} 1 & 0 & 0 & | . & - 2 \\ 0 & 1 & 0 & | . & 1 \\ 0 & 0 & 1 & | . & 1 \end{array}] \Rightarrow Unique solution

Elementary matrices: Permutation

Denote a permutation by
$σ = (\begin{array}{cccc} 1 & 2 & \dots & m \\ i_{1} & i_{2} & \dots & i_{m} \end{array})$
with $i_{1}, \dots, i_{m} \in {1, \dots, m}$ , $i_{j} \neq i_{k}$ for $j \neq k$
The sign of a permutation, $ν (σ)$ is the number of pair swaps needed to obtain the permutation starting from the identity permutation
$(\begin{array}{cccc} 1 & 2 & \dots & m \\ 1 & 2 & \dots & m \end{array})$
A permutation can be specified by a permutation matrix $𝑷$ obtained from $𝑰$ by swapping rows and columns $k \leftrightarrow i_{k}$

Elementary matrices: Row combinations

Recall the basic operation in row echelon reduction: constructing a linear combination of rows to form zeros beneath the main diagonal, e.g.
$𝑨 = (\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 m} \\ a_{21} & a_{22} & \dots & a_{2 m} \\ a_{31} & a_{32} & \dots & a_{3 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m m} \end{array}) \sim (\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 m} \\ 0 & a_{22} - \frac{a_{21}}{a_{11}} a_{12} & \dots & a_{2 m} - \frac{a_{21}}{a_{11}} a_{1 m} \\ 0 & a_{32} - \frac{a_{31}}{a_{11}} a_{12} & \dots & a_{3 m} - \frac{a_{31}}{a_{11}} a_{1 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & a_{m 2} - \frac{a_{m 1}}{a_{11}} a_{12} & \dots & a_{m m} - \frac{a_{m 1}}{a_{11}} a_{1 m} \end{array})$
This can be stated as a matrix multiplication operation, with $l_{i 1} = a_{i 1} / a_{11}$
$(\begin{array}{ccccc} 1 & 0 & 0 & \dots & 0 \\ - l_{21} & 1 & 0 & \dots & 0 \\ - l_{31} & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ - l_{m 1} & 0 & 0 & \dots & 1 \end{array}) (\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 m} \\ a_{21} & a_{22} & \dots & a_{2 m} \\ a_{31} & a_{32} & \dots & a_{3 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m m} \end{array}) = (\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 m} \\ 0 & a_{22} - l_{21} a_{12} & \dots & a_{2 m} - l_{21} a_{1 m} \\ 0 & a_{32} - l_{31} a_{12} & \dots & a_{3 m} - l_{31} a_{1 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & a_{m 2} - l_{m 1} a_{12} & \dots & a_{m m} - l_{m 1} a_{1 m} \end{array})$

Gaussian multiplier matrix

Definition. The matrix

$𝑳_{k} = (\begin{array}{ccccc} 1 & \dots & 0 & \dots & 1 \\ 0 & ⋱ & 0 & \dots & 0 \\ 0 & \dots & 1 & \dots & 0 \\ 0 & \dots & - l_{k + 1, k} & \dots & 0 \\ 0 & \dots & - l_{k + 2, k} & \dots & 0 \\ ⋮ & \dots & ⋮ & ⋱ & ⋮ \\ 0 & \dots & - l_{m, k} & \dots & 1 \end{array})$

with $l_{i, k} = a_{i, k}^{(k)} / a_{k, k}^{(k)}$ , and $𝑨^{(k)} = (a_{i, j}^{(k)})$ the matrix obtained after step $k$ of row echelon reduction (or, equivalently, Gaussian elimination) is called a Gaussian multiplier matrix.

Permutation and Gaussian multiplier matrices are elementary matrices.

Inverse matrix

Consider elementary matrices
$𝑬_{1} = [\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 3 & 0 & 1 \end{array}], 𝑬_{2} = [\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 3 & 0 & 1 \end{array}], 𝑬_{1} 𝑬_{2} = 𝑬_{2} 𝑬_{1} = 𝑰,$
stating that $𝑬_{1}$ undoes the effect of $𝑬_{2}$ .
$𝑨 \in ℝ^{m \times m}$ is invertible if there exists $𝑿 \in ℝ^{m \times m}$ such that
$𝑨 𝑿 = 𝑿 𝑨 = 𝑰$
Notation $𝑿 = 𝑨^{- 1}$ , is the inverse of $𝑨$ .