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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\vec{x} = \vec{0}} . So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\hat{x} = \vec{0}} can become Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^{-1}A\hat{x} = A^{-1}\vec{0}} . $I{\hat {x}}={\vec {0}}$, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{x} = \vec{0}}

(2) → (3): Rewrite Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\vec{x} = \vec{0}} in row echelon form as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U\vec{x} = \vec{0}} . If one diagonal entry of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} , then there exists a sequence of elementary matrices Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_1,\ldots,E_k} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{i=k}^1 E_i = A} . Therefore, $A^{-1}=\prod _{k=1}^{k}E_{i}^{-1}$ (note reverse order), so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is nonsingular.

Corrolary 1.4.3

The Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \times n} system of equations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\vec{x} = \vec{b}} has a unique solution iff Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is nonsingular.

• $A$ is nonsingular, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\vec{x} = \vec{b}} can be rewritten as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{x} = A^{-1}\vec{b}}
• Assume unique solution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{x}} exists. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} were singular then homogeneous system $A{\vec {x}}={\vec {0}}$ would have a nonzero solution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{y} \ne \vec{0}} (by Theorem 1.4.2). If this were the case, ... there would be another solution, which is a contradiction.