SYSTEMS of LINEAR EQUATIONS

Background: Applications

• Leontief Models in Economics
• Electric Circuits

Systems of Linear Equations

$$\begin{array}{c} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n =... ..._{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n = b_m \\ \end{array}$$

Solution Types

• None - inconsistent system
• Only one (unique) - consistent system
• Infinitely many - consistent system

Matrix Notation

$$\stackrel {\left[ \begin{array}{cccc} a_{11} & a_{12} & \ldo... ... & b_m \\ \end{array}\right]} {\mbox{{\bf augmented matrix}}}$$

Solution Method:

Use elementary row operations to simplify.

$$\left. \begin{array}{l} \mbox{Replacement}\\ \mbox{Interchan... ...w \mbox{\bf Triangular system}\Rightarrow \mbox{\bf Solution}.$$

Examples

ROW REDUCTION and ECHELON FORMS

Echelon Forms:

$\bullet =$ nonzero entry, * = any number

$$\rule{0pt}{5pt}\hspace{-1cm} A {{ \atop \sim} \atop {\mbox{{\... ...\\ 0 & 0 & 0 & 0 & 0 & \ldots & 0 & 1 & * \end{array}\right]}$$

Examples

Uniqueness:

$$\rule{0pt}{5pt}\hspace{-2cm} A {{ \atop \sim} \atop {\mbox{{\... ... \atop {\mbox{{\small row ops}}} } \mbox{\ unique reduced\ } U$$

Pivots:

• Pivot Position corresponds to a leading nonzero entry in a row of U
• Pivot Column contains a pivot position

Row Reduction Algorithm:

1.

Start with left-most nonzero column

2.

Interchange rows to find nonzero pivot

3.

Use row replacement ops to create zeros below pivot

4.

Repeat steps 1, 2, 3 on submatrix below current pivot row

Solution of Linear Systems:

• Basic variables correspond to pivot columns
• Free variables correspond to non pivot columns
• Backsubstitution determines x_n first, then $x_{n-1}, \ldots, x_1$.

Existence and Uniqueness:

Consistent systems

• If and only if rightmost column of augmented U is not a pivot column
• Could have a unique solution (no free x's) or $\infty$ solutions