Week 7 - More Gaussian Elimination and Matrix Inversion

1. When Gaussian Elimination Breaks Down

  • Let ARn×nA \in \mathbb{R}^{n \times n} and assume that ALUA \to LU completes with a matrix UU that has no zero elements on its diagonal.
    • Ax=bAx=b has a unique solution.

1.1. Permutation

  • Let p=(k0,,kn1)Tp = (k_0, \ldots, k_{n-1})^T be a permutation vector. Then P=P(p)=(ek0Tek1Tekn1T) P = P(p) = \left(\begin{array}{c} e_{k_0}^T \\ e_{k_1}^T \\ \vdots \\ e_{k_{n-1} }^T \end{array}\right) is said to be a permutation matrix.
    • If p=(0123) then P(p)=(1000010000100001)\text{If}\ p = \left(\begin{array}{c}0 \\ 1 \\ 2 \\ 3\end{array}\right)\ \text{then}\ P(p) = \left(\begin{array}{c c c c}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{array}\right)
  • Px=P(p)x=(ek0Tek1Tekn1T)x=(ek0Txek1Txekn1Tx)=(xk0xk1xkn1) P x = P(p) x = \left(\begin{array}{c} e_{k_0}^T \\ e_{k_1}^T \\ \vdots \\ e_{k_{n-1} }^T \end{array}\right) x = \left(\begin{array}{c} e_{k_0}^T x \\ e_{k_1}^T x \\ \vdots \\ e_{k_{n-1} }^T x \end{array}\right) = \left(\begin{array}{c} x_{k_0} \\ x_{k_1} \\ \vdots \\ x_{k_{n-1} } \end{array}\right)

  • Let A=(a~0Ta~1Ta~n1T)A = \left(\begin{array}{c} \widetilde a_0^T \\ \widetilde a_1^T \\ \vdots \\ \widetilde a_{n-1}^T \end{array}\right)

    • PA=P(p)A=(ek0Tek1Tekn1T)A=(a~k0Ta~k1Ta~kn1T)PA = P(p)A = \left(\begin{array}{c} e_{k_0}^T \\ e_{k_1}^T \\ \vdots \\ e_{k_{n-1} }^T \end{array}\right) A = \left(\begin{array}{c} \widetilde a_{k_0}^T \\ \widetilde a_{k_1}^T \\ \vdots \\ \widetilde a_{k_{n-1} }^T \end{array}\right)
  • Let A=(a0a1an1)A = \left(\begin{array}{c | c | c | c} a_0 & a_1 & \ldots & a_{n-1} \end{array}\right)

    • APT=(ak0ak1akn1)AP^T = \left(\begin{array}{c | c | c | c} a_{k_0} & a_{k_1} & \ldots & a_{k_{n-1} } \end{array}\right)
  • If PP is a permutation matrix, then so is PTP^T.

Pivot matrix

    • Swap the π\pith row with the 00th.
  • P~(π)=(P~(π))T\widetilde P(\pi) = (\widetilde P(\pi))^T

  • Summary

    • Permutation matrices, when applied from the left, swap rows.
    • Permutation matrices, when applied from the right, swap columns.

1.2. LU factorization algorithm that incorporates row (partial) pivoting

  • Solving Ax=bAx = b then changes to
    • Compute P,L and UP, L \text{ and } U such that PA=LUPA = LU.
    • Update b:=Pbb:= Pb.
    • Solve Lz=bLz = b (forward substitution)
    • Solve Ux=zUx = z (backward substitution)

2. The Inverse Matrix

  • Definition: an n-by-n square matrix A is called invertible (also nonsingular) if there exists an n-by-n square matrix B such that AB=BA=In\mathbf {AB} =\mathbf {BA} =\mathbf {I} _{n}

2.1. Inverse Functions in 1D

  • f:RRf: \mathbb{R} \to \mathbb{R} maps a rea to a real and it is a bijection(both one-to-one and onto)
    • bijection means: every element in R, there is a unique output in R.
  • then
    • f(x)=yf(x) = y has a unique solution for all yRy \in \mathbb{R}.
    • The function that maps y to x so that g(y)=xg(y) = x is called the inverse of ff.
    • It is denoted by f1:RRf^{-1}: \mathbb{R} \to \mathbb{R}.
    • f(f1(x))=f1(f(x))=xf(f^{-1}(x)) = f^{-1}(f(x)) = x

2.2. General principle

  • If A,BRn×nA, B \in R^{n \times n} and AB=IAB = I, then Abj=ejAb_j = e_j, where bjb_j is the jjth column of B and eje_j is the jjth unit basis vector.

2.3. Properties of the inverse

  • Assume A, B, and C are square matrices that are nonsingular. Then

    • (αB)1=1αB1(\alpha B)^{-1} = \frac{1}{\alpha} B^{-1}
    • (AB)1=B1A1(AB)^{-1} = B^{-1} A^{-1}
    • (ABC)1=C1B1A1(ABC)^{-1} = C^{-1} B^{-1} A^{-1}
    • (AT)1=(A1)T(A^T)^{-1} = (A^{-1})^{T}
    • (A1)1=A(A^{-1})^{-1} = A
  • The following statements are equivalent statements about ARn×nA \in \mathbb{R}^{n \times n} :

    • A is nonsingular(不可逆).
    • A is invertible.
    • A1A^{-1} exists.
    • AA1=A1A=IAA^{-1} = A^{-1}A = I.
      • A1A^{-1} undoes what matrix A did.
      • AA1x=Ix=xAA^{-1}x = Ix = x
      • Identity Matrix
    • A represents a linear transformation that is a bijection.
    • Ax = b has a unique solution for all bRnb \in \mathbb{R}^n.
    • Ax=0Ax = 0 implies that x=0x = 0.
    • Ax=ejAx = e_j has a solution for all j0,,n1j \in {0, \ldots, n-1}.
    • The determinant of A is nonzero: det(A)0\text{det}(A) \ne 0. Will talk this in next section.
  • Theorem: Let PP be a permutation matrix. Then P1=PTP^{-1} = P^T.

2.4. Determinant

  • The determinant of a matrix A is denoted det(A)\text{det}(A)
  • Let A=[abcd]A = \begin{bmatrix}a & b \\ c & d \end{bmatrix}
  • det(A)=adbc\text{det}(A) = ad - bc
  • A1=1adbc[dbca]A^{-1} = \frac{1}{ad - bc} \begin{bmatrix}d & -b \\ -c & a \end{bmatrix}
  • So if det(A)=adbc=0\text{det}(A) = ad - bc = 0, then A1A^{-1} doesn't exist and AA is non-invertible.
  • A formula for the determinant of a 3×3 matrix:
    • Similar to the n×nn \times n matrix.

2.5. Inverses of special matrices

3. Refers

4. Words

  • permutation [,pə:mju:'teiʃən] n. [数] 排列;[数] 置换
  • bijection [bai'dʒekʃən] n. [数] 双射
  • determinant [di'tə:minənt] adj. 决定性的 n. 决定因素;[数] 行列式

results matching ""

    No results matching ""