01 - Linear System

Linear System (of equations)

Set of $m$ simultaneous equations in $n$ real variables $x_1,x_2,\cdots ,x_n$ that can be written as

$$\begin{array}{rlrlrlrl}{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;\\ & ⋮& & ⋮& & ⋮& & \\ a_{m1}& x_1+a_{m2}& & x_2+\cdots +a_{mn}& & x_n=& & b_m;\end{array}$$

with $a_{ij},b_i\in \mathbb{R}$

Matrix Representation of a Linear System

$$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right),\mathbf{b}=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right),\mathbf{x}=\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right)$$

So above can be written as

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

Augmented Matrix

$$(A\mid \mathbf{b})=\left(\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}& b_m\end{array}\right)$$

Linear Systems can have none, one or $\infty$ solutions

Terminology

• Solution: Any vector $(x_1,x_2,\cdots ,x_n)$ that satisfies the Linear System
• General Solution: Any description of all the solutions of the system
• Consistent - If there are one or more solutions
• Augmented Matrix - Written as $(A\mid \mathbf{b})$

---

Consistent Linear System lemma

$$(A\mid )\text{ is consistent}⟺\mathrm{Col}(A\mid \mathbf{b})=\mathrm{Col}(A)$$

Proof

Suppose that $A$ is a $m\times n$ matrix and denote the columns of $A$ as ${\mathbf{c}}_1,{\mathbf{c}}_2,\cdots ,{\mathbf{c}}_n$
Then

$$\begin{array}{rl}(A\mid \mathbf{b})\text{ is consistent }& ⟺A\mathbf{x}=\mathbf{b}\text{ for some }\mathbf{x}\in {\mathbf{F}}_{\mathrm{col}}^n\\ & ⟺x_1{\mathbf{c}}_1+\cdots +x_n{\mathbf{c}}_n=\mathbf{b}\text{ for some }\mathbf{x}\in {\mathbf{F}}_{\mathrm{col}}^n\\ & ⟺\mathbf{b}\in \mathrm{Col}(A)\\ & ⟺\mathrm{Col}(A\mid \mathbf{b})=\mathrm{Col}(A)\end{array}$$