Linear Simultaneous Equations

The Problem

Solve the system:

$\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \end{cases}$

In matrix form: $A\mathbf{x} = \mathbf{b}$.

---

Gaussian Elimination

Transform to row echelon form:

$\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & | & b_1 \\ 0 & a'_{22} & \cdots & a'_{2n} & | & b'_2 \\ \vdots & & \ddots & & | & \vdots \\ 0 & 0 & \cdots & a'_{nk} & | & b'_m \end{pmatrix}$

Row operations:

1. Swap rows
2. Multiply row by non-zero scalar
3. Add multiple of one row to another

---

Classification of Solutions

Case	Condition	Solutions
Unique	$\det(A) \neq 0$ (square)	Exactly one
Underdetermined	Rank < number of variables	Infinitely many
Overdetermined	Inconsistent equations	No solutions
Dependent equations	Rows linearly dependent	Redundant equations

---

Rank

The rank of $A$ is:

• Number of non-zero rows in row echelon form
• Number of linearly independent rows (or columns)
• Dimension of the image: $\text{rank}(A) = \dim(\text{im}(A))$

Rank theorem:

$\text{rank}(A) + \dim(\ker(A)) = n$

(for $m \times n$ matrix)

---

Example: $2 \times 2$ System

Solve: $\begin{cases} 2x + y = 5 \\ 3x + 2y = 8 \end{cases}$

Matrix form: $\begin{pmatrix} 2 & 1 \\ 3 & 2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 5 \\ 8 \end{pmatrix}$

Row operations: $[2\ 1\ |\ 5]$ $[3\ 2\ |\ 8]$ $\to$ subtract $\frac{3}{2}$ of row 1 from row 2: $[2\ 1\ |\ 5]$ $[0\ \frac{1}{2}\ |\ \frac{1}{2}]$ $\to$ back-substitute: $y = 1$, then $2x + 1 = 5$, so $x = 2$.

---

Cramer’s Rule

For $n \times n$ system with $\det(A) \neq 0$:

$x_i = \frac{\det(A_i)}{\det(A)}$

where $A_i$ is $A$ with column $i$ replaced by $\mathbf{b}$.

Impractical for large $n$ — use Gaussian elimination instead.

---

Homogeneous Systems

$A\mathbf{x} = \mathbf{0}$

• Always has trivial solution $\mathbf{x} = \mathbf{0}$
• Non-trivial solutions exist $\Leftrightarrow$ $\det(A) = 0$

---

Kernel and Image

Kernel: $\ker(A) = \{\mathbf{x} : A\mathbf{x} = \mathbf{0}\}$

Image: $\text{im}(A) = \{A\mathbf{x} : \mathbf{x} \in \mathbb{R}^n\}$

Fundamental theorem:

• $\ker(A)$ gives the “freedom” in solutions
• $\mathbf{b} \in \text{im}(A)$ is required for solution to exist

---

Why Linear Systems Matter

• Engineering: structures, circuits, control systems
• Economics: input-output models
• Statistics: regression (least squares)
• Physics: equilibrium problems, eigenvalue problems

Almost every quantitative problem involves solving linear systems at some stage.