\documentclass[11pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd}
\usepackage{graphicx, epsfig}
\usepackage{multicol}
\usepackage{boxedminipage}
\usepackage{subfigure}
\usepackage{euler,palatino,array}
\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}
\usepackage{wrapfig}
\usepackage{bbold}


\setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in} 
\setlength{\parindent}{0in}
\newcounter{prob}
\setcounter{prob}{0}
\newcommand{\problem}{\stepcounter{prob}\medskip{\bf Presentation problem \theprob.}\ }
\newcommand{\answer}{\medskip{\bf Answer to Question \theprob.}\ }
\newcommand{\solution}{\medskip{\bf Solution to Question \theprob.}\ }



% ***** Some useful abreviations *****
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\B}{\mathscr{B}}
\newcommand{\LL}{\mathscr{L}}
\newcommand{\PP}{\mathscr{P}}
\newcommand{\ra}{\rightarrow}
\newcommand{\ds}{\displaystyle}
\newcommand{\bnum}{\begin{enumerate}} %Use with \item to create numbered lists
\newcommand{\enum}{\end{enumerate}}
\newcommand{\babc}{\bnum\renewcommand{\labelenumi}{(\alph{enumi})}}%Use with \item for abc lists
\newcommand{\eabc}{\end{enumerate}}
\newcommand{\bijk}{\bnum\renewcommand{\labelenmi}{\roman{enumi}.}}%Roman numeral lists
\newcommand{\eijk}{\end{enumerate}}

\renewcommand{\ss}{\smallskip}
\newcommand{\ms}{\medskip}
\newcommand{\bs}{\bigskip}




\pagestyle{myheadings} \markright{Math 4310 (Fall 2020) \hspace{2in}
(HW11)}

\begin{document}


%% PREAMBLE

\thispagestyle{empty}

\begin{minipage}[t]{1.1in}
{\vspace{-0.2in}
  \includegraphics[width=1.1in]{cornell-logo.jpg}}
\end{minipage}
\hfill
\begin{minipage}[t]{3in}
%\vspace{.05in}
  {\large Homework \# 11

    \medskip
    Math 4310 Fall 2020

    \medskip
    
    Due dates are below.
  }

\end{minipage}
\hfill
\begin{minipage}[t]{3.4in}
\end{minipage}

\vskip 0.25in

%\vspace*{-66mm}

Problems (1)-(6) are due Friday night, December 11, at midnight.  Problems (7)-(8) are due Wednesday night, December 16, at midnight.

\medskip

Please submit your completed homework via gradescope on canvas.
I encourage you to work with your classmates on this homework (except for the journal entries!)
When you submit your work, please {\bf list your collaborators}.
(Your grade will not be affected.)
Even if you work in a group, you should write up 
your solutions {\bf yourself}! 
You should include all computational details, and proofs should be carefully 
written with full details.
As always, please write {\bf neatly and legibly} (feel free to use \LaTeX\ to write up your solutions, if you wish!).

\vskip 4mm

%% END PREAMBLE

\noindent {\bf Journal entry.} There is no journal entry this week.

\vskip 0.1in

\noindent {\bf Exercises.} 

\vskip 0.1in

\begin{enumerate}

  \item{\bf (Square root of a symmetric matrix)}
    Recall from homework 9 that a symmetric $n \times n$ matrix
    $A$ is called {\bf positive definite} if for all ${\bf x} \ne 0
    \in \R^n$, that $x^T A x > 0$.  If instead, the symmetric matrix
    $A$ satisfies that if ${\bf x} \ne 0 \in \R^n$, then $x^T A x \ge
    0$, we call $A$ {\bf positive semi-definite}.

    Suppose that $A \in \R^{n \times n}$
    is positive semi-definite.  Show the following.
    \babc
  \item Every eigenvalue of $A$ is non-negative.
  \item There exists a symmetric matrix $B \in \R^{n \times n}$, such that $A = B^2$.
    \eabc

\item Find a singular value decomposition for the matrix
  \[
  A = \begin{pmatrix}
    1 & 1 & 1 & -1 \\
    1  & 0 & 1 & 2 \\
    1 & -1 & 1 & -1
    \end{pmatrix}
  \]

  Do this computation by hand.  Then check your work using software
  (e.g. Matlab, Julia, Macaulay2).

  \item Rank 1 matrices.  Let $A \in \R^{m \times n}$ be a rank one matrix.
    \babc
    \item Show that there exists unit vectors ${\bf x} \in \R^m$ and
    ${\bf y} \in \R^n$, and a number $\alpha > 0$ such that $A = \alpha x y^T$.
    \item If $A$ has rank 1, find a compact singular value decomposition for $A$.
      \item If $A = \alpha x y^T$ as in (a), find the eigenvalues and eigenvectors of $A$.
    \eabc

  \item Let $V = \R^{m \times n}$ be the vector space of $m \times n$ matrices, equipped with
    the ``standard'' inner product:
    \[ \langle A, B \rangle = \sum_{i,j} A_{i,j} B_{i,j}. \]
    The Frobenius norm of a matrix $A \in V = \R^{m \times n}$ is
    \[ ||A|| = \langle A, A \rangle = \sqrt{\sum_{i,j} A_{ij}^2}, \]
    This is sometimes written as $||A||_F$.
    In this problem. we also assume that $A = \sigma_1 u_1 v_1^T + \ldots + \sigma_r u_r v_r^T$ arises from a compact singular
    value decomposition of $A$.
    For $k \le r$, let $A_k := A = \sigma_1 u_1 v_1^T + \ldots + \sigma_k u_k v_k^T$.

    Recall that the trace $tr(C)$ of a square matrix $C$ satisfies $tr(AB) = tr(BA)$, whenever both of these matrix products are well defined,
    and that 
    \[ \langle A, B \rangle = trace(A^TB) = trace(BA^T). \]
    \babc
   \item Show that the  matrices $M_i = u_i v_i^T$ are orthonormal (in $V$, using the standard inner product described above), and consequently, $||A||^2 = \sigma_1^2 + \ldots + \sigma_r^2$.
     \item Find $||A - A_k||$.
   \item Show that if $Q$ is an orthogonal $m \times m$ matrix, then $||Q A|| = ||A||$.  What is $||A|| = ||U \Sigma V^T||$ for an SVD of $A$?
     \eabc

     This is the beginning of the proof of the Eckart-Young theorem, which states that for every $m \times n$ matrix $B$ of rank at most $k$, then
     \[ ||A - A_k|| \le ||A - B||, \]
     i.e. that $A_k$ is the closest rank $k$ matrix to $A$.  See also
     \url{https://en.wikipedia.org/wiki/Low-rank_approximation#Proof_of_Eckart%E2%80%93Young%E2%80%93Mirsky_theorem_(for_Frobenius_norm)}

     \item ({\bf Rayleigh quotients}).
       Let $B \in \R^{n \times n}$ be a symmetric matrix.  If ${\bf x} \ne {\bf 0} \in \R^n$,
       then the Rayleigh quotient of ${\bf x}$ is
       \[ R({\bf x}) = \frac{{\bf x}^T B {\bf x}}{{\bf x}^T {\bf x}}. \]
       \babc
     \item Show that $\max_{{\bf x} \ne {\bf 0}} R({\bf x}) = \lambda_1$, the largest eigenvalue of
       $B$, and that $\min_{{\bf x}\ne {\bf 0}} R({\bf x}) = \lambda_n$, the smallest eigenvalue of
       $B$.
     \item Suppose that $A \in \R^{n \times n}$ is a matrix (not necessarily symmetric).
       Define
       \[ ||A||_E := \max_{{\bf x} \ne {\bf 0}}  \frac{||A {\bf x}||}{||{\bf x}||}. \]
       Suppose that the singular values of $A$ are $\sigma_1 \ge \sigma_2 \ge \ldots \ge \sigma_r$.
       Find $||A||_E$, and, if $A$ is invertible, find $||A^{-1}||_E$.

       \eabc

       We aren't using it here, but the {\bf condition number} of a
       matrix $A$ is defined to be $cond(A) = {\frac{\sigma_1}{\sigma_n}}$ (if $A$
       is invertible) and $cond(A) = \infty$ (if $A$ is not invertible).

       \pagebreak
     \item {\bf (Pseudo-inverses)}. 
       \babc
     \item
       Suppose that $A \in \R^{m \times n}$ has rank $m$, and $m \le n$.  Using
     SVD's, find a matrix $B \in \R^{n \times m}$ such that $AB = I_m$.  (Remember, these
     are not square matrices!)
   \item Given $A$, find a matrix $B \in \R^{n \times m}$ satisfying the following 4
     conditions (these conditions uniquely determine $B$ given $A$).  We write $A^\dagger := B$
     for this matrix.
     \begin{itemize}
     \item $ABA = A$ (i.e. although $AB$ is not necessarily the identity,
       it does map each column of $A$ to itself).
     \item $BAB = B$.
     \item $AB$ is symmetric.
       \item $BA$ is symmetric.
     \end{itemize}
     (using SVD's might be useful here!).
     \eabc

   \item Suppose that the matrix $A \in \C^{7 \times 7}$ satisfies:
     \begin{itemize}
     \item $A$ has 2 distinct eigenvalues $0, i$.
     \item The minimal polynomial of $A$ is $p(x) = (x-i)^2x^3$.
       \item The eigenspace for $\lambda = 0$ has dimension 2.
     \end{itemize}
     \babc
   \item Find the possible Jordan canonical forms of $A$.
   \item For each of these possible JCF's, what is the dimension of the eigenspace $E_i(A)$?
     \eabc

   \item Prove that if $A \in \C^{n \times n}$, then $A$ and $A^T$ are similar. (Hint: use Jordan canonical form!).

\end{enumerate}

\end{document}



