09 Elementary Row Operations, Gauss Elimination, Inverse Matrices, Inverse Theorem

Lecture from 16.10.2024 | Video: Videos ETHZ

Elementary Row Operations

Why Elementary Row Operations Preserve the Solution Set

Each elementary row operation corresponds to an invertible transformation of the system of equations. Since each operation is invertible, we can always reverse the operation to recover the original system, implying that the two systems (before and after applying operations) are equivalent.

Formally: (Lemma 3.3)

If we say $A^{\prime }x=MAx=Mb=b^{\prime }$ then there exists $M^{\prime }$ such that $Ax=M^{\prime }{A}^{\prime }x=M^{\prime }{b}^{\prime }=b$. Hence, every solution of $Ax=b$ is a solution of $A^{\prime }x=b^{\prime }$.

Intuitively, if we have a $x$ which works out for $Ax=b$ and we simply multiply both side by the same thing, then $A^{\prime }x=b^{\prime }$ must be true too. $Ax=b⟺A^{\prime }x=b^{\prime }$.

Gauss Elimination

Theorem 3.5

Let $Ax=b$ be a system of $m$ equations and $m$ variables. The following statements are equivalent:

1. Gauss Elimination works out
2. The columns of $A$ are linearly independent

Proof:

We’ll show (i) $⟹$ (ii) and not (i) $⟹$ not (ii) (contrapositive).

(i) ⇒(ii):

If Gauss elimination succeeded, then we transformed $A\to U$, an upper diagonal matrix with $u_{jj}\ne 0$ for all $j$. U has linearly independent columns (i.e. no column is a linear combination of the previous). It becomes trivial to see that this is the case, since for every pivot the previous columns all have zeros in that position.

not (i) ⇒ not (ii)

If Gauss elimination fails, then for some column $c_j$ a pivot is zero.

The part before is alright, cause it’s pivots are non-zero, but at our column $c_j$ we have a zero pivot. Now we need to show that the columns of this matrix are linearly dependent.

To do that we’ll construct $x\ne 0$ such that $A^{\prime }x=0$.

Let us set $x_{j+1}=x_{j+2}=\cdots =x_m=0$ and choose the other $x_i$ such that:

Now this equation will have a solution since U is a valid upper triangular matrix with non-pivots which means that $Uy=v$ can be easily solved by back substitution (see: Gauss Elimination). We’ll then get a non-zero vector implying linear dependence.

Runtime

The runtime of Gauss Elimination is:

Inverse Matrices

TLDR: $M{M}^{-1}=M^{-1}M=I$.

In simpler terms, the inverse of a matrix “undoes” the effect of that matrix, similar to how division undoes multiplication for real numbers. For example, if you apply a matrix transformation to a vector, applying the inverse matrix transformation will return the vector to its original state.

Invertible Matrices

Not all square matrices are invertible. (i.e. not all linear transformations are undo-able, for example ${\mathbb{R}}^3\to {\mathbb{R}}^2$).

Case 1x1:

Case 2x2:

Proof:

1. Let’s first make an augmented matrix:

   $$[M|I]=\left[\begin{array}{cccc}a& b& 1& 0\\ c& d& 0& 1\end{array}\right]$$

2. We’ll make the pivot in the first row = 1. If $a\ne 0$

   $$\left[\begin{array}{cccc}1& \frac{b}{a}& \frac{1}{a}& 0\\ c& d& 0& 1\end{array}\right]$$

3. We’ll now eliminate the first element in the second row: $R_2\to R_2-c{R}_2$

   $$\left[\begin{array}{cccc}1& \frac{b}{a}& \frac{1}{a}& 0\\ 0& d-\frac{bc}{a}& -\frac{c}{a}& 1\end{array}\right]$$

   which simplifies to:

   $$\left[\begin{array}{cccc}1& \frac{b}{a}& \frac{1}{a}& 0\\ 0& \frac{ad-bc}{a}& -\frac{c}{a}& 1\end{array}\right]$$

4. Make the pivot in the second row and second column 1

   Next, we need to make the pivot in the second row and second column equal to 1. If ($ad-bc\ne 0$), we can divide the second row by ($\frac{ad-bc}{a}$). The resulting matrix is: $\left[\begin{array}{cccc}1& \frac{b}{a}& \frac{1}{a}& 0\\ 0& 1& \frac{-c}{ad-bc}& \frac{a}{ad-bc}\end{array}\right]$

5. Eliminate the second element in the first row

   We subtract ($\frac{b}{a}$) times the second row from the first row: $R_1\to R_1-\frac{b}{a}{R}_2$ The resulting matrix becomes:

   $$\left[\begin{array}{cccc}1& 0& \frac{d}{ad-bc}& \frac{-b}{ad-bc}\\ 0& 1& \frac{-c}{ad-bc}& \frac{a}{ad-bc}\end{array}\right]$$ $$M^{-1}=\frac{1}{ad-bc}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]$$

   which holds provided that ($ad-bc\ne 0$) (the determinant of $M$ is non-zero).

The inverse is unique

If we have a matrix $M$ with two inverses $A$ and $B$, then $A=B$.

Proof:

Inverse of a product

If $A$ and $B$ are invertible matrices then $AB$ is also invertible and $(AB)=B^{-1}{A}^{-1}$.

Proof:

Inverse of a Transposition

If we have a matrix $A$ which is invertible then:

Inverse Theorem (Theorem 3.11)

Let $A$ be a $m\times m$ matrix. The following are equivalent.

1. A is invertible
2. For every $b\in {\mathbb{R}}^m$, $Ax=b$ has a unique solution $x$
3. The columns of $A$ are independent

Proof:

We’ll prove the following implications:

1. (i) ⇒ (ii)

If A is invertible then: $x=A^{-1}b$ is a solution because

And it’s also unique because for any $x$, $x=Ix=A^{-1}Ax=A^{-1}b$.

(ii) ⇒ (iii)

If $Ax=b$ always has a unique solution, then also for $b=0$. And we’ve proven that if $Ax=0$ has a unique (trivial) solution, then it’s linearly independent (See Gauss Elimination).

(iii) ⇒ (ii)

Let $x,x^{\prime }$ be solutions of $Ax=b$.

If Gauss elimination succeeds, which it must since the columns are independent, then we’ll find a solution to our equation.

But since the columns of A are linearly independent, there must only exists one trivial solution $x-x^{\prime }=0⟹x=x^{\prime }$.

(ii) ⇒ (i)

If $Ax=b$ has a unique solution for all $b$, then also for $b=e_1,e_2,\dots ,e_m$ (unit vectors). This implies that there are $v_1,v_2,\dots ,v_m$ such that:

But now we also need to show $BA=I$.

Continue here: 10 Calculating the Inverse, LU and LUP Decomposition