% 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}{8} % Set to one less than the week number \chapter{Determinants} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% {\large This week we will learn about: \begin{itemize} \item Determinants of matrices, and \item That's it. Determinants, determinants, determinants. \end{itemize}\bigskip\bigskip \noindent Extra reading and watching: \begin{itemize} \item Section 3.2 in the textbook \item Lecture videos \href{https://www.youtube.com/watch?v=1Jkzf54lyXQ&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=34}{34}, \href{https://www.youtube.com/watch?v=MU7vS4ixDLA&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=35}{35}, and \href{https://www.youtube.com/watch?v=wbu3deAxuEA&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=36}{36} on YouTube \item \href{http://en.wikipedia.org/wiki/Determinant}{Determinant} at Wikipedia \end{itemize}\bigskip\bigskip \noindent Extra textbook problems: \begin{itemize} \item[$\star$] 3.2.1, 3.2.3, 3.2.4, 3.2.9 \item[$\star \, \star$] 3.2.5--3.2.8, 3.2.10, 3.2.12, 3.2.17 \item[$\star\star\star$] 3.2.14, 3.2.16, 3.2.18 \item[$\skull$] 3.2.19--3.2.21 \end{itemize}} \newpage We now introduce one of the most important properties of a matrix: its \textbf{determinant}, which roughly is a measure of how ``large'' the matrix is. More specifically, recall that... \horlines{6} % every matrix A can be thought of as a linear transformation that sends v to Av. That linear transformation sends the unit square (or cube, or hypercube, ...) with sides $\e_1, \e_2, \ldots, \e_n$ to the parallelogram (or parallelopiped\index{parallelopiped}, or hyperparallelopiped, ...) with side vectors equal to the columns of A: $A\e_1, A\e_2, \ldots, A\e_n$ % DRAW 2D PICTURE The determinant of $A$, which we denote by $\det(A)$, is the area (or volume) of this image of the unit hypercube. In other words, it measures how much $A$ expands space when acting as a linear transformation. \horlines{5} %it is the ratio %\frac{volume of output region}{volume of input region}. %Since linear transformations behave so uniformly on $\R^n$, this definition does not rely specifically on using the unit square as the input to $A$---if $A$ doubles the area of the unit square (i.e., det(A) = 2), then it also doubles the area of any square, and in fact it doubles the area of any region. % DRAW PICTURE with some other region having its area doubled too, like picture in the textbook \noindent Let's now start looking at some of the properties of determinants, so that we can (eventually!) learn how to compute it. \section*{Definition and Basic Properties} Before we even properly define the determinant, let's think about some properties that it should have. The first important property is that, since the identity matrix does not stretch or shrink $\R^n$ at all... \horlines{1} % $\det(I) = 1$ \newpage Next, since every $A \in \mathcal{M}_n$ expands space by a factor of $\det(A)$, and similarly each $B \in \mathcal{M}_n$ expands space by a factor of $\det(B)$... \horlines{3} % AB must stretch space by the product of these two factors. That is, $\det(AB) = \det(A)\det(B)$ for all $A,B \in \mathcal{M}_n$. We will also need one more property of determinants, which is a bit more difficult to see. What happens to $\det(A)$ if we multiply one of the columns of $A$ by a scalar $c \in \R$? \horlines{7} % Geometrically, this corresponds to multiplying one of the sides of the image of the unit square by $c$, which in turn scales the area of that image by $c$. That is, we have $\det\big([\ \a_1 \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ c\a_i \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_n \ ]\big) = \ c\cdot\det\big([\ \a_1 \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_i \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_n \ ]\big)$. % DRAW PICTURE \noindent Similarly, if we add a vector to one of the columns of a matrix, then... \horlines{8} % corresponds geometrically to adding that vector to one of the side vectors of the output parallelogram, while leaving all of the other sides alone. Thus we should expect that the area of this parallelogram is the sum of the areas of the two individual parallelograms: %\begin{align*} % & \det\big([\ \a_1 \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \v + \w \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_n \ ]\big) \\ % & \qquad = \det\big([\ \a_1 \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \v \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_n \ ]\big) + \det\big([\ \a_1 \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \w \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_n \ ]\big). %\end{align*} % DRAW PICTURE, but harder to draw :( % INSTEAD, insert week9/determinant_multilinear.png \newpage In other words, the determinant is linear in the columns of a matrix (sometimes called \textbf{multilinearity}). We now \emph{define} the determinant to be the function that satisfies this multilinearity property, as well as the other two properties that we demonstrated earlier: \begin{definition}[Determinant]\label{defn:determinant} The \textbf{determinant} is the (unique!) function $\det : \mathcal{M}_n \rightarrow \mathbb{R}$ that satisfies the following three properties: \begin{enumerate}[label=\alph*)] \item $\det(I) = 1$, \item $\det(AB) = \det(A)\det(B)$ for all $A,B \in \mathcal{M}_n$, and \item for all $c \in \R$ and all $\v,\w,\a_1,\a_2,\ldots,\a_n \in \R^n$, it is the case that\vspace*{-0.2cm} \begin{align*} & \det\big([\ \a_1 \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \v + c\w \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_n \ ]\big) \\ & \quad \ \ = \det\big([\ \a_1 \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \v \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_n \ ]\big) + c\cdot\det\big([\ \a_1 \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \w \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ \a_n \ ]\big). \end{align*} \end{enumerate} \end{definition} \exx[5]{Compute the determinant of the matrix $A = \begin{bmatrix}2 & 0 \\ 0 & 3\end{bmatrix}$.} % use property (c) twice and then property (a). det = 6 % stretches by 2 in one direction, 3 in other, draw picture Let's start looking at some of the basic properties of the determinant. First, if $A \in \mathcal{M}_n$ is invertible then properties~(a) and~(b) tell us that \horlines{3} % 1 = \det(I) = \det(AA^{-1}) = \det(A)\det(A^{-1}), so det(A) \neq 0 and det(A^-1) = 1/det(A). \newpage This makes sense geometrically, since if $A$ expands space by a factor of $\det(A)$ then \horlines{7} % $A^{-1}$ must shrink it back down by that same amount. % DRAW PICTURE (A^-1 just moves space back to where it started) \noindent On the other hand, if $A$ is not invertible, then \horlines{7} % it squishes all of $\R^n$ down into some $(n-1)$-dimensional (or smaller) subspace. Thus $A$ squashes the unit cube until something that is ``flat'' and thus has $0$ volume (for example, a $1$-dimensional line in $\R^2$ has $0$ area, a $2$-dimensional plane in $\R^3$ has $0$ volume, and so on). Thus if A not invertible then det(A) = 0 % DRAW picture of matrix squashing R2 into a line \noindent We summarize our observations about the determinant of invertible and non-invertible matrices in the following theorem: \begin{theorem}[Determinants and Invertibility]\label{thm:determinant_inverse} Suppose $A \in \mathcal{M}_n$. Then $A$ is invertible if and only if $\det(A) \neq 0$, and if it is invertible then $\det(A^{-1}) = 1/\det(A)$. \end{theorem} \newpage There are also a few other basic properties of determinants that are useful to know, so we state them here (but for time reasons we do not explicitly prove them): \begin{theorem}[Other Properties of the Determinant]\label{thm:det_properties} Suppose $A \in \mathcal{M}_n$ and $c \in \R$. Then \begin{enumerate}[label=\alph*)] \item $\det(cA) = c^n\det(A)$, and \item $\det(A^T) = \det(A)$. \end{enumerate} \end{theorem} % GIVE GEOMETRIC intuition for why (a) holds: stretches in each of n directions by a factor of c \exx[6]{Suppose $A,B \in \mathcal{M}_3$ are matrices with $\det(A) = 2$ and $\det(B) = 5$. Compute...} % Things like det(AB^2), det(2A^TB^{-1}). Use previous properties. Be careful with scalars! 2 in the second example here pulls out in front as 2^3 \section*{Computation} In order to come up with a general method of computing the determinant, we start by computing it on elementary matrices.\\ \noindent \hrule\vspace*{1.25em} The elementary matrix corresponding to the row operation $cR_i$ has the form \horlines{4} % Identity, but with c in one of the diagonal entries \newpage \noindent This matrix has determinant equal to... \horlines{4} % By defining property (c) of determinants, has determinant c. % Also DRAW PICTURE. Just stretches in one direction by factor of c. \noindent \hrule\vspace*{1.25em} The elementary matrix corresponding to the row operation $R_i + cR_j$ has the form \horlines{4} % Identity, but with c instead of 0 in (i,j)-entry. \noindent This matrix has determinant equal to... \horlines{4} % By defining property (c) of determinants, has determinant 1. Can split into det(I) + cdet(B), where B is a matrix with a repeated column and thus determinant 0. \noindent \hrule\vspace*{1.25em} The elementary matrix corresponding to the row operation $R_i \leftrightarrow R_j$ has the form \horlines{4} % Identity, but with two rows swapped. \newpage \noindent This matrix has determinant equal to... \horlines{4} % Start off by computing \det\([ \e_1 | ... | \e_i + \e_j | ... | \e_i + \e_j | ... | \e_n ]), but use multilinearity to split it up. Will be left with det(I) + det(swap) + det(non-inv) + det(non-inv) = 0, so det(swap) = -1. \noindent \hrule\vspace*{1.25em} Wait, so the determinant of a matrix can be \textbf{\emph{negative}}? But it measures area/volume! \horlines{5} % No, it measures *signed* area/volume. |det(A)| is the area/volume, and sign tells us whether or not A flips the orientation of space. % Analogous to definite integrals -- we add areas above axis, subtract areas below (DRAW PICTURE). Necessary if we want integrals/determinants to have nice mathematical properties. Since multiplication on the left by an elementary matrix corresponds to performing a row operation, we can rephrase our above calculations as the following theorem: \begin{theorem}[Computing Determinants via Row Operations]\label{thm:det_compute_rref} Suppose $A,B \in \mathcal{M}_n$. If $B$ is obtained from $A$ via a single row operation, then their determinants are related as follows: \begin{enumerate}[label=\alph*),leftmargin=3.4\parindent] \item[$cR_i$:] $\det(B) = c\cdot\det(A)$, \item[$R_i + cR_j$:] $\det(B) = \det(A)$, and \item[$R_i \leftrightarrow R_j$:] $\det(B) = -\det(A)$. \end{enumerate} \end{theorem} % Proof: Write B = EA, where E is the elementary matrix corresponding to the row operation. Then det(B) = det(EA) = det(E)det(A), and we computed det(E) earlier The above theorem gives us everything we need to know to be able to compute determinants in general -- row reduce $A$ to $I$, keeping track of the row operations that we performed along the way, and use the fact that $\det(I) = 1$. If we cannot row reduce to $I$, then $A$ is not invertible, so $\det(A) = 0$. \newpage \exx[8]{Compute the determinant of $A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix}$.}\vspace*{-0.6cm} % When multiplying a row by a scalar, we have to *DIVIDE* the determinant of the resulting triangular matrix by that scalar to get back to the determinant of the original matrix. % IMPORTANT: Do not get zeros above diagonal until AFTER getting to REF, since this leads into next theorem. % Answer is 2 In the previous example, the determinant of the row echelon form ended up being the product of its diagonal entries. We now state this observation as a theorem: \begin{theorem}[Determinant of a Triangular Matrix]\label{thm:det_triangular} Let $A \in \mathcal{M}_n$ be a triangular matrix. Then $\det(A)$ is the product of its diagonal entries: \[\det(A) = a_{1,1}a_{2,2}\cdots a_{n,n}.\] \end{theorem} \begin{proof} The idea is that a triangular matrix can be row-reduced to $I$ just by operations of the form $R_i + cR_j$ (which do not affect the determinant) and $(1/a_{1,1})R_1$, $\ldots$, $(1/a_{n,n})R_n$: \horlines{5}\vspace*{-1.3cm} % Draw upper triangular matrix and how to row reduce last column % Mention how you would then do it for second-to-last column, and so on. \end{proof} \newpage By using this fact, we can compute determinants a bit more quickly, by just row-reducing to row echelon form (instead of \emph{reduced} row echelon form). This method is best illustrated with another example. \exx[13]{Compute the determinant of $A = \begin{bmatrix} 1 & 2 & 3 & 0 \\ 1 & 1 & 2 & 3 \\ 0 & -1 & 1 & 0 \\ 0 & -1 & 3 & 0 \end{bmatrix}$.} % just row reduce to REF, not RREF, then note that determinant of REF is product of diagonal entries. % Answer is -6 \section*{Explicit Formulas and Cofactor Expansions} Remarkably, the determinant can be computed via an explicit formula just in terms of multiplication and addition of the entries of the matrix. Before presenting the general formula for $n \times n$ matrices, let's start with what it looks like for $2 \times 2$ matrices. \newpage \begin{theorem}[Determinant of $\mathbf{2 \times 2}$ Matrices]\label{thm:det_2x2} The determinant of a $2 \times 2$ matrix is given by \[\det\left(\begin{bmatrix}a & b \\ c & d\end{bmatrix}\right) = ad-bc.\] \end{theorem} \begin{proof} We prove this theorem by making use of multilinearity (i.e., defining property~(c) of the determinant): \horlines{2} %\det([a & b \\ c & d]) = \det([a & b \\ 0 & d]) + \det([0 & b \\ c & d]), % since the two matrices on the right differ only in their leftmost column. \noindent Well, \horlines{5} % \det([a & b \\ 0 & d]) = ad (since upper triangular) % det([0 & b \\ c & d]) = -\det([c & d \\ 0 & b]) = -bc, (swap and then upper triangular) Adding these two quantities together gives the desired formula. \end{proof} The above theorem is perhaps best remembered in terms of diagonals of the matrix -- the determinant of a $2 \times 2$ matrix is the product of its forward diagonal minus the product of its backward diagonal. \exx[3]{Compute the determinant of $A = \begin{bmatrix}1 & 2 \\ 3 & 4\end{bmatrix}$.} \newpage The formula for the determinant of a $3 \times 3$ matrix is somewhat more complicated: \begin{theorem}[Determinant of $\mathbf{3 \times 3}$ Matrices]\label{thm:det_3x3} The determinant of a $3 \times 3$ matrix is given by \[\det\left(\begin{bmatrix}a & b & c \\ d & e & f \\ g & h & i\end{bmatrix}\right) = aei + bfg + cdh - afh - bdi - ceg.\] \end{theorem} \begin{proof} Again, we make use of multilinearity (i.e., defining property~(c) of the determinant) to write \horlines{3}\vspace*{-0.4cm} % \det\left(\begin{bmatrix}a & b & c \\ d & e & f \\ g & h & i\end{bmatrix}\right) \\ %& \qquad \qquad = \det\left(\begin{bmatrix}a & b & c \\ 0 & e & f \\ 0 & h & i\end{bmatrix}\right) + \det\left(\begin{bmatrix}0 & b & c \\ d & e & f \\ 0 & h & i\end{bmatrix}\right) + \det\left(\begin{bmatrix}0 & b & c \\ 0 & e & f \\ g & h & i\end{bmatrix}\right), % since the 3 matrices on the right differ only in their leftmost column. \noindent Let's compute the first of the three determinants on the right by using a similar trick on its second column: \horlines{3}\vspace*{-0.4cm} % \det\left(\begin{bmatrix}a & b & c \\ 0 & e & f \\ 0 & h & i\end{bmatrix}\right) = \det\left(\begin{bmatrix}a & b & c \\ 0 & e & f \\ 0 & 0 & i\end{bmatrix}\right) + \det\left(\begin{bmatrix}a & b & c \\ 0 & 0 & f \\ 0 & h & i\end{bmatrix}\right), % since the two matrices on the right differ only in their middle column. \noindent Well, these two determinants are \horlines{5} % the first matrix on the right is upper triangular so its determinant is the product of its diagonal entries, and the second matrix on the right can be made upper triangular by swapping two of its rows (which multiplies the determinant by $-1$): % \det\left(\begin{bmatrix}a & b & c \\ 0 & e & f \\ 0 & h & i\end{bmatrix}\right) & = aei - \det\left(\begin{bmatrix}a & b & c \\ 0 & h & i \\ 0 & 0 & f\end{bmatrix}\right) = aei - afh. \noindent The computation of the remaining terms in the determinant is similar. \end{proof} \newpage We can also think of the formula for determinants of $3 \times 3$ matrices in terms of diagonals of the matrix -- it is the sum of the products of its forward diagonals minus the sum of the products of its backward diagonals, with the understanding that the diagonals ``loop around'' the matrix: \horlines{4} % Draw 3x3 matrix, highlighting forward and backward diagonals. \exx[4]{Compute the determinant of $A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix}$.} % Use the formula. % Answer 2, notice that it's the same as before. The following theorem tells us how to come up with these formulas in general, and it is just a direct generalization of the $2 \times 2$ and $3 \times 3$ formulas that we already saw. \begin{theorem}[Cofactor Expansion]\label{thm:cofactor_expansion} Let $A \in \mathcal{M}_{n}$. For each $1 \leq i,j \leq n$, define $c_{i,j} = (-1)^{i+j}\det(\overline{A_{i,j}})$, where $\overline{A_{i,j}}$ is the matrix obtained by removing the $i$-th row and $j$-th column of $A$. Then the determinant of $A$ can be computed via \begin{align*} \det(A) & = a_{i,1}c_{i,1} + a_{i,2}c_{i,2} + \cdots + a_{i,n}c_{i,n} \quad \text{for all $1 \leq i \leq n$,} \quad \text{and} \\ \det(A) & = a_{1,j}c_{1,j} + a_{2,j}c_{2,j} + \cdots + a_{n,j}c_{n,j} \quad \text{for all $1 \leq j \leq n$.} \end{align*} \end{theorem} \newpage That theorem is a mouthful! Several remarks are in order: \begin{itemize} \item If we use this theorem to compute the determinant of a $2 \times 2$ or $3 \times 3$ matrix, \horlines{1}\vspace*{-0.5cm} % We get the formulas we already know. \item The above method of computing the determinant is called a ``cofactor expansion,'' since the number $c_{i,j}$ is called the ``$(i,j)$-cofactor of $A$.'' % Highlight the definition of cofactor in the previous bullet \item The theorem gives \emph{multiple} formulas for $\det(A)$: \horlines{2}\vspace*{-0.5cm} %it says you can pick any fixed row or column of $A$ and ``expand'' along that row/column. % get same answer no matter which row/column you use \end{itemize} \exx[11]{Compute the determinant of $A = \begin{bmatrix} 2 & 1 & -1 & 0 \\ 0 & -2 & 1 & 3 \\ 0 & 0 & 1 & 0 \\ -1 & 3 & 0 & 2 \end{bmatrix}$.} % Ask students which row/column they want to cofactor long, but note that you should choose one with lots of zeroes to make life eaiser. % Then do same computation along a different row or column, get same answer. \newpage \exx[9]{Compute the determinant of $A = \begin{bmatrix} 0 & -1 & 2 & 1 & 3 \\ 0 & 0 & 0 & 2 & 0 \\ -2 & 1 & 1 & -1 & 0 \\ 1 & 0 & -3 & 1 & 0 \\ 2 & 1 & -1 & 0 & 0 \end{bmatrix}$.}\vspace*{-0.5cm} % Again, pick row or column with lots of zeroes. Every time you apply theorem, gets 1 dimension smaller, so iterate. % Answer: 60 In general, computing determinants via cofactor expansions is extremely inefficient. It's not too bad for $2 \times 2$, $3 \times 3$, or maybe $4 \times 4$ matrices. But for an $n \times n$ matrix $A$, a cofactor expansion contains $n!$ terms being added up, and each of those terms is the product of $n$ entries of $A$. For example, \begin{align*} \det\left(\begin{bmatrix} a & b & c & d \\ e & f & g & h \\ i & j & k & \ell \\ m & n & o & p \end{bmatrix}\right) & = afkp - af\ell o - agjp + ag\ell n + ahjo - ahkn \\[-0.85cm] & \quad - bekp + be\ell o + bgip - bg\ell m - bhio + bhkm \\ & \quad + cejp - ce\ell n - cfip + cf\ell m + chin - chjm \\ & \quad - dejo + dekn + dfio - dfkm - dgin + dgjm. \end{align*} \noindent Ugh! So for large matrices, use the Gaussian elminiation method instead. Nonetheless, cofactor expansions will be useful for us for theoretical reasons next week. \end{document}