MATH 323 Lecture 5

« previous | Tuesday, September 11, 2012 | next »

Elementary Matrices

System of equations now in form $A\overrightarrow{x}=\overrightarrow{b}$, where $A$ is $m\times n$, and $\overrightarrow{x}$ and $\overrightarrow{b}$ are ${\mathbb{ℝ}}^n$

For a non-singular, invertible $m\times m$ matrix $M$, $MA\overrightarrow{x}=M\overrightarrow{b}$, and this system will be equivalent to the original. $M$ could even be product of several matrices: $M=E_k{E}_{k-1}\dots E_2{E}_1$, where $E_i$ is an elementary matrix.

Types of elementary matrices (each corresponds to rules of matrix):

1. $E$ obtained by interchanging two rows of identity matrix $I$
   • $EA$ permutes rows
   • $AE$ permutes columns
2. $E$ obtained by multiplying row of identity matrix $I$ by a nonzero constant $\alpha$
   • $EA$ scales corresponding row by $\alpha$
   • $AE$ scales corresponding column by $\alpha$.
3. $E$ obtained from $I$ by adding a multiple of one row $i$ to another row $i^{\prime }$:
   • $EA$ adds multiple of row $i$ to row $i^{\prime }$
   • $AE$ adds multiple of column $i$ to column $i^{\prime }$

Note: $I$ (and thus $E$) is always a square matrix, but $A$ can be of any size

$E$ is a $n\times n$ matrix: we can think of it as being obtained from $I$ by either a row operation or column operation. If $A$ is a $n\times r$ matrix, premultiplying $A$ by $E$ has the effect of performing the same row operation on $A$. If $B$ is a $m\times n$ matrix, postmultiplying $B$ by $E$ is equivalent to performing that same column operation on $B$.

Theorem 1.4.1

If $E$ is an elementary matrix, then $E$ is nonsingular and $E^{-1}$ is an elementary matrix of the same type as $E$

1. $EE=I$, since interchanging two rows twice undoes the effect, so $E=E^{-1}$
2. if $E$ has an $\alpha$ at position $i,i$. $E^{-1}$ will have $1/\alpha$ at $i,i$
3. $E$ has a $m$ at position $i,j$, where $i\ne j$. $E^{-1}$ will have $-m$ at $i,j$. In multiplying $E$ by $E^{-1}$, position $i,j$ will be product of $i$th row and $j$th column: $\sum _{k=1}^n{e}_{i,k}{e}_{k,j}^{-1}=m-m=0$

Row Equivalence

$B$ is row equivalent to $A$ (written $B\sim A\leftrightarrow A\sim B$ iff there exists a finite sequence $E_1,E_2,\dots ,E_k$ of elementary matrices such that $B=E_k{E}_k-1\dots E_2{E}_{1}A$. In other words, $B$ can be obtained from $A$ by a finite number of row operations.

By extension, two augmented matrices $(A|\overrightarrow{b})$ and $(B|\overrightarrow{c})$ are row equivalent iff $A\overrightarrow{x}=\overrightarrow{b}$ and $B\overrightarrow{x}=\overrightarrow{c}$ are equivalent systems.

Theorem 1.4.2

Equivlent Conditions for Nonsingularity

Let $A$ be a $n\times n$ matrix. Then the following are equivalent:

1. $A$ is nonsingular
2. $A\overrightarrow{x}=\overrightarrow{0}$ has only trivial solution $\overrightarrow{0}$
3. $A$ is row equivalent to identity matrix of size $n$ ($A\sim I_n$)

(1) → (2): Let $\hat{x}$ be solution of $A\overrightarrow{x}=\overrightarrow{0}$. So $A\hat{x}=\overrightarrow{0}$ can become $A^{-1}A\hat{x}=A^{-1}\overrightarrow{0}$. $I\hat{x}=\overrightarrow{0}$, so $\hat{x}=\overrightarrow{0}$

(2) → (3): Rewrite $A\overrightarrow{x}=\overrightarrow{0}$ in row echelon form as $U\overrightarrow{x}=\overrightarrow{0}$. If one diagonal entry of $U$ is 0, then there is at least one free variable and infinitely many solutions, one of which is nonzero. This leads to a contradiction, so all diagonal entries of $U$ must be 1, so rref will be identity matrix.

(3) → (1): If $A$ is row equivalent to $I$, then there exists a sequence of elementary matrices $E_1,\dots ,E_k$ such that $\prod _{i=k}^1{E}_i=A$. Therefore, $A^{-1}=\prod _{k=1}^k{E}_i^{-1}$ (note reverse order), so $A$ is nonsingular.

Corrolary 1.4.3

The $n\times n$ system of equations $A\overrightarrow{x}=\overrightarrow{b}$ has a unique solution iff $A$ is nonsingular.

• $A$ is nonsingular, $A\overrightarrow{x}=\overrightarrow{b}$ can be rewritten as $\hat{x}=A^{-1}\overrightarrow{b}$
• Assume unique solution $\hat{x}$ exists. If $A$ were singular then homogeneous system $A\overrightarrow{x}=\overrightarrow{0}$ would have a nonzero solution $\overrightarrow{y}\ne \overrightarrow{0}$ (by Theorem 1.4.2). If this were the case, ... there would be another solution, which is a contradiction.