% DEFINE some information that will be populated throughout the course notes.
\def \coursename {Linear Algebra}
\def \coursecode {MATH 2221}
\def \courseterm {Winter 2021}
\def \instructorname {Nathan Johnston}
% END DEFINITIONS


% IMPORT the course note formatting and templates
\input{course_notes_template}
% END IMPORT
	
	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\setcounter{chapter}{5} % Set to one less than the week number
	\chapter{Elementary Matrices \\ and Inverses}
	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	
	{\large This week we will learn about:
		
		\begin{itemize}
			\item Elementary matrices,
			\item The inverse of a matrix, and
			\item How awesome inverses are.
		\end{itemize}\bigskip\bigskip
		
		\noindent Extra reading and watching:
		\begin{itemize}
			\item Section 2.2 in the textbook
			\item Lecture videos \href{https://www.youtube.com/watch?v=5178ErHm6bE&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=22}{22}, \href{https://www.youtube.com/watch?v=UjSVdMqeXTU&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=23}{23}, \href{https://www.youtube.com/watch?v=Gt2pqIQv4g4&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=24}{24}, and \href{https://www.youtube.com/watch?v=aq6qih0mNlU&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=25}{25} on YouTube
			\item \href{https://en.wikipedia.org/wiki/Elementary_matrix}{Elementary matrix} at Wikipedia
			\item \href{https://en.wikipedia.org/wiki/Invertible_matrix}{Invertible matrix} at Wikipedia
			
		\end{itemize}\bigskip\bigskip
		
		\noindent Extra textbook problems:
		\begin{itemize}
			\item[$\star$] 2.2.1, 2.2.2
			\item[$\star \, \star$] 2.2.4--2.2.6, 2.2.8, 2.2.9, 2.2.13, 2.2.15, 2.2.20
			\item[$\star\star\star$] 2.2.7, 2.2.10, 2.2.11, 2.2.21, 2.2.22
			\item[$\skull$] 2.2.23
	\end{itemize}}
	
	
	\newpage
	
	\section*{Elementary Matrices}
	
	Last week, we learned how to solve systems of linear equations by repeatedly applying one of three row operations to the augmented matrix associated with that linear system. Remarkably, all three of those row operations can be carried out by matrix multiplication (on the left) by carefully-chosen matrices.\\
	
	For example, if we wanted to swap the first and second rows of the matrix
	
	\horlines{2}
	% some 3x4 matrix. Make it have a 0 in the top-left entry so that the next row swap gets you closer to RREF (not important from a correctness point of view, but helpful for students for pedagogical reasons)
	
	\noindent we could multiply it on the left by the matrix
	
	\horlines{2}
	% \begin{bmatrix}
	%		0 & 1 & 0 \\
	%		1 & 0 & 0 \\
	%		0 & 0 & 1
	%	\end{bmatrix}
	%
	% Then do the multiplication
	
	Similarly, to perform the row operations $\qquad \qquad \qquad \qquad \qquad$ and $\qquad \qquad \qquad \qquad \qquad$, we could multiply on the left by the matrices
	
	\horlines{6}
	% Do a "addition" and "multiplication" operation. Again, explicitly do the multiplication.
	
	\noindent Matrices that implement one of these three row operations in this way have a name:
	
	\begin{definition}[Elementary Matrices]\label{defn:elementary_matrices}
		A square matrix $A \in \M_n$ is called an \textbf{elementary matrix} if it can be obtained from the identity matrix via a single row operation.
	\end{definition}
	
	
	\newpage
	
	
	For example, the elementary matrix corresponding to the ``Swap'' row operation $R_i \leftrightarrow R_j$ looks like
	
	\horlines{3}
	% Draw it. Identity, but with row i and row j swapped.
	
	\noindent Similarly, the elementary matrices corresponding to the ``Addition'' row operation $R_i + cR_j$ and the ``Multiplication'' row operation $cR_i$ look like
	
	\horlines{3}
	% Draw them.
	
	Notice that if the elementary matrices $E_1, E_2, \ldots, E_k$ are used to row reduce a matrix $A$ to its reduced row echelon form $R$, then
	
	\horlines{1}
	%R = E_k\cdots E_2E_1A.
	
	\noindent In particular, $E_1, E_2, \ldots, E_k$ act as a log that keeps track of which row operations should be performs to put $A$ into RREF. Furthermore, if we define $E = E_k\cdots E_2E_1$, then $R = EA$, so $E$ acts as a condensed version of that log. Let's now do an example to see how to construct this matrix $E$.
	
	\exx[3]{Let $A =$\\[2cm]Find a matrix $E$ such that $EA = R$, where $R$ is the RREF of $A$.}
	% A = some 3x4 matrix. Make sure it's not square so that its RREF is non-trivial.
	% 0 & 2 & 4 & 0
	% 1 & 1 & 0 & -1
	% 3 & 4 & 2 & 1
	% Augment with identity matrix on the right and row reduce. Then check at the end that matrix on the right times A equals R
	
	
	\newpage
	
	
	\horlines{12}
	
	The fact that the method of the previous example works in general can be seen by combining some block matrix multiplication trickery with the fact that multiplication on the left by an elementary matrix is equivalent to performing the corresponding row operation. In particular, if row reducing $[ \, A \ {\color{gray}|} \ I \, ]$ to some other matrix $[ \, R \ {\color{gray}|} \ E \, ]$ makes use of the row operations corresponding to elementary matrices $E_1, E_2, \ldots, E_k$, then
	
	\horlines{1}
	% [R \ | \ E] = E_k\cdots E_2E_1[A \ | \ I] = [E_k\cdots E_2E_1A \ | \ E_k\cdots E_2E_1].
	
	\noindent This means (by looking at the right half of the above block matrix) that $E = E_k\cdots E_2E_1$, which then implies (by looking at the left half of the block matrix) that $R = EA$. We state this observation as a theorem:
	
	\begin{theorem}[Row Reduction is Multiplication on the Left]\label{thm:row_red_mult_left}
		If the block matrix $[ \, A \ {\color{gray}|} \ I \, ]$ can be row reduced to $[ \, R \ {\color{gray}|} \ E \, ]$ then... %$EA = R$.
	\end{theorem}
	
	
	\newpage
	
	
	This theorem says that, not only is performing a single row operation equivalent to multiplication on the left by an elementary matrix, but performing a \emph{sequence} of row operations is also equivalent to multiplication on the left (by some potentially non-elementary matrix).
	
	
	\section*{The Inverse of a Matrix}
	
	When working with (non-zero) real numbers, we have an operation called ``division,'' which acts as an inverse of multiplication. In particular, $a(1/a) = 1$ for all $a \neq 0$. It turns out that we can (usually) do something very similar for matrix multiplication:
	
	\begin{definition}[Inverse of a Matrix]
		If $A$ is a square matrix, the \textbf{inverse} of $A$, denoted by $A^{-1}$, is a matrix (of the same size as $A$) with the property that\\[0.3cm]
		\begin{align*}
			%{}A^{-1}A = AA^{-1} = I.
		\end{align*}
		If such a matrix $A^{-1}$ exists, then $A$ is called \textbf{invertible}.
	\end{definition}
	
	%\begin{itemize}
	%	\item Sometimes, other courses and textbooks refer to matrices that are invertible as ``non-singular'', and matrices that are not invertible are sometimes called... $\quad \quad\quad\quad\quad\quad\quad$ \\ % singular
	%	
	
	Inverses (when they exist) are unique (i.e., every matrix has at most one inverse). To see this...
	
	\horlines{5}
	% Suppose BA = AC = I (i.e., B and C are both inverses of A). Then BAC = B(AC) = B and also BAC = (BA)C = C, so B = C.
	
	\exx[4]{Show that $\begin{bmatrix}3 & -5 \\ -1 & 2\end{bmatrix}$ is the inverse of $\begin{bmatrix}2 & 5 \\ 1 & 3\end{bmatrix}$.}
	% Just do the matrix multiplication and get the identity matrix. Easy.
	% Need to mention that it works both ways.
	
	So if we are given a particular pair of matrices, it is easy to check whether or not they are inverses of each other. But how could we \emph{find} the inverse of a matrix in the first place? We'll see how soon!\\
	
	As always, let's think about what properties our new mathematical operation (matrix inversion) has.
	
	\begin{theorem}[Properties of Matrix Inverses]
		Let $A$ and $B$ be invertible matrices of the same size, and let $c$ be a non-zero real number. Then
		\begin{enumerate}
			\item $A^{-1}$ is invertible and $(A^{-1})^{-1} = A$
			\item $cA$ is invertible and $(cA)^{-1} = \frac{1}{c}A^{-1}$
			\item $A^T$ is invertible and $(A^T)^{-1} = (A^{-1})^T$
			\item $AB$ is invertible and $(AB)^{-1} = B^{-1}A^{-1}$ % NOTE THAT this is not a typo
		\end{enumerate}
	\end{theorem}
	
	\begin{proof}
		Most parts of this theorem are intuitive enough, so we just prove part~(d) (you can prove parts~(a), (b) and~(c) on your own: they're similar). To this end...
		
		\horlines{5}\vspace*{-1.35cm}
		% We have to show there exists a matrix X such that X(AB) = (AB)X = I. Choose X = B^-1A^-1 and check.
		% Mention general rule that if you have a guess for what an inverse is, it's easy to verify: just multiply and check.
	\end{proof}
	
	
	\newpage
	
	
	The fact that $(AB)^{-1} = B^{-1}A^{-1}$ (as opposed to the incorrect $(AB)^{-1} = A^{-1}B^{-1}$) is actually intuitive enough: you put on your socks before your shoes, but when reversing that operation, you take off your shoes before your socks. \\
	
	Not every matrix is invertible. For example,
	
	\horlines{2}
	% The zero matrix is not invertible (should be intuitively clear).
	% Even in the 1x1 case, not every matrix is invertible!
	
	\noindent However, there are even more exotic examples of non-invertible matrices. For example, recall that if $\u$ is a unit vector then the matrix $A = \u\u^T$...
	
	\horlines{7}
	% Projects space down onto the line in the direction of \u
	% DRAW PICTURE
	% Since multiple vectors go to the same place, not invertible (how could we ever send a vector back to where it started?)
	
	In order to come up with a general method for determining whether or not a matrix is invertible (and constructing its inverse if it exists), we first notice that if $A$ has reduced row echelon form equal to $I$, then Theorem~\ref{thm:row_red_mult_left} tells us that
	
	\horlines{2}
	% Row reducing [A | I] to [I | E] gives EA = I, so it seems like E might be the inverse of A (but doesn't prove, since this is only one-sided).
	
	It thus seems like $A$ being invertible is closely related to whether or not it can be row reduced to the identity matrix. The following theorem shows that this is indeed the case (along with a whole lot more):
	
	
	\newpage
	
	
	\begin{theorem}[Characterization of Invertible Matrices]\label{thm:invertible_characterization_one}
		Let $A \in \M_{n}$. The following are equivalent:
		\begin{enumerate}
			\item $A$ is invertible.\vspace*{-0.1cm}
			
			\item The reduced row echelon form of $A$ is $I$ (the identity matrix).\vspace*{-0.1cm}
			
			\item There exist elementary matrices $E_1, E_2, \ldots, E_k$ such that $A = E_1E_2\cdots E_k$.\vspace*{-0.1cm}
			
			\item The linear system $A\x = \b$ has a solution for all $\b \in \R^n$.\vspace*{-0.1cm}
			
			\item The linear system $A\x = \b$ has a unique solution for all $\b \in \R^n$.\vspace*{-0.1cm}
			
			\item The linear system $A\x = \0$ has a unique solution.
		\end{enumerate}
	\end{theorem}
	
	\exx[4]{Determine whether or not the matrix $A = \begin{bmatrix}1 & 2 \\ 2 & 4\end{bmatrix}$ is invertible.}
	% Row reduce, get a zero row, so does not have I as RREF, so not invertible.
	
	We won't rigorously prove the above theorem, but we'll try to give a rough idea for why some of its equivalences hold. First, notice that every elementary matrix is invertible:
	
	\horlines{6}
	
	
	\newpage
	
	
	\horlines{3}
	% Note that every row operation can be undone by a row operation of the same type.
	% Go through all 3 types in detail. Draw the matrices too.
	
	\noindent Since the product of invertible matrices is still invertible, it follows that any matrix of the form $A = E_1E_2\cdots E_k$ (where $E_1,E_2,\ldots,E_k$ are elementary) is invertible, which shows why (c) $\implies$ (a).\\
	
	The connection between invertibility and linear systems can be clarified by noting that if $A$ is invertible, then we can rearrange the linear system
	
	\horlines{1}
	% Ax = b as x = A^{-1}b. HIGHLIGHT the fact that x = A^{-1}b is the unique solution described by the theorem.
	
	\noindent Thus (a) $\implies$ (e), which implies each of (d) and (f).\\
	
	When we combine our previous two theorems, we get a method for not only determining whether or not a matrix is invertible, but also for computing its inverse if it exists:
	
	\begin{theorem}[How to Compute Inverses]
		A matrix $A \in \M_n$ is invertible if and only if the RREF of $[ \, A \ {\color{gray}|} \ I \, ]$ has the form $[ \, I \ {\color{gray}|} \ B \, ]$ for some $B \in \M_n$. If the RREF has this form then $A^{-1} = B$.
	\end{theorem}
	
	\exx[4]{Determine whether or not the matrix $A = \begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix}$ is invertible, and find its inverse if it exists.}
	% Row reduce, inverse is [-2 1;3/2, -1/2]
	
	
	\newpage
	
	
	\horlines{4}
	
	\exx[8]{Solve the linear system $x + 2y = 3$, $3x + 4y = 5$.}
	% Just multiply (2,4) by the inverse that we found on the last page [-2 1;3/2, -1/2]. Answer: (-1,2)
	% Advantage: Can change right hand side and all we need to do with matrix multiply again.
	
	\exx[6]{Find the inverse of $\begin{bmatrix}
		1 & 2 & -1 \\ 2 & 2 & 4 \\ 1 & 3 & -3
		\end{bmatrix}$ if it exists.}
	% Exists
	%  9.00000  -1.50000  -5.00000
	% -5.00000   1.00000   3.00000
	% -2.00000   0.50000   1.00000
	
	
	\newpage
	
	
	\horlines{7}
	
	\exx[6]{Find the inverse of $\begin{bmatrix}
		2 & 1 & -4 \\ -4 & -1 & 6 \\ -2 & 2 & -2
		\end{bmatrix}$ if it exists.}
	% Does not exist (zero row).
	
	Using our characterization of invertible matrices, we can prove all sorts of nice properties of them. For example, even though the definition of invertibility required that both $AA^{-1} = I$ and $A^{-1}A = I$, the following theorem shows that it is enough to just multiply on the left \emph{or} the right: you don't need to check both.
	
	\begin{theorem}[One-Sided Matrix Inverses]
		Let $A \in \M_n$ be a square matrix. If $B \in \M_n$ is a matrix such that either $AB = I$ or $BA = I$, then $A$ is invertible and $A^{-1} = B$.
	\end{theorem}
	
	
	\newpage
	
	
	\begin{proof}
		Suppose $BA = I$, and consider the equation $A\mathbf{x} = \mathbf{0}$.
		
		\horlines{7}
		% Then BAx = 0, so Ix = 0, so x = 0 is the unique solution. By characterization earlier, A is invertible. Multiplying BA = I on the right by the inverse gives B = A^-1.
		
		\noindent This completes the proof of the $BA = I$ case. Try to prove the case when $AB = I$ on your own.
	\end{proof}
	
	Similarly, we can even come up with an explicit formula for the inverse of matrices in certain small cases. For example, for $2 \times 2$ matrices, we have the following formula:
	
	\begin{theorem}[Inverse of a $\mathbf{2 \times 2}$ Matrix]\label{thm:2x2_inverse}
		Suppose $A$ is the $2 \times 2$ matrix \[A = \begin{bmatrix}
		a & b \\ c & d
		\end{bmatrix}.\]Then $A$ is invertible if and only if $ad-bc \neq 0$, and if it is invertible then\[
		A^{-1} = \frac{1}{ad-bc}\begin{bmatrix}
		d & -b \\ -c & a
		\end{bmatrix}.
		\]
	\end{theorem}
	
	
	\begin{proof}
		If $ad-bc \neq 0$ then we can show that the inverse of $A$ is as claimed just by multiplying it by $A$:
		
		\horlines{2}
		%	\begin{align*}
		%		\left(\frac{1}{ad-bc}\begin{bmatrix}
		%			d & -b \\ -c & a
		%		\end{bmatrix}\right)\begin{bmatrix}
		%			a & b \\ c & d
		%		\end{bmatrix} = \frac{1}{ad-bc}\begin{bmatrix}
		%			ad-bc & 0 \\ 0 & ad-bc
		%		\end{bmatrix} = \begin{bmatrix}
		%			1 & 0 \\ 0 & 1
		%		\end{bmatrix}.
		%	\end{align*}
		
		
		\newpage
		
		
		On the other hand, if $ad-bc = 0$ then $ad=bc$.
		
		\horlines{7}\vspace*{-1.35cm}
		%	From here we split into two cases: (i) if either $a = 0$ or $b = 0$ then $ad=bc$ implies that two of the entries of $A$ in the same row or column are both $0$, so $A$ can be row reduced so as to have a zero row and thus is not invertible, or (ii) if $a,b \neq 0$ then $ad=bc$ implies $d/b = c/a$, so the second row of $A$ is a multiple of its first row, so again it can be row reduced so as to have a zero row and thus is not invertible.
	\end{proof}
	
	\exx[9]{Compute the inverse (or show that none exists) of the following matrices:}
	% Ask for some matrices from class. Purposely make one non-invertible. Maybe do 2 or 3
	
	\noindent Keep in mind that you can always use the general method of computing inverses (row reduce $[ \, A \ {\color{gray}|} \ I \, ]$ to $[ \, I \ {\color{gray}|} \ A^{-1} \, ]$) if you forget this formula for the $2 \times 2$ case.
\end{document}