\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
\pdfpageheight 11.7in
\setlength\textwidth{6.15in}
\setlength\textheight{9.3in}
\setlength\topmargin{-0.1in}
\setlength\oddsidemargin{0.1in}
\setlength\evensidemargin{0.1in}


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

\begin{document}

\maketitle

\def\id{\operatorname{id}}
\def\im{\operatorname{im}}
\def\ker{\operatorname{ker}}
\def\eps{\varepsilon}

\vspace{-1.5\baselineskip}
\section*{Homework week 5}
\vspace{0.5\baselineskip}

Due by the beginning of class on Friday 1st November (hand in via Gradescope).
\vspace{0.5\baselineskip}

Given an linear map $\phi$ between finite dimensional inner product spaces, we write $\sigma_1(\phi)$ for the largest singular value of $\phi$.
\begin{enumerate}[label={\bf\arabic*.}, itemsep=0.8\baselineskip, leftmargin=2em, labelsep=2em, listparindent=0em, parsep=0.3\baselineskip]

  \item If $V$ is a finite-dimensional inner product space and $\phi \colon V \to V$ is a normal map with eigenvalues $\lambda_1,\dots,\lambda_n$. Prove that the singular values of $\phi$ are $|\lambda_1|,\dots,|\lambda_n|$.

  \item Let $U, V, W$ be finite-dimensional inner product spaces and $\phi \colon U \to V$, $\psi \colon V \to W$ linear maps, show that $\sigma_1(\psi \circ \phi) \le \sigma_1(\psi) \sigma_1(\phi)$.

  \item 
    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Let $V$ be a finite dimensional inner product space and $\phi \colon V \to V$ a linear map.  For any positive integer $k$, prove that $\sigma_1(\phi^k) \le \sigma_1(\phi)^k$.
      Prove that if $\phi$ is normal then $\sigma_1(\phi^k) = \sigma_1(\phi)^k$.
      \item Consider $V = \CC^2$ and $\phi(x,y) = (x + (3/2) y, y)$.  Prove that $\sigma_1(\phi)^{1000} = 2^{1000}$ but $\sigma_1(\phi^{1000}) \le 1500 + \frac1{1500}$.
    \end{enumerate}

  \item Let $V$ be an inner product space (not necessarily finite-dimensional) and $\phi \colon V \to V$ a self-adjoint, non-negative definite linear map (i.e., $\langle \phi(v),w \rangle = \langle v, \phi(w) \rangle$ for all $v,w \in V$, and $\langle \phi(v), v \rangle \ge 0$ for all $v \in V$).
    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Prove carefully that for all $v,w \in V$, $|\langle \phi(v), w \rangle|^2 \le \langle \phi(v), v \rangle \langle \phi(w), w \rangle$.
      \item Prove that if $\langle \phi(v), v \rangle = 0$ then $\phi(v)=0$.  [If you proved Pset 4 Q1(a) like this already, great; if not this gives a new proof.]
      \item Now suppose $\psi \colon V \to V$ is another self-adjoint, non-negative definite linear map and $\langle (\phi + \psi)(v), v \rangle = 0$.  Prove that $\phi(v) = \psi(v) = 0$.
    \end{enumerate}

  \item Let $V$ be an inner product space (not necessarily finite-dimensional) and let $\phi, \psi \colon V \to V$ be two self-adjoint, non-negative definite linear maps such that $\phi^2 = \psi^2$.
    Suppose moreover that $\phi \circ \psi = \psi \circ \phi$.  Prove that $\phi = \psi$.

    [{\bf Hint:} You could look at something like $\langle (\phi + \psi) (\phi - \psi) (v), (\phi - \psi)(v) \rangle$ for arbitrary $v \in V$, and remember Q1.  But there are probably many other starting points.]


  \item My office has three chairs, arranged in a row.\footnote{My office does actually now have chairs in.  They are not arranged in a row; that bit is a lie.}  Every hour, I receive an instruction by email from the university authorities.  
    If the instruction says ``FLIP'', I roll a fair $2$-sided die and accordingly move to one of the chairs I am not currently sitting in, with probability $1/2$ each.

    If the instruction says ``FLOP'', I roll a fair $4$-sided die and move chairs, or not, based on the rule given in Pset 3 Q7.

    So, if my probabilities of being in each chair one hour are $(p_L, p_M, p_R)$, then the probabilities for the next hour are given by
    \[
      \psi(p_L, p_M, p_R) = \left(\frac12 p_M + \frac12 p_R, \frac12 p_L + \frac12 p_R, \frac12 p_L + \frac12 p_M \right)
    \]
    if the instruction is ``FLIP'', and
    \[
      \phi(p_L, p_M, p_R) = \left(\frac3{4} p_L + \frac1{4} p_M, \frac1{4} p_L + \frac1{2} p_M + \frac1{4} p_R, \frac1{4} p_M + \frac3{4} p_R \right) 
    \]
    if the instruction is ``FLOP''.

    The university authorities are a law unto themselves, and their instructions are unpredictable, arbitrary and follow no predictable pattern.  In particular you may \emph{not} assume that FLIP and FLOP occur according to any particular random rule.

    I start in the left chair.  Show that the probability I am in the left chair again after 1000 straight hours in my office is $1/3 + \eps$ where $|\eps| \le 2 \cdot (3/4)^{1000}$ (which is around $2.3 \cdot 10^{-125}$).

    [{\bf Hint:} it might help to consider Q1, Q2 and the subspace $\{1,1,1\}^\perp$.] 
\end{enumerate}
\end{document}
