\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amssymb,amsmath}
\usepackage{mathrsfs}
\usepackage[pdftex]{graphicx}
\usepackage{tikz}
\usetikzlibrary{intersections, calc}



\topmargin = 0.1in \textwidth=5.7in \textheight=8.9in

\oddsidemargin = 0.2in \evensidemargin = 0.2in


\begin{document}

\begin{center}
MATHEMATICS E-23a, Fall 2016 \\
Linear Algebra and Real Analysis I

\smallskip

Module \#1, Week 1 (Fields, Vectors, and Matrices)
\end{center}
Authors: Paul Bamberg and Kate Penner\\
R scripts by Paul Bamberg \\
Last modified: July 7, 2016 by Paul Bamberg
\medskip

\paragraph*{Reading}

\begin{itemize}
\item Hubbard, Sections 0.1 through 0.4
\item Hubbard, Sections 1.1, 1.2, and 1.3
\item Lawvere and Schanuel, \underline{Conceptual Mathematics}\\
Search the Internet for  ``Harvard HOLLIS" and type ``Conceptual Mathematics" into the Search box.\\
Choose View Online. You will have to log in with your Harvard PIN.

At a minimum, read the following:\\
Article I (Sets, maps, composition -- definition of a category)\\
Session 2 \\
 This is very easy reading.

DO NOT PURCHASE THIS BOOK! We will be using only a little bit of it.

\end{itemize}

\paragraph*{Recorded Lectures}
\begin{itemize}
\item September 3, 2015 (watch on September 1)
\item September 8, 2015 (watch on September 6)
\item September 10, 2015 (watch on September 8)
\end {itemize}

\pagebreak

\paragraph*{Proofs to present in section or to a classmate who has done them.}
\begin{itemize}
\item 1.1
Suppose that $a$ and $b$ are two elements of a field $F$. Using only the axioms for a field, prove the following:
\begin{itemize}
\item$\forall a \in F$, $0a = 0.$
\item If $ab =0$, then either $a$ or $b$ must be 0. 
\item The additive inverse of $a$ is unique.
\end{itemize}

\item 1.2(Generalization of Hubbard, proposition 1.2.9)
$A$ is an $n \times m$ matrix. The entry in row $i$, column $j$ is $a_{i,j}$\\
$B$ is an $m \times p$ matrix.  \\
$C$ is an $p \times q$ matrix.  \\ 
The entries in these matrices are all from the same field $F$.
Using summation notation, prove that matrix multiplication is associative:\\ that $(AB)C = A(BC)$.
Include a diagram showing how you would lay out the calculation in each case so the intermediate results do not have to be recopied.

\item 1.3 (Hubbard, proposition 1.3.14)
 Suppose that linear transformation\\ $T: F^n \rightarrow
F^m$ is represented by the $m \times n$ matrix $[T]$. 

\begin{itemize}
\item  Suppose that the matrix $[T]$ is invertible. Prove that the linear transformation $T$
is one-to-one and onto (injective and surjective), hence invertible.

\item  Suppose that linear transformation $T$ is invertible. Prove that its inverse $S$ is linear and
that the matrix of $S$ is $[S] = [T]^{-1}$

\end{itemize}

Note: Use * to denote matrix multiplication and $\circ$ to denote
composition of linear transformations. You may take it as already
proved that matrix multiplication represents composition of linear
transformations. Do not assume that $m=n.$ That is true, but we are far from being able to prove it, and you do not need it for the proof.

\end{itemize}

\pagebreak

\paragraph*{R Scripts}
\begin{itemize}
\item Script 1.1A-Finite Fields.R\\
Topic 1 - Why the real numbers form a field\\
Topic 2 - Making a finite field, with only five elements\\
Topic 3 - A useful rule for finding multiplicative inverses
\item Script 1.1B-PointsVectors.R\\
Topic 1 - Addition of vectors in $\mathbb{R}^2$\\
Topic 2 - A diagram to illustrate the point-vector relationship\\
Topic 3 - Subtraction and scalar multiplication
\item Script 1.1C-Matrices.R\\
Topic 1 - Matrices and Matrix Operations in R\\
Topic 2 - Solving equations using matrices\\
Topic 3 - Linear functions and matrices\\
Topic 4 - Matrices that are not square\\
Topic 5 - Properties of the determinant
\item Script 1.1D-MarkovMatrix\\
Topic 1 - A game of volleyball\\
Topic 2 - traveling around on ferryboats
\item Script 1.1L-LinearMystery\\
Topic 1 - Define a mystery linear function $fMyst: \mathbb{R}^2 \rightarrow \mathbb{R}^2$
\end{itemize}




\pagebreak
\begin{center}
\end{center}
\section{Executive Summary}
\begin{itemize}
\item Quantifiers and Negation Rules\\
The ``universal quantifier'' $\forall$ is read ``for all.''\\
The ``existential quantifier'' $\exists$ is read ``there exists.'' It is usually\\ followed by ``s.t,'' a standard abbreviation for ``such that.''\\
The negation of ``$\forall x, P(x)$ is true'' is ``$\exists x, P(x)$ is not true.''\\
The negation of ``$\exists x, P(x)$ is true'' is ``$\forall x, P(x)$ is not true.''\\
The negation of ``$P$ and $Q$ are true'' is ``either $P$ or $Q$ is not true.''\\
The negation of ``either $P$ or $Q$ is true'' is ``both $P$ and $Q$ are not true.''\\
\item Functions\\
A function $f$ needs two sets: its domain $X$ and its codomain $Y$. \\
$f$ is a rule that, to any element $x \in X$, assigns a specific element $y \in Y$. We write $y = f(x).$\\
$f$ must assign a value to every $x \in X$, but not every $y \in Y$ must be of the form $f(x)$. The subset of the codomain consisting of elements that are of the form $y = f(x)$ is called the \emph{image} of $f$. If the image of $f$ is all of the codomain $Y$, $f$ is called \emph{surjective} or \emph{onto}.\\
$f$ need not assign different of elements of $Y$ to different elements of $X$. If $x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$, $f$ is called \emph{injective} or \emph{one-to-one}\\
If $f$ is both surjective and injective, it is \emph {bijective} and has an inverse $f^{-1}$.\\
\item Categories\\
A category $\mathscr{C}$ has objects (which might be sets) and arrows (which might be functions)\\
An arrow $f$ must have a specific domain object $X$ and a specific codomain object $Y$; we write $f: X \rightarrow Y$ or $X \xrightarrow{f}Y$.\\
If arrows $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ are in the category, then the composition arrow $g \circ f: X \rightarrow Z$ is in the category.\\
For every object $X$ there must be an identity arrow $I_X: X \rightarrow X$\\
Identity laws: Given $f: X \rightarrow Y$, $f \circ I_X = f$ and $I_Y \circ f = f$.\\
Associative law: given $X \xrightarrow{f}Y \xrightarrow{g}Z \xrightarrow{h}W$, $h\circ(g \circ f) = (h\circ g) \circ f $\\
Given an arrow $f: X \rightarrow Y$, an arrow $g: Y \rightarrow X$ such that $g\circ f = I_X$ is called a \emph{retraction}.\\
Given an arrow $f: X \rightarrow Y$, an arrow $g: Y \rightarrow X$ such that $f\circ g = I_Y$ is called a \emph{section}.\\
If, for arrow $f$, arrow $g$ is both a retraction and a section, then $g$ is the inverse of $f$, $g = f^{-1}$, and $g$ must be unique.\\
Almost everything in mathematics is a special case of a category.




\end{itemize}

\pagebreak

 


\subsection{Fields and Field Axioms}A {\bf field $F$} is a set of elements for which the
familiar operations of addition and multiplication are defined and behave in the
usual way. Here is a set of axioms for a field. You can use them to
prove theorems that are true for any field.
\begin{enumerate}
\item Addition is commutative: $a+b = b+a$.
\item Addition is associative: $(a+b)+c = a + (b+c)$. \item
Additive identity: $\exists 0$ such that $\forall a \in F, 0 + a = a
+ 0 = a$.

\item Additive inverse: $\forall a \in F, \exists -a$  such that $-a + a = a + (-a)
=0$.

\item Multiplication is associative: $(ab)c = a(bc)$.

\item Multiplication is commutative: $ab = ba$.

\item Multiplicative identity: $\exists 1$ such that $\forall a \in F, 1a =
a$.


\item Multiplicative inverse: $\forall a \in F-\{0\}, \exists a^{-1}$  such that $a^{-1}a  =
1$.

\item Distributive law: $a(b+c) = ab + ac$.

\end{enumerate}

Examples of fields include:



 The {\bf rational numbers} $\mathbb{Q}$. 
%When you learned to add and multiply fractions in middle school, you were proving that the rational numbers are closed under the operations of addition and multiplication.

 The {\bf real numbers} $\mathbb{R}$. 
%When you learned to add and multiply decimals, you were close to proving that the real numbers are closed under the operations of addition and multiplication. (As a practical matter, proving that addition and multiplication of infinite decimals is commutative and associative is tricky.)

 The {\bf complex numbers} $\mathbb{C}$. 
%When you learned the trick of multiplying the numerator and denominator of a complex fraction by the complex conjugate of the denominator, e.g.
%$$\frac{3+2i}{2 + i} = (\frac{3+2i}{2 + i})(\frac{2-i}{2 - i}) = \frac{8 + i}{5}$$
%you were verifying that every nonzero complex number has a multiplicative inverse.

 The {\bf finite field} $\mathbb{Z}_p$, constructed for any  prime number $p$ as follows:
\begin{itemize}
 \item Break up the set of integers into $p$ subsets.  Each subset is named after the
remainder when any of its elements is divided by $p$.

$[a]_p = \{m  | m = np+a, n \in \mathbb{Z}\}$

Notice that $[a+kp]_p = [a]_p$ for any $k$. There are only $p$ sets,
but each has many alternate names. These $p$ infinite sets are the elements of the field
$\mathbb{Z}_p$.

\item Define addition by $[a]_p + [b]_p = [a+b]_p$. Here $a$ and $b$
can be any names for the subsets, because the answer is independent
of the choice of name. The rule is ``Add $a$ and $b$, then divide by
$p$ and keep the remainder.''

\item Define multiplication by $[a]_p  [b]_p = [ab]_p$. Again $a$ and $b$
can be any names for the subsets, because the answer is independent
of the choice of name. The rule is ``Multiply $a$ and $b$, then
divide by $p$ and keep the remainder.''

\end{itemize}
\pagebreak
\subsection{Points and Vectors}

$F^n$ denotes the set of ordered lists of $n$ elements from a field
$F$. Usually the field is $\mathbb{R},$ but it could be the field of
complex numbers $\mathbb{C}$ or a finite field like $\mathbb{Z}_5.$ 

A given element of $F^n$ can be regarded either as a point, which represents
``position data,'' or as a vector, which represents ``incremental
data.''


If an element of $F^n$ is a point, we represent it by a bold letter
like $\bold{p}$ and write it as a column of elements enclosed in
parentheses.
$$\bold{p} = \begin{pmatrix} 1.1 \\ -3.8 \\2.3
\end{pmatrix} $$
If an element of $F^n$ is a vector, we represent it by a bold
letter with an arrow like $\vec{\bold{v}}$ and write it as a
column of elements enclosed in square brackets.
$$\vec{\bold{v}} = \begin{bmatrix} -0.2 \\ 1.3 \\ 2.2
\end{bmatrix}$$
To add a vector to a point, we add the components in identical positions together.  The result is a point: $\bold{q} = \bold{p}+ \vec{\bold{v}}$. 
Geometrically we represent this by anchoring the vector at the initial point $\bold{p}$.  The location of the arrowhead of the vector is the point $\bold{q}$ that represents our sum.\\

\begin{center}
\begin{tikzpicture}[scale=1]
  \coordinate[label=below:$\bold{p}$] (p) at (0,0);
  \coordinate[label=right:$\bold{q}$] (q) at (3,0.5);
  

\draw[->,style = very thick](p) -- node[below=1pt]{$\vec{\bold{v}}$}(q);
  
  \foreach \p in {p,q}
  \fill (\p) circle (0.3mm);
\end{tikzpicture}
\end{center}

To add a vector to a vector, we again add component by component.  The result is a vector.
Geometrically, the vector created by beginning at the initial point of the first vector and ending at the arrowhead of the second vector is the represents our sum.

\begin{center}
\begin{tikzpicture}[scale=1]
  \coordinate (A) at (0,0);
  \coordinate (B) at (3,-1);
  \coordinate (C) at (5,1);
  

\draw[->,style = very thick](A) -- node[below=1pt]{$\vec{\bold{v}}$}(B);
\draw[->,style = very thick](B) -- node[below=1pt]{$\vec{\bold{w}}$}(C);
\draw[->,style = very thick](A) -- node[above=1pt]{$\vec{\bold{v}}+\vec{\bold{w}}$}(C);
  
  \foreach \p in {A,B,C}
  \fill (\p) circle (0.3mm);
\end{tikzpicture}
\end{center}

To form a scalar multiple of a vector, we multiply each component by the scalar.   In $\mathbb{R}^n$, the geometrical effect is to multiply the length of the vector by the scalar. If the scalar is a negative number, we switch the position of the arrow to the other end of the vector.

\begin{center}
\begin{tikzpicture}[scale=1]
  \coordinate (A) at (0,0);
  \coordinate (B) at (3/2, 1/2);
  \coordinate (C) at (2,0);
  \coordinate (D) at (5,1);
  \coordinate (E) at (9,1);
  \coordinate (F) at (6, 0);
   
  

\draw[->,style = very thick](A) -- node[below=1pt]{$\vec{\bold{v}}$}(B);
\draw[->,style = very thick](C) -- node[below=1pt]{$2\vec{\bold{v}}$}(D);
\draw[->,style = very thick](E) -- node[above=1pt]{$-2\vec{\bold{v}}$}(F);
  
  \foreach \p in {A,B,C,D,E,F}
  \fill (\p) circle (0.3mm);
\end{tikzpicture}
\end{center}

\subsection{Standard basis vectors}
The {\bf standard basis vector} $\vec{\bold{e}}_k$ has a 1 as its $k$th component, and all its other components are 0. Since the additive identity 0 and the multiplicative identity 1 must be present an any field, there will always be $n$ standard basis vectors in $F^n$. Geometrically, the standard basis vectors in $\mathbb{R}^2$ are usually associated with "one unit east" and "one unit north" respectively.
\begin{center}
\begin{tikzpicture}[scale=0.8]
  \coordinate (A) at (0,0);
  \coordinate (B) at (1, 0);
  \coordinate (C) at (0,1);
  
  

\draw[->,style = very thick](A) -- node[below=1pt]{$\vec{\bold{e}}_1$}(B);
\draw[->,style = very thick](A) -- node[left=1pt]{$\vec{\bold{e}}_2$}(C);
 
  
\end{tikzpicture}
\end{center}
\subsection{Matrices and linear transformations}
An $m \times n$ {\bf matrix }over a field $F$ has $m$ rows and $n$ columns. \\
Matrices represent linear functions, also known as {\bf linear transformations}:\\
A function $\bold{g}: F^n \rightarrow F^m $ is called linear if 
$$g(a\vec{\bold{v}}+b\vec{\bold{w}})=
ag(\vec{\bold{v}})+bg(\vec{\bold{w}}).$$
For a linear function  $\bold{g}$, if we know the value of $\bold{g}(\vec{\bold{e}}_i)$ for each standard basis vector $\vec{\bold{e_i}}$,
the value of $\bold{g}(\vec{\bold{v}})$ for any vector $v$ follows by linearity:
$$\bold{g}(v_1\vec{\bold{e}}_1+v_2\vec{\bold{e}}_2+ \cdots +v_n\vec{\bold{e}}_n )=
v_1\bold{g}(\vec{\bold{e}}_1)+v_2\bold{g}(\vec{\bold{e}}_2) + \cdots + v_n\bold{g}(\vec{\bold{e}}_n)$$

The matrix $G$ that represents the linear function $\bold{g}$ is formed by using $\bold{g}(\vec{\bold{e}}_k)$ as the $k$th column. Then, if $g_{i,j}$ denotes the entry in the $i$th row and $j$th column of matrix $G$, the function value $\vec{\bold{w}}=\bold{g}(\vec{\bold{v}})$ can be computed by the rule

$$w_i = \sum_{j=1}^ng_{i,j}v_j$$
\subsection{Matrix multiplication}
 If $m \times n$ matrix $G$ represents linear function $\bold{g}: F^n \rightarrow F^m$ and  $n \times p$ matrix $H$ represents linear function $\bold{h}: F^p \rightarrow F^n$, then the matrix product $GH$  is defined so that it represents their composition: the linear function $\bold{g}\circ\bold{h}: F^p \rightarrow F^m$.

 Start with standard basis vector $\vec{\bold{e}}_j$. Function $\bold{h}$ converts this to the $j$th column $\vec{\bold{h}}_j$ of matrix $H$. Then function $\bold{g}$ converts this column to $\bold{g}(\vec{\bold{h}}_j)$, which must therefore be the $j$th column of matrix $GH$.

The rule for forming the product $GH$ can be stated in terms of the
rule for a matrix acting on a vector: to form $GH$, just multiply $G$ by each column of $H$ in turn, and put the results side by side to
create the matrix $GH$. If $C = GH$,

$$c_{i, j}= \sum_{k=1}^ng_{i,k}h_{k,j}.$$While matrix multiplication is associative, it is not commutative.  Order matters!

\pagebreak

\subsection{Examples of matrix multiplication}
\hspace{62pt} $B\begin{bmatrix}0  & 1 \\ 2 & -1 \\ -2 & 0\end{bmatrix}$ \hspace{150pt} $A\begin{bmatrix}2 & 1 & 0 \\ 1 & -1 & -2 \end{bmatrix}$\\
 \vspace{10pt}\\
 $A\begin{bmatrix}2 & 1 & 0 \\ 1 & -1 & -2 \end{bmatrix}$  $\begin{bmatrix}2 & 1  \\ -6 & 2 \end{bmatrix}AB$ \hspace{80pt} $B\begin{bmatrix}0  & 1 \\ 2 & -1 \\ -2 & 0\end{bmatrix}$
$\begin{bmatrix}1  & -1 & 2\\ 3 & 3& -2\\-4  & -2 & 0\end{bmatrix}BA$

The number of columns in the first factor must equal the number of rows in the second factor.
 




\subsection{Function inverses}
A function $f: X \rightarrow Y $ is invertible if it has the following two properties:
\begin{itemize}
\item It is {\bf injective} (one-to-one): if $f(x_1) = f(x_2)$ , then $ x_1 = x_2$.
\item It is {\bf surjective} (onto): $\forall y \in Y, \exists x \in X$ such that $f(x) = y$.

\end{itemize}

The inverse function $g = f^{-1}$ has the property that if $f(x) = y$ then $g(y) = x$. So $g(f(x)) = x$ and $f(g(y)) = y$. Both $f\circ g$ and $g \circ f$ are the identity function.

\subsection{The determinant of a $2 \times 2$ matrix}
For matrix $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$, $\det A = ad-bc$.
If you fix one column, it is a linear function of the other column, and it changes sign if you swap the two columns.

\subsection{Matrix inverses}
A non-square $m \times n$ matrix $A$ can have a ``one-sided {\bf inverse}.''

If $m > n$, then $A$ takes a vector in $\mathbb{R}^n$ and produces
a longer vector in $\mathbb{R}^m$. In general, there will be many
matrices $B$ that can recover the original vector in
$\mathbb{R}^n$, so that $BA = I_n$. In this case there is no right inverse.

If $m < n$, then $A$ takes a vector in $\mathbb{R}^n$ and produces
a shorter vector in $\mathbb{R}^m$. In general, there will be no
left inverse matrix $B$ that can recover the original vector in
$\mathbb{R}^n$, but there may be many different right inverses for which $AB = I_m.$


For a square matrix, it is possible for both a right
inverse $B$ and a left inverse $C$ to exist. In this case, we can prove that $B$ and
$C$ are equal and they are unique. We can say that ``an inverse''
$A^{-1}$ exists, and it represents the inverse of the linear function represented by matrix $A$.  

You can find the inverse of a $2\times 2$ matrix $A$ whose determinant is not zero by using the formula 
$$A^{-1}=\frac{1}{\det(A)} \begin{bmatrix} d & -b \\ -c & a\end{bmatrix}=\frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a\end{bmatrix}$$

\subsection{Matrix transposes}
The {\bf transpose} of a given matrix $A$ is written $A^T$.  The two are closely related.  The rows of $A$ are the columns of $A^T$ and the columns of $A$ are the rows of $A^T$. 
$$A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}, A^T=\begin{bmatrix} a & c \\ b & d\end{bmatrix}$$

The transpose of a matrix product is the product of the transposes, but in the opposite order:

$$(AB)^T = B^TA^T$$

A similar rule holds for matrix inverses:

$$(AB)^{-1} = B^{-1}A^{-1}$$

\subsection{Applications of matrix multiplication}
In these examples, the ``sum of products" rule for matrix multiplication arises naturally, and so it is efficient to use matrix techniques.
\begin{itemize}

\item Counting paths:
Suppose we have four islands connected by ferry routes:
\begin{center}
\begin{tikzpicture}[scale=0.4]
  \coordinate [label=left:1]  (I1)at (-2,2);
  \coordinate  [label=left:2](I2) at (-2,-2);
  \coordinate  [label=right:3](I3) at (2,2);
  \coordinate  [label=right:4](I4) at (2,-2);
 

\draw[->,style = very thick](I1) -- (I2);
\draw[<->,style = very thick](I1) -- (I3);
\draw[->,style = very thick](I3) -- (I4);
\draw[->,style = very thick](I2) -- (I4);
\draw[->,style = very thick](I4) -- (I1);
.
  \foreach \p in {I1,I2,I3,I4}
  \draw (\p) circle (1cm);
\end{tikzpicture}
\end{center}

The entry in row $i$, column $j$ of the matrix $A=\begin{bmatrix}0 & 0 & 1 & 1\\
1 & 0 & 0 & 0\\1 & 0 & 0 & 0\\ 0 & 1 & 1 &0\end{bmatrix}$ shows how many ways there are to reach island $i$ by a single ferry ride, starting from island $j$.
The entry in row $i$, column $j$ of the matrix $A^n$ shows how many ways there are to reach island $i$ by a sequence of $n$ ferry rides, starting from island $j$.

\item Markov processes: A game of beach volleyball has two ``states'': in state 1, team 1 is serving, in state 2, team 2 is serving. With each point that is played there is a ``state transition'' governed by probabilities:
for example, from state 1, there is a probability of 0.8 of remaining in state 1, a probability of 0.2 of moving to state 2. The transition probabilities can be collected into a matrix like $A =
\begin{bmatrix}0.8 & 0.3 \\ 0.2 & 0.7\end{bmatrix}.$ Then the matrix $A^n$ specifies the transition probabilities that result from playing $n$ consecutive points.

\end{itemize}







\pagebreak

\section{Lecture Outline}
\begin{enumerate}

\item Quantifiers and negation\\

Especially when you are explaining a proof to someone, it saves some
writing to use the symbols $\exists$ (there exists) and $\forall$
(for all).

Be careful when negating these.

The negation of ``$\forall x, P(x)$ is true'' is ``$\exists x, P(x)$
is not true.''

The negation of ``$\exists x, P(x)$ is true'' is ``$\forall x, P(x)$
is not true.''


When negating a statement, also bear in mind that

The negation of ``$P$ and $Q$ are true'' is ``either $P$ or $Q$ is
not true.''

The negation of ``either $P$ or $Q$ is true'' is ``both $P$ and $Q$
are not true.''

For practice, let's negate the following statements (which may or
may not be true!)

\begin{itemize}
\item There exists an even prime number.

Negation: \vspace{15pt}

\item All 11-legged alligators are orange with blue spots. (Hubbard, page 5)

Negation: \vspace{50pt}

\item  The function $f(x)$ is continuous on the open interval (0,1),
which means that
$\forall x \in (0,1), \forall \epsilon > 0, \exists \delta
>0$ such that $\forall y \in (0,1),\\ |y-x| < \delta$ implies
$|f(y)- f(x)| < \epsilon.$ \\

Negation: $f(x)$ is discontinuous on the open interval (0,1) means that




\end{itemize}
\pagebreak


\item Set notation\\
Here are the standard set-theoretic symbols:
\begin{itemize}
\item $\in$ (is an element of)

\item \{$a| p(a)$\} (the set of elements $a$ for which $p(a)$ is true)

\item $\subset$ (is a subset of)

\item $\cap$ (intersection)

\item $\cup$ (union)

\item $\times$ (Cartesian product)

\item - or $\backslash$ (set difference)
\end{itemize}

Using the integers $\mathbb{Z}$ and the real numbers $\mathbb{R}$,
let's construct some sets. In each case there is one way to
describe the set using a restriction and another more constructive
way to describe the set.
\begin{itemize}
\item The set of real numbers whose cube is greater than 8 in magnitude.

Restrictive: \vspace{55pt}

Constructive: \vspace{55pt}


\item The set of coordinate pairs for points on the circle of radius 2
centered at the origin (an example of a ``smooth manifold'').

 Restrictive: \vspace{55pt}

Constructive: \vspace{55pt}
\end{itemize}
\pagebreak

\item Function terminology:\\

Here are some terms that should be familiar from your study of
precalculus and calculus:

\large

$
\begin{array}{|c|c|c|c|}
\hline   \mbox{   } & \mbox{Example a      } & \mbox{Example b }&
\mbox{Example c       }\\ 
\cline{1-4}
\mbox{domain}    & & &  \\
\cline{1-4}
\mbox{codomain}    & & &  \\
\cline{1-4}
\mbox{image}    & & &  \\
\cline{1-4}
\mbox{one-to-one = injective}    & & &  \\
\cline{1-4}
\mbox{onto = surjective}    & & &  \\
\cline{1-4}
\mbox{invertible = bijective}    & & &  \\
\cline{1-4}
\end{array}$

\normalsize

 Using the sets $X = \{1,2\}$ and $Y
= \{A,B,C\}$, draw diagrams to illustrate the following functions,
and fill in the table to show how the terms apply to them:

\begin{itemize}
\item $f: X \rightarrow Y, f(1) = A, f(2) = B$.
\vspace{90pt}

\item $g: Y \rightarrow X, g(A) = 1, g(B) = 2, g(C) = 1$.
\vspace{90pt}

\item $h: Y \rightarrow Y, h(A) = B, h(B) = C, h(C) = A$. (a permutation)
\vspace{90pt}

\end{itemize}

\pagebreak

Here are those function words again, with two additions:


\begin{itemize}
\item domain
\item natural domain (often deduced from a formula)
\item codomain
\item image
\item one-to-one = injective
\item onto = surjective
\item invertible = bijective
\item inverse image = $\{x | f(x) \in A\}$
\end{itemize}

Here are functions from $\mathbb{R}$ to $\mathbb{R}$, defined by
formulas.

\begin{itemize}
\item $f_1(x) = x^2$ \item $f_2(x) = x^3$ \item $f_3(x) = \log x$(natural logarithm)
\item $f_4(x) = e^x$
\end{itemize}

\begin{itemize}
\item Find one that is not injective (not one-to-one)
\vspace{25pt}


\item For $f_1$, what is the inverse image of $(1,4)$?
\vspace{30pt}

\item Which function is invertible as a function from $\mathbb{R}$
to $\mathbb{R}$? \vspace{30pt}

\item What is the natural domain of $f_3$?
\vspace{25pt}

\item What is the image of $f_4$?
\vspace{25pt}

\item Specify domain and codomain so that $f_3$ and $f_4$ are
inverses of one another. \vspace{25pt}

\item Did your calculus course use ``range'' as a synonym for
``image'' or for ``codomain?'' \end{itemize} \pagebreak



\item Composition of functions\\
Sometimes people find that a statement is hard to prove because it is
so obvious. An example is the associativity of function composition,
which will turn out to be crucial for linear algebra.

Prove that $(f \circ g)\circ h = f \circ (g\circ h)$. Hint: Two
functions $f_1$ and $f_2$ are equal if they have the same domain $X$
and, $\forall x \in X$, $f_1(x) = f_2(x)$. \vspace {120pt}


Consider the set of men who have exactly one brother and exactly one
son.

$h(x)$ = ``father of $x$'',  $g(x)$ = ``brother of $x$'', $f(x)$ =
``oldest son of $x$''

\large

 \begin{itemize}

\item $f\circ g$ is called
\item $(f\circ g)\circ h$ is
 \item $g\circ h$ is called

\item $f\circ(g\circ h)$ is
\item Simpler name for both $(f\circ g)\circ h$ and $f\circ(g\circ h)$

\vspace {30pt}
\end{itemize}
\normalsize

Consider the real-valued functions

$g(x) = e^x$,  $h(x) = 3 \log x$, $f(x) = x^2$
\large
 \begin{itemize}

\item $f\circ g$ has the formula
\item $(f\circ g)\circ h$ has the formula
 \item $g\circ h$ has the formula

\item $f\circ(g\circ h)$ has the formula

\item Simpler formula for both $(f\circ g)\circ h$ and $f\circ(g\circ h)$

\vspace {30pt}
\end{itemize}
\normalsize


\pagebreak

\item Finite sets and functions form the simplest example of a \emph{category}
\begin{itemize}
\item The \emph{objects} of the category are finite sets.
\item The \emph{arrows} of the category are functions from one finite set to another. The definition of a function involves quantifiers.

Requirements for a function $f: X \rightarrow Y$

$ \forall x \in X, \exists ! y \in Y$ such that $f(x) = y$. \\(The notation $\exists ! y$ means ``there exists a \emph{unique} $y$.)''

What is wrong with the following?

\begin{center}
\begin{tikzpicture}[scale=0.7]
\coordinate [label=below:$X$] (X) at (0,0); 
\draw (X) circle(2cm);
\coordinate (X1) at (0.2, 1);
\coordinate  (X2) at (0.4, 0);
\coordinate  (X3) at (0.2, -1);

\coordinate [label=below:$Y$] (Y) at (5,0); 
\draw (Y) circle(2cm);
\coordinate (Y1) at (4.8,1);
\coordinate  (Y2) at (4.8,-1);


\draw[->,style = very thick](X1) -- (Y1);
\draw[->,style = very thick](X2) -- (Y2);

\foreach \p in {X1,X2,X3,Y1,Y2}
  \fill (\p) circle (0.9mm);







\end{tikzpicture} 
\end{center}

What is wrong with the following?

\begin{center}
\begin{tikzpicture}[scale=0.7]
\coordinate [label=below:$X$] (X) at (0,0); 
\draw (X) circle(2cm);
\coordinate (X1) at (0.2, 1);

\coordinate  (X2) at (0.2, -1);

\coordinate [label=below:$Y$] (Y) at (5,0); 
\draw (Y) circle(2cm);
\coordinate (Y1) at (4.8,1);
\coordinate  (Y2) at (4.8,-1);
\coordinate  (Y3) at (4.6, 0);


\draw[->,style = very thick](X1) -- (Y1);
\draw[->,style = very thick](X2) -- (Y2);
\draw[->,style = very thick](X2) -- (Y3);

\foreach \p in {X1,X2,Y3,Y1,Y2}
  \fill (\p) circle (0.9mm);

\end{tikzpicture} 
\end{center}

\item If  arrows $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ are in the category, then the composition arrow $g \circ f: X \rightarrow Z$ is in the category.

\item For any object $X$ there is an identity arrow $I_X: X \rightarrow X$

\item Given $f: X \rightarrow Y$, $f \circ I_X = f$ and $I_Y \circ f = f$

\item Composition of arrows is associative:

Given $X \xrightarrow{f}Y \xrightarrow{g}Z \xrightarrow{h}W$, $h\circ(g \circ f) = (h\circ g) \circ f $

\end{itemize}

The objects do not have to be sets and the arrows do not have to be functions. For example, the objects could be courses, and an arrow from course $X$ to course $Y$ could mean "if you have taken course $X$, you will probably do better in course $Y$ as a result." Check that the identity and composition rules are satisfied.

\pagebreak

\item Invertible functions - an example of invertible arrows

First consider the category of finite sets and functions between them.

The term ``inverse'' is used only for a ``two-sided inverse.'' Given $f: X \rightarrow Y$, an inverse $f^{-1}: Y \rightarrow X$ must have the properties \\
$f^{-1} \circ f = I_X$ and $f \circ f^{-1} = I_Y$ 

Prove that the inverse is unique. This proof uses only things that are true in any category, so it is valid in any category!
\vspace{50 pt}

This function is not invertible because it is not injective, but it is surjective.

\begin{center}
\begin{tikzpicture}[scale=0.7]
\coordinate [label=below:$X$] (X) at (0,0); 
\draw (X) circle(2cm);
\coordinate (X1) at (0.2, 1);
\coordinate  (X2) at (0.4, 0);
\coordinate  (X3) at (0.2, -1);

\coordinate [label=below:$Y$] (Y) at (5,0); 
\draw (Y) circle(2cm);
\coordinate (Y1) at (4.8,1);
\coordinate  (Y2) at (4.8,-1);


\draw[->,style = very thick](X1) -- (Y1);
\draw[->,style = very thick](X2) -- (Y2);
\draw[->,style = very thick](X3) -- (Y2);

\foreach \p in {X1,X2,X3,Y1,Y2}
  \fill (\p) circle (0.9mm);

\end{tikzpicture} 
\end{center}

However, it has a ``preinverse'' (my terminology -- the official word is ``section.'') Starting at an element of $Y$, choose any element of $X$ from which there is an arrow to that element. Call that function $g$. Then $f \circ g = I_Y$ but $g \circ f \neq I_X$. Furthermore, $g$ is not unique.

Prove the cancellation law that if $f$ has a section and $h \circ f = k \circ f$, then $h = k$ (another proof that is valid in any category!)\vspace{50pt}

This function $f$ is not invertible because it is not surjective, but it is injective.

\begin{center}
\begin{tikzpicture}[scale=0.7]
\coordinate [label=below:$X$] (X) at (0,0); 
\draw (X) circle(2cm);
\coordinate (X1) at (0.2, 1);

\coordinate  (X2) at (0.2, -1);

\coordinate [label=below:$Y$] (Y) at (5,0); 
\draw (Y) circle(2cm);
\coordinate (Y1) at (4.8,1);
\coordinate  (Y2) at (4.8,-1);
\coordinate  (Y3) at (4.6, 0);


\draw[->,style = very thick](X1) -- (Y1);

\draw[->,style = very thick](X2) -- (Y3);

\foreach \p in {X1,X2,Y3,Y1,Y2}
  \fill (\p) circle (0.9mm);

\end{tikzpicture} 
\end{center}

It has a ``postinverse'' $g$ (the official word is ``retraction''). First reverse all the arrows to undo its effect, then define $g$ any way you like on the element of $Y$ that is not in the image of $f$. Then  $g \circ f = I_X$ but $f \circ g \neq I_Y.$ 

\pagebreak


\item Fields\\
Loosely speaking, a field $F$ is a set of elements for which the
familiar operations of arithmetic are defined and behave in the
usual way. Here is a set of axioms for a field. You can use them to
prove theorems that are true for any field.
\begin{enumerate}
\item Addition is commutative: $a+b = b+a$.
\item Addition is associative: $(a+b)+c = a + (b+c)$. \item
Additive identity: $\exists 0$ such that $\forall a \in F, 0 + a = a
+ 0 = a$.

\item Additive inverse: $\forall a \in F, \exists -a$  such that $-a + a = a + (-a)
=0$.

\item Multiplication is associative: $(ab)c = a(bc)$.

\item Multiplication is commutative: $ab = ba$.

\item Multiplicative identity: $\exists 1$ such that $\forall a \in F, 1a =
a$.


\item Multiplicative inverse: $\forall a \in F-\{0\}, \exists a^{-1}$  such that $a^{-1}a  =
1$.

\item Distributive law: $a(b+c) = ab + ac$.

\end{enumerate}

This set of axioms for a field includes properties (such as the
commutativity of addition) that can be proved as theorems by using
the other axioms. It therefore does not qualify as an
``independent'' set, but there is no general requirement that axioms
be independent.

Some well-known laws of arithmetic are omitted from the list of
axioms because they are easily proved as theorems. The most obvious
omission is

$\forall a \in F, 0a = 0$.

Here is the proof. What axiom justifies each step?

\large

\begin{itemize}

\item 0 + 0 = 0 so $(0+0)a = 0a$.
\item $0a + 0a = 0a$.
\item $(0a + 0a) + (-0a) = 0a +  (-0a)$.
\item $0a + (0a + (-0a)) = 0a +  (-0a)$.
\item $0a + 0 = 0$.
\item $0a = 0$.
\end {itemize}

\normalsize



\pagebreak




\item Finite fields\\
Computing with real numbers by hand can be a pain, and most of
linear algebra works for an arbitrary field, not just for the real
and complex numbers. Alas, the integers do not form a field
because in general there is no multiplicative inverse.  Here is a
simple way to make from the integers a finite field in which messy
fractions cannot arise.

\begin{itemize}
\item Choose a prime number $p$. \item Break up the set of
integers into $p$ subsets.  Each subset is named after the
remainder when any of its elements is divided by $p$.

$[0]_p = \{m  | m = np, n \in \mathbb{Z}\}$

$[1]_p = \{m  | m = np+1, n \in \mathbb{Z}\}$

$[a]_p = \{m  | m = np+a, n \in \mathbb{Z}\}$

Notice that $[a+kp]_p = [a]_p$ for any $k$. There are only $p$ sets,
but each has many alternate names.

These $p$ infinite sets are the elements of the field
$\mathbb{Z}_p$.

\item Define addition by $[a]_p + [b]_p = [a+b]_p$. Here $a$ and $b$
can be any names for the subsets, because the answer is independent
of the choice of name. The rule is ``Add $a$ and $b$, then divide by
$p$ and keep the remainder.''

\item What is the simplest name for $[5]_7 + [4]_7$? \vspace{35pt}

\item What is the simplest name for the additive inverse of
$[3]_7$? \vspace{35pt}


\item Define multiplication by $[a]_p  [b]_p = [ab]_p$. Again $a$ and $b$
can be any names for the subsets, because the answer is independent
of the choice of name. The rule is ``Multiply $a$ and $b$, then
divide by $p$ and keep the remainder.''

\item What is the simplest name for $[5]_7 [4]_7$?
\vspace{30pt} 

\item Find the multiplicative inverse for each nonzero element of $\mathbb{Z}_7$

\end{itemize}

\pagebreak



\item Rational numbers\\
The rational numbers $\mathbb{Q}$ form a field. You learned how to
add and multiply them years ago! The multiplicative inverse of
$\frac{a}{b}$ is $\frac{b}{a}$ as long as $a \neq 0$.

The rational numbers are not a ``big enough'' field for doing
Euclidean geometry or calculus.  Here are some irrational
quantities:

\begin{itemize}
\item $\sqrt{2}$
\item $\pi$.
\item most values of trig functions, exponentials, or logarithms.
\item coordinates of most intersections of two circles.
\end{itemize}

\item Real numbers\\ The real numbers $\mathbb{R}$ constitute a
field that is large enough so that any characterization of a
number in terms of an infinite sequence of real numbers still
leads to a real number.

A positive real number is an expression
like 3.141592... where there is no limit to the number of decimal
places that can be provided if requested. To get a negative
number, put a minus sign in front. This is Hubbard's definition.

An equivalent viewpoint is that a positive real number is the sum
of an integer and an infinite series of the form

$$\sum_{i=1}^\infty{a_i}(\frac{1}{10})^i$$

where each $a_i$ is one of the decimal digits 0...9.

Write the first three terms of an infinite series that converges
to $\pi$. \vspace{40pt}







The rational numbers and the real numbers are both ``ordered fields.'' This means that there
is a subset of positive elements that is closed under both addition
and multiplication. No finite field is ordered.

In $\mathbb{Z}_5,$ you can name the elements $[0], [1], [2], [-2],
[-1],$ and try to call the elements [1] and [2] ``positive.'' Why
does this attempt to make an ordered field fail?

\pagebreak

\item Proof 1.1 - two theorems that are valid in any field

\begin{enumerate}
\item Using nothing but the field axioms and the theorem that $0a=0$, prove that if $ab =0$, then either $a$ or $b$ must be 0.   

\vspace{150pt}

\item Using nothing but the field axioms, prove that the additive inverse of an element $a$ is unique.
(Standard strategy for uniqueness proofs: assume that there are two different inverses $b$ and $c$, and prove that $b = c$.

\end{enumerate}
\pagebreak



\item Lists of field elements as points and vectors:

$F^n$ denotes the set of ordered lists of $n$ elements from a field
$F$. Usually the field is $\mathbb{R},$ but it could be the field of
complex numbers $\mathbb{C}$ or a finite field like $\mathbb{Z}_5.$

An element of $F^n$ can be regarded either as a point, which represents
``position data,'' or as a vector, which represents ``incremental
data.'' Beware: many textbooks ignore this distinction!



If an element of $F^n$ is a point, we represent it by a bold letter
like $\bold{p}$ and write it as a column of elements enclosed in
parentheses.
$$\bold{p} = \begin{pmatrix} 1.1 \\ -3.8 \\2.3
\end{pmatrix}, $$


If an element of $F^n$ is a vector, we represent it by by a bold
letter with an arrow like $\vec{\bold{v}}$ and write it as a
column of elements enclosed in square brackets.
$$\vec{\bold{v}} = \begin{bmatrix} -0.2 \\ 1.3 \\ 2.2
\end{bmatrix}$$


\item Relation between points and vectors, inspired by geometry:

\begin {itemize}
\item Add vector $\vec{\bold{v}}$ component by component to point
$\bold{A}$ to get point  $\bold{B}$.

\item Subtract point $\bold{A}$ component by component from point
$\bold{B}$ to get vector $\vec{\bold{v}}$.

\item Vector addition: if adding  $\vec{\bold{v}}$ to point
$\bold{A}$ gives point  $\bold{B}$ and adding $\vec{\bold{w}}$ to
point $\bold{B}$ gives point  $\bold{C}$, then adding
$\vec{\bold{v}}+\vec{\bold{w}}$ to point $\bold{A}$ gives point
$\bold{C}$.

\item A vector in $F^n$ can be multiplied by any element of $F$
to get another vector.


\end{itemize}
Draw a diagram to illustrate these operations without use of
coordinates, as is typically done in a physics course.

\pagebreak

\item Examples from coordinate geometry

Here are two points in the plane.

$$\bold{p} = \begin{pmatrix} 1.4 \\ -3.8
\end{pmatrix}, \bold{q} = \begin{pmatrix} 2.4 \\ -4.8
\end{pmatrix}$$

Here are two vectors.

$$\vec{\bold{v}} = \begin{bmatrix} -0.2 \\ 1.3
\end{bmatrix}, \vec{\bold{w}} = \begin{bmatrix} 0.6 \\ -0.2
\end{bmatrix}$$

\begin{itemize}
\item What is $\bold{q}-\bold{p}?$
\vspace{70pt}

\item What is $\bold{p} + \vec{\bold{v}}?$
\vspace{70pt}

\item What is $\vec{\bold{v}} -  1.5\vec{\bold{w}}?$
\vspace{70pt}

\item What, if anything, is $\bold{p}+\bold{q}?$
\vspace{70pt}

\item What is $0.5 \bold{p}+ 0.5 \bold{q}?$ Why is this apparently
illegal operation OK? \vspace{70pt}
\end{itemize}



\pagebreak









\item Subspaces of $F^n$

A subspace is defined only when the elements of $F^n$ are vectors.
It must be closed under vector addition and scalar multiplication.
The second requirement means that the zero vector must be in the
subspace. The empty set $\emptyset$ is not a subspace!

Geometrically, a subspace corresponds to a ``flat subset'' (line,
plane, etc.) \emph{that includes the origin}.

For $\mathbb{R}^3$ there are four types of subspace. What is the
geometric interpretation of each?

\begin{itemize}
\item 0-dimensional: the set \{$\begin{bmatrix} 0 \\ 0 \\0
\end{bmatrix}\}$

\item 1-dimensional: \{$t\vec{\bold{u}}|t \in \mathbb{R}$\}

Exception: 0-dimensional if \vspace{30pt}

\item 2-dimensional: \{$s\vec{\bold{u}}+t\vec{\bold{v}}|s,t \in
\mathbb{R}$\}

Exception: 1-dimensional if\vspace{60pt}

\item 3-dimensional:
\{$r\vec{\bold{u}}+s\vec{\bold{v}}+t\vec{\bold{w}}|r,s,t \in
\mathbb{R}$\}

Exceptions: 2-dimensional if\vspace{60pt}

1-dimensional if\vspace{50pt}

\end{itemize}



A special type of subset is obtained by adding all the vectors in
a subspace to a fixed point.
 It is in general not a subspace, but it has special
properties.  Lines and planes that do not contain the origin fall
into this category.

We call such a subset an ``affine subset.'' This terminology is
not standard: the Math 116 textbook uses ``linear variety.''

\pagebreak

\item Standard basis vectors:\\

These are useful when we want to think of $F^n$ more abstractly.

The standard basis vector $\vec{\bold{e_i}}$ has a 1 in position
$i$, a 0 everywhere else.  Since 0 and 1 are in every field, these vectors
are defined for any $F$.

The nice thing about standard basis vectors is that in $F^n$, any
vector can be represented uniquely in the form

$$\sum_{i=1}^nx_i\vec{\bold{e_i}}$$

This will turn out to be true also in an abstract $n$-dimensional
vector space, but in that case there will  be no ``standard'' basis.



\item Matrices

An $m \times n$ matrix over a field $F$ is a rectangular array of
elements of $F$ with $m$ rows and $n$ columns. Watch the convention:
the height is specified first!

As a mathematical object, any matrix can be multiplied by any
element of $F$. This could be meaningless in the context of an
application. Suppose you run a small hospital that has two rooms
with three patients in each.  Then

$$\begin{bmatrix}98.6 & 102.4 & 99.7 \\ 103.2 & 98.3 & 99.6
\end{bmatrix}$$

is a perfectly reasonable way to keep track of the body
temperatures of the patients, but multiplying it by 2.7 seems
unreasonable. This matrix, viewed as an element of $\mathbb{R}^6$,
is a point, not a vector, but we always use braces for matrices.

Matrices with the same size and shape can be added component by
component. What would you get if you add

$$\begin{bmatrix}0.2 & -1.4 & 0.0 \\ 0.6 & -0.9 & 2.35
\end{bmatrix}$$

to the matrix above to update the temperature data by one day?
\vspace{50pt}

\pagebreak
\item Matrix multiplication

Matrix multiplication is nicely explained on pages 43-46 of Hubbard.
To illustrate the rule, we will take

$A= \begin{bmatrix}2 & 1 & 0 \\ 1 & -1 & -2
\end{bmatrix}$,
$B=\begin{bmatrix}0  & 1 \\ 2 & -1 \\ -2 & 0
\end{bmatrix}$
\begin{itemize}
\item Compute $AB$. $\begin{bmatrix}0  & 1 \\ 2 & -1 \\ -2 & 0\end{bmatrix}$\\
 \vspace{10pt}\\
 $\begin{bmatrix}2 & 1 & 0 \\ 1 & -1 & -2 \end{bmatrix}$
 \vspace{30pt}\\



\item Compute $BA$.  $\begin{bmatrix}2 & 1 & 0 \\ 1 & -1 & -2 \end{bmatrix}$
 \vspace{15pt}\\
$\begin{bmatrix}0  & 1 \\ 2 & -1 \\ -2 & 0\end{bmatrix}$\\
 \vspace{10pt}\\

\end{itemize}


In a set of $n \times n$ square matrices, addition and
multiplication of matrices are always defined. Multiplication is
distributive with respect to addition, too. But because matrix
multiplication is noncommutative, the $n \times n$ matrices do not
form a field if $n > 1.$ (They are said to form a ring.) Let

$$A= \begin{bmatrix}1 & 1 \\ 1 & 0
\end{bmatrix} B= \begin{bmatrix}0 & 1 \\ 2 & 1
\end{bmatrix}$$
Find $AB$.  $\begin{bmatrix}0 & 1 \\ 2 & 1
\end{bmatrix}$
 \vspace{10pt}\\
$ \begin{bmatrix}1 & 1 \\ 1 & 0
\end{bmatrix}$ 
 \vspace{10pt}\\


Find $BA$.  $\begin{bmatrix}1 & 1 \\ 1 & 0
\end{bmatrix} $
 \vspace{10pt}\\
$\begin{bmatrix}0 & 1 \\ 2 & 1\end{bmatrix}$



\pagebreak


\item Matrices as functions:\\
 Since a column vector is also an $n
\times 1$ matrix, we can multiply an $m \times n$ matrix by a
vector in $F^n$ to get a vector in $F^m$. The product
$A\vec{\bold{e_i}}$ is the $i$th column of $A$. This is usually
the best way to think of a matrix $A$ as representing a \emph{linear function}
$f$: the $i$th column of $A$ is $f(\vec{\bold{e_i}})$.

Example: Suppose that $f$ is linear,  $f(\begin{bmatrix} 1 \\ 0 \end{bmatrix}) =
\begin{bmatrix} 1 \\ 4 \end{bmatrix}$, and  $f(\begin{bmatrix} 0 \\ 1 \end{bmatrix}) =
\begin{bmatrix} 2 \\ 3 \end{bmatrix}$.

What matrix $A$ represents $f$? \vspace{70pt}

By the definition of matrix multiplication, $A(x_i\vec{\bold{e_i}}+x_j\vec{\bold{e_j}})$ is the sum of
$x_i$ times column $i$ and $x_j$ times column $j$. So we see that

$$f(x_i\vec{\bold{e_i}}+x_j\vec{\bold{e_j}})=
x_if(\vec{\bold{e_i}})+x_jf(\vec{\bold{e_j}})$$

This is precisely the requirement for $f$ to be a linear function.

Use matrix multiplication to calculate $f(\begin{bmatrix} 2 \\ -1
\end{bmatrix}).$\vspace{90pt}

The rule for forming the product $AB$ can be stated in terms of the
rule for a matrix acting on a vector: to form $AB$, just let $A$ act
on each column of $B$ in turn, and put the results side by side to
create the matrix $AB$.

What function does the matrix product $AB$ represent? Consider
$(AB)\vec{\bold{e_i}}$. This is the $i$th column of the matrix
$AB$, and it is also the result of letting $B$ act on
$\vec{\bold{e_i}}$, then letting $A$ act on the result. So for any
standard basis vector, the matrix $AB$ represents the composition
$A\circ B$ of the functions represented by $B$ and by $A$.

What about the matrices $(AB)C$ and $A(BC)$? These represent the
composition of three functions: say $(f \circ g)\circ h$ and $f
\circ (g\circ h)$. But we already know that composition of
functions is associative.  So we have proved, without any messy algebra, that multiplication of matrices is
associative also.

\pagebreak

\item Proving associativity by brute force (proof 1.2)

$A$ is an $n \times m$ matrix.\\

$B$ is an $m \times p$ matrix.\\

$C$ is an $p \times q$ matrix.\\

What is the shape of the matrix $ABC?$

Show how you would lay out the calculation of $(AB)C.$ \vspace{60pt}

If $a_{i,j}$ represents the entry in the $i$th row, $j$th column of
$A$, then

$$(AB)_{i,k} = \sum_{j=1}^m a_{i,j}b_{j,k}$$
$$((AB)C)_{i,q} = \sum_{k=1}^p (AB)_{i,k}c_{k,q}=\sum_{j=1}^m\sum_{k=1}^p(a_{i,j}b_{j,k})c_{k,q}$$



Show how you would lay out the calculation of $A(BC).$ \vspace{60pt}
\large

$(BC)_{j,q} = $\vspace{30pt}\\ $(A(BC))_{i,q} = $\vspace{20pt}

\normalsize

On what basis can you now conclude that matrix multiplication is
associative for matrices over any field $F$?



\pagebreak



\item Identity matrix:\\
 It must be square, and the $i$th column
is the $i$th basis vector. For example,

$$I_3 = \begin{bmatrix}1 & 0 & 0\\ 0 & 1 & 0 \\ 0& 0& 1
\end{bmatrix}$$

\item Matrices as the arrows for a category $\mathscr{C}$

Choose a field $F$, perhaps the real numbers $\mathbb{R}$.
\begin{itemize}
\item An object of $\mathscr{C}$ is a vector space $F^n$.
\item An arrow of $\mathscr{C}$ is an $n \times m$ matrix $A$, with domain $F^m$ and codomain $F^n$.
\item Given $F^p \xrightarrow{B} F^m \xrightarrow{A} F^n$ the composition of arrows $A$ and $B$ is the matrix product $AB$.
Show that the ``shape'' of the matrices is right for multiplication. \vspace{100pt}
\item The identity arrow for object $F^n$ is the $n \times n$ identity matrix.
\end{itemize}
Now we just have to check the two rules that must hold in any category:\\
\begin{itemize}
\item The associative law for composition of arrows holds because, as we just proved, matrix multiplication is associative.
\item Verify the two identity rules for the case where $A = \begin{bmatrix}2 & 3 &4 \\ 1& 2 &3 \end{bmatrix}$.
\end{itemize}




\pagebreak

\item Matrix inverses:\\
 Consider first the case of a non-square $m \times n$ matrix $A$.

If $m > n$, then $A$ takes a vector in $\mathbb{R}^n$ and produces
a longer vector in $\mathbb{R}^m$. In general, there will be many
matrices $B$ that can recover the original vector in
$\mathbb{R}^n$. In the lingo of categories, such a matrix $B$ is a \emph{retraction}.

Here is a matrix that converts a 2-component vector (price of
silver and price of gold) into a three-component vector that
specifies the price of alloys containing 25\%, 50\%, and 75\% gold
respectively. Calculate $\vec{\bold{v}} =
A\begin{bmatrix}4\\8\end{bmatrix}.$

$A = \begin{bmatrix}.75 & .25\\ .5 & .5 \\ .25 & .75
\end{bmatrix},  \vec{\bold{v}}=A\begin{bmatrix}4\\8\end{bmatrix}=$

By elementary algebra you can reconstruct the price of silver and
of gold from the price of any two of the alloys, so it is no
surprise to find two different left inverses. Apply each of the
following to $\vec{\bold{v}}$.

$B_1 = \begin{bmatrix}2 & -1 & 0\\ -2 & 3 & 0
\end{bmatrix}, B_1 \vec{\bold{v}}=$ \vspace{15pt}

$B_2 = \begin{bmatrix}0 & 3 & -2\\ 0 &-1 & 2
\end{bmatrix},B_2 \vec{\bold{v}}=$ \vspace{15pt}

However, in this case there is no right inverse.

If $m < n$, then $A$ takes a vector in $\mathbb{R}^n$ and produces
a shorter vector in $\mathbb{R}^m$. In general, there will be no
left inverse matrix $B$ that can recover the original vector in
$\mathbb{R}^n$, but there may be many different right inverses.
Let $A = \begin{bmatrix}1 & -1
\end{bmatrix}$ and find two different right inverses.  In the lingo of categories, such a matrix $A$ is a \emph{section}.

\pagebreak
 \item Inverting square matrices

For a square matrix, the interesting case is where both a right
inverse $B$ and a left inverse $C$ exist. In this case, $B$ and
$C$ are equal and they are unique. We can say that ``an inverse''
$A^{-1}$ exists.





Proof of both uniqueness and equality:\\
To prove uniqueness of the left inverse matrix,
assume that matrix $A$ has two different left inverses $C$ and $C'$ and a right inverse $B$:\\
$$C'A = CA = I$$
$$C'(AB) = C(AB) = IB$$
$$C'I = CI = B$$
$$C' = C = B$$


In general, inversion of matrices is best done by ``row reduction,''
discussed in Chapter 2 of Hubbard. For $2 \times 2$ matrices there
is a simple formula that is worth memorizing:

If

$$A = \begin{bmatrix}a & b\\ c & d
\end{bmatrix}$$

then

$$A^{-1} = \frac{1}{ad-bc}\begin{bmatrix}d & -b\\ -c & a
\end{bmatrix}$$

If $ad-bc=0$ then no inverse exists.

Write down the inverse of $\begin{bmatrix}3 & 1\\ 4 & 2
\end{bmatrix},$ where the elements are in $\mathbb{R}$.
\vspace{50pt}


\pagebreak

The matrix inversion recipe works in any field: try inverting \\$A = \begin{bmatrix}3 & 1\\
4 & 2
\end{bmatrix}$ where the elements are in $\mathbb{Z}_5$.
\vspace{120pt}





\item Other matrix terminology:\\ All these terms are nicely
explained on pp 49-50 of Hubbard.

\begin{itemize}
\item transpose
\item symmetric matrix
\item antisymmetric matrix
\item diagonal matrix
\item upper or lower triangular matrix
\end{itemize}

Try applying them to some $3 \times 3$ matrices:

$A= \begin{bmatrix}3 & 1 & 2\\ 1 & 2 &3 \\2 & 3 & 4
\end{bmatrix}$

$B= \begin{bmatrix}3 & 0 & 0\\ 1 & 2 &0 \\2 & 3 & 4
\end{bmatrix}$

$C= \begin{bmatrix}3 & 1 & 2\\ 0 & 2 &3 \\0 & 0 & 4
\end{bmatrix}$

$D= \begin{bmatrix}3 & 0 & 0\\ 0 & 2 &0 \\0 & 0 & 4
\end{bmatrix}$

$E= \begin{bmatrix}0 & -1 & -2\\ 1 & 0 &-3 \\2 & 3 & 0
\end{bmatrix}$

\pagebreak


\item Linear transformations:\\

A function $T: F^n \rightarrow F^m$ is called \emph{linear} if, for any
vectors $\vec{\bold{v}},  \vec{\bold{w}}\in F^n$ and any scalars
$a, b \in F$

$$T(a\vec{\bold{v}}+b\vec{\bold{w}}) = a T(\vec{\bold{v}})+ b
T(\vec{\bold{w}})$$

Example:

The components of $\vec{\bold{v}}$ are the quantities of sugar,
flour, and chocolate required to produce a batch of brownies. The
components of $\vec{\bold{w}}$ are the quantities of these ingredients
required to produce a batch of fudge. $T$ is the function that
converts such a vector into the total cost of ingredients. $T$ is
represented by a matrix $[T]$ (row vector) of prices for the various
ingredients.

Write these vectors for the following data:
\begin{itemize}

\item A batch of brownies takes 3 pounds of sugar, 6 of flour, 1
of chocolate, while a batch of fudge takes 4 pounds of sugar, 0 of
flour, 2 of chocolate. \vspace{50pt}

\item Sugar costs \$2 per pound, flour costs \$1 per pound,
chocolate costs \$6 per pound. \end{itemize}\vspace{30pt}


Then $a\vec{\bold{v}}+b\vec{\bold{w}}$ is the vector of ingredients
required to produce $a$ batches of brownies and $b$ batches of
fudge, while $T(\vec{\bold{v}})$ is the cost of parts for a
single batch of brownies. The statement

$T(a\vec{\bold{v}}+b\vec{\bold{w}}) = a T(\vec{\bold{v}})+ b
T(\vec{\bold{w}})$ is sound economics.

Two ways to find the cost of 3 batches of brownies plus 2
batches of fudge. 

\large

$T(3\vec{\bold{v}}+2\vec{\bold{w}}) = $

\vspace{10pt}

$3 T(\vec{\bold{v}})+2T(\vec{\bold{w}})=$

\vspace{15pt}

\normalsize

Suppose that $T$  produces a 2-component vector of costs from two
competing grocers. In that case $[T]$ is a $2 \times 3$ matrix.

\pagebreak




\item Matrices and linear transformations

Use * to denote the mechanical operation of matrix multiplication.

Any vector can be written as $\vec{\bold{v}}=x_1\vec{\bold{e_1}} +
... + x_n\vec{\bold{e_n}}$.

The rule for multiplying a matrix [$T$] by a vector $\vec{\bold{v}}$
is equivalent to

$$[T]*\vec{\bold{v}}=x_1[T]*\vec{\bold{e_1}} + ...
+ x_n[T]*\vec{\bold{e_n}}=[T]*(x_1\vec{\bold{e_1}} +
... + x_n\vec{\bold{e_n}})$$.

So multiplication by $[T]$ specifies a linear transformation of $F^n$.

The matrix $[T]$ has columns
$[T]*(\vec{\bold{e_1}}),...[T]*(\vec{\bold{e_n}}).$

The distinction is subtle. $T$ is a function, a rule. $[T]$ is
just a collection of numbers, but the general rule for matrix
multiplication turns it into a function.

\item Composition and multiplication:\\

Suppose $S: F^n \rightarrow F^m$ and $T: F^m \rightarrow F^p$ are
both linear transformations. Then the codomain of $S$ equals the
domain of $T$ and we can define the composition $U = T \circ S$.

Prove that $U$ is linear. \vspace{60pt}



To find the matrix of $U$, we need only determine its action on each
standard basis vector.

$$U(\vec{\bold{e_i}})=T(S(\vec{\bold{e_i}}))=T([S]*\vec{\bold{e_i}})=
[T]*([S]*\vec{\bold{e_i}}) = ([T]*[S])*\vec{\bold{e_i}}$$

So the matrix of $T \circ S$ is $[T]*[S]$.


\pagebreak
\item Inversion

A function $f$ is invertible if it is 1-to-1 (injective) and onto
(surjective). If $g$ is the inverse of $f$, then both $g\circ f$ and
$f\circ g $ are the identity function. How do we reconcile this observation with
the existence of matrices that have one-sided inverses?

Here are two simple examples that identify the problem.
\begin{enumerate}
\item Define $f$ by the formula $f(x) = 2x$. Then

$f: \mathbb{R}\rightarrow \mathbb{R}$ is invertible.

$f: \mathbb{Z}_3\rightarrow \mathbb{Z}_3$ is invertible.

$f: \mathbb{Z}\rightarrow \mathbb{Z}$ is not invertible.

$f: \mathbb{Z}\rightarrow 2\mathbb{Z}$ is invertible.
($2\mathbb{Z}$ is the set of even integers)

In the last case, we have made $f$ invertible by redefining its
codomain to equal its image.

\item If we want to say that the inverse of $f(x) = x^2$ is $g(x)
= \sqrt{x}$, we have to redefine $f(x)$ so that its codomain is the
nonnegative reals (makes it onto) and its domain is the nonnegative
reals (makes it one-to-one).

\end{enumerate}

The codomain of the function that an $m \times n$ matrix
represents is all of $\mathbb{R}^m$.

Hubbard p. 64 talks about the invertibility of a linear
transformation $T: F^n \rightarrow F^m$ and ends up commenting that
$m$ and $n$ must be equal. Here is the problem, whose proof will
have to wait:

If $m > n$, $T$ cannot be onto, because its image is just a subspace
of $F^m$.

Show how the case where $[T] = \begin{bmatrix}1 \\ 2
\end{bmatrix}$ illustrates the problem. \vspace{75pt}

If $m < n$, $T$ cannot be one-to-one, because there is always a
subspace of $F^n$ that gets mapped to the zero vector.

Show how the case where $[T] = \begin{bmatrix}1 & -1
\end{bmatrix}$ illustrates the problem.





\pagebreak

\item Example - constructing the matrix of a linear transformation

Here is what we know about function $f$:

\begin{itemize}
\item Its domain and codomain are both $\mathbb{R}^2.$
\item It is linear.
\item $f(\begin{bmatrix}1 \\ 2 \end{bmatrix}) = \begin{bmatrix}7 \\ 5 \end{bmatrix}.$
\item $f(\begin{bmatrix}1 \\ 4 \end{bmatrix}) = \begin{bmatrix}11 \\ 9 \end{bmatrix}.$

\end{itemize}

Find the matrix $T$ that represents $f$ by using linearity to determine what $f$ does to the standard basis vectors.

Then automate the calculation by writing down a matrix equation and solving it for $T.$
\pagebreak









\pagebreak

\item Invertibility of linear functions and of matrices\\ (proof 1.3, Hubbard, proposition 1.3.14)

Since the key issue in this proof is the subtle distinction between a linear function $T$ and the matrix $[T]$ that represents it, it is a good idea to use * to denote matrix multiplication and $\circ$ to denote composition of linear transformations. 

It is also a good idea to use $\vec{\bold{x}}$ for a vector in the domain of $T$ and  $\vec{\bold{y}}$ for a vector in the codomain of $T$.

 Suppose that linear transformation $T: F^n \rightarrow
F^m$ is represented by the $m \times n$ matrix $[T]$. 

\begin{enumerate}
\item Suppose that the matrix $[T]$ is invertible. Prove that the linear transformation $T$
is one-to-one and onto (injective and surjective), hence invertible.\vspace{150pt}

\item Suppose that linear transformation $T$ is invertible. Prove that its inverse $S$ is linear and
that the matrix of $S$ is $[S] = [T]^{-1}$

The shortest version of this proof starts by exploiting the linearity of $T$ when it is applied to a cleverly-chosen sum of vectors.
$$T(aS(\vec{\bold{y_1}})+ bS(\vec{\bold{y_2}}))=aT \circ S(\vec{\bold{y_1}})+
bT \circ S(\vec{\bold{y_2}}).$$

\end{enumerate}
\pagebreak



\item Application: graph theory

This is inspired by example 1.2.22 in Hubbard (page 51), but I
have extended it by allowing one-way edges and multiple edges.

A graph has $n$ vertices: think of them as islands. Given two
vertices $V_i$ and $V_j$, there may be $A_{i,j}$ edges (ferryboats) that lead from $V_j$ to $V_i$ and $A_{j,i}$ edges that
lead from $V_i$ to $V_j$. If a ferryboat travels in both directions between two islands, it counts twice.
In the interest of simplicity, we allow at most one ferryboat between a given pair of islands.
The matrix \vspace{20pt}

\large

$A=\begin{bmatrix}0 & 0 & 1 & 1\\ 1 & 0 & 0 & 0\\1 & 0 & 0 & 0\\ 0
& 1 & 1 &0\end{bmatrix}$

\normalsize

corresponds to the following directed graph:

\includegraphics[width=600pt]{2-islands.png}

The matrix $A$ describes the graph completely. 

\pagebreak

\item The category of islands and itineraries

The \emph {objects} of the category are the islands.

The \emph {arrows} of the category are itineraries: e.g 4-1 (one step), 1-3-4 (two steps) or 4-1-3-1-2 (four steps). A zero-step itinerary like 1 means ``just stay on island 1."

Checking the requirements for a category:
\begin{itemize}
\item What are the domain and codomain of the itinerary 4-1-3-1-2?
\vspace{40pt}

\item If $f$ = 4-1, $g$ = 1-3-4 and $h$ =  4-1-3-1-2 , what is the itinerary $g \circ f$? 
\vspace{20pt}

What is $h \circ g$?\\

\item Check the associative law $h\circ(g \circ f) = (h\circ g) \circ f $.
\vspace{40pt}

\item Check the identity rules for the itinerary 1-3-4.
\vspace{40pt}

\end{itemize}

Now consider a vector $\vec{\bold{v}}= \begin{bmatrix}x_1 \\ x_2
\\... \\ x_n\end{bmatrix}$ whose entries are arbitrary non-negative
integers. $x_j$ represents the number of itineraries that end at island $j$ After one more ferryboat ride, the number of itineraries that
end at island $i$ is

$$\sum_{j=1}^nA_{i,j}x_j.$$ 







So we see
that the vector $A\vec{\bold{v}}$ represents the number of itineraries ending at each island after extending the existing list of
itineraries by taking one extra ferry ride wherever possible.

If you start on island $j$ and take $n$ ferryboat rides, then the
number of itineraries leading to each island is specified by the
components of the vector $A^n\vec{\bold{e_j}}$.

Hubbard does the example of a cube, where all edges are two-way.

\pagebreak

For the four-island graph, with $A=\begin{bmatrix}0 & 0 & 1 & 1\\
1 & 0 & 0 & 0\\1 & 0 & 0 & 0\\ 0 & 1 & 1 &0\end{bmatrix}$,

use matrix multiplication to find 

\begin{enumerate}
\item the number of two-step itineraries from island 1 to island 4.
\item  the number of three-step itineraries from island 1 to island 2.
\item  the number of four-step itineraries from island 3 to island 1.
\end{enumerate}\vspace{20pt}

\large

\hspace{90pt}$\begin{bmatrix}0 & 0 & 1 & 1\\
1 & 0 & 0 & 0\\1 & 0 & 0 & 0\\ 0 & 1 & 1 &0\end{bmatrix}\hspace{20pt}\begin{bmatrix}0 & 0 & 1 & 1\\
1 & 0 & 0 & 0\\1 & 0 & 0 & 0\\ 0 & 1 & 1 &0\end{bmatrix}$

$\begin{bmatrix}0 & 0 & 1 & 1\\
1 & 0 & 0 & 0\\1 & 0 & 0 & 0\\ 0 & 1 & 1 &0\end{bmatrix}$

\normalsize





 \pagebreak \item Application: Markov processes

This is inspired by example 1.2.21 in Hubbard, but in my opinion he
breaks his own excellent rule by using a ``line matrix'' to
represent probabilities.  The formulation below uses a column
vector.

Think of a graph where the vertices represent ``states'' of a random
process. A state could, for example, be

\begin{enumerate}
\item A traveler is on a specific island. \item Player 1 is
serving in a game of badminton. \item Hubbard's reference books
are on the shelf in the order (2,1,3). \item A roulette player has
two chips. \item During an inning of baseball, there is one man
out and runners on first base and third base.
\end{enumerate}

All edges are one way, and attached to each edge is a number in [0,1], the ``transition probability'' of following that edge in one
step of the process. The sum of the probabilities on all the edges
leading out of a state cannot exceed 1, and if it is less than 1
there is some probability of remaining in that state.

Examples: write at least one column of the matrix for each case.
\begin{enumerate}
\item If you are on Oahu, the probability of taking a ferry to Maui is
0.2, and the probability of taking a ferry to Lanai is 0.1. Otherwise you
stay put.

\vspace{60pt}
 \item Badminton: if player 1 serves, the probability of losing
the point and the serve is 0.2. If player 2 serves, the probability
of losing the point and the serve is 0.3.\vspace{60pt}
 \item If John Hubbard's reference books are on the shelf in the order (2,1,3),
the probability that he consults book 3 and places it at the left
to make the order (3,2,1) is $P_3$.\vspace{60pt} \item Roulette:
after starting with 2 chips and betting a chip on red, the
probability of having 3 chips is $\frac{9}{19}$ and the
probability of having 1 chip is $\frac{10}{19}.$ (in a fair
casino, each probability would be $\frac{1}{2}$). \vspace{60pt}
\end{enumerate}



For the badminton example, the transition matrix is $$A =
\begin{bmatrix}0.8 & 0.3 \\ 0.2 & 0.7\end{bmatrix}.$$

What matrix represents the transition resulting from two
successive points?

\large

\hspace{60pt}$\begin{bmatrix}0.8 & 0.3 \\ 0.2 & 0.7\end{bmatrix}$\\
\vspace{5pt}\\
$\begin{bmatrix}0.8 & 0.3 \\ 0.2 & 0.7\end{bmatrix}$

\normalsize

\vspace{5pt}

What matrix represents the transition resulting from four
successive points?

\large

\hspace{65pt}$\begin{bmatrix}0.7 & 0.45 \\ 0.3 & 0.55\end{bmatrix}$\\
\vspace{5pt}\\
$\begin{bmatrix}0.7 & 0.45 \\ 0.3 & 0.55\end{bmatrix}$

\normalsize

\vspace{5pt}


If you raise the transition matrix $A$ to a high power, you might
conjecture that after a long time the probability that player 1 is
serving is 0.6, no matter who served first.

In support of this conjecture, show that the matrix $A^{\infty} =
\begin{bmatrix}0.6 & 0.6 \\ 0.4 & 0.4\end{bmatrix}$ has the
property that $AA^{\infty}=A^{\infty}$.



















\end{enumerate}


\pagebreak








\section{Group Problems}

Organize each ``early'' section into three problem-solving groups. Try to set up the groups so that either everyone in the group or no one in the group is interested in working with R.\\
Group 1 does problems 1a and 2a, plus 3a, 3b or 4a.\\
Group 2 does problems 2b and 3b, plus 1a, 1b or 4b.\\
Group 3 does problems 3a and 1b, plus 2a, 2b, 4a or 4b.\\

Problems 4a and 4b require editing R scripts. They will be easy if you have watched the R script videos and downloaded the R scripts onto a laptop that you bring to section. Students enrolled for graduate credit and anyone who wants to use the graduate credit grading option should do one of these.  Undergraduates are free to ignore R completely.

Once your group has solved its problem, use a cell phone to take a picture of your solution, and upload it to the topic box for your section on the Week 1 page of the Web site.


%%%%%%%GROUP PROBLEMS 2, 3-part problems.  Each group does 2.%%%%%
\begin{enumerate}

\item Some short proofs


\begin{enumerate}

\item  
\begin{itemize}

\item Starting with $-1 + 1 = 0,$ prove that $(-1)a = -a$ for any $a \in F$. Justify each step of your proof by reference to one or more of the field axioms or to a theorem that was proved in class.

\item Prove that $\mathbb{Z}_6$ is not a field. (Either show that it fails to satify one of the field axioms, or show that it violates a theorem that is true any any field.)

\end{itemize}

\item Using only principles of category theory, prove that if arrow $f$ has a retraction and $f \circ h  = f \circ k$, then $h = k$. Then invent the corresponding theorem about a matrix that has a left inverse by considering the special case of a category whose only objects are $\mathbb {R}^n$ (for various $n$) and whose arrows are matrices. No proof will be needed, since you have already done a proof that applies in any category! To illustrate your proof, invent a non-square matrix that has a retraction.




\end{enumerate}


\pagebreak

\item Matrices and linear functions
\begin{enumerate}
\item Here is what we know about the function $f$:
\begin{itemize}
\item The space it maps from and the space it maps to (the domain and codomain, respectively) are both $\mathbb{R}^2$.
\item It is linear.
\item$ f(\begin{bmatrix} 1 \\ 1 \end{bmatrix}) = \begin{bmatrix} 4\\ 2\end{bmatrix}$
\item $f(\begin{bmatrix} 1 \\ 3 \end{bmatrix}) = \begin{bmatrix} 6 \\ 4 \end{bmatrix}$
\end{itemize}
\begin{enumerate}
\item Find the matrix $T$ that represents $f$ by using linearity to determine what $f$ does to the standard basis vectors.
\item Automate the calculation of $T$ by writing down a matrix equation and solving it for $T$.
\end{enumerate}
\item Suppose that $T: \mathbb({Z}_5)^2 \rightarrow \mathbb({Z}_5)^2$ is a
linear transformation for which

$T\begin{bmatrix}1\\-1\end{bmatrix} =
\begin{bmatrix}1\\2\end{bmatrix}, T\begin{bmatrix}1\\1\end{bmatrix} =
\begin{bmatrix}3\\0\end{bmatrix}.$

Construct the matrix $[T]$ that represents $T$ and the matrix
$[S]$ that represents $T^{-1}$.

Since you are working in a finite field, there are no fractions. Dividing by 2 is the same as multiplying by 3.

\end{enumerate}

\pagebreak

\item Applications of matrix multiplication
\begin{enumerate}
\item Suppose we have four islands connected by ferry routes. The ferries run clockwise around the four islands, and there are also ferries in both directions between 3 and 1 and  between 4 and 2.
\begin{center}
\begin{tikzpicture}[scale=0.6]
  \coordinate [label=left:1]  (I1)at (-2,2);
  \coordinate  [label=left:4](I2) at (-2,-2);
  \coordinate  [label=right:2](I3) at (2,2);
  \coordinate  [label=right:3](I4) at (2,-2);
 

\draw[->,style = very thick](I1) -- (I3) ;
\draw[->,style = very thick](I3) -- (I4);
\draw[->,style = very thick](I4) -- (I2);
\draw[->,style = very thick](I2) -- (I1);
\draw[<->,style = very thick](I4) -- (I1);
\draw[<->,style = very thick](I2) -- (I3);

.
  \foreach \p in {I1,I2,I3,I4}
  \draw (\p) circle (1cm);
\end{tikzpicture}
\end{center}

Write down the matrix $A$ that represents this graph, and use matrix multiplication to find how many six-step itineraries start at island 1 and end at island 3. If you are efficient, you will need to do only three multiplications.





\item The final exam in Humanities 10 always includes either a question about the Iliad or a question about the Odyssey. The choice is made by rolling a die, according to the following rules:

\begin{itemize}
\item If the exam in year $n$ had an Iliad question, the exam in year $n+1$ will have an Iliad question if the die roll is even, an Odyssey question if the die roll is odd.
\item If the exam in year $n$ had an Odyssey question, the exam in year $n+1$ will have an Odyssey question if the die roll is 1, an Iliad question otherwise.
\end{itemize}
\begin{enumerate}
\item You know that there was an Iliad question in 2012. Use matrix multiplication to calculate the probability of an Iliad quaestion in 2015.
\item You are planning that your first child will take Humanities 10 some time in the 2040s. Estimate the probability that there will be an Iliad question on the final exam. (Hint: find a vector of probabilities that does not change from year $n$ to year $n+1$.)
\end{enumerate}

\end{enumerate}

 
 
\pagebreak

\item Problems to be solved by writing or editing R scripts

Upload your scripts to the Week 1 page of the course Web site.
\begin{enumerate}
\item (similar to script 1.1A, topics 2 and 3)\\
Use the \verb!outer()! function of R to make a table of the multiplication facts for $\mathbb{Z}_{17}$ and use it to find the multiplicative inverse of each nonzero element. Then use these inverses to find the result of dividing 11 by 5 and the result of dividing 5 by 11 in this field.


\item (similar to script 1.1D, topic 1)\\You are playing roulette in an American casino, and for any play you may have 0, 1, 2, or 3 chips. When you bet a chip on ``odd'' you have only an 18/38 chance of winning, because the wheel has 18 odd numbers, 18 even numbers, plus 0 and 00 which count as neither even nor odd.
\begin{itemize}
\item If you have 0 chips you cannot bet and continue to have 0 chips.
\item If you have 1 chip you have probability 9/19 of moving up to 2 chips, probability 10/19 of moving down to 0 chips.
\item If you have 2 chip you have probability 9/19 of moving up to 3 chips, probability 10/19 of moving down to 1 chip.
\item If you have 3 chips you declare victory, do not bet, and continue to have 3 chips.
\end{itemize}

Create the $4 \times 4$ matrix that represents the effect of one play. Assume that before the first play you are certain to have 2 chips. Use matrix multiplication to determine the probability of your having 0, 1, 2, or 3 chips after 1, 2, 4 and 8 plays. Make a conjecture about the situation after a very large number of plays.


 

 


\end{enumerate}

\end{enumerate}

\pagebreak





\section{Homework} (PROBLEM SET 1 - due on Wednesday, September 14 at 11:59 PM Eastern time)
%%%%HOMEWORK - 4 problems, 2 R script problems, 2 written problems %%%%

Problems 1-7 should be done in a single .pdf file and uploaded to the Assignments page of the Web site. The easest way is to solve the problems on paper and scan them. If you are expert with LaTeX, MS Word, or the Canvas editor, that is a fine alternative.

Problems 8 and 9 are only for students who are doing the graduate credit work. Both should be done in a single R script and uploaded to the Assignments page of the course Web site.

\begin{enumerate}

\item Prove the following, using only the field axioms and the results of group problem 1(a).

\begin{enumerate}

\item The multiplicative inverse $a^{-1}$ of a nonzero element $a$ of a field is unique.

\item $(-a)(-b) = ab.$


\end{enumerate}

\item Function composition\\
( Hubbard, exercise 0.4.10.)

Prove the following:

\begin{enumerate}
\item Let the functions $f: B \rightarrow C$ and $g: A \rightarrow
B$ be onto. Then the composition $(f \circ g)$ is onto.

\item Let the functions $f: B \rightarrow C$ and $g: A \rightarrow
B$ be one-to-one. Then the composition $(f \circ g)$ is
one-to-one.


\end{enumerate}

This problem asks you to prove two results that we will use again and
again. All you need to do is to use the definitions of
``one-to-one'' and ``onto.''

Here are some strategies that may be helpful:
\begin{itemize}
\item Exploit the definition:

If you are told that $f(x)$ is onto, then, for any $y$ in the
codomain $Y$, you can assert the existence of an $x$ such that
$f(x) = y$.

If you are told that $f(x)$ is one-to-one, then, for any $a$ and
$b$ such that $f(a) = f(b)$, you can assert that $a=b$.

\item Construct what the definition requires by a procedure that
cannot fail:

To prove that $h(x)$ is onto, describe a procedure for
constructing an $x$ such that $h(x) = y$. The proof consists in
showing that this procedure works for all $y$ in the codomain $Y$.

\item Prove uniqueness by introducing two names for the same
thing:

To prove that $h(x)$ is one-to-one, give two different names to
the same thing: assume that $h(a) = h(b)$, and prove that $a = b$.

\end{itemize}

\item Hubbard, exercise 1.2.2, parts (a) and (e) only. Do part (a)
in the field $\mathbb{R}$, and do part (e) in the field
$\mathbb{Z}_7$, where -1 is the same as 6. Check your
answer in (e) by doing the calculation in two different orders:
according to the associative law these should give the same
answer. See Hubbard, figure 1.2.5, for a nice way to organize the
calculation.

\item \begin{enumerate}
\item Prove theorem 1.2.17 in Hubbard: that the transpose of a matrix
product is the product of the matrices in the opposite order:
$(AB)^T = B^TA^T$.
\item Let $A = \begin{bmatrix}1 & 2\\ 2 & 3
\end{bmatrix}, B = \begin{bmatrix}2 & -1\\ -1 & 3
\end{bmatrix}$. Calculate $AB$. Then, using the theorem you just
proved, write down the matrix $BA$ without doing any matrix
multiplication. (Notice that $A$ and $B$ are symmetric matrices.)
\item Prove that if $A$ is any matrix, then $A^TA$ is symmetric.
\end{enumerate}

\item
  \begin{enumerate}
\item Here is a matrix whose entries
are in the finite field $\mathbb{Z}_5.$

 $$A = \begin{bmatrix}[1]_5  & [2]_5\\
[3]_5 & [3]_5\end{bmatrix}$$

Write down the inverse of $A$, using the names $[0]_5 \cdots [4]_5$
for the entries in the matrix. Check your answer by matrix
multiplication.
\item Count the number of different $2 \times 2$ matrices
with entries in the finite field $\mathbb{Z}_5.$ Of these, how many
are invertible? Hint: for invertibility, the left column cannot be
zero, and the right column cannot be a multiple of the left column.
\end{enumerate}



\item \begin{enumerate}

\item Hubbard, Exercise 1.3.19, which reads:

``If $A$ and $B$ are $n \times n$ matrices, their Jordan product is $\frac{AB+BA}{2}$. Show that this product is commutative but not associative."

 Since this problem has an odd number, it is solved in the solutions manual for the textbook. If you cannot resist the temptation to consult the manual, you must cite it as a source!

\item Denote the Jordan product of $A$ and $B$ by $A * B$. Prove
that it satisfies the distributive law $A * (B + C) = A*B + A*C.$

\item Prove that the Jordan product satisfies the special
associative law $A * (B * A^2) = (A * B) * A^2$.
\end{enumerate}

\pagebreak

\item \begin{enumerate}
\item Suppose that $T$ is linear and that $T\begin{bmatrix}3\\2\end{bmatrix} =
\begin{bmatrix}6\\8\end{bmatrix},T\begin{bmatrix}2\\1\end{bmatrix} =
\begin{bmatrix}5\\5\end{bmatrix}$.

 Use the linearity of $T$ to determine $T\begin{bmatrix}1\\0\end{bmatrix}$ and $T\begin{bmatrix}0\\1\end{bmatrix}$, and thereby determine the matrix $[T]$ that
represents $T$. (This brute-force approach works fine in the $2 \times 2$ case but not in the $n \times n$ case.)


\item Express the given information about $T$ from part (a) in the
form $[T][A] = [B],$ and determine the matrix $[T]$ that
represents $T$ by using the matrix $[A]^{-1}$. (This approach will work in the general case once you know how to invert an $n \times n$ matrix .)
\end{enumerate}

The last two problems (graduate credit only) require R scripts. It is fine to copy and edit similar scripts from the course Web site, but it is unacceptable to copy and edit your classmates' scripts!

\item (similar to script 1.1C, topic 5)\\
Let $\vec{\bold{v1}}$ and $\vec{\bold{v2}}$ denote the columns of a $2 \times 2$ matrix $M$. Write an R script that draws a diagram to illustrate the rule for the sign of det $M$, namely
\begin{itemize}
\item If you have to rotate $\vec{\bold{v1}}$ counterclockwise (through less than $180^\circ$)  to make it line up with 
$\vec{\bold{v2}}$, then det$M > 0$.
\item If you have to rotate $\vec{\bold{v1}}$ clockwise (through less than $180^\circ$)  to make it line up with 
$\vec{\bold{v2}}$, then det$M < 0$.
\item  If $\vec{\bold{v1}}$ and $\vec{\bold{v2}}$ lie on the same line through the origin, then\\ det $M=0$.
\end{itemize}


\item (similar to script 1.1D, topic 2)\\
 Busch Gardens proposes to open a theme
park in Beijing, with four regions connected by monorail. From
region 1 (the Middle Kingdom), a guest can ride on a two-way
monorail to region 2(Tibet), region 3(Shanghai) or region 4(Hunan)
or back. Regions 2, 3, and 4 are connected by a one-way monorail
that goes from 2 to 3 to 4 and back to 2.




\begin{enumerate}
\item Draw a diagram to show the four regions and their monorail connections.
\item Construct the $4 \times 4$ transition matrix $A$ for this graph of
four vertices.
\item Using matrix multiplication in R, determine how many different
sequences of four monorail rides start in Tibet and end in the
Middle Kingdom.
\end{enumerate}

\end{enumerate}

 











\end{document}
