Solving Systems of Linear Equations Notes

Coordinate Geometry: Studied the properties of straight lines.
Straight Lines: Explored equations and characteristics of linear graphs.
Quadratics:
- Explored parabolas and their standard forms.
- Reviewed quadratic equations and methods for solving them.

Core Concept: A system of linear equations involves multiple equations with multiple variables (unknowns) that must be satisfied simultaneously.
Notation:
- Two variables: $a_1x + b_1y = c_1$ and $a_2x + b_2y = c_2$ .
- General form ( $m$ equations, $n$ variables): $a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m$ .
Applications:
- Circuits: Used to solve for voltages and currents using Kirchhoff's Laws.
- Web Search: The PageRank algorithm uses systems of linear equations to determine the importance of webpages.
- Polynomial Fit: Determining coefficients ( $a, b, c, d, e$ ) for a curve passing through specific data points like $(1.0, 0.5)$ , $(2.0, 2.0)$ , and $(3.0, 1.5)$ .

Setup: Consider 5 webpages labeled $x_0, x_1, x_2, x_3, x_4$ .
Principles of Importance:
- An arrow from Page A to Page B means "Page A gives importance to Page B."
- Each page divides its importance equally among its outgoing links.
Mathematical Representation:
- $x_0 = \frac{x_3}{3}$ (Page 0 receives $\frac{1}{3}$ of Page 3's importance).
- $x_1 = x_0 + \frac{x_3}{3}$ (Page 1 receives all of Page 0's importance and $\frac{1}{3}$ of Page 3's).
- $x_2 = \frac{x_1}{2}$ (Page 2 receives half of Page 1's importance).
- $x_3 = \frac{x_1}{2} + \frac{x_2}{2} + x_4$ .
- $x_4 = \frac{x_2}{2} + \frac{x_3}{3}$ .
System Matrix: These equations are rearranged to equal zero to form a matrix for solving (e.g., $-1x_0 + 0x_1 + 0x_2 + \frac{1}{3}x_3 + 0x_4 = 0$ ).

Standard Form:
- $a_1x + b_1y = c_1$
- $a_2x + b_2y = c_2$
Views of the Problem:
1. Graphical View: Each equation represents a straight line. The solution is the point of intersection.
2. Algebraic View: Using the elimination method to isolate one variable.
3. Matrix-Vector View: A prelude to linear algebra where coefficients are organized in a grid.
Types of Solutions (Graphical):
1. Intersect at one point: Exactly 1 solution (Lines have different slopes).
2. Identical lines: Infinitely many solutions (Lines are the same; equations are multiples of each other).
3. Parallel lines: No solution (Lines have the same slope but different intercepts; they never intersect).

Equation: $ax + by = c$
Isolation of y: $y = (\frac{-a}{b})x + \frac{c}{b}$
Solution Set: All points on the line. The general solution can be written as $(u, (\frac{-a}{b})u + \frac{c}{b})$ , where $u \in \mathbb{R}$ .
Vector Notation: $\begin{pmatrix} x_0 \\ y_0 \end{pmatrix} = u \begin{pmatrix} 1 \\ -a/b \end{pmatrix} + \begin{pmatrix} 0 \\ c/b \end{pmatrix}$
- Horizontal vector logic: $\text{All solutions} = \text{One specific solution} + \text{Line through origin parallel to original line}$ .
Example Problem: For $3y + 4x = 15$ :
- Solve for $y$ : $y = \frac{-4}{3}x + 5$ .
- If $x = u$ , points are $(u, \frac{15 - 4u}{3})$ . If $y = u$ , points are $(\frac{15 - 3u}{4}, u)$ .
- The point $(0, 5)$ is a solution ( $3(5) + 4(0) = 15$ ).

Form:
- $a_{11}x_1 + a_{12}x_2 = b_1$
- $a_{21}x_1 + a_{22}x_2 = b_2$
- $a_{31}x_1 + a_{32}x_2 = b_3$
Method: Eliminate $x_1$ from the second and third equations using the first equation. This results in a system of two equations for $x_2$ . If a consistent $x_2$ exists, back-substitute to find $x_1$ .

Scenario: Since there are more unknowns ( $n=3$ ) than equations ( $m=2$ ), the system usually has a free variable.
Method:
1. Eliminate $x_1$ from the second equation.
2. Treat one variable (e.g., $x_3$ ) as a constant or parameter $u$ .
3. Solve the remaining $2 \times 2$ system for $x_1$ and $x_2$ in terms of $u$ .
4. The final result expresses the variables as a vector: $\mathbf{x} = \mathbf{p} + u\mathbf{v}$ .

Form: Standard structure for a unique solution.
Method: Perform Gaussian elimination to transform the rectangular coefficient matrix into a Triangular Matrix (or Row Echelon Form).
- Zeros should appear below the diagonal.
- Pivots: The diagonal elements (should be non-zero to proceed easily).

Augmented Matrix: Combining coefficients and constants into one grid: $[A | b]$ .
Row Operations:
- Subtracting a multiple of one row from another: $R_2 \leftarrow R_2 - (\frac{a_{21}}{a_{11}})R_1$ .
Back-substitution: Once the matrix is triangular (e.g., bottom row is $0x_1 + 0x_2 + a_{33}x_3 = b_3$ ), solve for the last variable and work upward to find the others.

Row Echelon Form (REF): Result of elimination.
Rank ( $r$ ): The number of non-zero rows (pivots) in REF.
Outcomes:
1. No Solution: If the elimination results in a row like [0 \dots 0 | \b_k] where \b_k \neq 0 (contradiction).
2. Unique Solution: Occurs when $r = n$ (rank equals the number of variables) and no contradictions exist.
3. Infinitely Many Solutions: Occurs when $r < n$ and no contradictions exist. There are $n - r$ free variables.

Exercise 1: $x_1 + 2x_2 + 3x_3 = 4$ and $5x_1 + 6x_2 + 7x_3 = 8$ .
- Row Op: $R_2 - 5R_1 \rightarrow -4x_2 - 8x_3 = -12 \implies x_2 + 2x_3 = 3$ .
- Let $x_3 = u$ , then $x_2 = 3 - 2u$ and $x_1 = 4 - 2(3-2u) - 3u = -2 + u$ .
- Vector Form: $\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} -2 \\ 3 \\ 0 \end{pmatrix} + u \begin{pmatrix} 1 \\ -2 \\ 1 \end{pmatrix}$ .
Exercise 2: Checking unique/infinite solutions for parameter $k$ and $d$ .
- Equations: $8x_1 + 12x_2 = 24$ and $-6x_1 + kx_2 = d$ .
- The first simplifies to $2x_1 + 3x_2 = 6$ .
- By comparison, if $k = -9$ and $d = -18$ , the second equation is just $-3 \times (2x_1 + 3x_2 = 6)$ , leading to infinitely many solutions.

Pivot: The first non-zero element in a row used to eliminate elements below it.
Triangular Matrix: A matrix where all elements below the diagonal are zero, making it "easy to solve" via back-substitution.
LHS (Left Hand Side) and RHS (Right Hand Side): Terms used to verify if a candidate solution $(x_0, y_0)$ satisfies the original equation.