\documentclass[10pt,reqno,letterpaper]{amsart}

\usepackage{tabularx}
\usepackage{enumitem}
\usepackage{url}

\newcommand{\RR}[0]{\mathbb{R}}
\newcommand{\NN}[0]{\mathbb{N}}
\newcommand{\FF}[0]{\mathbb{F}}
\newcommand{\CC}[0]{\mathbb{C}}
\newcommand{\ZZ}[0]{\mathbb{Z}}
\newcommand{\spn}[0]{\operatorname{span}}

\pdfpagewidth 8.3in %chktex 1
\pdfpageheight 11.7in %chktex 1
\setlength\textwidth{6.15in}
\setlength\oddsidemargin{0.1in}
\setlength\evensidemargin{0.1in}


%\pagenumbering{gobble}
\title{MATH 202A \\ Applied Algebra I \\ Fall 2021}

\begin{document}

\maketitle

\section*{Homework week 1}
\vspace{0.5\baselineskip}

Due by 2359 on Sunday October 3 (hand in via Gradescope).
\vspace{0.5\baselineskip}

\begin{enumerate}[label={\bf\arabic*.}, itemsep=0.8\baselineskip, leftmargin=2em, labelsep=2em,parsep=0.4\baselineskip]

  \setlength{\parindent}{0em}
  \item Prove, using only the results from Section 1.2, that (i) any finitely-generated vector space has a (finite) basis, and (ii) any two bases of a finitely-generated vector space $V$ have the same size.

    [Recall that we say a vector spaces is finitely-generated to mean that it has a finite spanning set.]

  \item Suppose $n$ is a positive integer and a collection of subsets $S_1,\dots,S_k \subseteq \{1,\dots,n\}$ (not necessarily distinct) are given.
    A set $I \subseteq \{1,\dots,k\}$ is called \emph{awesome} if it has the following property: for every $x \in \{1,\dots,n\}$, the number
    \[
      \lvert \{ i \in I \colon x \in S_i \} \rvert
    \]
    is even.

    Prove that the number of awesome sets $I \subseteq \{1,\dots,k\}$ is always a power of $2$.

  \item Let $V$, $W$ be vector spaces, $U \subseteq V$ a subspace, and $\phi \colon V \to W$ a linear map.  Suppose also that $\ker \phi \supseteq U$.

    Prove that there exists a unique linear map $\psi \colon V/U \to W$ such that $\phi(v) = \psi(v + U)$ for all $v \in V$.

    Prove that $\psi$ is injective if and only if $U = \ker \phi$.

  \item Let $V$ be a finite-dimensional vector space and $U \subseteq V$ a subspace.  Suppose that $u_1,\dots,u_k$ are a basis for $U$, and $v_1,\dots,v_m$ are vectors in $V$ such that $v_1+U,\dots,v_m+U$ is a basis for $V/U$.

    Prove that $u_1,\dots,u_k,v_1,\dots,v_m$ is a basis for $V$ (and hence $\dim V = \dim U + \dim (V/U)$).

  \item Suppose $V$ is a vector space over $\RR$, that $w_1, w_2, w_3 \in V$ is a spanning set for $V$, and that $u_1,u_2,u_3$ are linearly independent where
    \begin{align*}
      u_1 &= 4 w_1 -3 w_3 \\
      u_2 &= -w_1 + w_3 \\
      u_3 &= w_1 + w_2 + w_3 .
    \end{align*}
    It is a consequence of Theorem 1.2.1 that $u_1, u_2, u_3$ spans $V$ (since we can add $3-3=0$ elements from $w_1,w_2,w_3$ to make it span).
    In particular, $w_1, w_2, w_3$ lie in $\spn(u_1,u_2,u_3)$, meaning there exist coefficients $a_{ij} \in \RR$ such that $w_j = a_{j1} u_1 + a_{j2} u_2 + a_{j3} u_3$.

    Our proofs are constructive: that is, we can---and will---find the coefficients $a_{ij}$ explicitly by close inspection of \emph{the proof of Theorem 1.2.1} and its subsidiary lemmas.

    This ``expanded'' proof is as follows.
    Set $B_0 = w_1,w_2,w_3$.
    \begin{enumerate}[leftmargin=5em, itemsep=0.5\baselineskip]
      \item[Step 1:] Consider the spanning list $u_1,w_1,w_2,w_3$.
        It is linearly dependent (by Lemma~1.2.3, as $B_0$ spans).
        Using this dependence relation and Lemma~1.2.2, we discover that $w_3 \in \spn(u_1, w_1, w_2)$ and $B_1 = u_1, w_1, w_2$ spans $V$.
      \item[Step 2:] Consider the spanning list $u_2,u_1,w_1,w_2$.
        It is linearly dependent (by Lemma~1.2.3, as $B_1$ spans).
        Using this dependence relation and Lemma~1.2.2, we discover that $w_1 \in \spn(u_2, u_1)$ and $B_2=u_2, u_1, w_2$ spans $V$.
      \item[Step 3:] Consider the spanning list $u_3,u_2,u_1,w_2$.
        It is linearly dependent (by Lemma~1.2.3, as $B_2$ spans).
        Using this dependence relation and Lemma~1.2.2, we discover that $w_2 \in \spn(u_3,u_2, u_1)$ and $B_3=u_3,u_2, u_1$ spans $V$.
    \end{enumerate}

    Now, in each Step $i$ ($1 \le i \le 3$):---
    \begin{enumerate}[label=(\alph*), leftmargin=0em, labelsep=0.5em, itemsep=0.5\baselineskip]
      \item find an explicit dependence relation in the length $4$ list, and explicit coefficients in each of the statements after ``we discover that'' (i.e., respectively $w_3 \in \spn(u_1, w_1, w_2)$, $w_1 \in \spn(u_2, u_1)$, $w_2 \in \spn(u_3,u_2, u_1)$);

      \item using your answers to (a), find explicit coefficients for each of the statements $u_1 \in \spn(B_i)$, $u_2 \in \spn(B_i)$, $u_3 \in \spn(B_i)$, and summarize your answers in a $3 \times 3$ matrix;
      \item using your answers to (a), find explicit coefficients for each of the statements $w_1 \in \spn(B_i)$, $w_2 \in \spn(B_i)$, $w_3 \in \spn(B_i)$, and summarize your answers in a $3 \times 3$ matrix.
    \end{enumerate}

    Note the similarity of this process with any other algorithms (Gaussian elimination / reducing to RREF / LU decomposition / etc.) with which you are familiar.
    [You need not write anything for this part.]
\end{enumerate}

\end{document}
