System of Linear Equations Notes

System of Linear Equations

1.1 Definition of Equation

An equation is a statement of equality containing one or more variables.
Solving the equation means determining which values of the variables make the equality true.
Variables are called unknowns, and the values satisfying the equality are called solutions.
General form: $ax + by = c$
- Expressions on the left and right-hand sides are separated by an equal sign "=".

1.2 Linear and Non-linear Equations

Linear Equation: Unknown variables occur only to the first power and are multiplied by constants.
- Example: $ax + b = 0$ , where $a$ and $b$ are real numbers.
Non-linear Equation: Involve products of unknown variables or variables as arguments of trigonometric, logarithmic, exponential, or other functions.
- Examples: $y = 2x - 6$ , $y = 6x^3 + 7x + 3$ , $z = 6xy + 5x$ , $y = e^x$ , $y = \sin x$

1.3 System of 2 Linear Equations

One-dimensional real space $\mathbb{R}$
- If $a \neq 0$ in the linear equation $ax + b = 0$ , there is a unique solution: $x = -\frac{b}{a}$ .
Two-dimensional real space $\mathbb{R}^2$
- Consider the system: $\begin{cases} ax + by = p \ cx + dy = q \end{cases}$ , where $a, b, c, d, p$ , and $q$ are real numbers.

Geometric Interpretation

The equations $ax + by = p$ and $cx + dy = q$ represent lines in the $xy$ -plane.
The solution to the system is the intersection point(s) of these lines.
- Consistent System: At least one solution exists.
  - Exactly One Solution: The lines intersect at one point.
  - Infinitely Many Solutions: The lines coincide.
- Inconsistent System: No solution exists.
  - No Solution: The lines are parallel.

Algebraic Methods

Substitution
- Given the system:
  - $ax + by = p$ (1)
  - $cx + dy = q$ (2)
- Rearrange (1) to express $y$ in terms of $x$ : $y = -\frac{a}{b}x + \frac{p}{b}$ (3)
- Substitute (3) into (2).
- If $ad - bc \neq 0$ , there is a unique solution (consistent).
- If $ad - bc = 0$ and $pd - bq = 0$ , there are infinitely many solutions (consistent).
- If $ad - bc = 0$ and $pd - bq \neq 0$ , there is no solution (inconsistent).
Gaussian Elimination
- Based on elementary row operations:
 - (Interchange): Swap two equations.
 - (Scaling): Multiply an equation by a non-zero constant.
 - (Replacement): Add a multiple of one equation to another.
- Example:
 - $\begin{cases} 3x1 + x2 = 4 \ 6x1 + 5x2 = 2 \end{cases} \longrightarrow \begin{cases} 6x1 + 2x2 = 8 \ 6x1 + 5x2 = 2 \end{cases} \longrightarrow \begin{cases} -3x2 = 6 \ 6x1 + 5x2 = 2 \end{cases} \longrightarrow \begin{cases} x2 = -2 \ x_1 = 2 \end{cases}$

1.4 System of 3 Linear Equations

How to find three unknowns from three linear equations.

1.5 General System of Linear Equations

An equation in $n$ variables $x1, x2, …, x_n$ can be written in the form:
- $a1x1 + a2x2 + … + a{n-1}x{n-1} + anxn = b$
- where $a1, a2, …, a_n$ and $b$ are real or complex numbers.
- The constants $a_j$ are coefficients, and $b$ is the right-hand side.
A system of $m$ linear equations in $n$ variables:
- $\begin{cases} a{11}x1 + a{12}x2 + … + a{1n}xn = b1 \ a{21}x1 + a{22}x2 + … + a{2n}xn = b2 \ … \ a{m1}x1 + a{m2}x2 + … + a{mn}xn = b_m \end{cases}$
- $bi$ and $a{ij}$ are real or complex numbers.
- $m$ and $n$ are positive integers.

Cases:

Case m = n (same number of equations and variables)
- High chance of having one set of solutions.
Case m > n (more equations than variables)
- High chance of having no solutions.
Case m < n (fewer equations than variables)
- High chance of having many solutions.
- $x{m+1}$ to $xn$ can be free variables.

Questions:

How to solve the system when $m$ and $n$ are large?
How to determine if the system has one solution, no solution, or multiple solutions?

1.6 Matrix Notation

Example:
- System: $\begin{cases} 3x1 + x2 = 4 \ 6x1 + 5x2 = 2 \end{cases}$
- Vector form: $\begin{bmatrix} 3 \ 6 \end{bmatrix} x1 + \begin{bmatrix} 1 \ 5 \end{bmatrix} x2 = \begin{bmatrix} 4 \ 2 \end{bmatrix}$
- Matrix form: $\begin{bmatrix} 3 & 1 \ 6 & 5 \end{bmatrix} \begin{bmatrix} x1 \ x2 \end{bmatrix} = \begin{bmatrix} 4 \ 2 \end{bmatrix}$
- Augmented matrix form: $\begin{bmatrix} 3 & 1 & 4 \ 6 & 5 & 2 \end{bmatrix}$
 - The size of a matrix is given by the number of rows and columns (e.g., a 3 × 4 matrix has 3 rows and 4 columns).

1.7 Solving a Linear System

Example:

$\begin{aligned} x1 - 2x2 + x3 &= 0 \ 5x1 - 5x3 &= 10 \ 2x2 - 8x_3 &= 8 \end{aligned}$

Augmented Matrix:

$\begin{bmatrix} 1 & -2 & 1 & 0 \ 5 & 0 & -5 & 10 \ 0 & 2 & -8 & 8 \end{bmatrix}$

Row Operations to Eliminate $x_1$ from equations 2 and 3:

$\begin{bmatrix} 1 & -2 & 1 & 0 \ 0 & 1 & -4 & 4 \ 0 & 0 & 1 & -1 \end{bmatrix}$

Back Substitution to Solve for the Variables:

$\begin{aligned} x1 &= 1 \ x2 &= 0 \ x_3 &= -1 \end{aligned}$

1.8 Existence and Uniqueness Questions

Two Fundamental Questions:
- Is the system consistent (does at least one solution exist)?
- If a solution exists, is it the only one (is the solution unique)?

Existence and Uniqueness Theorem

A linear system is consistent if and only if an echelon form of the augmented matrix has no row of the form:
- $\begin{bmatrix} 0 & … & 0 & b \end{bmatrix}$ , with $b$ nonzero.
If a linear system is consistent, then the solution set contains either:
- (i) a unique solution when there are no free variables, or
- (ii) infinitely many solutions when there is at least one free variable.

Numerical Note

In real-world problems, computers solve systems of linear equations using elimination algorithms.
Floating-point arithmetic represents numbers as decimals with a finite number of digits, leading to round-off errors.
Inaccuracies seldom cause problems, but numerical notes warn of potential issues.

2.1 Echelon ("steplike") Forms

Triangular form is a special case of echelon form.
A leading entry of a row refers to the leftmost nonzero entry.
Any nonzero matrix may be row-reduced (by elementary row operations) into more than one matrix in echelon form, using different sequences of row operations. However, the reduced echelon form for a matrix is unique.

2.2 The Row Reduction Algorithm

Write the augmented matrix of the system.
Use row reduction to obtain an equivalent augmented matrix in echelon form.
- Decide whether the system is consistent. If there is no solution, stop; otherwise, go to the next step.
Continue row reduction to obtain the reduced echelon form.
Write the system of equations corresponding to the matrix obtained in step 3.
Rewrite each nonzero equation from step 4 so that its one basic variable is expressed in terms of any free variables appearing in the equation.

Elementary row operations:
- (Interchange): Swapping two rows.
- (Scaling): Multiplying all entries in a row by a non-zero constant.
- (Replacement): Replacing one row by the sum of itself and a multiple of another row.

2.3 Existence and Uniqueness Theorem

A linear system is consistent if and only if an echelon form of the augmented matrix has no row of the form [0…0 b] with b nonzero.
If a linear system is consistent, then the solution set contains either:
- (i) a unique solution, when there are no free variables, or
- (ii) infinitely many solutions, when there is at least one free variable.

2.4 An Example

To find the solution of the system of linear equations with the following augmented matrix representation:

\begin{pmatrix} 1 & 4 & 5 & -9 & -7 \ 0 & 2 & 4 & -6 & -6 \ 0 & 5 & 10 & -15 & -15\0&-3&-6&4&9 \end{pmatrix}

After row operations the matrix transforms to:

\begin{pmatrix} 1 & 4 & 5 & -9 & -7 \ 0 & 2 & 4 & -6 & -6 \ 0 & 0 & 0 & 0 & 0\0&0&0&0&0 \end{pmatrix}

And the equations are given as:
$\begin{cases} x1 + 4x2 + 5x3 -9x4 = -7 \ 2x2 + 4x3 -6x_4 = -6 \ 0 = 0 \ 0 = 0 \end{cases}$
Explicit Equations
From the equations (2) and (3), we have $x2 = -2x3 - 3$
From the equations (1), (2) and (3), we have $x1 = \frac{3}{5}x3 + \frac{5}{4}$
There is no constraint on $x_3$ , so it can be treated as a free variable.
We have more than one solution.
The solution can be written as:

$x4 = 0$ $x2 = -2x3 - 3$ $x1 = \frac{3}{5}x_3 + \frac{5}{4}$

3.1 A Simple Economy

Suppose an economy consists of the Coal, Electric (power), Steel, and the output of each sector is distributed among the various sectors.
Denote the prices of the total annual outputs of the Coal, Electric, and Steel sectors by pC, pE, and pS, respectively.
If possible, find equilibrium prices that make each sector’s income match its expenditures.
The total expenses used by Coal company are $0.0pC + 0.4pE + 0.6p_S$ .
The total value produced by Coal company is $p_C$ .
Therefore, we have $pC = 0.0pC + 0.4pE + 0.6pS$ .
The total expenses used by Electric company are $0.6pC + 0.1 pE + 0.2p_S$
The total value produced by Electric company is $p_E$
Therefore we have $pE = 0.6pC + 0.1 pE + 0.2pS$
The total expenses used by Steel company are $0.4pC+0.5pE + 0.2p_S$
The total value produced by Steel company is $p_S$
Therefore we have $pS = 0.4pC+0.5pE + 0.2pS$
$\begin{cases} -0.6pC + 0.9pE - 0.2pS = 0 \ -0.4pC - 0.5pE + 0.8pS = 0 \end{cases}$
The general solution is pc = .94ps, PE = .85ps, and ps is free. The equilibrium price vector for the economy has the form

3.2 Traffic flow

Suppose the vehicles per hour over several streets are given on the map. We want to determine the unknowns x1, x2, x3, x4 , x5.
Write equations that describe the flow, and then find the general solution of the system.
We make use of the fact that at each intersection, the traffic flow in must be equal to the flow out.
Putting all the equations together, we have

$\begin{cases} x1 + x2 = 800 \ x2 - x3 + x4 = 300 \ x1 + x5 = 600 \ x4 + x5 = 400 \ x3 = 500 \end{cases}$

3.3 Balancing chemical equation

$\begin{aligned} x1(C3H8) + x2(O2) \rightarrow x3(CO2) + x4(H_2O) \end{aligned}$

We want to determine x1, x2, x3, x4 such that the number of atoms of each type will be the same on both sides.

For carbon C, we have 3x1 = x3
For hydrogen H, we have 8x1 = 2x4
For oxygen O, we have 2x2 = 2x3+x4
We have a system of linear equations

$\begin{cases} 3x1 + 0x2 - x3 + 0x4 = 0 \ 8x1 + 0x2 + 0x3 - 2x4 = 0 \ 0x1 + 2x2 - 2x3 - x4 = 0 \end{cases}$

Solution in mathematics

$x1 = (1/ 4) x4$
$x2 = (5/ 4) x4$
$x3 = (3/ 4) x4$

The numbers of atoms of C, H and O for this chemical reaction have to be integers.
So, x1, x2, x3, x4 have to be integer, the minimum x4 = 4. so that x3 = 3; x2 = 5; x1 = 1.
Solution in Chemistry

$\begin{aligned} C3H8 + 5O2 \rightarrow 3CO2 + 4H_2O \end{aligned}$