Week 7 - More Gaussian Elimination and Matrix Inversion #

When Gaussian Elimination Breaks Down #

Let $A \in \mathbb{R}^{n \times n}$ and assume that $A \to LU$ completes with a matrix $U$ that has no zero elements on its diagonal.
- $Ax=b$ has a unique solution.

Let $p = (k_0, \ldots, k_{n-1})^T$ be a permutation vector. Then $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.
- $$\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)$$
$$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 = \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 = \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 = \left(\begin{array}{c | c | c | c} a_0 & a_1 & \ldots & a_{n-1} \end{array}\right)$$
- $$AP^T = \left(\begin{array}{c | c | c | c} a_{k_0} & a_{k_1} & \ldots & a_{k_{n-1} } \end{array}\right)$$
If $P$ is a permutation matrix, then so is $P^T$.

* Swap the $\pi$th row with the $0$th.
$\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.

Solving $Ax = b$ then changes to
- Compute $P, L \text{ and } U$ such that $PA = LU$.
- Update $b:= Pb$.
- Solve $Lz = b$ (forward substitution)
- Solve $Ux = z$ (backward substitution)

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 $$\mathbf {AB} =\mathbf {BA} =\mathbf {I} _{n}$$

$f: \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) = y$ has a unique solution for all $y \in \mathbb{R}$.
- The function that maps y to x so that $g(y) = x$ is called the inverse of $f$.
- It is denoted by $f^{-1}: \mathbb{R} \to \mathbb{R}$.
- $f(f^{-1}(x)) = f^{-1}(f(x)) = x$

If $A, B \in R^{n \times n}$ and $AB = I$, then $Ab_j = e_j$, where $b_j$ is the $j$th column of B and $e_j$ is the $j$th unit basis vector.

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