Section02 The idea of Elimination

• example $$\begin{array}{ll} \textbf{before } \begin{array}{rrrr} x-2y & = & 11\\ 3x +2y & = &1 \end{array} \ \ \ \ \textbf{ after } \begin{array}{rrrr} x-2y & = & 11\\ 8y & = &8 \end{array} \end{array}$$

• upper triangular system $$\left[ \begin{matrix} t_{11} & t_{12} & t_{13} & \cdots & t_{1n} \\ 0 & t_{22} & t_{23} & \cdots & t_{2n} \\ 0 & 0 & t_{33} & \cdots & t_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & t_{nn}\\ \end{matrix} \right]$$

• Pivot and Multiplier

  Pivot

  first nonzero in the row that does the elimination

  Multiplier

  (entry to eliminate) devided by (pivot)

  • the pivot are on the diagonal of the triangle after elemination.

Breakdown of Elimination

Permanent failure with no solution.

• example $$\begin{array}{ll} \textbf{original matrix } & \begin{array}{rrrr} x - 2y & = & 1\\ 3x - 6y & = & 11\\ \end{array} \\ \textbf{matrix after elimination } & \begin{array}{rrrr} x - 2y & = & 1\\ 0y & = & 8\\ \end{array} \end{array}$$

perspective of rows

• two lines in xy plane are parallel. => there isn't intersectional point between two lines.

perspective of columns

• two arrows with the sample direction, but the point(1,11) is not on this line.

Failure with infinitely many solutions.

• example $$\begin{array}{ll} \textbf{original matrix } & \begin{array}{rrrr} x - 2y & = & 1\\ 3x - 6y & = & 3\\ \end{array} \\ \textbf{matrix after elimination } & \begin{array}{rrrr} x - 2y & = & 1 \\ 0y & = & 0 \\ \end{array} \end{array}$$

perspective of rows

• two lines in xy plane is the same line. => all points on this line is the solutions of equations.

perspective of columns

• two arrows with the sample direction, and the point(1,3) is on this line.

Elimination in Julia

using LinearAlgebra
L,U = lu(::matrix);

Steps of Elimination

1. Use the first equations (first row) to create zeros below the first pivot.
2. Use the second equations (second row) to create zeros below the second pivot.
3. to $n$. Keep going to find all $n$ pivots and the upper triangular $\boldsymbol{U}$

Properties from Exercise

1. Linear Combination $$\text{If } \boldsymbol{Ax} = \boldsymbol{b} \text{'s solution is } \boldsymbol{c}\\ \text{then } \boldsymbol{Ax} = n \cdot \boldsymbol{b} \text{'s solution is } n \cdot \boldsymbol{c}\\ $$

2. Equal rows and Equal columns

   • $\boldsymbol{A}$ is a $3 \times 3$ matrix.
   • When $\text{row}_{1} = \text{row}_{2}$ the $\text{row}_{3}$ has no pivot.
   • When $\text{col}_{1} = \text{col}_{2}$ the $\text{col}_{2}$ has no pivot.