% 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}{7} % Set to one less than the week number
\chapter{Bases of Subspaces and \\ the Rank of a Matrix}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\large This week we will learn about:
	
	\begin{itemize}
		\item The dimension of a subspace,
		\item Bases of subspaces,
		\item The rank of a matrix, and
		\item The rank--nullity theorem.
	\end{itemize}\bigskip\bigskip
	
	\noindent Extra reading and watching:
	\begin{itemize}
		\item Sections 2.4 in the textbook
		\item Lecture videos \href{https://www.youtube.com/watch?v=j2iLHEkHy0k&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=30}{30}, \href{https://www.youtube.com/watch?v=03AbedID9ok&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=31}{31}, \href{https://www.youtube.com/watch?v=RuWR7w6iocM&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=32}{32}, and \href{https://www.youtube.com/watch?v=K8i4Wg_spIA&list=PLOAf1ViVP13jmawPabxnAa00YFIetVqbd&index=33}{33} on YouTube
		\item \href{https://en.wikipedia.org/wiki/Basis_(linear_algebra)}{Basis (linear algebra)} at Wikipedia
		\item \href{https://en.wikipedia.org/wiki/Rank_(linear_algebra)}{Rank (linear algebra)} at Wikipedia
		
	\end{itemize}\bigskip\bigskip
	
	\noindent Extra textbook problems:
	\begin{itemize}
		\item[$\star$] 2.4.1, 2.4.2, 2.4.8
		\item[$\star \, \star$] 2.4.5, 2.4.6, 2.4.9, 2.4.10
		\item[$\star\star\star$] 2.4.11, 2.4.12, 2.4.13, 2.4.25, 2.4.30
		\item[$\skull$] 2.4.27
	\end{itemize}}


\newpage


\section*{Bases of Subspaces}

A plane in $\R^3$ is spanned by any two vectors that are parallel to the plane, but not parallel to each other (i.e., are linearly independent). More than two vectors could be used to span the plane, but they would necessarily be linearly dependent. On the other hand, there is no way to use \emph{fewer} than two vectors to span a plane (the span of just one vector is just a line). This leads to the idea of a \emph{basis} of a subspace:

\begin{definition}[Bases]
	A \textbf{basis} of a subspace $\mathcal{S} \subseteq \R^n$ is a set of vectors in $\mathcal{S}$ that
	\begin{enumerate}
		\item spans $\mathcal{S}$, and
		\item is linearly independent.
	\end{enumerate}
\end{definition}

The idea of a basis is that it is a set that is ``big enough'' to span the subspace, but it is not ``so big'' that it contains redundancies. That is, it is ``just'' big enough to span the subspace.

\begin{center}
	\begin{tabular}{lcr}
		\includegraphics[width=1.25cm]{images/week7/goldilocks_1.png} & \raisebox{1cm}{\hspace*{13cm}} & \includegraphics[width=2cm]{images/week7/goldilocks_2.png}
	\end{tabular}
\end{center}
% A basis is not too big and not too small.
% It's just right!


\exx{The standard basis of $\R^n$.}
% Just mention that it really is a basis. Both properties should be "obvious". Notice also that we used the term "basis" for these vectors ever since Week 1.


\exx[3]{Show that the set $\big\{(2,1), (1,3) \big\}$ is a basis of $\R^2$.}


\newpage


\horlines{5}
% Show linearly independent and span R^2
% Lin indep: not multiples of each other
% Span: Row reduce [2 1 x;1 3 y] to get the identity matrix augmented with something. Thus unique solution so any vector (x,y) is a lin comb of these two vectors.

The above example demonstrates that the same subspace can (and will!) have more than one basis:

\horlines{2}
% (1,0),(0,1) and above example are both bases of R^2

\noindent However, the \emph{number} of vectors in a basis of a given subspace is always the same, which we now state as a theorem.

\begin{theorem}[Uniqueness of Size of Bases]
	Let $\mathcal{S}$ be a subspace of $\R^n$. Then every basis of $\mathcal{S}$ has the same number of vectors.
\end{theorem}

We don't prove the above theorem (it is a fairly long and ugly mess), but we can use it to pin down something we have been hand-wavey about up until now: we have never actually defined exactly what we mean by the ``dimension'' of a subspace of $\mathbb{R}^n$. We now fill in this gap:

\begin{definition}[Dimension of a Subspace]
	Let $\mathcal{S}$ be a subspace of $\mathbb{R}^n$. The number of vectors in a basis of $\mathcal{S}$ is called the \textbf{dimension} of $\mathcal{S}$.
\end{definition}

As one minor technicality, we notice that the set $\mathcal{S} = \{\mathbf{0}\}$ is a subspace of $\mathbb{R}^n$. However, the only basis of this subspace is the empty set $\{\}$ (why?), so its dimension is $0$.
% Any set containing 0 must be linearly dependent, so no basis can contain 0. Basis must be empty then, which has no vectors, so dimension 0. (maybe mention empty sum equalling 0 if it helps people understand why it spans {0})


\newpage


\exx[2]{What is the dimension of $\R^n$?}
% n, since the standard basis has n vectors
% Agrees with intuitive understanding of dimension when n <= 3

\exx[7]{Find a basis for $\mathcal{S} = \textrm{span}(\mathbf{v},\mathbf{w},\mathbf{x})$, where $\mathbf{v} = (1,2,3)$, $\mathbf{w} = (3,2,1)$, $\mathbf{x} = (1,1,1)$. What is the dimension of this subspace?}
% Already span space, just need to check lin. indep.
% Last vector is linear combination of first two. First two are not multiples of each other. Thus (v,w) is a basis.
% Dimension is 2. It's a plane!
% Maybe insert picture (I don't have one made up yet).

We will now show how to find bases of the fundamental subspaces associated with a matrix: $\mathrm{range}(A)$ and $\mathrm{null}(A)$.


% If short on time, don't bother doing this! Just move on to rank.
\exx[4]{Find bases for the range and null space of the following matrix and thus compute their dimensions:
	\begin{align*}
		\begin{bmatrix}
			1 & 0 & 1 & 0 & -1 \\
			1 & 1 & 0 & 0 & 1 \\
			-1 & 0 & -1 & 1 & 4 \\
			2 & 1 & 1 & -1 & -3
		\end{bmatrix}
	\end{align*}\vspace*{-0.25cm}}
	% RECALL that range is span of columns, just need to toss away some linear combinations to make it a basis
	% Find RREF. Basis of range is just columns that have a leading 1 in RREF (but the columns are taken from the original matrix).
	% Justification: each column without a leading entry is a linear combination of columns before it with leading entries (e.g., col_3 = col_1 + 2col_2 in this case), so these contribute nothing to column space. Rows ops do no affect column linear combinations.
	% Dimension 3.
	% For null space, same stuff we always do, just new terminology. Solve the system $Ax = 0$, write it in terms of free variables times vectors. Already in RREF so easy. Those vectors form the basis. (-1,-2,1,0,0) and (1,-3,0,-4,1), dimension 2.
	
	
	\newpage
	
	
	\horlines{12}
	
	
	The quantities $\mathrm{dim}(\mathrm{range}(A))$ and $\mathrm{dim}(\mathrm{null}(A))$ that we computed in the previous example highlight a lot of the structure of the matrix $A$, so let's have a closer look at them now.


\section*{The Rank of a Matrix}

With many of the technical details of this course out of the way, we are now in a position to introduce one of the most important properties of a matrix: its rank.

\begin{definition}[Rank of a Matrix]
	Let $A \in \mathcal{M}_{m,n}$ be a matrix. Then its \textbf{rank}, denoted by $\mathrm{rank}(A)$, is the dimension of its range.
\end{definition}

\noindent Rank can be thought of as a measure of how degenerate a matrix is, as it describes how much of the output space can actually be reached by $A$.

% MENTION that for nxn matrix goes from 0 to n, with lower numbers being "more" degenerate


\newpage


\exx[4]{Suppose $A \in \mathcal{M}_n$ is the standard matrix of a projection onto a line. What is $\mathrm{rank}(A)$?}
% 1 since everything is projected down onto a line (1-dimensional output)
% remind students that A = uu^T, where u is the unit vector we are projecting onto

\exx[4]{Suppose $C \in \mathcal{M}_2$ is the standard matrix of a rotation. What is $\mathrm{rank}(C)$?}
% 2 since everything in R^2 can be reached from somewhere
% remind students that A = [cos, -sin;sin, cos].

One of the reasons why the rank of a matrix is so useful is that it can be interpreted in so many different ways. While it equals the dimension of the range, it also equals some other quantities that we have already seen as well:

\begin{theorem}[Characterization of Rank]
	Let $A \in \mathcal{M}_{m,n}$ be a matrix. Then the following quantities are all equal to each other:
	\begin{enumerate}
		\item $\mathrm{rank}(A)$
		
		\item $\mathrm{rank}(A^T)$.
		
		\item The number of non-zero rows in any row echelon form of $A$.
		
		\item The number of leading columns in any row echelon form of $A$.
	\end{enumerate}
\end{theorem}


\newpage


\begin{proof}
	To see the equivalence of (c) and (d)...
	
	\horlines{3}
	% every non-zero row in a row echelon form has exactly one leading entry, as does every leading column.

	\noindent To see the equivalence of (a) and (d)...
	
	\horlines{4}
	% From our method of constructing a basis of $\mathrm{range}(A)$. Specifically, the basis of $\mathrm{range}(A)$ that we constructed consisted of the columns of $A$ corresponding to leading columns in its row echelon forms. Thus the number of these leading columns equals the number of vectors in the basis, which (by definition) equals the dimension of $\mathrm{range}(A)$, and that dimension (again, by definition) equals $\mathrm{rank}(A)$.
	
	The equivalence of (b) and (c) is similar:
	
	\horlines{2}\vspace*{-1.35cm}
	% Recall that range is span of columns, so range(A^T) is span of rows
	% the non-zero rows in RREF of A give basis of range of A^T.
\end{proof}\vspace*{0.2cm}

\exx[7]{Find the rank of the matrix $A = \begin{bmatrix}0 & 0 & -2 & 2 & -2 \\ 2 & -2 & -1 & 3 & 3 \\ -1 & 1 & -1 & 0 & -3\end{bmatrix}$}
% Get in row echelon form, count non-zero rows
% Rank 2.


\newpage


Similarly, the \textbf{nullity} of a matrix, denoted by $\mathrm{nullity}(A)$, is the dimension of its null space (i.e., the dimension of the solution set of the linear system $A\x = \0$). The following theorem demonstrates the close connection between the rank and nullity of a matrix:

\begin{theorem}[Rank--Nullity]
	Let $A \in \mathcal{M}_{m,n}$ be a matrix. Then $\mathrm{rank}(A) + \mathrm{nullity}(A) = n$.
\end{theorem}

\begin{proof}
	We use the equivalence of the quantities (a) and (d) from the previous theorem:
	
	\horlines{10}\vspace*{-1.35cm}
	% Let r = rank(A) = number of leading variables in linear system Ax = 0. Then there are n - r free variables (n = total number of variables, r are leading, the rest are free). But from earlier we know that these free variables each provide one member of a basis for null(A), so nullity(A) = n-r too. Done.
\end{proof}
% Emphasize that rank = number of leading variables, nullity = number of free variables

\exx[4]{Find the nullity of the matrix $A = \begin{bmatrix}0 & 0 & -2 & 2 & -2 \\ 2 & -2 & -1 & 3 & 3 \\ -1 & 1 & -1 & 0 & -3\end{bmatrix}$}
% Get in row echelon form, count non-zero rows
% Rank 2.
% Go back to example at the end of the last section and note that rank = 3, nullity = 2


\newpage


The previous theorem makes some geometric sense---there are $n$ dimensions that go into $A$. $\mathrm{rank}(A)$ of them are sent to the output space, and the other $\mathrm{nullity}(A)$ of them are ``squashed away'' by $A$. This observation leads immediately to \emph{yet another} characterization of invertibility:

\begin{theorem}[Rank and Invertible Matrices]\label{thm:rank_invertible}
	Let $A \in \mathcal{M}_{n}$. The following are equivalent:\smallskip
	\begin{enumerate}[label=\alph*)]
		\item $A$ is invertible.
		
		\item $\mathrm{rank}(A) = n$
		
		\item $\mathrm{nullity}(A) = 0$
	\end{enumerate}
\end{theorem}

% think of as a measure of "how" not invertible a matrix is

	
% SKIP ENTIRE SECTION if short on time
%\section*{Coordinate Systems}
%	
%The main result of this section demonstrates our primary reason for introducing bases in the first place: they let us unambiguously define coordinate systems in $\R^n$ or subspaces of $\R^n$:
%	
%	\begin{theorem}[Unique Linear Combinations]
%		Let $\mathcal{S}$ be a subspace of $\R^n$ and let $B = \{\v_1,\v_2,\ldots,\v_k\}$ be a basis of $\mathcal{S}$. For every vector $\v \in \mathcal{S}$, there is exactly one way to write $\v$ as a linear combination of the basis vectors in $B$:\\[0.5cm]
%		
%		${}$
%		%\begin{align*}
%			%\mathbf{v} = c_1\v_1 + c_2\v_2 + \cdots + c_k\v_k.
%		%\end{align*}
%		% Write this final line in instead
%	\end{theorem}
%	
%	\begin{proof}
%		Since $B$ is a basis, it spans $\mathcal{S}$, so $\v$ can be written as such a linear combination in at least one way.
%		
%		\horlines{4}
%		
%		
%		\newpage
%		
%		
%		\horlines{3}\vspace*{-1.3cm}
%		% Let c1v1 + ... ckvk be one such lin. comb.
%		% Want to rule out others. Suppose d1v1 + ... + dkvk = v be another. Then (c1-d1)v1 + ... (ck-dk)vk = 0, but these are lin indep so c1 = d1, c2 = d2, etc, and they're the same.
%	\end{proof}
%	
%	
%	The (unique!) coefficients $c_1, c_2, \ldots, c_k$ described by the previous theorem are called the \textbf{coordinates} of $\v$.
%	
%	\begin{definition}[Coordinates with Respect to a Basis]
%		Let $\mathcal{S}$ be a subspace of $\R^n$ and let $B = \{\v_1,\v_2,\ldots,\v_k\}$ be a basis of $\mathcal{S}$. Let $\v \in \mathcal{S}$, and write $\v = c_1\v_1 + c_2\v_2 + \cdots + c_k\v_k$. Then $c_1, c_2, \ldots, c_k$ are called the \textbf{coordinates of} $\v$ \textbf{with respect to} $B$, and the vector
%		\begin{align*}
%			[\v]_{B} \defeq (c_1, c_2, \cdots, c_k)
%		\end{align*}
%		is called the \textbf{coordinate vector of} $\v$ \textbf{with respect to} $B$.
%	\end{definition}
%	
%	\exx{Let $B = \{\e_1,\e_2\}$ be the standard basis of $\R^2$. Find the coordinate vector of...} % some 2D vector with respect to B. is the same vector
%	% The point is: our vectors have been with respect to the standard basis all along
%	
%	\exx[5]{Let $B = \big\{(2,1),(1,3)\big\}$ (this is a basis of $\R^2$). Find the coordinate vector of...} % Maybe (4/7)
%	% the same vector as previous example, with respect to this new basis
%	% Solving this is a linear system.
%	% Draw picture.
%	
%	
%	\newpage
%	
%	
%	\horlines{10}
\end{document}