\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{8.3in}
\setlength\topmargin{0.1in}
\setlength\oddsidemargin{0.1in}
\setlength\evensidemargin{0.1in}


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

\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 4}
\vspace{0.5\baselineskip}

Due by 23:59 on Sunday 24th October (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 Let $V$ be a finite-dimensional inner product space and $\phi \colon V \to V$ a self-adjoint linear map.
    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Suppose $\phi$ is non-negative definite, and $v \in V$, $v \ne 0$ satisfies $\langle \phi(v), v \rangle = 0$.
        Prove that $\phi$ is singular (i.e., not injective / not surjective / not an isomorphism).
      \item Does (a) hold if $\phi$ is not assumed to be non-negative definite (but is still self-adjoint)?
        Give either a proof or a counter-example.
    \end{enumerate}

  \item Let $V$ be a finite-dimensional complex vector space and $\phi \colon V \to V$ a linear map.  Prove that the following are equivalent: (i) $\phi$ is diagonalizable and every eigenvalue $\lambda$ of $\phi$ satisfies $|\lambda|=1$; and (ii) there exists an inner product $\langle -,- \rangle$ on $V$ such that $\phi$ is unitary.

    [If you can pronounce it, you can say such a $\phi$ is \emph{unitarizable}.]

  \item Suppose $V, W$ are inner product spaces and $\phi \colon V \to W$ is a linear map.  (You may \emph{not} assume $V$, $W$ are finite-dimensional.)
    
    Suppose there exists an adjoint $\phi^\ast \colon W \to V$ for $\phi$; i.e., $\phi^\ast$ is a linear map such that $\langle \phi(v), w \rangle = \langle v, \phi^\ast(w) \rangle$ holds for all $v \in V$ and $w \in W$.
    
    Let $A>0$ be a given real number, and suppose that $\|\phi(v)\| \le A \|v\|$ holds for all $v \in V$.
    
    Prove that $\|\phi^\ast(w)\| \le A \|w\|$ holds for all $w \in W$.

  \item Let $V$ be a finite-dimensional inner product space an $\phi \colon V \to V$ a linear map.
    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Prove that there is a unique choice of self-adjoint linear maps $\sigma, \tau \colon V \to V$ such that $\phi = \sigma + i \tau$.

      \item Prove that $\mathcal F(\sigma) = \{ \operatorname{Re}(z) \colon z \in \mathcal F(\phi) \}$.

      \item Let $\lambda_1 \ge \dots \ge \lambda_n$ be the eigenvalues of $\sigma$ with multiplicity, and similarly let $\mu_1 \ge \dots \ge \mu_n$ be the eigenvalues of $\tau$.  Prove that
        \[
          \mathcal F(\phi) \subseteq \big\{ a + i b \in \CC \colon \lambda_n \le a \le \lambda_1,\ \mu_n \le b \le \mu_1 \big\}.
        \]
    \end{enumerate}

  \item Let $V$ be a finite-dimensional inner product space, let $\phi \colon V \to V$ be a self-adjoint linear map, and let $U \subseteq V$ be a subspace of codimension $1$ (i.e., dimension $\dim V - 1$).

    Let $\psi \colon U \to U$ be the linear map $P_U \circ \phi|_U$.

    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Prove that $\psi$ is self-adjoint.
      \item If $\lambda_1 \ge \dots \ge \lambda_n$ are the eigenvalues of $\phi$ (with multiplicity), and $\mu_1 \ge \dots \ge \mu_{n-1}$ are the eigenvalues of $\psi$ (with multiplicity), prove that for each $i$, $1 \le i \le n-1$, we have $\lambda_i \ge \mu_i \ge \lambda_{i+1}$.
    \end{enumerate}

  \item Suppose a group of 100 people, named $x_1,\dots,x_{100}$, are such that each has exactly $50$ friends in the group.
    Let $A$ be the $100 \times 100$ matrix with entries $A_{ij} = 1$ if $i \ne j$ and $x_i,x_j$ are friends, and $A_{ij}= 0$ otherwise.
    You may assume that friendship is symmetric, and therefore so is $A$.
    Suppose $\lambda_1 \ge \dots \ge \lambda_{100}$ are the eigenvalues of $A$, with multiplicity.

    \begin{enumerate}[label={\bf(\alph*)}, leftmargin=0em, labelsep=0.5em, itemsep=0.3\baselineskip, parsep=0.3\baselineskip, listparindent=0em]
      \item Prove that $\lambda_1 = 50$.
      \item Suppose further that $\lambda_2=40$ and $\lambda_{100} = -40$.
        Prove that, for any set $S \subseteq \{x_1,\dots,x_{100}\}$ of size $|S|=50$, the number $M$ of pairs $xy \in S$ such that $x,y$ are friends, satisfies
        \[
          125 \le M \le 1125.
        \]
        [\textbf{Hint:} consider the vector $y=(y_1,\dots,y_{100})$ where $y_i=1$ if $i \in S$ and $y_i=0$ otherwise, and investigate the value $\langle A y, y \rangle$.]
    \end{enumerate}
\end{enumerate}

\end{document}
