Echelon Forms - Row Reduction Algorithms for Solving Systems of Linear Equations

EchelonForms.md

Game Mathematics

Linear Algebra

• Matrices

Writing Systems

$1x + 1y = 5$

$3x - 2y = 10$

The oldschool way of solving it would tell us that we should first zero out one of the values in order to eliminate it like the following:

//- multipling all elements of the first equation by two

$2*1x + 2*1y = 2*5$
$3x - 2y = 10$

//- adding both equation together in order to eliminate y

$2x + 2y = 10$
$3x - 2y = 10$

//- and solving the rest

$5x = 20$

$x = 4$

Then use the new found value to find the last one

$1x + 1y = 5$ would become $1 * 4 + 1y = 5$
Or
$3x - 2y = 10$ would become $3 * 4 - 2y = 10$

Solving any would bring us the y value of 1

---

To solve the same system we could use Coefficient Matrix We take only the coefficient and apply on a coefficient matrix

[[1,  1],
 [3, -2]]

A augmented matrix has the result on the third column

[[1,  1,  5],
 [3, -2, 10]]

to better visualize you can trace it

[[1,  1,|  5],
 [3, -2,| 10]]

Now we should apply the follow algorithm to zero out the value on Y column
$2*Row 1 + Row 2 => Row 1$
//- we use 2, in order to zero -2

$2*1 + 3 = 5$
$2*1 + -2 = 0$
$2*5 + 10 = 20$

[[5,  0,|  20],
 [3, -2,|  10]]

then simplify by dividing the first row by 5

[[1,  0,|  4],
 [3, -2,| 10]]

Then again for the second Row but with -3 to zero out the X column
$-3*Row 1 + row 2 => Row 2$
//- we use -3, in order to zero 3

$-3*1 + 3 = 0$
$-3*0 + -2 = -2$
$-3*4 + 10 = -2$

[[1,  0,|  4],
 [0, -2,| -2]]

Then simplify by dividing the second row by -2

  x   y    value
[[1,  0,|  4],
 [0,  1,|  1]]

---

Echelon Forms

Terminology

• Linear equation: An algebraic equation of the first degree, which means that the highest power is 1.
• System of linear equations: A collection of two or more linear equations using the same variables.
• Solution: A list of numbers that makes each equation of a system true when variables are substituted.
• Solution set: The set of all possible solutions to a system.

Types of Systems

• Inconsistent: Where we have no solutions, as an example, two parallel lines.
• Consistent:
  • One Solution: Two lines touching at a single point.
  • Infinity Many Solutions: Two identical lines overlapping each other.

Solving System of Linear Equations in Augmented Matrices Using Row Operations

• Row Operations:
  • Replacement: Replace one row by the sum of itself and a multiple of another row, i.e., (multiply * row1) + row2. Useful to seek the value 1 for a column.
  • Interchange: Swap two rows, used when there is a 0 in a not useful position, like the first row.
  • Scaling: Multiply a row by a non-zero constant, useful for halving or multiplying the entire row, seeking the value 1 for a column.

Existence and Uniqueness

A way of determining if the system is consistent (Does it have a solution?)
If so, determining if the solution is unique (Is there just one solution?)

If in any step we face the following:

[[1,  -3/2, 1|  1/2],
 [0,    1, -4|   8 ],
 [0,    0,  0|  15 ]]

Where all numbers in a row is 0, means that there is no solution for the system. Meaning it is an inconsistent system.

Row Reduction and Echelon Forms

Echelon

• All Non-Zero Rows are above all zero rows
• Each leading entry of a row is in a column to the right of the leading entry of the row above it.
• All entries in a column below a leading entry are zeros

[[2, 7, 6 3 | 2],
 [0, 1, 4 9 | 3],
 [0, 0, 0 1 | 6],
 [0, 0, 0 0 | 0]]

RREF - Reduced Row Echelon Form - all three above and:

• The leading entry in each non-zero row is 1
• Each leading 1 is the only non-zero entry in the column

[[1, 0, 0, 0 |  1],
 [0, 0, 1, 0 |  4],
 [0, 0, 0, 1 | -9],
 [0, 0, 0, 0 |  0]]

Pivot

• Pivot position - Corresponds to leading 1 in RREF
• Pivot column - the column that contains the Pivot
• Pivot - Non zero number in pivot position used to create zeros in row operations

   *       *           //Pivot Columns
[[_1_, 4,  2,  3 |  9],
 [ 0,  0, _2_  7 |  9],
 [ 0,  0,  0,  0 |  0]]

The row reduction algorithm

1. Begin at leftmost nonzero column which is a pivot column. Select a nonzero entry as a pivot and interchange if necessary, to move that entry into the pivot position (Row 1)

System of linear equations

x,  - 3x,,,        =  8
2x, + 2x,, + 9x,,, =  7
       x,, + 5x,,, = -2

Augmented Matrix

[[_1_, 0, -3 |  8],
 [ 2,  2,  9 |  7],
 [ 0,  1,  5 | -2]]

2. Use row operations to create zeros in all entries below the pivot
   • Row operation used: replacement $-2 * Row1 + Row2 => Row2$

[[ 1, 0, -3 |  8],
 [ 0, 2, 15 | -9],
 [ 0, 1,  5 | -2]]

3. Repeat this process for remaining rows, ignoring rows you've already applied the algorithm to.
   • Row operation used: scaling $0.5 * Row2 => Row2$

[[ 1, 0,  -3 |    8],
 [ 0, 1, 7.5 | -4.5],
 [ 0, 1,   5 |   -2]]

• Row operation used: replacement $-1 * row2 + row3 => row3$

[[ 1, 0,   -3 |    8],
 [ 0, 1,  7.5 | -4.5],
 [ 0, 0, -2.5 |  2.5]]

4. Ensure each pivot is a 1, using scaling as necessary.
   • Row operation used: scaling $-0.4 * Row3 => Row3$

[[ 1, 0,  -3 |    8],
 [ 0, 1, 7.5 | -4.5],
 [ 0, 0,   1 |   -1]]

5. Beginning with the rightmost pivot and working upwards and to the left, use row operations to create zeros above each pivot

[[ 1, 0,  -3 |    8],
 [ 0, 1, 7.5 | -4.5],
 [ 0, 0,   1 |   -1]]

• Row operation used: replacement $-7.5 * row3 + row2 => row2$

[[ 1, 0, -3 |  8],
 [ 0, 1,  0 |  3],
 [ 0, 0,  1 | -1]]

• Row operation used: replacement $3 * row3 + row1 => row1$

 [[ 1, 0, 0 |  5],
  [ 0, 1, 0 |  3],
  [ 0, 0, 1 | -1]]

Result: (5, 3, -1)

---

*Another way of visualization of operations would be using a code abstraction of the process
Using the script from the following gist:

const systemOfEquations = [
  '1x, +  0x,,,  -3x,,, =  8',
  '2x, +  2x,,  + 9x,,, =  7',
  '0x, +  1x,,  + 5x,,, = -2'
]

const augmentedMatrix = augmentedMatrixConversion(systemOfEquations)

const matrix = augmentedMatrixAndRowOperations(augmentedMatrix)
  .replacement({ floor: 1, target: 0, multiply: -2 })
  .scaling({ floor: 1, multiply: 0.5 })
  .replacement({ floor: 2, target: 1, multiply: -1 })
  .scaling({ floor: 2, multiply: -0.4 })
  .replacement({ floor: 1, target: 2, multiply: -7.5 })
  .replacement({ floor: 0, target: 2, multiply: 3 })
  .getMatrix()
  // .getResults()

console.log(matrix[0])
console.log(matrix[1])
console.log(matrix[2])
//results (5, 3, -1)