MATH 323 Lecture 5

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

Elementary Matrices

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

For a non-singular, invertible $m\times m$ matrix $M$, $M\,A\,{\vec {x}}=M\,{\vec {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'$:
   • $EA$ adds multiple of row $i$ to row $i'$
   • $AE$ adds multiple of column $i$ to column $i'$

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\neq 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},\ldots ,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|{\vec {b}})$ and $(B|{\vec {c}})$ are row equivalent iff $A{\vec {x}}={\vec {b}}$ and $B{\vec {x}}={\vec {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{\vec {x}}={\vec {0}}$ has only trivial solution ${\vec {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{\vec {x}}={\vec {0}}$. So $A{\hat {x}}={\vec {0}}$ can become $A^{-1}A{\hat {x}}=A^{-1}{\vec {0}}$. $I{\hat {x}}={\vec {0}}$, so ${\hat {x}}={\vec {0}}$

(2) → (3): Rewrite $A{\vec {x}}={\vec {0}}$ in row echelon form as $U{\vec {x}}={\vec {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},\ldots ,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{\vec {x}}={\vec {b}}$ has a unique solution iff $A$ is nonsingular.

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