Systems Of Equations

Solution Space

Given a field F, and a system of m equations and n variables,

$$\begin{array}{rl}{a}_{11}{x}_1+a_{12}{x}_2+...a_{1n}{x}_n& =y_1\\ & ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+...+a_{mn}{x}_n& =y_m\end{array}$$

A solution space is the set of all n-tuple $(b_1,...,b_n)\in F^n$ such that it solves all of the equations. Can be either of the three cases

1. The system is not solvable Then there are no solutions to the system,
2. The system is solvable Then there are either 1 or infinitely many solutions (cannot have any other finite number of solutions other than 1, think about lines intersecting)

Back Substitution

A method of solving a system of equations where the equations are shaped like a triangle, with no 0’s on the diagonals!

Example

$$\begin{array}{rl}{a}_{11}{x}_1+a_{12}{x}_2+...+a_{1(n-1)}{x}_{n-1}+a_{1n}{x}_n& =y_1\\ a_{22}{x}_2+...a_{2(n-1)}{x}_{n-1}+a_{2n}{x}_n& =y_2\\ & ⋮\\ a_{(m-1)(n-1)}{x}_{n-1}+a_{(m-1)n}{x}_n& =y_{m-1}\\ a_{mn}{x}_n& =y_m\\ \Updownarrow & \end{array}$$ $$\begin{array}{rl}{x}_1& =\frac{1}{a_{11}}(y_1-...)\\ & ⋮\\ x_{n-1}& =\frac{1}{a_{(n-1)(n-1)}}(y_{m-1}-\frac{y_m}{a_{mn}})\\ x_n& =\frac{1}{a_{mn}}{y}_m\end{array}$$

$a_{ii}\ne 0,i\in [n]$, OR WE GET DIVISION BY ZERO!

We assume that

Unique Solution

$$\begin{array}{rl}1x_1+x_2& =-2\\ 3x_2& =1\end{array}\Rightarrow x_2=\frac{1}{3}\Rightarrow 2x_1+\frac{1}{3}=-2\Rightarrow x_1=\frac{-2-1/3}{2}$$

Unique solution

$$\begin{array}{rl}{x}_1& =-7/6\\ x_2& =1/3\end{array}$$

Infinitely Many Solutions

$$\begin{array}{rl}0x_1+2x_2& =-2\\ 3x_2& =6\end{array}$$

Note, this system has Infinitely many solutions! $x_2=2\Rightarrow =0x_1=2\cdot 2=4\Rightarrow 0=0$ Hence, we can form a solution space $(c,2)$, where $c\in F$

Symbolic representation of systems of linear equations

We can represent any system in the following way : $A=(a_{ij})i\in [m],j\in [n],a_{ij}\in F$ $Ax=y,x=(x_1,...,x_n),y\in F^n$