MATH 323 Lecture 2

« previous | Thursday, August 30, 2012 | next »

Systems of Equations as Matrices

${\begin{cases}x_{1}+2x_{2}+x_{3}=3\\3x_{1}-x_{2}-3x_{3}=-1\\2x_{1}+3x_{2}+x_{3}=4\end{cases}}$

Coefficient Matrix: ${\begin{bmatrix}1&2&1\\3&-1&-3\\2&3&1\end{bmatrix}}$

Augmented Matrix: $\left[{\begin{array}{ccc|c}1&2&1&3\\3&-1&-3&-1\\2&3&1&4\end{array}}\right]$

Elementary Row Operations

similar to Rules for Systems of Equations:

1. Interchange two rows
2. Multiply a row by a non-zero real number
3. Replace a row by its sum with a multiple of another row

Solving Systems with Augmented Matrices: Gaussian Elimination

Convert to row echelon form (analogous to Strict Triangular Form):

$\left[{\begin{array}{ccc|c}1&2&1&3\\3&-1&-3&-1\\2&3&1&4\end{array}}\right]$

Top row is called pivotal row since it is used to simplify the remaining rows
First non-zero entry in pivotal row is called pivotal element (should not be zero; better if 1)
Use pivotal row to make all elements in column below pivotal element zero
If at any point a pivot cannot be used for a certain column, skip it and continue with next column

$\left[{\begin{array}{ccc|c}1&2&1&3\\0&-7&-6&-10\\0&-1&-1&-2\end{array}}\right]$

Use 2^nd row as pivotal row and −7 as pivotal element.

$\left[{\begin{array}{ccc|c}1&2&1&3\\0&-7&-6&-10\\0&0&-{\frac {1}{7}}&-{\frac {4}{7}}\end{array}}\right]$

Simple Example

$\left[{\begin{array}{cccc|c}0&-1&-1&1&0\\1&1&1&1&6\\2&4&1&-2&-1\\3&1&-2&2&3\end{array}}\right]$

The first element in row 1 is 0, so it cannot be used as a pivotal row. Swap rows 1 and 2 since row 2 has a 1 in the first position.

$\left[{\begin{array}{cccc|c}1&1&1&1&6\\0&-1&-1&1&0\\2&4&1&-2&-1\\3&1&-2&2&3\end{array}}\right]\longrightarrow \left[{\begin{array}{cccc|c}1&1&1&1&6\\0&-1&-1&1&0\\0&2&-1&-4&-13\\0&-2&-5&-1&-15\end{array}}\right]\longrightarrow \left[{\begin{array}{cccc|c}1&1&1&1&6\\0&-1&-1&1&0\\0&0&-3&-2&-13\\0&0&-3&-3&-15\end{array}}\right]\longrightarrow \left[{\begin{array}{cccc|c}1&1&1&1&6\\0&-1&-1&1&0\\0&0&-3&-2&-13\\0&0&0&-1&-2\end{array}}\right]$

From the resulting matrix, we can use back substitution on strict triangular form to solve for all unknowns.

$(x_{1},x_{2},x_{3},x_{4})=(2,-1,3,2)$

Chapter 1.2: Row Echelon Form

A matrix is said to be in row echelon form if:

1. The first non-zero entry in each non-zero row is 1
2. If row $k$ does not consist entirely of zeroes, the number of leading zero entries in row $k+1$ is greater than the number of leading zero entries in row $k$
3. If there are rows whose entries are all zero, they are below the rows having non-zero entries

$\left[{\begin{array}{ccccc|c}1&1&1&1&1&1\\-1&-1&0&0&1&-1\\-2&-2&0&0&3&1\\0&0&1&1&3&-1\\1&1&2&2&4&1\end{array}}\right]\longrightarrow \left[{\begin{array}{ccccc|c}1&1&1&1&1&1\\0&0&1&1&2&0\\0&0&0&0&1&3\\0&0&0&0&0&-4\\0&0&0&0&0&-3\end{array}}\right]$

This matrix is not in strict triangular form, but the "staircase" made above all columns with zeroes and the fact that all pivot elements are 1 show that it is in row echelon form (similar to triangular form, but not strictly along diagonal.

This system is clearly inconsistent since the matrix states that $0=-4$ and $0=-3$

However, changing two numbers (bottom-right; answers), makes the system consistent:

$\left[{\begin{array}{ccccc|c}1&1&1&1&1&1\\-1&-1&0&0&1&-1\\-2&-2&0&0&3&1\\0&0&1&1&3&3\\1&1&2&2&4&4\end{array}}\right]\longrightarrow \left[{\begin{array}{ccccc|c}1&1&1&1&1&1\\0&0&1&1&2&0\\0&0&0&0&1&3\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right]$

The columns that have pivotal elements (1, 3, and 5) correspond to lead unknowns ($x_{1}$, $x_{3}$, and $x_{5}$) Columns that do not have pivotal elements (2 and 4) correspond to free unknowns ($x_{2}$ and $x_{4}$)

The system has strict triangular form with respect to lead unknowns, and the system has infinite solutions bounded by following equations: (move all free unknowns to the right, leaving the lead unknowns on the left)

${\begin{aligned}x_{1}+x_{3}+x_{5}&=1-x_{2}-x_{4}\\x_{3}+2x_{5}&=-x_{4}\\x_{5}&=3\end{aligned}}$

If we let $x_{2}=\alpha$ and $x_{4}=\beta$ for $\alpha ,\beta \in \mathbb {R}$, we can solve all unknowns in terms of two parameters:

$(x_{1},x_{2},x_{3},x_{4},x_{5})=(4-\alpha ,\alpha ,-\beta -6,\beta ,3)$

Overdetermined Systems

Systems of equations are defined by $m\times n$

• $m>n$ → overdetermined (typically inconsistent)
• $m<n$ → underdetermined (typically infinite solutions)
• $m=n$ → "normal" (typically one unique solution)

Reduced Row Echelon Form

An augmented matrix is said to be in reduced row echelon form if:

1. it is in row echelon form
2. the first non-zero entry in each row is the only non-zero entry in its column

How to achieve this? Consider the following system of equations and its augmented matrix:

${\begin{cases}-x_{1}+x_{2}-x_{3}+3x_{4}&=0\\3x_{1}+x_{2}-x_{3}-x_{4}&=0\\2x_{1}-x_{2}-2x_{3}-x_{4}&=0\end{cases}}\longrightarrow \left[{\begin{array}{cccc|c}-1&1&-1&3&0\\3&1&-1&-1&0\\2&-1&-2&-1&0\end{array}}\right]$

The resulting row echelon form matrix is

$\left[{\begin{array}{cccc|c}1&-1&1&-3&0\\0&1&-1&2&0\\0&0&1&-1&0\end{array}}\right]$

Now we use the bottom row as the pivotal row and use it to eliminate all values above its pivotal element:

$\left[{\begin{array}{cccc|c}1&-1&0&-2&0\\0&1&0&1&0\\0&0&1&-1&0\end{array}}\right]\longrightarrow \left[{\begin{array}{cccc|c}1&0&0&-1&0\\0&1&0&1&0\\0&0&1&-1&0\end{array}}\right]$

From this form, it is easy to find the solution set:

${\begin{aligned}x_{1}&=x_{4}\\x_{2}&=-x_{4}\\x_{3}&=x_{4}\\(x_{1},x_{2},x_{3})&=(\alpha ,-\alpha ,\alpha )\quad \alpha \in \mathbb {R} \end{aligned}}$