Section03 Elimination Using Matrices

$$\text{elimination matrix } \boldsymbol{E}$$

The Matrix Form of One Elimination Step

elimination (elementary) matrix

• The elementary matrix or elimination matrix $\boldsymbol{E}_{ij}$ has the extra nonzero entry $-\ell$ in the $i,j$ position. The $\boldsymbol{E}_{ij}$ subtracts a multiple $\ell$ of row $j$ from row $i$, for example:

$$\boldsymbol{E}_{31} = \left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -\ell & 0 & 1 \\ \end{matrix} \right]$$

• The purpose of $\boldsymbol{E}_{31}$ is to produce a zero in the $(3,1)$ position of the matrix.

Matrix Multiplication

• Associative law is true $$\boldsymbol{A}(\boldsymbol{BC}) = (\boldsymbol{AB})\boldsymbol{C}$$
• Commutative law is false $$\boldsymbol{AB} \ne \boldsymbol{BA}$$

Matrix multiplication

$$\boldsymbol{AB} = \boldsymbol{A} \left[ \begin{matrix} \boldsymbol{b}_{\boldsymbol{\cdot}1} & \boldsymbol{b}_{\boldsymbol{\cdot}2} & \cdots & \boldsymbol{b}_{\boldsymbol{\cdot}n} \end{matrix} \right] = \left[ \begin{matrix} \boldsymbol{Ab}_{\boldsymbol{\cdot}1} &\boldsymbol{Ab}_{\boldsymbol{\cdot}2} & \cdots & \boldsymbol{Ab}_{\boldsymbol{\cdot}n} \end{matrix} \right]\\ \boldsymbol{b}_{\boldsymbol{\cdot}j} \text{ is } j^{\text{th}} \text{ column of matrix } \boldsymbol{B}$$

• represented by code

  • Julia

    A = randn(3,3); B = randn(3,3);
    println(hcat((fill(A, size(B,2)) .* [eachcol(B)...])...));
    println(A * B);
    

  • Matlab

    A = randn(3); B = rand(3,3);
    for i = 1:size(B,2)
      if i == 1
         C = A * B(:,i)
      else
          C = [C A * B(:,i)]
      end
    end
    

The Matrix $P_{ij}$ for a Row Exchange

• Permutation matrix
  • $P_{ij}$: exchange the row $i$ with row $j$.
  • example $$P_{23} = \left[ \begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} \right]$$
  • $P_{ij}$ is the identity matrix with row $i$ and $j$ reversed.
  • When this Permutation Matrix $P_{ij}$ multiplies with a matrix, it exchanges the row $i$ and $j$ of the matrix be multiplied.

The Augmented Matrix

• Key Idea: Elimination does the same row operations to $\boldsymbol{A}$ and $\boldsymbol{b}$. We can include $\boldsymbol{b}$ as extra column and follow it through elimination. $$\left[ \begin{matrix} \boldsymbol{A} & \boldsymbol{b} \end{matrix} \right] = \left[ \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n} & b_{1} \\ a_{21} & a_{22} & \cdots & a_{2n} & b_{2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & b_{n} \end{matrix} \right]\\ \boldsymbol{E} \left[ \begin{matrix} \boldsymbol{A} & \boldsymbol{b} \end{matrix} \right] = \left[ \begin{matrix} \boldsymbol{EA} & \boldsymbol{Eb} \end{matrix} \right]$$

Properties from Exercise

• the determinant of Matrix $A$ is equal to the determinant of Matrix $A^{*}$ which has been eliminated.

  • example of 2-dimension matrix $$\boldsymbol{A} = \left[ \begin{matrix} a & b \\ c & d \end{matrix} \right] \text{ and } \textbf{det} \boldsymbol{A} = ad - bc\\ \boldsymbol{A}^{*} = \left[ \begin{matrix} a & b \\ 0 & d - \frac{c}{a}b \end{matrix} \right]\\ \textbf{det } \boldsymbol{A}^{*} = a \cdot (d - \frac{c}{a}b) - b \cdot 0 = ad - cb = \textbf{det }\boldsymbol{A}$$
  • more general $$\boldsymbol{A}^{*} = \left[ \begin{matrix} a & b \\ c - \ell a & d - \ell b \end{matrix} \right]\\ \textbf{det } \boldsymbol{A}^{*} = a \cdot (d - \ell b) - b \cdot (c - \ell a) = ad - \ell ab - (bc - \ell ab) = ad - bc = \textbf{det }\boldsymbol{A}\\ $$

• 2 $$\boldsymbol{E} = \left[ \begin{matrix} 1 & 0 & 0\\ a & 1 & 0\\ b & 0 & 1 \end{matrix} \right]$$

  • The meaning of$\boldsymbol{EE}$
    $$\boldsymbol{EE} = \left[ \begin{matrix} \boldsymbol{e_{1 \boldsymbol{\cdot}}}\\ a \boldsymbol{e_{1 \boldsymbol{\cdot}}} + \boldsymbol{e_{2 \boldsymbol{\cdot}}} \\ b \boldsymbol{e_{1 \boldsymbol{\cdot}}} + \boldsymbol{e_{3 \boldsymbol{\cdot}}} \end{matrix} \right]$$

• $\boldsymbol{AB} = \boldsymbol{I} \text{ and } \boldsymbol{BC} = \boldsymbol{I} \Rightarrow \boldsymbol{A} = \boldsymbol{C}$

  • proof $$\begin{array}{ll} \because & \boldsymbol{AB} = \boldsymbol{BC} = \boldsymbol{I} \text{ and for any Matrix } \boldsymbol{A} \text{ always } \boldsymbol{IA} = \boldsymbol{A} \\ \therefore & \boldsymbol{ABC} = (\boldsymbol{AB})\boldsymbol{C} = \boldsymbol{A} (\boldsymbol{BC}) = \boldsymbol{A} = \boldsymbol{C} \\ \end{array}$$

• Pascal's Matrix $$\begin{array}{c} \boldsymbol{P} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{matrix} \right] = \left[ \begin{matrix} \boldsymbol{p}_{1 \boldsymbol{\cdot}} \\ \boldsymbol{p}_{2 \boldsymbol{\cdot}} \\ \boldsymbol{p}_{3 \boldsymbol{\cdot}} \\ \boldsymbol{p}_{4 \boldsymbol{\cdot}} \\ \end{matrix} \right]\\ \boldsymbol{E}_{1} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{matrix} \right] \text{ and } \boldsymbol{E}_{2} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{matrix} \right] \text{ and } \boldsymbol{E}_{3} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{matrix} \right]\\ \boldsymbol{E}_{3}\boldsymbol{E}_{2}\boldsymbol{E}_{1}\boldsymbol{P} = \boldsymbol{I} \\ \boldsymbol{E}_{3}\boldsymbol{E}_{2}\boldsymbol{E}_{1} = \boldsymbol{P}^{-1} = \left[ \begin{matrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ -1 & 3 & -3 & 1 \end{matrix} \right] \end{array}$$