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


% IMPORT the course note formatting and templates
\input{course_notes_template}
% END IMPORT


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{chapter}{1} % Set to one less than the week number
\chapter{Bases and Coordinate Systems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\large This week we will learn about:

\begin{itemize}
	\item Bases of vector spaces,
	\item How to change bases in vector spaces, and
	\item Coordinate systems for representing vectors.
\end{itemize}\bigskip\bigskip

\noindent Extra reading and watching:
\begin{itemize}
	\item Sections~1.1.3--1.2.2 in the textbook
	\item Lecture videos \href{https://www.youtube.com/watch?v=R9Ojqw2QU0o&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=6}{5}, \href{https://www.youtube.com/watch?v=KXeu7YW6KV0&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=7}{6}, \href{https://www.youtube.com/watch?v=njPQaYanjmw&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=8}{7}, and \href{https://www.youtube.com/watch?v=WheKDNhdT0M&list=PLOAf1ViVP13jdhvy-wVS7aR02xnDxueuL&index=9}{8} on YouTube
	\item \href{https://en.wikipedia.org/wiki/Basis_(linear_algebra)}{Basis (linear algebra)} at Wikipedia
	\item \href{http://en.wikipedia.org/wiki/Change_of_basis}{Change of basis} at Wikipedia
\end{itemize}\bigskip\bigskip

\noindent Extra textbook problems:
\begin{itemize}
	\item[$\star$] 1.1.3, 1.1.4(g), 1.2.1, 1.2.4(a--c,f,g)
	\item[$\phantom{\star}\star\star$] 1.1.15, 1.1.16, 1.2.2, 1.2.5, 1.2.7, 1.2.29
	\item[$\star\star\star$] 1.1.17, 1.1.21, 1.2.9, 1.2.23
	\item[$\skull$] 1.2.34
\end{itemize}}


\newpage


In introductory linear algebra, we learned a bit about bases, but we weren't really able to do too much with them when we were restricted to $\mathbb{R}^n$. Now that we are dealing with general vector spaces, bases will really start to shine, as they let us turn almost any vector space calculation into a familiar calculation in $\R^n$ (or $\C^n$).

\begin{definition}[Bases]\label{defn:abstract_bases}
	A \textbf{basis} of a vector space $\V$ is a set of vectors in $\V$ that
	\begin{enumerate}[label=\alph*)]
		\item spans $\V$, and
		\item is linearly independent.
	\end{enumerate}
\end{definition}

% Mention intuition of bases being "not too big" (linearly independent) and "not too small" (spanning)

\noindent \textcolor{red}{\textbf{Be careful:}} A vector space can have many bases that look very different from each other!

\exx[4]{Let $\mathbf{e}_j$ be the vector in $\R^n$ with a $1$ in its $j$-th entry and zeros elsewhere. Show that $\{\mathbf{e}_1,\mathbf{e}_2,\ldots,\mathbf{e}_n\}$ is a basis of $\R^n$.\vspace*{-0.6cm}\[\][Side note: This is called the \textbf{standard basis} of $\R^n$.]}
% Span: easy, every v = (v1,v2,...,vn) is v1*e1 + v2*e2 + ... + vn*en
% LI: easy, if c1*e1 + ... + cn*en = 0 then (c1,...,cn) = 0, so c1 = ... = cn = 0.

\exx[6]{Let $E_{i,j} \in \M_{m,n}$ be the matrix with a $1$ in its $(i,j)$-entry and zeros elsewhere. Show that $\{E_{1,1},E_{1,2},\ldots,E_{m,n}\}$ is a basis of $\M_{m,n}$.\vspace*{-1.15cm}\[\][Side note: This is called the \textbf{standard basis} of $\M_{m,n}$.]}
% Almost the exact same calculation as above


\newpage


\exx[6]{Show that the set of polynomials $\{1, x, x^2, \ldots, x^p\}$ is a basis of $\P^p$.\vspace*{-1.15cm}\[\][Side note: This is called the \textbf{standard basis} of $\P^p$.]}
% Span is easy (already showed) since each polynomial is of the form c0 + c1*x + ... + cp*x^p.
% To show linearly independent plug in x = 0 to get c1 = 0, then take derivative and plug in 0 to get c2 = 0, and so on.

\exx[9]{Is $\{1+x, 1+x^2, x+x^2\}$ a basis of $\P^2$?}
% Set up system of 3 equations in 3 unknowns (show that it is spanning first -- linear independence is extremely similar). It has rank 3, so it is invertible, so there is always a unique solution. This gives both independence and spanning.

In the previous example, to answer a linear algebra question about $\P^2$, we converted the question into one about matrices, and then we answered that question instead. \emph{This works in complete generality!} We will now start using bases to see that almost any linear algebra question that I can ask you about any vector space can be rephrased in terms of more ``concrete'' things like vectors in $\mathbb{R}^n$ and matrices in $\M_{m,n}$.


\newpage


Our starting point is the following theorem:

\begin{theorem}[Uniqueness of Linear Combinations]
	Let $\V$ be a vector space and let $B$ be a basis for $\V$. Then for every $\v \in \V$, there is exactly one way to write $\v$ as a linear combination of the basis vectors in $B$.
\end{theorem}

\begin{proof}
	The proof is very similar to the corresponding statement about bases of $\R^n$ from the previous course:
	
	\horlines{6}\vspace*{-1.3cm}
	% Idea: every v is a linear combination because B spans V. Linear combination is unique because B is linear independent (otherwise could get contradiction).
	% Since B spans V, can write v = c_1v_1 + ... c_nv_n. If not unique then v = d_1v_1 + ... d_nv_n too. Thus 0 = (c_1-d_1)v_1 + ... + (c_n-d_n)v_n. Thus c_j = d_j for all j, done.
\end{proof}

\noindent The above theorem tells us that the following definition makes sense:

\begin{definition}[Coordinate Vectors]
	Suppose $\V$ is a vector space over a field $\mathbb{F}$ with a finite (ordered) basis $B = \{\v_1,\v_2,\ldots,\v_n\}$, and $\v \in \V$. Then the unique scalars $c_1$, $c_2$, $\ldots$, $c_n \in \mathbb{F}$ for which\\[1.5cm]
	${}$
	% Fill this in here:
	%	\[
%	\[
%		\v = c_1\v_1 + c_2\v_2 + \cdots + c_n\v_n
%	\]
	are called the \textbf{coordinates} of $\v$ with respect to $B$, and the vector\\[1.5cm]
	${}$
	% Fill this in here:
	%	\[
%	\begin{align*}
%		[\v]_{B} \defeq (c_1, c_2, \ldots, c_n)
%	\end{align*}
	is called the \textbf{coordinate vector}\index{coordinate vector} of $\v$ with respect to $B$.
\end{definition}

The above theorem and definition tell us that if we have a basis of a vector space, then we can treat the vectors in that space just like vectors in $\mathbb{F}^n$ (where $n$ is the number of vectors in the basis). In particular, coordinate vectors respect vector addition and scalar multiplication ``how you would expect them to:''

\horlines{1}
% Fill in:
%\[[\v+\w]_{B} = [\v]_{B} + [\w]_{B} \quad \text{and} \quad [c\v]_{B} = c[\v]_{B} \quad \text{for all} \quad \v,\w \in \V, c \in \mathbb{F}.\]


\newpage


\exx[1]{Find the coordinate vector of... $\quad \quad \quad \quad \quad \quad \quad \quad \quad$ ...with respect to the basis $\{1,x,x^2\}$ of $\P^2$.}
% Ask for an example polynomial from the class. Coordinate vector of a2*x^2 + a1*x + a0 is (a0,a1,a2).

\noindent More generally,

\horlines{2}
% The coordinate vector of a_0 + a_1x + ... + a_px^p with respect to the standard basis {1,x,x^2,...,x^p} is [a0,a1,...,ap]

\noindent \textbf{\textcolor{red}{Be careful:}} The order in which the basis vectors appear in $B$ affects the order of the entries in the coordinate vector. This is kind of janky (technically, sets don't care about order), but everyone just sort of accepts it.

\exx[1]{Find the coordinate vector of... $\quad \quad \quad \quad \quad \quad \quad \quad \quad$ ...with respect to the basis $\{x^2,x,1\}$ of $\P^2$.}
% Same quadratic as before. Entries just get reversed in answer.

\exx[9]{Find the coordinate vector of... $\quad \quad \quad \quad \quad \quad \quad \quad \quad$ ...with respect to the basis $\{1+x, 1+x^2, x+x^2\}$ of $\P^2$.}
% Use the same quadratic as in the previous example. Do the calculation, get a different vector than in the previous example.


\newpage


Notice that when we change the basis $B$ that we are working with, coordinate vectors $[\v]_B$ change as well (even though $\v$ itself does not change). We will soon learn how to easily change coordinate vectors from one basis to another, but first we need to know that all coordinate vectors have the same number of entries:

\begin{theorem}[Linearly Independent Sets versus Spanning Sets]
	Let $\V$ be a vector space with a basis $B$ of size $n$. Then
	\begin{enumerate}
		\item Any set of more than $n$ vectors in $\V$ must be linearly dependent, and
		\item Any set of fewer than $n$ vectors cannot span $\V$.
	\end{enumerate}
\end{theorem}

\begin{proof}
	For~(a), suppose there are $m > n$ vectors, which we call $\v_1,\v_2,\ldots,\v_m$. We want to solve $c_1\v_1 + \cdots + c_m\v_m = \0$. This is the same as
	
	\horlines{11}\vspace*{-1.3cm}
	% c_1[v_1] + ... + c_m[v_m] = 0. This is a system of n equations with m unknowns (m > n). There can never be a unique solution in this case, and the system has at least one solution (the zero solution), so there must be infinitely many. In particular, there is a non-zero solution. Maybe draw a short and fat matrix to help out here.
	%
	% For (b), maybe leave for students. Tall and skinny matrix this time (i.e., more equations than unknowns). Rank of the matrix equals dimension of rank, which is at most m < n, so there is something not in the range (i.e., not a linear combination of the columns).
\end{proof}

The previous theorem immediately implies the following one (which we proved for subspaces of $\mathbb{R}^n$ in the previous course):

\begin{corollary}[Uniqueness of Size of Bases]
	Let $\V$ be a vector space that has a basis consisting of $n$ vectors. Then \emph{every} basis of $\V$ has exactly $n$ vectors.
\end{corollary}


\newpage


Based on the previous corollary, the following definition makes sense:

\begin{definition}[Dimension of a Vector Space]
	A vector space $\V$ is called...
	\begin{enumerate}
		\item \textbf{finite-dimensional} if it has a finite basis, and its \textbf{dimension}, denoted by $\mathrm{dim}(\V)$, is the number of vectors in one of its bases.
		
		\item \textbf{infinite-dimensional} if it has no finite basis, and we say that $\mathrm{dim}(\V) = \infty$.
	\end{enumerate}
\end{definition}

\exx[7]{Let's compute the dimension of some vector spaces that we've been working with.}
% Create a table.
% Dimension of R^n is n.
% C^n is n.
% P^p is p+1.
% \M_{mn} is mn.
% P is infinite.
% F is infinite (but larger infinite: 2^c, whereas P has cardinality aleph_0!)
% Give standard basis in table too.

Before proceeding, it is worth noting that every finite-dimensional vector space has a basis. The situation for infinite-dimensional vector spaces, however, is a bit murky...
	
\horlines{6}
% For example, what is a basis of \mathcal{F}? (space of functions) I can't tell you! Even every basis of \mathcal{C} (the space of continuous functions) must contains pathological hideous functions that we can't really write down.

%\item We might sometimes say that all finite-dimensional vector spaces are ``isomorphic'' to $\R^n$ (or $\C^n$ or $\mathbb{F}^n$). This just means that we can use coordinate vectors to treat them the same.
	

\newpage


\section*{Change of Basis}

Sometimes one basis (i.e., coordinate system) will be much easier to work with than another. While it is true that the standard basis (of $\R^n$, $\C^n$, $\P^p$, or $\M_{m,n}$) is often the simplest one to use for calculations, other bases often reveal hidden structure that can make our lives easier. \\

We will discuss how to find these other bases shortly, but for now let's talk about how to convert coordinate systems from one basis to another.

\begin{definition}[Change-of-Basis Matrix]
	Suppose $\V$ is a vector space with bases $B = \{\v_1,\v_2,\ldots,\v_n\}$ and $C$. The \textbf{change-of-basis matrix} from $B$ to $C$, denoted by $P_{C\leftarrow B}$, is the $n\times n$ matrix whose columns are the coordinate vectors $[\v_1]_{C},[\v_2]_{C},\ldots,[\v_n]_{C}$:\\[1cm]
	${}$
	% Fill this in here:
%	\[
%		P_{C\leftarrow B} \defeq \big[ \ [\v_1]_{C} \ {\color{gray}|} \ [\v_2]_{C} \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ [\v_n]_{C} \ \big].
%	\]
\end{definition}

%The idea is to think of $B$ as the ``old'' basis and $C$ as the ``new'' basis, so the columns of $P_{C\leftarrow B}$ are the vectors from the ``old'' basis, but ``updated'' so that they are represented in the new basis.\\

The following theorem shows that the change-of-basis matrix $P_{C\leftarrow B}$ does exactly what its name suggests: it converts coordinate vectors from basis $B$ to basis $C$.

\begin{theorem}[Change-of-Basis Matrices]\label{thm:cob_matrices}
	Suppose $B$ and $C$ are bases of a finite-dimensional vector space $\V$, and let $P_{C \leftarrow B}$ be the change-of-basis matrix from $B$ to $C$. Then\smallskip

	\begin{enumerate}[label=\alph*)]
		\item $P_{C\leftarrow B}[\v]_B = [\v]_C$ for all $\v \in \V$, and\smallskip
		
		\item $P_{C\leftarrow B}$ is invertible and $P_{C\leftarrow B}^{-1} = P_{B\leftarrow C}$.\smallskip
	\end{enumerate}
	
	\noindent Furthermore, $P_{C\leftarrow B}$ is the unique matrix with property~(a).
\end{theorem}

Some notes are in order:

\horlines{5}

% NOTE 1: The above theorem is the main reason why we use the notation $P_{C \leftarrow B}$ instead of $P_{B\rightarrow C}$: in part~(a) of the above theorem, the middle $B$s ``cancel out'' and leave just the $C$s behind. \\

% NOTE 2: The way to remember the definition is that this matrix turns B into C, so you should represent B in C (as columns)


\newpage


\begin{proof}[Proof of Theorem~\ref{thm:cob_matrices}]
	For~(a), suppose $\v \in \V$ and write $\v = c_1\v_1 + c_2\v_2 + \cdots + c_n\v_n$, so that $[\v]_{B} = (c_1,c_2,\ldots,c_n)$. Then
	
	\horlines{11}\vspace*{-1.3cm}
	%	we can directly compute
	%	\begin{align*}
	%		P_{C\leftarrow B}[\x]_{B} & = \big[ \ [\v_1]_{C} \ {\color{gray}|} \ [\v_2]_{C} \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ [\v_n]_{C} \ \big]\begin{bmatrix}c_1\\c_2\\\vdots\\c_n\end{bmatrix} \\
	%		& = c_1[\v_1]_{C} + c_2[\v_2]_{C} + \cdots + c_n[\v_n]_{C} \\
	%		& = [c_1\v_1 + c_2\v_2 + \cdots + c_n\v_n]_{C} \\
	%		& = [\x]_{C}.
	%	\end{align*}
	%	
	%	On the other hand, to see why $P_{C\leftarrow B}$ is the \emph{unique} matrix with property~(a), suppose $P \in \M_n$ is any matrix such that $P[\x]_{B} = [\x]_{C}$ for all $\x \in \V$. If $\x = \v_i$ then we see that $[\x]_B = \e_i$ (the $i$-th standard basis vector), so $P[\x]_B = P\e_i$ is the $i$-th column of $P$. On the other hand, it is also the case that $P[\x]_B = [\x]_C = [\v_i]_C$. Thus the $i$-th column of $P$ is $[\v_i]_C$, so $P = P_{C\leftarrow B}$ by definition.
	%	
	%	To see why~(b) holds, observe that since $B = \{\v_1,\v_2,\ldots,\v_n\}$ is a basis of $\V$, we know that $\{[\v_1]_C,[\v_2]_C,\ldots,[\v_n]_C\}$ is a basis of $\mathbb{F}^n$ by Exercise~\ref{exer:coord_vector_span_indep}. Thus the columns of $P_{C\leftarrow B}$ form a basis of $\mathbb{F}^n$, so it is invertible by Theorem~??. Furthermore, $P_{C\leftarrow B}[\x]_{B} = [\x]_{C}$ implies $[\x]_{B} = (P_{C\leftarrow B})^{-1}[\x]_{C}$, so $(P_{C\leftarrow B})^{-1}$ is the change-of-basis matrix from $C$ to $B$. By uniqueness, it follows that $(P_{C\leftarrow B})^{-1} = P_{B\leftarrow C}$.
\end{proof}


\exx[8]{Find the change-of-basis matrix $P_{C\leftarrow B}$ for the bases $B = \{1,x,x^2\}$ and $C = \{1+x,1+x^2,x+x^2\}$ of $\P^2$. Then find the coordinate vector of... $\quad \quad \quad \quad \quad \quad \quad \quad \quad$ ...with respect to $C$.}
% Use the same polynomial suggested by the class earlier this week.
% Directly computing P_C<-B looks messy (write down what its columns would be and note that we would have to solve a linear system for each one). Instead, write down P_B<-C and note that it is much easier to find (easy to convert INTO the standard basis). Then just invert.
% [w1]_B = [1 1 0], [w2]_B = [1 0 1], [w3]_B = [0 1 1]. Thus
% P = [1 1 0;1 0 1;0 1 1]. The change-of-basis matrix from B to C is the inverse of this, which is (1/2)*[-1 1 1;1 -1 1;1 1-1]. Then just multiply to get new coordinate vector. Should be the same as from previous example.


\newpage


The previous example was not too difficult, since $B$ happened to be the standard basis of $\P^2$. However, if it \emph{weren't} the standard basis, then computing the columns of $P_{C\leftarrow B}$ would have been much more difficult (each column would require us to solve a linear system). The following theorem gives a better way of computing $P_{C\leftarrow B}$ in general:

\begin{theorem}[Computing Change-of-Basis Matrices]
	Let $\V$ be a finite-dimensional vector space with bases $B$, $C$, and $E$. Then the reduced row echelon form of the augmented matrix
	\[
		\big[ \ P_{E \leftarrow C} \ {\color{gray}|} \ P_{E \leftarrow B} \ \big] \quad \text{is} \qquad\qquad\qquad\qquad {}
	%Fill in: \smallaug{I}{P_{C \leftarrow B}}.
	\]
\end{theorem}

\begin{proof}
	Suppose for now that we just wanted to compute $[\v_j]_{C}$ (the $j$-th column of $P_{C\leftarrow B}$).
	
	\horlines{11}\vspace*{-1.3cm}
	% Side note: More general fact is that if A is invertible, then [A | B] row reduces to [I | A^{-1}B]. This gives us what we want then, since [P_EC | P_EB] row reduces to [I | P_CE P_EB] = [I | P_CB].
	% One way to find it would be to first compute $[\v_1]_{E}$ and then solve the linear system $P_{E\leftarrow C}[\v_1]_{C} = [\v_1]_{E}$, which has the augmented form $[P_{E \leftarrow C} \ {\color{gray}|} \ [\v_1]_{E}\, ]$, which can be row reduced to $[I \ {\color{gray}|} \ [\v_1]_{C}\, ]$ since $P_{E \leftarrow C}$ is invertible.
	%	
	% However, we can then repeat this process to find $[\v_2]_{C}, \ldots, [\v_n]_{C}$ (the other columns of $P_{C\leftarrow B}$): we solve the linear systems with augmented matrix forms $[P_{E \leftarrow C} \ {\color{gray}|} \ [\v_2]_{E}\, ]$, $\ldots$, $[P_{E \leftarrow C} \ {\color{gray}|} \ [\v_n]_{E}\, ]$. Since the coefficient matrix $P_{E \leftarrow C}$ is the same for all of these linear systems, we can solve them simultaneously by row reducing the $n \times 2n$ matrix
	%	\[
	%	[P_{E \leftarrow C} \ {\color{gray}|} \ [\v_1]_{E} \ {\color{gray}|} \ [\v_2]_{E} \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ [\v_n]_{E}\, ] = [P_{E \leftarrow C} \ {\color{gray}|} \ P_{E \leftarrow B}]
	%	\]
	%	into the form 
	%	\[
	%	[I \ {\color{gray}|} \ [\v_1]_{C} \ {\color{gray}|} \ [\v_2]_{C} \ {\color{gray}|} \ \cdots \ {\color{gray}|} \ [\v_n]_{C}\, ] = [I \ {\color{gray}|} \ P_{C \leftarrow B}].
	%	\]
\end{proof}


\noindent It is worth making some notes about the above theorem:
\begin{itemize}
	\item $P_{E \leftarrow B}$ and $P_{E \leftarrow C}$ are both...
	
	\horlines{2}
	% easy to compute if we choose $E$ to be the standard basis. In general, converting \emph{into} the standard basis is easy since you can just ``eyeball'' the entries of the coefficient vectors.
	
	
	\newpage
	
	
	\item This method for computing $P_{C\leftarrow B}$ is almost identical to the method you learned in introductory linear algebra for computing...
	
	\horlines{1}
	% matrix inverses
\end{itemize}

\exx[16]{Find the change-of-basis matrix $P_{C \leftarrow B}$, where
$$
	B = \big\{\quad \quad \quad \quad, \quad \quad \quad \quad, \quad \quad \quad \quad\big\} \quad \text{and} \quad C = \big\{\quad \quad \quad \quad, \quad \quad \quad \quad, \quad \quad \quad \quad\big\}
$$
are bases of $\quad \quad \quad \quad$. Then compute $[\mathbf{v}]_{C}$ if $[\mathbf{v}]_{B} = (1,2,3)$.}

\end{document}