Line 17: | Line 17: | ||
Suppose we have an equation $A \times A^{-1} = I$ | Suppose we have an equation $A \times A^{-1} = I$ | ||
* how can we solve it to find $A^{-1}$? Let's replace $A^{-1}$ by $X$ and solve $A \times X = I$ | * how can we solve it to find $A^{-1}$? Let's replace $A^{-1}$ by $X$ and solve $A \times X = I$ | ||
− | * | + | * <math>A \times X = \begin{bmatrix} |
a_{11} & a_{12} \\ | a_{11} & a_{12} \\ | ||
a_{21} & a_{22} \\ | a_{21} & a_{22} \\ | ||
Line 26: | Line 26: | ||
1 & 0 \\ | 1 & 0 \\ | ||
0 & 1 | 0 & 1 | ||
− | \end{bmatrix} = I | + | \end{bmatrix} = I</math> |
* one idea: Solve $n$ different [[System of Linear Equations|systems of linear equations]] | * one idea: Solve $n$ different [[System of Linear Equations|systems of linear equations]] | ||
− | ** | + | ** <math>\begin{bmatrix} |
a_{11} & a_{12} \\ | a_{11} & a_{12} \\ | ||
a_{21} & a_{22} \\ | a_{21} & a_{22} \\ | ||
Line 37: | Line 37: | ||
1 \\ | 1 \\ | ||
0 | 0 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> and |
− | ** | + | ** <math>\begin{bmatrix} |
a_{11} & a_{12} \\ | a_{11} & a_{12} \\ | ||
a_{21} & a_{22} \\ | a_{21} & a_{22} \\ | ||
Line 47: | Line 47: | ||
0 \\ | 0 \\ | ||
1 | 1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
** i.e. for $i$th system, take $i$th column of $X$ ($\mathbf x_i$) and $i$th row of $I$ ($\mathbf e_i$) | ** i.e. for $i$th system, take $i$th column of $X$ ($\mathbf x_i$) and $i$th row of $I$ ($\mathbf e_i$) | ||
* we have a bunch of systems like $A \mathbf x_i = \mathbf e_i$ that we know how to solve | * we have a bunch of systems like $A \mathbf x_i = \mathbf e_i$ that we know how to solve | ||
** so we can use [[Gaussian Elimination]] for that | ** so we can use [[Gaussian Elimination]] for that | ||
− | ** we'll have several augmented matrices like | + | ** we'll have several augmented matrices like <math>\left[ \begin{array}{cc|c} |
a_{11} & a_{12} & 1 \\ | a_{11} & a_{12} & 1 \\ | ||
a_{21} & a_{22} & 0 \\ | a_{21} & a_{22} & 0 \\ | ||
− | \end{array} \right] | + | \end{array} \right]</math> and <math>\left[ \begin{array}{cc|c} |
a_{11} & a_{12} & 0 \\ | a_{11} & a_{12} & 0 \\ | ||
a_{21} & a_{22} & 1 \\ | a_{21} & a_{22} & 1 \\ | ||
− | \end{array} \right] | + | \end{array} \right]</math> that we can solve to get <math>\begin{bmatrix} |
x_{11} \\ | x_{11} \\ | ||
x_{21} \\ | x_{21} \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> and <math>\begin{bmatrix} |
x_{12} \\ | x_{12} \\ | ||
x_{22} \\ | x_{22} \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* but we can also put all such vectors $\mathbf x_i$ and $\mathbf e_i$ at the same time! | * but we can also put all such vectors $\mathbf x_i$ and $\mathbf e_i$ at the same time! | ||
− | ** | + | ** <math>\left[ \begin{array}{cc|cc} |
a_{11} & a_{12} & 1 & 0 \\ | a_{11} & a_{12} & 1 & 0 \\ | ||
a_{21} & a_{22} & 0 & 1 \\ | a_{21} & a_{22} & 0 & 1 \\ | ||
− | \end{array} \right] | + | \end{array} \right]</math> |
Gaussian Elimination: | Gaussian Elimination: | ||
− | * so once we have an augmented matrix | + | * so once we have an augmented matrix <math>\Big[ \ A \; \Big| \; I \ \Big] = \left[ \begin{array}{cc|cc} |
a_{11} & a_{12} & 1 & 0 \\ | a_{11} & a_{12} & 1 & 0 \\ | ||
a_{21} & a_{22} & 0 & 1 \\ | a_{21} & a_{22} & 0 & 1 \\ | ||
− | \end{array} \right] | + | \end{array} \right]</math> |
* we come from $A$ to $I$ while applying the same actions to the augmented part $I$. | * we come from $A$ to $I$ while applying the same actions to the augmented part $I$. | ||
− | * at the end we should get | + | * at the end we should get <math>\Big[ \ A \; \Big| \; I \ \Big] \to \Big[ \ I \; \Big| \; A^{-1} \ \Big]</math> |
A square $n \times n$ matrix $A$ has inverse (or $A$ is invertible) if there exists $B$ s.t. $A \times B = B \times A = I_n$
There are two types of inverses:
Suppose we have an equation $A \times A^{-1} = I$
Gaussian Elimination:
Why does it work?