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$

- If $B$ exists, then it's denoted $A^{-1}$
- $A$ in such case is called
*non-singular* - otherwise (no $A^{-1}$ exists) $A$ is called
*singular*

There are two types of inverses:

- left and right
- $\underbrace{A \times A^{-1}}_\text{left} = I_n = \underbrace{A^{-1} \times A}_\text{right}$
- for square matrices left and right inverses are equal

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$
- [math]A \times X = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix} \times \begin{bmatrix} x_{11} & x_{12} \\ x_{21} & x_{22} \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I[/math]
- one idea: Solve $n$ different systems of linear equations
- [math]\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix} \times \begin{bmatrix} x_{11} \\ x_{21} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}[/math] and
- [math]\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix} \times \begin{bmatrix} x_{12} \\ x_{22} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \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$)

- 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
- we'll have several augmented matrices like [math]\left[ \begin{array}{cc|c} a_{11} & a_{12} & 1 \\ a_{21} & a_{22} & 0 \\ \end{array} \right][/math] and [math]\left[ \begin{array}{cc|c} a_{11} & a_{12} & 0 \\ a_{21} & a_{22} & 1 \\ \end{array} \right][/math] that we can solve to get [math]\begin{bmatrix} x_{11} \\ x_{21} \\ \end{bmatrix}[/math] and [math]\begin{bmatrix} x_{12} \\ x_{22} \\ \end{bmatrix}[/math]

- 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_{21} & a_{22} & 0 & 1 \\ \end{array} \right][/math]

Gaussian Elimination:

- 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_{21} & a_{22} & 0 & 1 \\ \end{array} \right][/math]
- we come from $A$ to $I$ while applying the same actions to the augmented part $I$.
- at the end we should get [math]\Big[ \ A \; \Big| \; I \ \Big] \to \Big[ \ I \; \Big| \; A^{-1} \ \Big][/math]

Why does it work?

- suppose you did your elimination on $A$ alone, so you obtained $EA = I$ (assume no row exchanges)
- let's apply $E$ to augmented $\Big[ \ A \; \Big| \; I \ \Big]$.
- $E \times \Big[ \ A \; \Big| \; I \ \Big] = \Big[ \ EA \; \Big| \; EI \ \Big] = \Big[ \ I \; \Big| \; E \ \Big]$
- what is $E$? Since $EA = I$ we know that it can be only when $E = A^{-1}$
- so we finally have $\Big[ \ I \; \Big| \; A^{-1} \ \Big]$

- We can compute the inverse of $A$ using the following formula:
- $A^{-1} = \cfrac{1}{| A |} C^T$
- where $|A|$ is the Determinant of $A$ and $C^T$ is the Cofactors matrix

- $(AB)^{-1} = B^{-1} A^{-1}$
- $(A^{-1})^T = (A^T)^{-1}$

- Linear Algebra MIT 18.06 (OCW)
- http://en.wikipedia.org/wiki/Invertible_matrix
- Курош А.Г. Курс Высшей Алгебры