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:
$ \circledast: a_1x_1 + a_2x_2 + a_3x_3 \ … \ a_nx_n =d$

The solution to $\circledast$ is a vector

Let

$$ \circledcirc: \left( \begin{array}{rrrrrrrr} a_{(1,1)}x_1 + a_{(1,2)}x_2 + a_{(1,3)}x_3 \ … \ a_{(1,n)}x_n = d_1 \\ a_{(2,1)}x_1 + a_{(2,2)}x_2 + a_{(2,3)}x_3 \ … \ a_{(2,n)}x_n = d_2 \\ … \\ a_{(n,1)}x_1 + a_{(n,2)}x_2 + a_{(n,3)}x_3 \ … \ a_{(n,n)}x_n = d_n \end{array} \right) $$

be a system of $m$ linear equations in $n$ variable $x_1, x_2 … 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? $\rightarrow$ Goal: use an algorithm

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

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

$$ A = \left[ {\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)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{(m,1)} & a_{(m,2)} & a_{(m,3)} & \dots & a_{(m,n)} \end{array}} \right] $$

---

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

1. the $m \times n$ matrix $A$ written above is called a coefficient matrix of $ \circledcirc $
2. the $m \times n$ matrix is called an augmented

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

---

An algorithm for solving linear equations

input: a system of linear equations $\circledcirc$

1. From augmented matrix of $\circledcirc$
2. Perform elementary row operations (EPOs) to get good form
3. Solve (substitution and elimination)

EPOs

• Switching any 2 rows
• Multiplying a row by $ c \in \mathbb{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:

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

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