Linear Algebra - Systems of Linear Equations

Systems of Linear Equations

General System

$a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1$ $a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2$ … $a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m$

Matrix form: $Ax = b$

Solution Methods

Gaussian Elimination: Convert to row echelon form.

• Swap rows
• Multiply row by nonzero constant
• Add multiple of one row to another

Row Echelon Form (REF):

• Leading entries move right as you go down
• Zero rows at bottom

Reduced Row Echelon Form (RREF):

• Leading entries are 1 (called pivot)
• Pivot columns have single 1, others 0

Solution Structure

For system $Ax = b$:

Number of solutions:

• If $\text{rank}(A) = \text{rank}([A|b]) = n$: unique solution
• If $\text{rank}(A) = \text{rank}([A|b]) < n$: infinitely many ($n$ - rank free variables)
• If $\text{rank}(A) < \text{rank}([A|b])$: no solution

Homogeneous system $Ax = 0$:

• Always has solution (trivial $x = 0$)
• If $\det(A) \neq 0$: only trivial solution
• If $\det(A) = 0$: infinitely many solutions

Linear Dependence

Vectors $v_1, \dots, v_k$ are linearly dependent if there exist scalars (not all zero) such that $c_1v_1 + \dots + c_kv_k = 0$.

Otherwise: linearly independent.

Check: Form matrix with columns as vectors. Linearly independent $\iff$ columns are pivot columns $\iff$ null space has only zero vector.