8a_GJE_examples

$\newcommand{\la}{\langle}$ $\newcommand{\ra}{\rangle}$ $\newcommand{\vu}{\mathbf{u}}$ $\newcommand{\vv}{\mathbf{v}}$ $\newcommand{\vw}{\mathbf{w}}$ $\newcommand{\vzz}{\mathbf{z}}$ $\newcommand{\nc}{\newcommand}$ $\nc{\Cc}{\mathbb{C}}$ $\nc{\Rr}{\mathbb{R}}$ $\nc{\Qq}{\mathbb{Q}}$ $\nc{\Nn}{\mathbb{N}}$ $\nc{\cB}{\mathcal{B}}$ $\nc{\cE}{\mathcal{E}}$ $\nc{\cC}{\mathcal{C}}$ $\nc{\cD}{\mathcal{D}}$ $\nc{\mi}{\mathbf{i}}$ $\nc{\span}[1]{\langle #1 \rangle}$ $\nc{\ol}[1]{\overline{#1} }$ $\nc{\norm}[1]{\left\| #1 \right\|}$ $\nc{\abs}[1]{\left| #1 \right|}$ $\nc{\vz}{\mathbf{0}}$ $\nc{\vo}{\mathbf{1}}$ $\nc{\DMO}{\DeclareMathOperator}$ $\DMO{\tr}{tr}$ $\DMO{\nullsp}{nullsp}$ $\nc{\va}{\mathbf{a}}$ $\nc{\vb}{\mathbf{b}}$ $\nc{\vx}{\mathbf{x}}$ $\nc{\ve}{\mathbf{e}}$ $\nc{\vd}{\mathbf{d}}$ $\nc{\vh}{\mathbf{h}}$ $\nc{\ds}{\displaystyle}$ $\nc{\bm}[1]{\begin{bmatrix} #1 \end{bmatrix}}$ $\nc{\gm}[2]{\bm{\mid & \cdots & \mid \\ #1 & \cdots & #2 \\ \mid & \cdots & \mid}}$ $\nc{\MN}{M_{m \times n}(K)}$ $\nc{\NM}{M_{n \times m}(K)}$ $\nc{\NP}{M_{n \times p}(K)}$ $\nc{\MP}{M_{m \times p}(K)}$ $\nc{\PN}{M_{p \times n}(K)}$ $\nc{\NN}{M_n(K)}$ $\nc{\im}{\mathrm{Im\ }}$ $\nc{\ev}{\mathrm{ev}}$ $\nc{\Hom}{\mathrm{Hom}}$ $\nc{\com}[1]{[\phantom{a}]^{#1}}$ $\nc{\rBD}[1]{ [#1]_{\cB}^{\cD}}$ $\DMO{\id}{id}$ $\DMO{\rk}{rk}$ $\DMO{\nullity}{nullity}$ $\DMO{\End}{End}$ $\DMO{\proj}{proj}$ $\nc{\GL}{\mathrm{GL}}$

Example 1. Solve the following system using GJE

\begin{cases} x_2 -2 x_3 +x_4 &= -1 \\ 2x_1 + 3x_2 +x_3 -x_4 &=2 \\ -2x_1 + x_2 +2x_4 &= 1 \end{cases}

In [2]:

%display latex
A = matrix(QQ,[(0,1,-2,1),(2,3,1,-1),(-2,1,0,2)]); b = column_matrix([-1,2,1]); 
#note that QQ, that stands for the rational.

M = block_matrix([A,b], ncols = 2); M #the augmented matrix of the system

Out[2]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 0 & 1 & -2 & 1 & -1 \\ 2 & 3 & 1 & -1 & 2 \\ -2 & 1 & 0 & 2 & 1 \end{array}\right]$

Let's apply GJE, by hand

In [3]:

M.swap_rows(0,1); M #R_2 <-->R_1 so that the 1st row has the left most pivot. 
#Also, recall that the indices start with 0

Out[3]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 2 & 3 & 1 & -1 & 2 \\ 0 & 1 & -2 & 1 & -1 \\ -2 & 1 & 0 & 2 & 1 \end{array}\right]$

In [4]:

M.rescale_row(0,1/2); M #1/2R_1 --> R_1, rescale the first row by 1/2

Out[4]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 1 & \frac{3}{2} & \frac{1}{2} & -\frac{1}{2} & 1 \\ 0 & 1 & -2 & 1 & -1 \\ -2 & 1 & 0 & 2 & 1 \end{array}\right]$

In [5]:

M.add_multiple_of_row(2,0,2); M #2R_1 + R_3 --> R_3
# M.add_multiple_of_row(i,k,c) means add to the ith row c(kth-row).

Out[5]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 1 & \frac{3}{2} & \frac{1}{2} & -\frac{1}{2} & 1 \\ 0 & 1 & -2 & 1 & -1 \\ 0 & 4 & 1 & 1 & 3 \end{array}\right]$

Now we are done with the 1st row (since all entries below its pivot are 0). We repeat the procedure to eliminate the entry below the next leftmost pivot.

In [6]:

M.add_multiple_of_row(2,1,-4); M

Out[6]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 1 & \frac{3}{2} & \frac{1}{2} & -\frac{1}{2} & 1 \\ 0 & 1 & -2 & 1 & -1 \\ 0 & 0 & 9 & -3 & 7 \end{array}\right]$

Now we are done with the 2nd (leftmost) pivot. Move onto the 3rd.

In [7]:

M.rescale_row(2,1/9); M

Out[7]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 1 & \frac{3}{2} & \frac{1}{2} & -\frac{1}{2} & 1 \\ 0 & 1 & -2 & 1 & -1 \\ 0 & 0 & 1 & -\frac{1}{3} & \frac{7}{9} \end{array}\right]$

We are now done with the forward elimination. Next step: backward substitution. That is, start by elminiating all entries above the pivot of the last row.

In [8]:

M.add_multiple_of_row(1,2,2); M

Out[8]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 1 & \frac{3}{2} & \frac{1}{2} & -\frac{1}{2} & 1 \\ 0 & 1 & 0 & \frac{1}{3} & \frac{5}{9} \\ 0 & 0 & 1 & -\frac{1}{3} & \frac{7}{9} \end{array}\right]$

In [9]:

M.add_multiple_of_row(0,2,-1/2); M

Out[9]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 1 & \frac{3}{2} & 0 & -\frac{1}{3} & \frac{11}{18} \\ 0 & 1 & 0 & \frac{1}{3} & \frac{5}{9} \\ 0 & 0 & 1 & -\frac{1}{3} & \frac{7}{9} \end{array}\right]$

We are done with the pivot of the last row. Now move onto the pivot of the 2nd last row.

In [10]:

M.add_multiple_of_row(0,1,-3/2); M

Out[10]:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left[\begin{array}{cccc|c} 1 & 0 & 0 & -\frac{5}{6} & -\frac{2}{9} \\ 0 & 1 & 0 & \frac{1}{3} & \frac{5}{9} \\ 0 & 0 & 1 & -\frac{1}{3} & \frac{7}{9} \end{array}\right]$

Examples of GJE¶