Differences

This shows you the differences between two versions of the page.

--- lecture_10_slides [2016/02/29 19:08] – rupert
+++ lecture_10_slides [2017/02/21 10:04] (current) – rupert
@@ Line 1: / Line 1: @@
 ~~REVEAL~~
-==== Last time ====
-{{page>the inverse}}
+===== Matrix equations =====
-  * $\def\mat#1{\left[\begin{smallmatrix}#1\end{smallmatrix}\right]}A=\mat{2&4\\0&1}$ is invertible, and $A^{-1}=\mat{\tfrac12&-2\\0&1}$.
+  * A linear equation can be written using [[row-column multiplication]].
-    * i.e. $\mat{2&4\\0&1}^{-1}=\mat{\tfrac12&-2\\0&1}$
+  * e.g. $ \newcommand{\m}[1]{\left[\begin{smallmatrix}#1\end{smallmatrix}\right]} 2x-3y+z=8$ is same as $ \m{2&-3&1}\m{x\\y\\z}=8$
-  * if $a$ is a non-zero scalar, then $[a]^{-1}=[\tfrac 1a]$
+  * or $ a\vec x=8$ where $a=\m{2&-3&1}$ and $\vec x=\m{x\\y\\z}$.
-  * $I_n^{-1}=I_n$ for any $n$
-  * $0_{n\times n}^{-1}$, $\mat{1&0\\0&0}^{-1}$ and $\mat{1&2\\-3&-6}^{-1}$ **do not exist**
-    * because these matrices aren't invertible
-==== Warning ====
-If $A$, $B$ are matrices, then $\frac AB$ doesn't make sense!
+==== ====
+  * We can write a whole [[system of linear equations]] in a similar way, as a matrix equation using [[matrix multiplication]].
+  * e.g. the linear system $\begin{align*} 2x-3y+z&=8\\ y-z&=4\\x+y+z&=0\end{align*}$
-  * Never write this down as it will almost always lead to mistakes.
+  * is same as $\m{2&-3&1\\0&1&-1\\1&1&1}\m{x\\y\\z}=\m{8\\4\\0}$
-  * In particular, $A^{-1}$ definitely doesn't mean $\frac 1A$. Never write this either!
+  * or $ A\vec x=\vec b$ where $A=\m{2&-3&1\\0&1&-1\\1&1&1}$, $\vec x=\m{x\\y\\z}$ and $\vec b=\m{8\\4\\0}$.
-==== Proposition: solving $AX=B$ when $A$ is invertible ====
+==== ====
-If $A$ is an invertible $n\times n$ matrix and $B$ is an $n\times k$ matrix, then $ AX=B$ has a unique solution: $X=A^{-1}B$.
+In a similar way, any linear system \begin{align*} a_{11}x_1+a_{12}x_2+\dots+a_{1m}x_m&=b_1\\ a_{21}x_1+a_{22}x_2+\dots+a_{2m}x_m&=b_2\\ \hphantom{a_{11}}\vdots \hphantom{x_1+a_{22}}\vdots\hphantom{x_2+\dots+{}a_{nn}} \vdots\ & \hphantom{{}={}\!} \vdots\\ a_{n1}x_1+a_{n2}x_2+\dots+a_{nm}x_m&=b_n \end{align*}
+can be written in the form
+\[ A\vec x=\vec b\]
+where $A$ is the $n\times m $ matrix, called the **coefficient matrix** of the linear system, whose $(i,j)$ entry is $a_{ij}$ (the number in front of $x_j$ in the $i$th equation of the system).
-=== Proof ===
+==== Solutions of matrix equations ====
-  * First check that $X=A^{-1}B$ really is a solution:
+  * More generally, might want to solve a matrix equation like \[AX=B\] where $A$, $X$ and $B$ are matrices of any size, with $A$ and $B$ fixed matrices and $X$ a matrix of unknown variables.
-    * $AX=A(A^{-1}B)=(AA^{-1})B=I_nB=B$ :-)
+  * If $A$ is $n\times m$, we need $B$ to be $n\times k$ for some $k$, and then $X$ must be $m\times k$
-  * Uniqueness: suppose $X$ and $Y$ are both solutions
+    * so we know the size of any solution $X$.
-  * Then $AX=B$ and $AY=B$, so $AX=AY$.
+  *  But which $m\times k$ matrices $X$ are solutions?
-  * Multiply both sides on the left by $A^{-1}$:
-    * $A^{-1}AX=A^{-1}AY$, or $I_nX=I_n Y$, or $X=Y$.
-  * So any two solutions are equal.■
-==== Corollary ====
+==== Example ====
-If $A$ is an $n\times n$ matrix and there is a non-zero $n\times m$ matrix $K$ so that $AK=0_{n\times m}$, then $A$ is not invertible.
+If $A=\m{1&0\\0&0}$ and $B=0_{2\times 3}$, then any solution $X$ to $AX=B$ must be $2\times 3$.
-=== Proof ===
+  * One solution is $X=0_{2\times 3}$
+    *  because then we have $AX=A0_{2\times 3}=0_{2\times 3}$.
+  * This is not the only solution!
+  * For example, $X=\m{0&0&0\\1&2&3}$ is another solution
+    * because then we have $AX=\m{1&0\\0&0}\m{0&0&0\\1&2&3}=\m{0&0&0\\0&0&0}=0_{2\times 3}.$
-  * $AX=0_{n\times m}$ has (at least) two solutions:
+  * So a matrix equation can have more than one solution.
-    * $X=K$,
-    * and $X=0_{n\times m}$
-  * If $A$ was invertible, this would contradict the Proposition.
-  * So $A$ cannot be invertible. ■
 ==== Example ====
-  * Let $A=\mat{1&2\\-3&-6}$. $A$ isn't invertible... why?
+  * Let $A=\m{2&4\\0&1}$
-  * One column of $A$ is $2$ times the other... exploit this.
+  * and $B=\m{3&4\\5&6}$
-  * Let $K=\mat{-2\\1}$
+  * Solve $AX=B$ for $X$
-  * $K$ is non-zero but $AK=\mat{1&2\\-3&-6}\mat{-2\\1}=\mat{0\\0}=0_{2\times 1}$
-  * So $A$ is not invertible, by the Corollary.
+  * $X$ must be $2\times 2$
+  * $X=\m{x_{11}&x_{12}\\x_{21}&x_{22}}$
+  * Do some algebra to solve for $X$
+  * ...
+  * Is there a quicker way?
 ==== Example ====
-  * $A=\mat{1&4&5\\2&5&7\\3&6&9}$ is not invertible
+  * Consider $AX=B$, where
-    * $X=\mat{1\\1\\-1}$ is non-zero
+    * $A=\def\m#1{\left[\begin{smallmatrix}#1\end{smallmatrix}\right]}\m{1&0\\0&0}$
-    * and $AX=0_{3\times 1}$.
+    * $B=0_{2\times 3}$,
-===== $2\times 2$ matrices: determinants and invertibility =====
+  * i.e. $\m{1&0\\0&0}X=\m{0&0&0\\0&0&0}$
+  * then any solution $X$ to $AX=B$ must be $2\times 3$.
+  * One solution is $X=0_{2\times 3}$
+  * Are there any more?
+  * Yes! e.g. $X=\m{0&0&0\\1&2&3}$
+  * So a matrix equation can have more than one solution.
-==== Question ====
+===== Invertibility ======
-Which $2\times 2$ matrices are invertible? For the invertible matrices, can we find their inverse?
+==== Example ====
+  * Take $A=\def\mat#1{\m{#1}}\mat{2&4\\0&1}$ and $B=\mat{3&4\\5&6}$, consider $AX=B$
+  * $\mat{2&4\\0&1}X=\mat{3&4\\5&6}$
+  * $X$ must be $2\times 2$ matrix
+  * One way to solve: write $X=\mat{x_{11}&x_{12}\\x_{21}&x_{22}}$
+  * Plug in and do matrix multiplication: $\mat{2x_{11}+4x_{21}&2 x_{12}+4x_{22}\\x_{21}&x_{22}}=\mat{3&4\\5&6}$
+  * Get four linear equations: $\begin{align*}2x_{11}+4x_{21}&=3\\2 x_{12}+4x_{22}&=4\\x_{21}&=5\\x_{22}&=6\end{align*}$
+  * Can solve in the usual way....
+  * Tedious! Can we do better?
-==== Lemma ====
+==== Simpler: $1\times 1$ matrix equations ====
-If $A=\mat{a&b\\c&d}$ and $J=\mat{d&-b\\-c&a}$, then we have
+  * Let $a,b$ be ordinary numbers ($1\times 1$ matrices) with $a\ne0$. How do we solve $ax=b$?
-\[ AJ=\delta I_2=JA\]
+  * Answer: multiply both sides by $a^{-1}$
-where $\delta=ad-bc$.
+    * (for numbers, $a^{-1}$ is same as $\tfrac1a$)
+  * Solution: $x=a^{-1}b$.
-  * Proof is a calculation!
+  * Why does this work?
+  * If $x=\tfrac1a\cdot b$, then $ax=a(\tfrac1a\cdot b)=(a\cdot \tfrac1a)b=1b=b$
+  * so $ax$ really is equal to $b$
+  * We do have a solution to $ax=b$.
-==== Definition: the determinant of a $2\times 2$ matrix ====
+==== Thinking about $a^{-1}$ for $a$ a number ====
-{{page>determinant of a 2x2 matrix}}
+  * What is special about $a^{-1}$ which made this all work?
+  * Write $c=a^{-1}$
-==== Theorem: the determinant determines the invertibility (and inverse) of a $2\times 2$ matrix ====
+  * $1b=b$, and $a c = 1$
+  * so $ x=cb$ has $ax=acb=1b=b$ :-)
-Let $A=\mat{a&b\\c&d}$ be a $2\times 2$ matrix.
+==== What about matrices? ====
-  - $A$ is invertible if and only if $\det(A)\ne0$.
+  * Can we do something similar for an $n\times n$ matrix $A$?
-  - If $A$ is invertible, then $A^{-1}=\frac{1}{\det(A)}\mat{d&-b\\-c&a}$.
+  * i.e. find a matrix $C$ with similar properties?
+    * Replace $1$ with $I_n$
+    * Then $I_nB=B$
+    * So if we had a matrix $C$ with $CA=I_n$...
+    * Then $X=CB$ would have $AX=ACB=I_nB=B$ :-)
+  * The key property of $C$ is that $AC=I_n$.
+  * Turns out we also want $CA=I_n$
-==== Proof ====
+==== Example revisited ====
+  * Let $A=\mat{2&4\\0&1}$
+  * The matrix $C=\mat{\tfrac12&-2\\0&1}$ **does** have the property\[ C A =I_2= AC.\]
+  * Check this!
+  * Multiply both sides of $AX=B$ on the left by $C$ and use $CA=I_2$:
+  * Get $X=CB=\mat{\tfrac12&-2\\0&1}\mat{3&4\\5&6} = \mat{-8.5&-10\\5&6}$.
+  * This is quicker than solving lots of equations
+    * although we don't yet know how to **find** $C$ from $A$
+  * Also, if we change $B$ we can easily find solutions to the new equation
-  * true for $A=0_{2\times 2}$!
+==== Definition: invertible ====
-  * Now suppose $A\ne0_{2\times 2}$. Let $J=\mat{d&-b\\-c&a}$.
-  * By the previous lemma, $AJ=(\det(A))I_2=JA$.
-  * If $\det(A)\ne0$, multiply by $\frac1{\det(A)}$ and write $B=\tfrac1{\det(A)}J$: \[ AB= A(\tfrac1{\det(A)}J)=I_2=(\tfrac1{\det(A)}J) A=BA\]
-  * So $ AB=I_2=BA$, so $A$ invertible with inverse $B=\frac1{\det(A)}J=\frac1{\det(A)}\mat{d&-b\\-c&a}$.
-  * If $\det(A)=0$, then $AJ=0_{2\times 2}$  and $J\ne 0_{2\times2}$ [why?]
+{{page>invertible}}
-  * Hence by the previous corollary, $A$ is not invertible in this case.  ■
-====== The transpose of a matrix ======
+==== Examples ====
-We defined this in tutorial sheet 4:
+  * $A=\mat{2&4\\0&1}$ is invertible, and $C=\mat{\tfrac12&-2\\0&1}$ is an inverse
+  * a $1\times 1$ matrix $A=[a]$ is invertible if and only if $a\ne0$, and if $a\ne0$ then an inverse of $A=[a]$ is $C=[\tfrac1a]$.
+  * $I_n$ is invertible for any $n$, with inverse $I_n$
+  * $0_{n\times n}$ is not invertible for any $n$... why?
+  * $A=\mat{1&0\\0&0}$ is not invertible... why?
+  * $A=\mat{1&2\\-3&-6}$ is not invertible. We'll see why later!
-{{page>transpose}}
+==== Proposition: uniqueness of the inverse ====
-==== Exercise: simple properties of the transpose ====
+If $A$ is an invertible $n\times n$ matrix, then $A$ has a //unique// inverse.
-Prove that for any matrix $A$:
-  * $(A^T)^T=A$; and
+=== Proof ===
-  * $(A+B)^T=A^T+B^T$ if $A$ and $B$ are matrices of the [[same size]]; and
+  * $A$ invertible, so $A$ has at least one inverse.
-  * $(cA)^T=c(A^T)$ for any [[scalar]] $c$.
+  * Suppose it has two inverses, say $C$ and $D$.
+  * Then $AC=I_n=CA$ and $AD=I_n=DA$.
-In tutorial sheet 4, we proved:
+  * So $C=CI_n=C(AD)=(CA)D=I_nD=D$
+  * So $C=D$.
+  * So any two inverses of $A$ are equal.
+  * So $A$ has a unique inverse.■
-==== Lemma: transposes and row-column multiplication ====
+==== Definition/notation: $A^{-1}$ ====
-If $a$ is a $1\times m$ row vector and $b$ is an $m\times 1$ column vector, then
+{{page>the inverse}}
-\[ ab=b^Ta^T.\]
+==== Examples again ====
+  * $A=\mat{2&4\\0&1}$ is invertible, and $A^{-1}=\mat{\tfrac12&-2\\0&1}$.
+    * i.e. $\mat{2&4\\0&1}^{-1}=\mat{\tfrac12&-2\\0&1}$
+  * if $a$ is a non-zero scalar, then $[a]^{-1}=[\tfrac 1a]$
+  * $I_n^{-1}=I_n$ for any $n$
+  * $0_{n\times n}^{-1}$, $\mat{1&0\\0&0}^{-1}$ and $\mat{1&2\\-3&-6}^{-1}$ **do not exist**
+    * because these matrices aren't invertible
+==== Warning ====
-==== Examples ====
+If $A$, $B$ are matrices, then $\frac AB$ doesn't make sense!
-  * $\det\mat{2&3\\-4&-6}=2(-6)-3(-4)=-12-(-12)=0$
+  * Never write this down as it will almost always lead to mistakes.
-    *  so $\mat{2&3\\-4&-6}$ is not invertible.
+  * In particular, $A^{-1}$ definitely doesn't mean $\frac 1A$. Never write this either!
-  * $\det\mat{2&3\\-4&5}=2(5)-3(-4)=10-(-12)=22\ne0$
-    * so $\mat{2&3\\-4&5}$ is invertible
-    * with inverse \[\mat{2&3\\-4&5}^{-1}=\frac1{22}\mat{5&-3\\4&2} = \mat{\frac 5{22}&-\frac3{22}\\\frac2{11}&\frac1{11}}.\]
+==== Proposition: solving $AX=B$ when $A$ is invertible ====
-==== Observation: the transpose swaps rows with columns ====
+If $A$ is an invertible $n\times n$ matrix and $B$ is an $n\times k$ matrix, then $ AX=B$ has a unique solution: $X=A^{-1}B$.
-Formally, for any matrix $A$ and any $i,j$, we have
+=== Proof ===
-\begin{align*}\def\col#1{\text{col}_{#1}}\def\row#1{\text{row}_{#1}}
-\row i(A^T)&=\col i(A)^T\\\col j(A^T)&=\row j(A)^T
-.\end{align*}
-==== Theorem: the transpose reverses the order of matrix multiplication ====
+  * First check that $X=A^{-1}B$ really is a solution:
+    * $AX=A(A^{-1}B)=(AA^{-1})B=I_nB=B$ :-)
+  * Uniqueness: suppose $X$ and $Y$ are both solutions
+  * Then $AX=B$ and $AY=B$, so $AX=AY$.
+  * Multiply both sides on the left by $A^{-1}$:
+    * $A^{-1}AX=A^{-1}AY$, or $I_nX=I_n Y$, or $X=Y$.
+  * So any two solutions are equal.
+  * So $AX=B$ has a unique solution.■
-If $A$ and $B$ are matrices and the [[matrix product]] $AB$ is defined, then $B^TA^T$ is also defined. Moreover, in this case we have
+==== Corollary ====
-\[ (AB)^T=B^TA^T.\]
+If $A$ is an $n\times n$ matrix and there is a non-zero $n\times m$ matrix $K$ so that $AK=0_{n\times m}$, then $A$ is not invertible.
 === Proof ===
-If $AB$ is defined, then $A$ is $n\times m$ and $B$ is $m\times k$ for some $n,m,k$, so $B^T$ is $k\times m$ and $A^T$ is $m\times n$, so $B^TA^T$ is defined. Moreover, in this case $B^TA^T$ is an $k\times n$ matrix, and $AB$ is an $n\times k$ matrix, so $(AB)^T$ is a $k\times n$ matrix. Hence $B^TA^T$ has the same size as $(AB)^T$. To show that they are equal, we calculate, using the fact that the transpose swaps rows with columns:
+  * $AX=0_{n\times m}$ has (at least) two solutions:
-\begin{align*}
+    * $X=K$,
-\text{the }(i,j)\text{ entry of }(AB)^T&= \text{the }(j,i)\text{ entry of }AB
+    * and $X=0_{n\times m}$
-\\&= \row j(A)\cdot\col i(B)
+  * If $A$ was invertible, this would contradict the Proposition.
-\\&=\col i(B)^T\cdot \row j(A)^T \quad\text{by the previous Lemma}
+  * So $A$ cannot be invertible. ■
-\\&=\row i(B^T)\cdot \col j(A^T) \quad\text{by the Observation}
-\\&=\text{the }(i,j)\text{ entry of }B^TA^T
+==== Example ====
-\end{align*}
-Hence $(AB)^T=B^TA^T$. ■
+  * Let $A=\mat{1&2\\-3&-6}$. $A$ isn't invertible... why?
+  * One column of $A$ is $2$ times the other... exploit this.
+  * Let $K=\mat{-2\\1}$
+  * $K$ is non-zero but $AK=\mat{1&2\\-3&-6}\mat{-2\\1}=\mat{0\\0}=0_{2\times 1}$
+  * So $A$ is not invertible, by the Corollary.
+  * Next time: a more systematic way to determine when a matrix is invertible: **determinants**