Study Guides / Linear Algebra / Exercise session 5
EXERCISE SESSION 5 · ETH ZURICH · HS19 · linalg

LU Decomposition, Vector Spaces, Injectivity and Surjectivity

LU decomposition, field, abelian group, vector spaces, subspace, injectivity, surjectivity, bijectivity

SB
Steven Battilana Quant · ex-ETH

LU Decomposition

Remark idea

For large linear systems Ax=bAx=b with A∈En×nA \in \mathbb{E}^{n \times n} and b,x∈Enb,x \in \mathbb{E}^n, the solution xx is usually not easy to find. So we would like to decompose AA into a simpler form made of triangular matrices, i.e. we look for matrices P,L,R∈En×nP,L,R \in \mathbb{E}^{n \times n} such that PA=LRPA = LR,

P=^ is a permutation matrix (contains only 1 and 0)L=^ is a left triangular matrix (lower triangular matrix)R (often U)=^ is a right triangular matrix (upper triangular matrix)\begin{aligned} P &\mathrel{\hat{=}} \text{ is a \emph{permutation matrix} (contains only $1$ and $0$)}\\ L &\mathrel{\hat{=}} \text{ is a \emph{left triangular matrix} (lower triangular matrix)}\\ R \text{ (often $U$)} &\mathrel{\hat{=}} \text{ is a \emph{right triangular matrix} (upper triangular matrix)} \end{aligned}L=(10⋯0∗⋱⋱⋮⋮⋱⋱0∗⋯∗1)R=(∗⋯⋯∗0⋱⋱⋮⋮⋱⋱0⋯0∗)L = \begin{pmatrix} 1 & 0 & \cdots & 0\\ * & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ * & \cdots & * & 1 \end{pmatrix} \quad\quad\quad\quad R = \begin{pmatrix} * & \cdots & \cdots & *\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & \\ 0 & \cdots & 0 & * \end{pmatrix}
Remark

Let A,P,L,R∈En×nA,P,L,R \in \mathbb{E}^{n \times n}. PP stores the row swaps needed for pivoting, LL stores the elimination steps that turn AA into row echelon form, RR is the row echelon form of AA.

Remark

Let A,P,L,R∈En×nA,P,L,R \in \mathbb{E}^{n \times n} and b,c,x∈Enb,c,x \in \mathbb{E}^n. The original system Ax=bAx=b can now be solved more easily:

  1. Solve Lc=PbLc = Pb for cc by forward substitution, i.e. "Gauss" (L∣Pb)(L|Pb) from top to bottom.
  2. Solve Rx=cRx=c for xx by back substitution, i.e. "Gauss" (R∣c)(R|c) from bottom to top.
Remark

That the relation from the remark above gives the correct solution x∈En\boldsymbol{x} \in \mathbb{E}^n for A,P,P−1,L,R∈En×nA,P,P^{-1},L,R \in \mathbb{E}^{n \times n} can also be seen from

Ax=P−1PAx=P−1LRx=P−1Lc=P−1Pb=b.A \boldsymbol{x} = P^{-1}PA\boldsymbol{x} = P^{-1}LR\boldsymbol{x} = P^{-1}L\boldsymbol{c} = P^{-1}P\boldsymbol{b} = \boldsymbol{b}.
Satz

For a regular square matrix A∈En×nA \in \mathbb{E}^{n \times n} there exists an LU decomposition, i.e.

∃P,L,R∈En×n:PA=LR.\exists P,L,R \in \mathbb{E}^{n \times n}: \quad PA = LR.
Remark LU decomposition light (i.e. without pivoting)

Assumption: no row swaps needed and AA has no zero column
Given: A∈En×nA \in \mathbb{E}^{n \times n}
Wanted: L∈En×n, R∈En×nL \in \mathbb{E}^{n \times n},\, R \in \mathbb{E}^{n \times n} such that: A=LRA = LR

  1. Write down the scheme (A∣𝟙)(A|\text{𝟙})

  2. Transform AA using Gaussian elimination (WITHOUT row swaps!) until you reach row echelon form. You do all of this only on the left-hand side of the augmented matrix.

  3. On the right-hand side, write down the ratios:

    lij:=aijajj,L=(10⋯0l21⋱⋱⋮⋮⋱⋱0ln1⋯lnn−11)l_{ij} := \frac{a_{ij}}{a_{jj}}, \quad\quad L = \begin{pmatrix} 1 & 0 & \cdots & 0\\ l_{21} & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ l_{n1} & \cdots & l_{nn-1} & 1 \end{pmatrix}

These steps look as follows:

(A∣𝟙)⇝⋯⇝(R∣L)(A|\text{𝟙}) \leadsto \cdots \leadsto (R|L)

in more detail:

(a11a12a13100a21a22a23010a31a32a33001)\left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ a_{21} & a_{22} & a_{23} & 0 & 1 & 0\\ a_{31} & a_{32} & a_{33} & 0 & 0 & 1 \end{array}\right)⇝(ii)−l21⋅(i)  (a11a12a13100a21−l21a11a22−l21a12a23−l21a13l2110a31a32a33001)⇝(iii)−l31⋅(i)  (a11a12a131000a22~a23~l2110a31−l31a11a32−l31a12a33−l31a13l3101)⇝  (a11a12a131000a22~a23~l21100a32~a33~l3101)⇝  ⋯  ⇝  (a11a12a131000a22~a23~l211000a33^l31l321)\begin{aligned} \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ a_{21} - l_{21}a_{11} & a_{22} - l_{21}a_{12} & a_{23} - l_{21}a_{13} & l_{21} & 1 & 0\\ a_{31} & a_{32} & a_{33} & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(iii) - l_{31} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}} & l_{21} & 1 & 0\\ a_{31} - l_{31}a_{11} & a_{32} - l_{31}a_{12} & a_{33} - l_{31}a_{13} & l_{31} & 0 & 1 \end{array}\right)\\[1.5ex] \leadsto \; & \left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 0 & 1 \end{array}\right)\\[1.5ex] \leadsto \; \cdots \; \leadsto \; & \left(\begin{array}{ccc|ccc} a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & 0 & \widehat{a_{33}} & l_{31} & l_{32} & 1 \end{array}\right) \end{aligned}⟹R=(a11a12a130a22~a23~00a33^),L=(100l2110l31l321)\quad \Longrightarrow \quad R = \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}}\\ 0 & 0 & \widehat{a_{33}} \end{pmatrix}, \quad\quad L = \begin{pmatrix} 1 & 0 & 0\\ l_{21} & 1 & 0\\ l_{31} & l_{32} & 1 \end{pmatrix}

Now we have:

A=(a11a12a13a21a22a23a31a32a33)=(100l2110l31l321)(a11a12a130a22~a23~00a33^)=LRA = \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ l_{21} & 1 & 0\\ l_{31} & l_{32} & 1 \end{pmatrix} \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ 0 & \widetilde{a_{22}} & \widetilde{a_{23}}\\ 0 & 0 & \widehat{a_{33}} \end{pmatrix} = LR
Example 1

Let A∈R3×3A \in \mathbb{R}^{3 \times 3} and b∈Rnb \in \mathbb{R}^n be given.

A=(12438142613),b=(35129109)A = \begin{pmatrix} 1 & 2 & 4\\ 3 & 8 & 14\\ 2 & 6 & 13 \end{pmatrix}, \quad\quad \boldsymbol{b} = \begin{pmatrix} 35\\ 129\\ 109 \end{pmatrix}

(i) Wanted: L,R∈R3×3:A=LR.L,R \in \mathbb{R}^{3 \times 3}:\quad A = LR.

Show solutionHide solution (12410038140102613001)\left(\begin{array}{ccc|ccc} 1 & 2 & 4 & 1 & 0 & 0\\ 3 & 8 & 14 & 0 & 1 & 0\\ 2 & 6 & 13 & 0 & 0 & 1 \end{array}\right)⇝(ii)−l21⋅(i)  (1241000223102613001)⇝(iii)−l31⋅(i)  (124100022310025201)⇝(iii)−l32⋅(ii)  (124100022310003211)\begin{aligned} \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} 1 & 2 & 4 & 1 & 0 & 0\\ 0 & 2 & 2 & 3 & 1 & 0\\ 2 & 6 & 13 & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(iii) - l_{31} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} 1 & 2 & 4 & 1 & 0 & 0\\ 0 & 2 & 2 & 3 & 1 & 0\\ 0 & 2 & 5 & 2 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(iii) - l_{32} \cdot (ii)}{\leadsto} \; & \left(\begin{array}{ccc|ccc} 1 & 2 & 4 & 1 & 0 & 0\\ 0 & 2 & 2 & 3 & 1 & 0\\ 0 & 0 & 3 & 2 & 1 & 1 \end{array}\right) \end{aligned}⟹A=(12438142613)=(100310211)(124022003)=LR.\Longrightarrow \quad A = \begin{pmatrix} 1 & 2 & 4\\ 3 & 8 & 14\\ 2 & 6 & 13 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 2 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 4\\ 0 & 2 & 2\\ 0 & 0 & 3 \end{pmatrix} =LR.

(ii) Wanted: x∈Rn:Ax=b\boldsymbol{x} \in \mathbb{R}^n: \quad A\boldsymbol{x}=\boldsymbol{b}.

Show solutionHide solution

We proceed as suggested in the remark above (forward and back substitution):

  1. Solve Lc=bL\boldsymbol{c} = \boldsymbol{b}:

    (10035310129211109)\left(\begin{array}{ccc|c} 1 & 0 & 0 & 35\\ 3 & 1 & 0 & 129\\ 2 & 1 & 1 & 109 \end{array}\right) ⇝(ii)−31⋅(i)  (1003501024211109)⇝(iii)−21⋅(i)  (100350102401139)⇝(iii)−11⋅(ii)  (100350102400115)⇒c=(352415)\begin{aligned} \stackrel{(ii) - \frac{3}{1} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 35\\ 0 & 1 & 0 & 24\\ 2 & 1 & 1 & 109 \end{array}\right)\\[1.5ex] \stackrel{(iii) - \frac{2}{1} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 35\\ 0 & 1 & 0 & 24\\ 0 & 1 & 1 & 39 \end{array}\right)\\[1.5ex] \stackrel{(iii) - \frac{1}{1} \cdot (ii)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 35\\ 0 & 1 & 0 & 24\\ 0 & 0 & 1 & 15 \end{array}\right) \quad\quad \Rightarrow \quad\quad \boldsymbol{c} = \begin{pmatrix} 35\\ 24\\ 15 \end{pmatrix} \end{aligned}
  2. Solve Rx=cR\boldsymbol{x} = \boldsymbol{c}:

    (124350222400315)\left(\begin{array}{ccc|c} 1 & 2 & 4 & 35\\ 0 & 2 & 2 & 24\\ 0 & 0 & 3 & 15 \end{array}\right) ⇝(ii)−23⋅(iii)  (124350201400315)⇝(i)−43⋅(iii)  (120150201400315)⇝(i)−22⋅(ii)  (10010201400315)⇝(ii)⋅12  (1001010700315)⇝(iii)⋅13  (100101070015)\begin{aligned} \stackrel{(ii) - \frac{2}{3} \cdot (iii)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 2 & 4 & 35\\ 0 & 2 & 0 & 14\\ 0 & 0 & 3 & 15 \end{array}\right)\\[1.5ex] \stackrel{(i) - \frac{4}{3} \cdot (iii)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 2 & 0 & 15\\ 0 & 2 & 0 & 14\\ 0 & 0 & 3 & 15 \end{array}\right)\\[1.5ex] \stackrel{(i) - \frac{2}{2} \cdot (ii)}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 2 & 0 & 14\\ 0 & 0 & 3 & 15 \end{array}\right)\\[1.5ex] \stackrel{(ii) \cdot \frac{1}{2}}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 7\\ 0 & 0 & 3 & 15 \end{array}\right)\\[1.5ex] \stackrel{(iii) \cdot \frac{1}{3}}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 7\\ 0 & 0 & 1 & 5 \end{array}\right) \end{aligned} ⇒x=(175)⟹L={(x1x2x3)∣(175)}\Rightarrow \quad\quad \boldsymbol{x} = \begin{pmatrix} 1\\ 7\\ 5 \end{pmatrix} \quad\quad \Longrightarrow \quad\quad \mathbb{L} = \left\{ \left. \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} \right| \begin{pmatrix} 1\\ 7\\ 5 \end{pmatrix}\right\}
Remark LU decomposition full (i.e. with pivoting)

Given: A∈En×nA \in \mathbb{E}^{n \times n}
Wanted: P∈Rn×n, L∈En×n, R∈En×nP \in \mathbb{R}^{n \times n},\, L \in \mathbb{E}^{n \times n},\, R \in \mathbb{E}^{n \times n} such that: PA=LRPA = LR

  1. Write down the scheme (𝟙∣A∣𝟙)(\text{𝟙}|A|\text{𝟙}). On the left you keep track of the row swaps, in the middle you "Gauss", and on the right you keep track of the ratios.

  2. Pivot in the current column jj, i.e. determine the index ip∈{j,j+1,...,n}i_p \in \{j,j+1, ..., n\} with ∣aipj∣=max⁡i∈{j,j+1,...,n}∣aij∣|a_{i_pj}| =\max \limits _{i \in \{j,j+1, ..., n\}} |a_{ij}|. If ∣aipj∣=0|a_{i_pj}| = 0, stop: no LU decomposition exists. Otherwise compute PijA=A~P_{ij}A=\widetilde{A} in the middle, where Pij∈Rn×nP_{ij} \in \mathbb{R}^{n \times n} is multiplied from the left onto the matrix on the left of the scheme, and on the right-hand side you have to swap the ratios accordingly (except in the first step).

    • If you have to pivot at the start, the result of the step looks as follows:
      (𝟙∣A∣𝟙)⇝(Pij∣A~∣𝟙)(\text{𝟙}|A|\text{𝟙}) \leadsto (P_{ij}|\widetilde{A}|\text{𝟙})

    • Otherwise, the result of the step looks as follows:

      (010a11a12a1310010000a23~l21100010a32~a33~l3101)\left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & 0 & 1 & 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 0 & 1 \end{array}\right) ⇝pivot(010a11a12a131000010a32~a33~l311010000a23~l2101)\stackrel{\text{pivot}}{\leadsto} \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 0 & 1 \end{array}\right)
  3. Transform AA using Gaussian elimination (WITHOUT row swaps!) until you reach row echelon form. You do all of this only on the left-hand side of the augmented matrix.
    If a zero entry shows up on the main diagonal again during the computation, you have to pivot again, i.e. repeat the second step. Then keep "Gaussing".

  4. On the right-hand side, write down the ratios:

    lij:=aijajj,L=(10⋯0l21⋱⋱⋮⋮⋱⋱0ln1⋯lnn−11)l_{ij} := \frac{a_{ij}}{a_{jj}}, \quad\quad L = \begin{pmatrix} 1 & 0 & \cdots & 0\\ l_{21} & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ l_{n1} & \cdots & l_{nn-1} & 1 \end{pmatrix}

The steps look as follows:

(𝟙∣A∣𝟙)⇝⋯⇝(P∣R∣L)(\text{𝟙}|A|\text{𝟙}) \leadsto \cdots \leadsto (P|R|L)

in more detail:

(100a11a12a13100010a21a22a23010001a31a32a33001)\left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 1 & 0 & a_{21} & a_{22} & a_{23} & 0 & 1 & 0\\ 0 & 0 & 1 & a_{31} & a_{32} & a_{33} & 0 & 0 & 1 \end{array}\right)⇝(ii)−l21⋅(i)  (100a11a12a13100010a21−l21a11a22−l21a12a23−l21a13l2110001a31a32a33001)⇝(iii)−l31⋅(i)  (100a11a12a1310001000a23~l2110001a31−l31a11a32−l31a12a33−l31a13l3101)\begin{aligned} \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 1 & 0 & a_{21} - l_{21}a_{11} & a_{22} - l_{21}a_{12} & a_{23} - l_{21}a_{13} & l_{21} & 1 & 0\\ 0 & 0 & 1 & a_{31} & a_{32} & a_{33} & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(iii) - l_{31} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & 0 & 1 & a_{31} - l_{31}a_{11} & a_{32} - l_{31}a_{12} & a_{33} - l_{31}a_{13} & l_{31} & 0 & 1 \end{array}\right) \end{aligned}⇝(100a11a12a1310001000a23~l21100010a32~a33~l3101)\leadsto \left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 1 & 0\\ 0 & 0 & 1 & 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 0 & 1 \end{array}\right)⇝pivot(100a11a12a131000010a32~a33~l311001000a23~l2101)\stackrel{\text{pivot}}{\leadsto} \left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & a_{11} & a_{12} & a_{13} & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & \widetilde{a_{32}} & \widetilde{a_{33}} & l_{31} & 1 & 0\\ 0 & 1 & 0 & 0 & 0 & \widetilde{a_{23}} & l_{21} & 0 & 1 \end{array}\right)PA=(100001010)(a11a12a13a21a22a23a31a32a33)=(100l3110l2101)(a11a12a130a32~a33~00a23~)=LRPA = \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ l_{31} & 1 & 0\\ l_{21} & 0 & 1 \end{pmatrix} \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ 0 & \widetilde{a_{32}} & \widetilde{a_{33}}\\ 0 & 0 & \widetilde{a_{23}} \end{pmatrix} = LR
Example 2

Let A∈R3×3A \in \mathbb{R}^{3 \times 3} and b∈Rnb \in \mathbb{R}^n be given.

A=(316−60−1608−17),b=(40−86−29)A = \begin{pmatrix} 3 & 1 & 6\\ -6 & 0 & -16\\ 0 & 8 & -17 \end{pmatrix}, \quad\quad \boldsymbol{b} = \begin{pmatrix} 40\\ -86\\ -29 \end{pmatrix}

(i) Wanted: L,P,R∈R3×3:PA=LR.L,P,R \in \mathbb{R}^{3 \times 3}:\quad PA = LR.

Show solutionHide solution (100316100010−60−1601000108−17001)\left(\begin{array}{ccc|ccc|ccc} 1 & 0 & 0 & 3 & 1 & 6 & 1 & 0 & 0\\ 0 & 1 & 0 & -6 & 0 & -16 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 0 & 1 \end{array}\right)⇝pivot:P21  (010−60−1610010031601000108−17001)⇝(ii)−l21⋅(i)  (010−60−1610010001−2−121000108−17001)⇝pivot:P32  (010−60−1610000108−1701010001−2−1201)\begin{aligned} \stackrel{\text{pivot:} P_{21}}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & -6 & 0 & -16 & 1 & 0 & 0\\ 1 & 0 & 0 & 3 & 1 & 6 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{(ii) - l_{21} \cdot (i)}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & -6 & 0 & -16 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & -2 & -\frac{1}{2} & 1 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 0 & 1 \end{array}\right)\\[1.5ex] \stackrel{\text{pivot:} P_{32}}{\leadsto} \; & \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & -6 & 0 & -16 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 1 & -2 & -\frac{1}{2} & 0 & 1 \end{array}\right) \end{aligned}⇝(iii)−l32⋅(ii)(010−60−1610000108−170101000018−12181)\stackrel{(iii) - l_{32} \cdot (ii)}{\leadsto} \left(\begin{array}{ccc|ccc|ccc} 0 & 1 & 0 & -6 & 0 & -16 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 8 & -17 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & \frac{1}{8} & -\frac{1}{2} & \frac{1}{8} & 1 \end{array}\right)PA=(010001100)(316−60−1608−17)=(100010−12181)(−60−1608−170018)=LRPA = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 3 & 1 & 6\\ -6 & 0 & -16\\ 0 & 8 & -17 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ -\frac{1}{2} & \frac{1}{8} & 1 \end{pmatrix} \begin{pmatrix} -6 & 0 & -16\\ 0 & 8 & -17\\ 0 & 0 & \frac{1}{8} \end{pmatrix} = LR

(ii) Wanted: x∈Rn:Ax=b\boldsymbol{x} \in \mathbb{R}^n: \quad A\boldsymbol{x}=\boldsymbol{b}.

Show solutionHide solution

We proceed as suggested in the remark above (forward and back substitution):

  1. Solve Lc=PbL\boldsymbol{c} = P\boldsymbol{b}:

    Pb=(010001100)(40−86−29)=(−86−2940)P\boldsymbol{b} = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 40\\ -86\\ -29 \end{pmatrix} = \begin{pmatrix} -86\\ -29\\ 40 \end{pmatrix} (100−86010−29−1218140)⇝(iii)−−1/21⋅(i)(100−86010−290181−3)⇝(iii)−1/81⋅(ii)(100−86010−2900158)\left(\begin{array}{ccc|c} 1 & 0 & 0 & -86\\ 0 & 1 & 0 & -29\\ -\frac{1}{2} & \frac{1}{8} & 1 & 40 \end{array}\right) \stackrel{(iii) - \frac{-1/2}{1} \cdot (i)}{\leadsto} \left(\begin{array}{ccc|c} 1 & 0 & 0 & -86\\ 0 & 1 & 0 & -29\\ 0 & \frac{1}{8} & 1 & -3 \end{array}\right) \stackrel{(iii) - \frac{1/8}{1} \cdot (ii)}{\leadsto} \left(\begin{array}{ccc|c} 1 & 0 & 0 & -86\\ 0 & 1 & 0 & -29\\ 0 & 0 & 1 & \frac{5}{8} \end{array}\right) ⇒c=(−86−2958)\Rightarrow \quad\quad \boldsymbol{c} = \begin{pmatrix} -86\\ -29\\ \frac{5}{8} \end{pmatrix}
  2. Solve Rx=cR\boldsymbol{x} = \boldsymbol{c}:

    (−60−16−8608−17−29001858)\left(\begin{array}{ccc|c} -6 & 0 & -16 & -86\\ 0 & 8 & -17 & -29\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right) ⇝(ii)−−171/8⋅(iii)  (−60−16−8608056001858)⇝(i)−−161/8⋅(iii)  (−600−608056001858)⇝(i)⋅(−16)  (100108056001858)⇝(ii)⋅18  (10010107001858)⇝(iii)⋅8  (100101070015)\begin{aligned} \stackrel{(ii) - \frac{-17}{1/8} \cdot (iii)}{\leadsto} \; & \left(\begin{array}{ccc|c} -6 & 0 & -16 & -86\\ 0 & 8 & 0 & 56\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right)\\[1.5ex] \stackrel{(i) - \frac{-16}{1/8} \cdot (iii)}{\leadsto} \; & \left(\begin{array}{ccc|c} -6 & 0 & 0 & -6\\ 0 & 8 & 0 & 56\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right)\\[1.5ex] \stackrel{(i) \cdot (-\frac{1}{6})}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 8 & 0 & 56\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right)\\[1.5ex] \stackrel{(ii) \cdot \frac{1}{8}}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 7\\ 0 & 0 & \frac{1}{8} & \frac{5}{8} \end{array}\right)\\[1.5ex] \stackrel{(iii) \cdot 8}{\leadsto} \; & \left(\begin{array}{ccc|c} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 7\\ 0 & 0 & 1 & 5 \end{array}\right) \end{aligned} ⇒x=(175)⟹L={(x1x2x3)∣(175)}\Rightarrow \quad\quad \boldsymbol{x} = \begin{pmatrix} 1\\ 7\\ 5 \end{pmatrix} \quad\quad \Longrightarrow \quad\quad \mathbb{L} = \left\{ \left. \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} \right| \begin{pmatrix} 1\\ 7\\ 5 \end{pmatrix}\right\}

Vector Spaces

Definition

A set E\mathbb{E} together with two operations

+:E×E→E,(x,y)↦x+y(addition)⋅:E×E→E,(x,y)↦x⋅y(multiplication)\begin{aligned} +:& \quad \mathbb{E} \times \mathbb{E} \to \mathbb{E}, \quad (x,y) \mapsto x + y \quad\quad &\text{(addition)}\\ \cdot:& \quad \mathbb{E} \times \mathbb{E} \to \mathbb{E}, \quad (x,y) \mapsto x \cdot y \quad\quad &\text{(multiplication)} \end{aligned}

is called a field if the following holds ∀x,y,z∈E\forall x,y,z \in \mathbb{E}:

K1 E\mathbb{E} together with addition ++ is an abelian group.
(Its neutral element is denoted by 00, the inverse of a∈Ea \in \mathbb{E} by −a-a; cf. Discrete Mathematics, 5. Algebra, Definitions 5.7 and 5.8: ⟨E;+⟩\langle \mathbb{E}; + \rangle is an abelian group):

  • (i) (associativity) (x+y)+z=x+(y+z)\quad (x+y)+z = x+(y+z)
  • (ii) (neutral element) ∃e∈E:x+e=e+x=x\quad \exists e \in \mathbb{E}: \quad x + e = e + x = x
  • (iii) (inverse element) ∃x′∈E:x+x′=x′+x=e\quad \exists x' \in \mathbb{E}: \quad x+x'=x'+x= e
  • (iv) (abelian ⇔\Leftrightarrow commutativity) x+y=y+x\quad x+y = y+x

K2 Writing E∗:=E∖{0}\mathbb{E}^* := \mathbb{E} \setminus \{0\}, for x,y∈E∗x,y \in \mathbb{E}^* we also have x⋅y∈E∗x\cdot y \in \mathbb{E}^*, and E∗\mathbb{E}^* together with the multiplication obtained this way is an abelian group.
(Its neutral element is denoted by 11, the inverse of x∈E∗x \in \mathbb{E}^* by x−1x^{-1} or 1/x1/x. One writes y/x=x−1y=yx−1y/x =x^{-1}y=yx^{-1}.
Cf. Discrete Mathematics, 5. Algebra, Definitions 5.7 and 5.8: ⟨E;⋅⟩\langle \mathbb{E}; \cdot \rangle is an abelian group)

(cf. Discrete Mathematics, 5. Algebra: Definition 5.26 and Theorem 5.23)

Remark

Mostly we will work with the fields R\mathbb{R} or C\mathbb{C}. Another field familiar to us computer scientists is the smallest finite field Z2\mathbb{Z}_2, which contains only {0,1}\{0,1\}.

Definition

A vector space VV over E\mathbb{E} (or E\mathbb{E}-vector space; VS) is a nonempty set VV together with two operations:

+:V×V→V,(x,y)↦x+y(addition)⋅:E×V→V,(α,x)↦αx(scalar multiplication)\begin{aligned} +:& \quad V \times V \to V, \quad (x,y) \mapsto x + y \quad\quad &\text{(addition)}\\ \cdot:& \quad \mathbb{E} \times V \to V, \quad (\alpha,x) \mapsto \alpha x \quad\quad &\text{(scalar multiplication)} \end{aligned}

such that ∀x,y,z∈V\forall x,y,z \in V and ∀α,β∈E\forall \alpha, \beta \in \mathbb{E}:

V1 VV together with addition is an abelian (commutative) group (the neutral element is called the zero vector and is denoted by 0\boldsymbol{0}, and the negative is denoted by −x-x; cf. Discrete Mathematics, 5. Algebra: ⟨V;+⟩\langle V; + \rangle is an abelian group):

  • (i) (associativity) (x+y)+z=x+(y+z)\quad (x+y)+z = x+(y+z)
  • (ii) (neutral element) ∃e∈V:x+e=e+x=x\quad \exists e \in V: \quad x + e = e + x = x
  • (iii) (inverse element) ∃x′∈V:x+x′=x′+x=e\quad \exists x' \in V: \quad x+x'=x'+x= e
  • (iv) (abelian ⇔\Leftrightarrow commutativity) x+y=y+x\quad x+y = y+x

V2 Multiplication by scalars must be compatible with the other operations as follows:

  • (i) (distributivity I) (α+β)x=αx+βx\quad (\alpha + \beta) x = \alpha x + \beta x
  • (ii) (distributivity II) α(x+y)=αx+αy\quad \alpha (x+y) = \alpha x + \alpha y
  • (iii) (associativity) (αβ)x=α(βx)\quad (\alpha \beta) x = \alpha (\beta x)
  • (iv) (compatibility with 11) 1x=x\quad 1x = x
Example 3
  1. nn-dimensional vectors form a vector space over E\mathbb{E}.
  2. m×nm \times n matrices form a vector space over E\mathbb{E}.
  3. Pn:={\mathcal{P}_n := \{polynomials in one variable with coefficients in E\mathbb{E} of degree at most n}n \} form a vector space over E\mathbb{E}.
Definition

Let VV be a vector space, U⊆V, U≠{}U \subseteq V, \, U \neq \{\}. UU is called a subspace (vector subspace, linear subspace) if it is closed under addition and scalar multiplication, i.e. if ∀x,y∈U\forall x,y \in U and ∀α∈E\forall \alpha \in \mathbb{E}:

U1 x+y∈Ux + y \in U

U2 αx∈U\alpha x \in U.

Remark

Every subspace UU contains the zero vector, i.e.

U0 0∈U\boldsymbol{0} \in U.

Satz

Every subspace is a vector space.

Example 4

To show: W={(x1x2x3)∈R3∣x1+x2+x3=0}W = \left\{ \left. \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} \in \mathbb{R}^3 \right| x_1+x_2+x_3 = 0 \right\} is a vector space.

Remark
We have two options:

  1. Check whether V1 and V2 from the vector space definition are satisfied
  2. Use the Satz above and show only U1 and U2
Show solutionHide solution

Proof:
We carry out the proof with the second option. So by the Satz it suffices to show that WW is a subspace.
Let x=(x1x2x3),y=(y1y2y3)∈W,λ∈Ex = \begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix}, y = \begin{pmatrix} y_1\\ y_2\\ y_3 \end{pmatrix} \in W, \lambda \in \mathbb{E}

U0 (000)∈W\begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \in W, since 0+0+0=00+0+0=0, (U0 follows trivially)

U1 x+y=(x1+y1x2+y2x3+y3)∈Wx+y = \begin{pmatrix} x_1+y_1\\ x_2+y_2\\ x_3+y_3 \end{pmatrix} \in W,
since (x1+y1)+(x2+y2)+(x3+y3)=(x1+x2+x3)⏟x1+x2+x3=0+(y1+y2+y3)⏟y1+y2+y3=0=0(x_1+y_1)+(x_2+y_2)+(x_3+y_3) = \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} + \underbrace{(y_1+y_2+y_3)}_{y_1+y_2+y_3 = 0} = 0

U2 λx=(λx1λx2λx3)∈W\lambda x = \begin{pmatrix} \lambda x_1\\ \lambda x_2\\ \lambda x_3 \end{pmatrix} \in W, since λx1+λx2+λx3=λ(x1+x2+x3)⏟x1+x2+x3=0=0\lambda x_1 + \lambda x_2 + \lambda x_3 = \lambda \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} = 0

Or instead of showing U1 and U2 separately, you can also show the "all in one" variant:

U1/U2 x−λy=(x1−λy1x2−λy2x3−λy3)∈Wx-\lambda y = \begin{pmatrix} x_1 - \lambda y_1\\ x_2 - \lambda y_2\\ x_3 - \lambda y_3 \end{pmatrix} \in W,
since (x1−λy1)+(x2−λy2)+(x3−λy3)=(x1+x2+x3)⏟x1+x2+x3=0−λ(y1+y2+y3)⏟y1+y2+y3=0=0□(x_1 - \lambda y_1) + (x_2 - \lambda y_2) + (x_3 - \lambda y_3) = \underbrace{(x_1+x_2+x_3)}_{x_1+x_2+x_3=0} - \lambda \underbrace{(y_1+y_2+y_3)}_{y_1+y_2+y_3 = 0} = 0 \quad\quad\quad\quad \square

Injectivity, Surjectivity, Bijectivity

Definition

A map f:X→Yf: X \to Y is called injective if

∀x1,x2∈X:x1≠x2⇒f(x1)≠f(x2).\forall x_1,x_2 \in X: \quad x_1 \neq x_2 \quad \Rightarrow \quad f(x_1) \neq f(x_2).

(In words: different elements of XX are mapped to different images in YY.)

Definition

A map f:X→Yf: X \to Y is called surjective if

∀y∈Y ∃x∈X:f(x)=y.\forall y \in Y \, \exists x \in X: \quad f(x) = y.

(In words: every element of YY is "hit" by ff.)

Definition

A map f:X→Yf: X \to Y is called bijective if

∀y∈Y ∃!x∈X:f(x)=y.\forall y \in Y \, \exists \boldsymbol{!} x \in X: \quad f(x) = y.

(In words: every element of YY is "hit" by ff exactly once.)