\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\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}
\def\spec{\operatorname{spec}}

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

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

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

  \item Consider the space $V$ of complex sequences $(a_0,a_1,a_2,\dots)$ satisfying
    \[
      a_n = r_1 a_{n-1} + r_2 a_{n-2} + \cdots + r_d a_{n-d}
    \]
    for all $n \ge d$, where $d \ge 1$ is an integer and $r_1,\dots,r_d \in \CC$ are fixed constants.
    We assume also that $r_d \ne 0$.
    You may also assume without proof that $V$ is finite-dimensional and $\dim V = d$.

    As in Problem Set 6 Q6, write $\phi \colon V \to V$ for the linear map
    \[
      \phi(a_0,a_1,a_2,\dots) = (a_1,a_2,a_3,\dots)
    \]
    and also write $\psi \colon V \to \CC$ for the linear functional $\psi(v_0,v_1,v_2,\dots) = v_0$.
    You may use without proof that $r_d \ne 0 \Rightarrow 0 \notin \spec(\phi)$.

    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Suppose $v=(v_0,v_1,v_2,\dots) \in G(\lambda, \phi)$.  By considering the action of $\phi^m$, or otherwise, prove that there exists constants $c_0,\dots,c_{k-1}$ where $k = \dim G(\lambda,\phi)$, such that
        \[
          v_m = \psi(\phi^m(v)) = \sum_{i=0}^{k-1} c_i \binom{m}{i} \lambda^m
        \]
        for all $m \ge 0$.
        (By convention, $\binom{n}{i} = 0$ if $i>n$.)
      \item Prove that the sequences $v^{\lambda,i} \in V$ for $\lambda \in \spec(\phi)$ and $0 \le i < \dim G(\lambda, \phi)$, given by
        \[
          v^{\lambda,i}_n = \binom{n}{i} \lambda^n,
        \]
        form a basis for $V$.

        [You should be careful to explain why these sequences are in $V$ and are linearly independent, although you should not need to prove these things directly.]
    \end{enumerate}

  \item 
    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Suppose $V$ is an inner product space with inner product $\langle -, - \rangle$ and associated norm $\|\cdot\|$.
        Prove that the \emph{parallelogram law} holds for $\|\cdot\|$: that is, for all $v,w \in V$ we have
        \[
          \|v + w\|^2 + \|v - w\|^2 = 2 \|v\|^2 + 2 \|w\|^2.
        \]
      \item Suppose $V$ is a finite-dimensional real vector space and $\|\cdot\|$ is a norm on $V$ obeying the parallelogram law: that is,
        \[
          \|v + w\|^2 + \|v - w\|^2 = 2 \|v\|^2 + 2 \|w\|^2
        \]
        for all $v,w \in V$.  Prove that there is an inner product $\langle -,- \rangle$ on $V$ such that $\|v\| = \sqrt{\langle v,v \rangle}$.
        
        [{\bf Hint}: consider the quantity $\frac12 \left( \|v+w\|^2 - \|v\|^2-\|w\|^2 \right)$.]

        [{\bf Hint}: it may be useful to prove the identity
        \begin{align*}
          &\|v+w\|^2 + \|v-w\|^2 - \|v'+w\|^2 - \|v'-w\|^2 \\
          {}-{}& \|v+w'\|^2 - \|v-w'\|^2 + \|v'+w'\|^2 + \|v'-w'\|^2 = 0
        \end{align*}
        by applying the parallelogram law four times to $(v,w)$, $(v',w)$, $(v,w')$ and $(v',w')$.
        This identity, with a suitable substitution of variables, should be what you need to prove linearity.]
        
      \item For every $n \ge 2$ and $1 \le p \le \infty$, $p \ne 2$, find vectors $v,w \in \RR^n$ such that
        \[
          \|v + w\|_p^2 + \|v - w\|_p^2 \ne 2 \|v\|_p^2 + 2 \|w\|_p^2.
        \]
        [Hence, the $\|\cdot\|_p$-norms do not secretly come from some exotic inner product.]

      \item[\bf(d*)] Prove the same statement as (b) assuming now that $V$ is a complex vector space.

        [{\bf Hint}: it may now help to build an expression from the quantities $\|v \pm w\|^2$ and $\|v \pm i w \|^2$.]
    \end{enumerate}

  \item Let $V = \RR^n$, and identify $V^\ast = \RR^n$ in the usual way; i.e., a vector $(a_1,\dots,a_n) \in \RR^n$ corresponds to a linear map $\RR^n \to \RR$,
    \[
      (x_1,\dots,x_n) \mapsto a_1 x_1 + \cdots + a_n x_n.
    \]
    For each of the norms $\|\cdot\|_\infty$ and $\|\cdot\|_1$ on $\RR^n$, determine carefully the value of the corresponding dual norms
      $\|(a_1,\dots,a_n)\|_\infty^\ast$, $\|(a_1,\dots,a_n)\|_1^\ast$ for all $(a_1,\dots,a_n) \in \RR^n \cong V^\ast$.

  \item 
    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
    \item 
      For every integer $n \ge 1$ and every pair of values $p,q$ with $1 \le p \le q \le \infty$, find the largest contsant $c \in \RR$ and the smallest constant $C \in \RR$ such that $c \|x\|_p \le \|x\|_q \le C \|x\|_p$ for all $x \in \CC^n$.
    \item If $A$ is an $n \times n$ complex matrix, we interpret it as a linear map $\CC^n \to \CC^n$ in the usual way.
      We use the usual Euclidean norm $\|\cdot\|_2$ on $\CC^n$.
      For every integer $n \ge 1$, find the largest contsant $c \in \RR$ and the smallest constant $C \in \RR$ such that
      \[
        c \|A\|_{\operatorname{op}} \le \max_{1 \le i,j \le n} |A_{ij}| \le C \|A\|_{\operatorname{op}}
      \]
      holds for all matrices $A$.
      
      [Specifically, $\|A\|_{\operatorname{op}}$ is the smallest constant $K$ such that $\|A x\|_2 \le K \|x\|_2$ for all $x \in \CC^n$.]
  \end{enumerate}

  \item Let $V$ be a finite-dimensional vector space.
    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Suppose $\|\cdot\|$, $\|\cdot\|'$ are two norms on $V$ such that  $\|\cdot\| \le \|\cdot\|'$.  Prove that ${\|\cdot\|'}^\ast \le \|\cdot\|^\ast$.

      \item If $\|\cdot\|$ is a norm on $V$ and $\alpha \in \RR_{>0}$ is a scalar, write $\alpha\|\cdot\|$ for the norm $v \mapsto \alpha \|v\|$.  Prove that the dual norm to $\alpha \|\cdot\|$ is $(1/\alpha) \|\cdot\|^\ast$.
    \end{enumerate}
  \end{enumerate}
\end{document}
