MATH 110 - Day 7

2024-09-18 17:33:27 -0400 EDT

Systems of Linear Equations

Definition: A linear equation is the variable x_1, x_2, x_3, is the equation of the term:
$⊛ : a_{1} x_{1} + a_{2} x_{2} + a_{3} x_{3} \dots a_{n} x_{n} = d$

The solution to $⊛$ is a vector

Let

$⊚ : (\begin{array}{rrrrrrrr} a_{(1, 1)} x_{1} + a_{(1, 2)} x_{2} + a_{(1, 3)} x_{3} \dots a_{(1, n)} x_{n} = d_{1} \\ a_{(2, 1)} x_{1} + a_{(2, 2)} x_{2} + a_{(2, 3)} x_{3} \dots a_{(2, n)} x_{n} = d_{2} \\ \dots \\ a_{(n, 1)} x_{1} + a_{(n, 2)} x_{2} + a_{(n, 3)} x_{3} \dots a_{(n, n)} x_{n} = d_{n} \end{array})$

be a system of $m$ linear equations in $n$ variable $x_{1}, x_{2} \dots x_{n}$ where:
$a_{i}, 1 \leq i \leq m$
$d_{i}, 1 \leq i \leq m$
$j, 1 \leq j \leq n$

How can we find solutions that exist? $\to$ Goal: use an algorithm

Algorithm: Infinite sequence of mathematically rigorous instructions to solve a particular problems

Matrices: Let $m, n \in N$ fixed once and for all. An $m \times n$ matrix $A$ is a rectangular array of $m n$ real numbers arranged in such a way that there are $m$ rows and $n$ columns:

$A = [\begin{array}{rrrr} a_{(1, 1)} & a_{(1, 2)} & a_{(1, 3)} & \dots & a_{(1, n)} \\ a_{(2, 1)} & a_{(2, 2)} & a_{(2, 3)} & \dots & a_{(2, n)} \\ a_{(3, 1)} & a_{(3, 2)} & a_{(3, 3)} & \dots & a_{(3, n)} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{(m, 1)} & a_{(m, 2)} & a_{(m, 3)} & \dots & a_{(m, n)} \end{array}]$

Given a system of linear equations in $n$ variables:

the $m \times n$ matrix $A$ written above is called a coefficient matrix of $⊚$
the $m \times n$ matrix is called an augmented

Example:
$2 c + 5 s - 13 p = 1000$
$3 c - 9 s + 3 p = 0$
$- 5 c - 9 s + 3 p = - 600$
$\Leftrightarrow$
$[\begin{array}{rrrrr} 2 & 5 & - 13 & | & 1000 \\ 3 & - 9 & 3 & | & 0 \\ - 5 & 6 & 8 & | & - 600 \end{array}]$

An algorithm for solving linear equations

input: a system of linear equations $⊚$

From augmented matrix of $⊚$
Perform elementary row operations (EPOs) to get good form
Solve (substitution and elimination)

EPOs

Switching any 2 rows
Multiplying a row by $c \in R, c \neq 0$
Add scaler multiple of a row to another row

what is good form?

good form := Reduced Row Echelon Form (RREF)
this is:

in each row, left to right the first nonzero number is 1
if an entire row is 0s, this row is at the bottom
if a column contains a leading 1 of in the first row, all other entires in the column and row must be zero.
the leading ones form a diagonal

Theorem: any matrix can be put into RREF by a finite number of elementary row operations