% DEFINE some information that will be populated throughout the course notes. \def \coursename {Linear Algebra} \def \coursecode {MATH 2221} \def \courseterm {Winter 2017} \def \instructorname {Nathan Johnston} % END DEFINITIONS % IMPORT the course note formatting and templates \input{course_notes_template} % END IMPORT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \setcounter{chapter}{6} % Set to one less than the week number \chapter{Subspaces, Spans, and \\ Linear Independence} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% {\large This week we will learn about: \begin{itemize} \item Subspaces, \item The span of a set of vectors, and \item Linear (in)dependence. \end{itemize}\bigskip\bigskip \noindent Extra reading and watching: \begin{itemize} \item Section 2.3 in the textbook \item Lecture videos \href{https://www.youtube.com/watch?v=qPjh6SF_zPA&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=26}{26}, \href{https://www.youtube.com/watch?v=vbJ3BmA_X3I&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=27}{27}, \href{https://www.youtube.com/watch?v=Jke7UVzR8zQ&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=28}{28}, and \href{https://www.youtube.com/watch?v=ru3HKhdLcT4&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=29}{29} on YouTube \item \href{https://en.wikipedia.org/wiki/Linear_subspace}{Linear subspace} at Wikipedia \item \href{https://en.wikipedia.org/wiki/Linear_independence}{Linear independence} at Wikipedia \end{itemize}\bigskip\bigskip \noindent Extra textbook problems: \begin{itemize} \item[$\star$] 2.3.1, 2.3.2, 2.3.4 \item[$\star \, \star$] 2.3.3, 2.3.5, 2.3.6, 2.3.9--2.3.11, 2.3.18, 2.3.19 \item[$\star\star\star$] 2.3.12, 2.3.14, 2.3.16, 2.3.22 \item[$\skull$] 2.3.27 \end{itemize}} \newpage \section*{Subspaces} Recall that linear systems can be interpreted geometrically as asking for the point(s) of intersection of a collection of lines or planes (depending on the number of variables involved). The following definition introduces ``subspaces'', which can be thought of as any-dimensional analogues of lines and planes. \begin{definition}[Subspaces] A \textbf{subspace} of $\R^n$ is a non-empty set $\mathcal{S}$ of vectors in $\R^n$ such that: \begin{enumerate} \item If $\v$ and $\w$ are in $\mathcal{S}$ then $\mathbf{v} + \mathbf{w}$ is in $\mathcal{S}$. % CLOSED UNDER ADDITION \item If $\v$ is in $\mathcal{S}$ and $c$ is a scalar, then $c\v$ is in $\mathcal{S}$. % CLOSED UNDER SCALAR MULTIPLICATION \end{enumerate} \end{definition} % Very reminiscent of linear transformations, which we required "respect" vector addition and scalar multiplication. Properties~(a) and~(b) above together are equivalent to requiring that $\mathcal{S}$ is closed under linear combinations: \horlines{2} % if v1,...,vn are in S and c1,...,cn are scalars, then c1v1 + ... cnvn is in S. \exx[5]{Is the set of vectors $(x,y)$ satisfying $y = x^2$ a subspace of $\mathbb{R}^2$?} % No, not additive. (1,1) and (2,4) are in there but (3,5) isn't. Draw picture. \exx[2]{Is the set of vectors $(x,y,z)$ satisfying $x = 3y$ and $z = -2y$ a subspace of $\mathbb{R}^3$?} % Yes. It is the set of vectors of the form $(3y,y,-2y) = y(3,1,-2)$. Multiples of $(3,1,-2)$. Line through that point. Easy to check both properties. \newpage \horlines{6} \exx[6]{Is the set of vectors $(x,y,z)$ satisfying $x = 3y+1$ and $z = -2y$ a subspace of $\mathbb{R}^3$?} % No. Does not contain the 0 vector, but every subspace contains the 0 vector (why?). % Maybe draw picture (it is a line, but it's in 3D). % Maybe mention that this is called an "affine space". % Note analogy with linear transformations (they must send 0 to 0) In $\R^3$, lines and planes through the origin are subspaces (this is hopefully not difficult to see for lines, and it can be seen for planes by using the parallelogram law): \horlines{5} % INSERT week7/subspace_plane.png % Also note that stretching a vector on a plane leaves it on that plane \newpage Even though we can't visualize subspaces in higher dimensions, you should keep the line/plane intuition in mind: a subspace of $\R^n$ looks like a copy of $\R^m$ (for some $m < n$) going through the origin. \section*{Subspaces Associated with Matrices} Let's now look at some other natural examples of subspaces that appear frequently when working with matrices. \begin{definition}[Matrix Subspaces] Let $A \in \M_{m,n}$ be an $m \times n$ matrix. \begin{enumerate} \item The \textbf{range} of $A$ is the subspace of $\R^m$, denoted by $\mathrm{range}(A)$, that consists of all vectors of the form $A\x$. \item The \textbf{null space} of $A$ is the subspace of $\R^n$, denoted by $\mathrm{null}(A)$, that consists of all solutions $\x$ of the linear system $A\x = \0$. \end{enumerate} \end{definition} \noindent Some remarks about these matrix subspaces are in order: \begin{itemize} \item $\mathrm{null}(A)$ is a subspace. Why? \horlines{6}\vspace*{-0.5cm} % check the two properties (first, non-empty since A0 = 0 so 0 \in null(A)): if Au = 0 and Av = 0 then A(u+v) = 0, and if Au = 0 then A(cu) = c(Au) = 0. \item $\mathrm{range}(A)$ is a subspace. Why? \horlines{2}\vspace*{-0.5cm} % If v,w in range then we can write v = Ax and w = Ay. Then v+w = A(x+y) so v+w in range, and cv = cAx = A(cx) so cv in range. \newpage \horlines{4} \item The term ``range'' is being used here in the exact same sense as in previous courses. \horlines{2} % Range of a function/linear transformation is the set of possible outputs of that function. \end{itemize} \exx[13]{Describe the range and null space of the $2 \times 3$ matrix} % Ask for an example 2x3 matrix from the class. Maye specifically choose a rank 1 example? % To find the null space, just set equal to 0 and solve (should be line in R^3) % To find range, find all b=(x,y) such that augmented system [A|b] has solution. To do this, row reduce [A|b] with (x,y) in RHS. If all rows on LHS are non-zero, everything is a solution (this should happen generically, but not if the example is rank 1). If zero bottom-left row and some function of x,y in bottom-right entry, then need that bottom-right entry = 0. Subspace of R^2 (maybe all of R^2) \newpage \section*{The Span of a Set of Vectors} One way to turn a set that is \emph{not} a subspace into a subspace is to add linear combinations to it. For example, the set containing only the vector $(2,1)$ is not a subspace of $\R^2$ because \horlines{1} % for example, $2(2,1) = (4,2)$ is not in the set. To fix this problem, we could \horlines{8} % add $(4,2)$ to the set and ask whether or not $\{(2,1),(4,2)\}$ is a subspace. However, it is also not a subspace for a very similar reason---there are other scalar multiples of $(2,1)$ still missing from the set. However, if we add \emph{all} of the scalar multiples of $(2,1)$, we get the line through the origin and the point $(2,1)$, which \emph{is} a subspace (DRAW PICTURE) In general, if our starting set contains more than just one vector, we might also have to add general linear combinations of those vectors (not just their scalar multiples) in order to create a subspace. This idea of enlarging a set so as to create a subspace is an important one that we now give a name and explore. \begin{definition}[Span]\label{defn:span} If $B = \{\v_1,\v_2,\ldots,\v_k\}$ is a set of vectors in $\mathbb{R}^n$, then the set of all linear combinations of those vectors is called their \textbf{span}, and is denoted by $\mathrm{span}(B)$ or $\mathrm{span}(\v_1,\v_2,\ldots,\v_k)$. \end{definition} For example, $\mathrm{span}\big((2,1)\big)$ is the line through the origin and the point $(2,1)$, as we discussed earlier. \newpage \exx[2]{Show that $\mathrm{span}(\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3) = \mathbb{R}^3$.} % Easy: (x,y,z) = x*e1 + y*e2 + z*e3, so we can write every vector as a linear combination of e1, e2, and e3 \noindent The natural generalization of this fact holds in all dimensions: \horlines{1} %\mathrm{span}(\mathbf{e}_1,\mathbf{e}_2,\ldots,\mathbf{e}_n) = \mathbb{R}^n \ \text{ for all $n$}. \exx[8]{What is $\mathrm{span}\big((1, 0, 3),(-1, 1, -3)\big)$ -- a line, a plane, or something else?} % Write with augmented right-hand-side x,y,z. Solve. Bottom-right entry must be 0, get equation of a plane. % INSERT PICTURE OF A PLANE (will have to make one in the textbook sometime, I don't have one yet) We motivated the span of a set of vectors as a way of turning that set into a subspace. We now state (but for the sake of time, do not prove) a theorem that says the span of a set of vectors is indeed always a subspace, as we would hope. \begin{theorem}[Spans are Subspaces] Suppose $\v_1, \v_2, \ldots, \v_k \in \R^n$. Then $\mathrm{span}(\v_1, \v_2, \ldots, \v_k)$ is a subspace of $\R^n$. \end{theorem} In fact, you can think of the span of a set of vectors as the \emph{smallest} subspace containing those vectors. \newpage % %\begin{proof} % We have to check that both of the properties in the definition of a subspace hold: % % \horlines{7}\vspace*{-1.3cm} % % 0 vector in span, so it is non-empty (or v_1,v_2,...,v_n in the span) % % sum of two vectors is in just by grouping coefficients % % scalar mult is in by grouping coefficients. %\end{proof} The range of a matrix can be expressed very conveniently as the span of a set of vectors in a way that requires no calculation whatsoever: \begin{theorem}[Range Equals the Span of Columns]\label{thm:range_columnspace} If $A \in \M_{m,n}$ has columns $\a_1,\a_2,\ldots,\a_n$ then $\mathrm{range}(A) = \mathrm{span}(\a_1,\a_2,\ldots,\a_n)$. \end{theorem} \noindent This theorem follows immediately from \horlines{2} % Theorem from week 3(?) that says that Ax is a linear combination of the columns of A. As x ranges over all vectors, Ax ranges over all linear combinations (i.e., gets the full span). \noindent For example, if we return to the $2 \times 3$ matrix from earlier, we see that its range is... \horlines{2}\vspace*{-0.5cm} % span of columns, should be all of R^2. We close this section by introducing a connection between the range of a matrix and invertible matrices. \begin{theorem}[Spanning Sets and Invertible Matrices]\label{thm:invertible_characterization_span} Let $A \in \M_{n}$. The following are equivalent: \begin{enumerate} \item $A$ is invertible. \item $\mathrm{range}(A) = \mathbb{R}^n$. \item The columns of $A$ span $\R^n$. \item The rows of $A$ span $\R^n$. \end{enumerate} \end{theorem} \begin{proof} The fact that properties~(a) and~(c) are equivalent follows from combining... \horlines{3}\vspace*{-0.25cm} % combining two of our recent previous results (GO TO THEIR OLD COURSE NOTES AND MENTION THEOREM #s): Theorem 6.3 tells us that $A$ is invertible if and only if the linear system $A\x = \b$ has a solution for all $\b \in \R^n$, which means that every $\b \in \R^n$ can be written as a linear combination of the columns of $A$ (by Theorem~??). This is exactly what it means for the columns of $A$ to span $\R^n$. \newpage \noindent The equivalence of properties~(c) and~(d) follows from the fact that \horlines{2} % $A$ is invertible if and only if $A^T$ is invertible (Theorem~\ref{thm:inverse_properties}(c)), and the rows of $A$ are the columns of $A^T$. \noindent Finally, the equivalence of properties (b) and (c) follows immediately from \horlines{2}\vspace*{-1.35cm} % Theorem 7.2: the range of a matrix equals the span of its columns \end{proof} The geometric interpretation of the equivalence of properties (a) and (b) in the above theorem is \horlines{4} % if the range of a matrix is smaller than $\R^n$ (for example, a plane in $\R^3$), then space that matrix ``squishes'' space, and that squishing cannot be undone (DRAW PICTURE). However, if its range is all of $\R^n$ then it just shuffles vectors around in space, and its inverse shuffles them back. \section*{Linear Dependence and Independence} Recall from earlier that a row echelon form of a matrix can have entire rows of zeros at the end of it. For example, the reduced row echelon form of \begin{align*} \left[\begin{array}{cc|c} 1 & -1 & 2 \\ -1 & 1 & -2 \end{array}\right] \quad \text{is} \quad {}\qquad{}\qquad{}\qquad{}\qquad{}\qquad{}\qquad{}\qquad{} \end{align*} % just put zeros at the bottom This happens when there is some linear combination of the rows of the matrix that equals the zero row, and we interpret this roughly as saying that one row the rows of the matrix (i.e., one of the equations in the associated linear system) does not ``contribute anything new.'' In the example above, \horlines{2}\vspace*{-0.25cm} % the second equation of associated the linear system says $-x+y=-2$, which is redundant since the first equation already said that $x-y=2$, and these equations can be obtained from each other just by multiplying one another by $-1$. \newpage The following definition captures this idea that a redundancy among vectors or linear equations can be identified by whether or not some linear combination of them equals zero. % Emphasize that row operations are just linear combinations, so in the above example redundancy meant we could find a linear combination of rows that added to 0 \begin{definition}[Linear Dependence and Independence]\label{defn:lin_dep} A set of vectors $B = \{\v_1,\v_2,\ldots,\v_k\}$ is \textbf{linearly dependent} if there exist scalars $c_1,c_2,\ldots,c_k \in \R$, at least one of which is not zero, such that \begin{align*} c_1\v_1 + c_2\v_2 + \cdots + c_k\v_k = \0. \end{align*} If a set of vectors is not linearly dependent, it is called \textbf{linearly independent}. \end{definition} For example, the set of vectors $\{(2,3), (1,0), (0,1)\}$ is linearly... \horlines{1}\vspace*{-0.25cm} % dependent because \[ (2,3) - 2(1,0) - 3(0,1) = (0,0).\] % Mention the idea that there's "redundancy" in that set -- one of the vectors is a linear combination of the others \noindent On the other hand, the set of vectors $\{(1,0,0), (0,1,0), (0,0,1)\}$ is linearly... \horlines{3} % independent, since the only linear combination of those three vectors that equals $(0,0,0)$ is the ``trivial'' linear combination: %\[ %0(1,0,0) + 0(0,1,0) + 0(0,0,1) = (0,0,0). %\] In general, to check whether or not a set of vectors $\{\v_1,\v_2,\ldots,\v_k\}$ is linearly independent, you should set \horlines{2}\vspace*{-0.25cm} % c_1\v_1 + c_2\v_2 + \cdots + c_k\v_k = \0 \noindent and then try to solve for the scalars $c_1, c_2, \ldots, c_k$. If they must all equal $0$, then the set is linearly independent, and otherwise it is linearly dependent. \exx[2]{Are these vectors linearly independent?}\vspace*{-0.4cm} % Ask class for 3 vectors in R^3 and then work through the linear system. More likely thank not, you'll get a unique solution, so independent. % Mention that you'll always get at least one solutions (all-zero), so options are unique (independent) or infinitely many (dependent). \newpage \horlines{7} We saw in the previous example that we can check linear (in)dependence of a set of vectors by placing those vectors as columns in a matrix and augmenting with a $\0$ right-hand side. This is true in general: \begin{theorem}[Checking Linear Dependence]\label{thm:check_lin_dep} Let $\v_1,\v_2,\ldots,\v_n \in \R^m$ be vectors and let $A$ be the $m \times n$ matrix with these vectors as its columns. The following are equivalent: \begin{enumerate} \item $\{\v_1,\v_2,\ldots,\v_n\}$ is a linearly dependent set. \item The linear system $A\x = \0$ has a non-zero solution. \end{enumerate} \end{theorem} Some notes about linear (in)dependence are in order: \begin{itemize} \item A set of vectors is linearly dependent if and only if at least one of the vectors can be written as a linear combination of the others. \horlines{2}\vspace*{-0.4cm} % Rearrange c1v1 + .. ckvk = 0 to v1 = -(c2/c1)v2 - ... - (ck/c1)vk. \item Every set of vectors containing the zero vector is linearly... \horlines{2} % dependent. % Because c1*0 + c2v2 + ... + ckvk = 0 works with c1 = 1, c2 = ... = ck = 0. \newpage \item Geometrically, linear dependence means that... \horlines{4} % The vectors all lie in a common subspace of smaller dimension than they "should". e.g., 2 vectors on a line, 3 vectors in a plane. Visualize 2D and 3D cases to students with 3 pencils or something, DRAW PICTURE of 2D case. \item For a set of just 2 vectors, linear dependence means that... \horlines{1} % They are multiples of each other. \end{itemize} \exx[3]{Is this set linearly independent?} % Ask for 2 vectors in R^3. Just check if they're multiples of each other or not. We close this section by introducing a connection between linear independence and invertible matrices, which we unfortunately have to state without proof due to time constraints. \begin{theorem}[Independence and Invertible Matrices]\label{thm:invertible_characterization_independence} Let $A \in \M_{n}$. The following are equivalent:\smallskip \begin{enumerate}[label=\alph*)] \item $A$ is invertible. \item The columns of $A$ form a linearly independent set. \item The rows of $A$ form a linearly independent set. \end{enumerate} \end{theorem} %% POSSIBLY OMIT THE PROOF IF LOW ON TIME %\begin{proof} % The fact that properties~(a) and~(b) are equivalent follows from combining two of our recent previous results: % % \horlines{4} % % Theorem~\ref{thm:invertible_characterization_one} tells us that $A$ is invertible if and only if the linear system $A\x = \0$ has a unique solution (which is necessarily $\x = \0$), and then Theorem~\ref{thm:check_lin_dep} says that is equivalent to the columns of $A$ forming a linearly independent set. % % \noindent The equivalence of properties~(b) and~(c) follows from... % % \horlines{2}\vspace*{-1.3cm} % % the fact that $A$ is invertible if and only if $A^T$ is invertible (Theorem~\ref{thm:inverse_properties}(c)), and the rows of $A$ are the columns of $A^T$. %\end{proof} % %For example, is the following matrix invertible? % %\horlines{3} %% Matrix with columns from lin. (in)dep. example from earlier. % %At this point, you might notice that there area whole lot of conditions that are equivalent to a matrix being invertible. We're going to see even more as we go forward from here (and we'll finally make a big long list of all of them near the end of the course). \end{document}