% LaTeX file -- M245, Fall 2012, Assignment 6

\documentclass[11pt]{amsart}
\usepackage{amssymb, amstext, amscd, amsmath}
\pagestyle{empty}
%\topmargin 1cm
\textheight 10.3in
\textwidth 7.0in
\oddsidemargin -0.250in
\evensidemargin -0.25in
\voffset -30mm

\newcommand{\bF}{{\mathbb F}}
\newcommand{\bN}{{\mathbb N}}
\newcommand{\bQ}{{\mathbb Q}}
\newcommand{\bR}{{\mathbb R}}
\newcommand{\bC}{{\mathbb C}}
\newcommand{\bZ}{{\mathbb Z}}

%      Capital script letters
  \newcommand{\A}{{\mathcal{A}}}
  \newcommand{\B}{{\mathcal{B}}}
  \newcommand{\C}{{\mathcal{C}}}
  \newcommand{\D}{{\mathcal{D}}}
  \newcommand{\E}{{\mathcal{E}}}
  \newcommand{\F}{{\mathcal{F}}}
  \newcommand{\G}{{\mathcal{G}}}
\renewcommand{\H}{{\mathcal{H}}}
  \newcommand{\I}{{\mathcal{I}}}
  \newcommand{\J}{{\mathcal{J}}}
  \newcommand{\K}{{\mathcal{K}}}  
\renewcommand{\L}{{\mathcal{L}}}
  \newcommand{\M}{{\mathcal{M}}}
  \newcommand{\N}{{\mathcal{N}}}
\renewcommand{\O}{{\mathcal{O}}}
\renewcommand{\P}{{\mathcal{P}}}
  \newcommand{\Q}{{\mathcal{Q}}}
  \newcommand{\R}{{\mathcal{R}}}
\renewcommand{\S}{{\mathcal{S}}}
  \newcommand{\T}{{\mathcal{T}}}
  \newcommand{\U}{{\mathcal{U}}}
  \newcommand{\V}{{\mathcal{V}}}
  \newcommand{\W}{{\mathcal{W}}}
  \newcommand{\X}{{\mathcal{X}}}
  \newcommand{\Y}{{\mathcal{Y}}}
  \newcommand{\Z}{{\mathcal{Z}}}

\newcommand{\fM}{{\mathfrak{M}}}

\newcommand{\FOR}{\text{ for }}
\newcommand{\FORAL}{\text{ for all }}
\newcommand{\AND}{\text{ and }}
\newcommand{\IF}{\text{ if }}
\newcommand{\OR}{\text{ or }}
\newcommand{\qand}{\quad\text{and}\quad}
\newcommand{\qor}{\quad\text{or}\quad}
\newcommand{\qfor}{\quad\text{for}\quad}
\newcommand{\qforal}{\quad\text{for all}\quad}
\newcommand{\qif}{\quad\text{if}\quad}

\newcommand{\ol}{\overline}
\newcommand{\ep}{\varepsilon}
\renewcommand{\phi}{\varphi}
\newcommand{\mt}{\emptyset}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\lip}{\langle}
\newcommand{\rip}{\rangle}
\newcommand{\ip}[1]{\lip #1 \rip}
\newcommand{\aff}{\operatorname{aff}}
\newcommand{\conv}{\operatorname{conv}}
\newcommand{\nul}{\operatorname{nul}}
\newcommand{\ran}{\operatorname{Ran}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\spn}{\operatorname{span}}
\newcommand{\Tr}{\operatorname{Tr}}
\newcommand{\dint}{\displaystyle\int}
\newcommand{\dlim}{\displaystyle\lim\limits}
\newcommand{\dsum}{\displaystyle\sum\limits}

\newcounter{exerci}[section]
\renewcommand{\theexerci}{\arabic{exerci}}
\newenvironment{Ex}{\begin{list}%
 {\theexerci.\hfill}{\usecounter{exerci}\rightmargin=0pt\leftmargin=12pt%
 \labelwidth=12pt\labelsep=3pt\itemsep=3ex}}{\end{list}\medbreak}
\newenvironment{parts}{\vspace{1ex}\begin{enumerate}\renewcommand{\itemsep}{1ex}
 \renewcommand{\labelenumi}{(\alph{enumi})}}{\end{enumerate}}
\newcommand{\hint}{\textbf{Hint:} }

\begin{document}
\thispagestyle{empty}

%%%%%%%   TITLE   %%%%%%
\begin{center}
\textbf{\large Math 245  Assignment 6\\
Due  Friday November 30}
\end{center}
\vskip 1em 

\begin{Ex}
\item A quadratic form is a real function of $n$ variables $x=(x_1,\dots,x_n) \in \bR^n$ of the form \\
\strut\hspace{35mm} $\displaystyle q(x_1,\dots,x_n) = \sum_{i=1}^n\sum_{j=1}^i a_{ij} x_ix_j$.  

\begin{parts}
\item Show that there is a real \textit{symmetric} matrix $A=A^*$ so that $q(x) = \ip{Ax,x}$.

\item Use the fact that $A$ can be diagonalized to show that there are
linear functions $L_i(x) = \sum_{j=1}^n b_{ij} x_j$ for $1 \le i \le n$ so that
$q(x) = \sum_{i=1}^n \ep_i L_i(x)^2$ where $\ep_i \in \{1,0,-1\}$.

\item Deduce that if a quadratic form takes only non-negative values, then it is the sum of squares
of linear functions. 

\item \textbf{Bonus.} Show that the polynomial $p(x,y,z) = x^4y^2 + x^2y^4 + z^6 - 3x^2y^2z^2$
takes only non-negative values, but is not the sum of squares of polynomials. 
\hint Use the arithmetic mean-geometric mean inequality.
For the second part, restrict attention to a sum of squares of homogeneous cubics.
\end{parts}

\item The \textit{Schur product} of two matrices $\big[a_{ij}\big]$ and $\big[b_{ij}\big]$
is $\big[a_{ij}b_{ij}\big]$. Prove that the Schur product of two positive matrices is positive.
\hint first establish this for two positive rank one matrices. Then express each positive matrix as a sum of positive rank one matrices.

\item Let $M$ and $N$ be subspaces of a vector space $V$. ($M^\perp$ is the annihilator of $M$ in $V'$.)
\begin{parts}
\item  Show that $(M+N)^\perp = M^\perp \cap N^\perp$.
\item  Show that $(M \cap N)^\perp = M^\perp + N^\perp$.
\item Show that the map $J$ from $M/(M \cap N)$ to $(M+N)/N$ 
given by $J\big( m+ (M \cap N) \big) = m+N$ is a linear isomorphism.
\item Provide an example to show that if $V$ is a normed vector space,
then $J$ may not be isometric.\\ \hint this can be done with $V=(\bR^2,\|\cdot\|_2)$.
\end{parts}


\item Let $A$ and $B$ be closed convex sets in $\bR^n$, and let $C$ be a compact convex set.
\begin{parts}
\item Define $A+B=\{a+b : a\in A,\ b\in B\}$.
Prove that $A+B$ is convex.
\item  Show that $A+C=B+C$ implies that $A=B$.  \hint separation theorem.
\item \textbf{Bonus.} Show that $A+C$ is closed. (This is easy, but it is real analysis.)
\end{parts}

\item Let $V$ be a finite dimensional vector space over $\bF = \bR$ or $\bC$.
Let $C$ be a closed bounded balanced convex subset of $V$ containing $0$ in 
its interior. Show that $C$ is the unit ball of a norm on $V$.


\item  Let $V$ be a real vector space. A subset $S$ of $V$ is \textit{affine} if $s_1,s_2\in S$
implies that $ts_1 + (1-t)s_2 \in S$ for all $t \in \bR$.
The \textit{affine hull} of $S \subset V$ is 
$\aff(S) = \big\{ \sum_i t_i s_i : s_i \in S,\ t_i \in \bR,\ \sum_i t_i = 1 \big\}$.
A set $S$ is \textit{affinely dependent} if some $s_0\in S$ is in the affine hull of $S\setminus\{s_0\}$.
Otherwise it is \textit{affinely independent}. 

\begin{parts}
\item Show that $\aff(S)$ is the smallest affine set containing $S$.
\item Show that $\aff(S)$ is a translate of a subspace.

\item Show that $s_0,s_1,\dots, s_k$ are affinely dependent if and only if $s_1\!-\!s_0,\dots,s_k\!-\!s_0$
are linearly dependent. 

\item Let $n=\dim V$. Suppose that $r \ge n+2$ and $s_1,\dots,s_r$ are vectors in $V$.
Show that there are disjoint sets $I$ and $J$ with $I \cup J = \{1,2,\dots,r\}$ so that
$C_I = \conv\{s_i : i \in I\}$ and $C_J = \conv\{s_i : i \in J\}$ intersect.
\hint use (c) to get a non-trivial affine relation; split  into positive and negative terms.

\item  \textbf{Bonus.} \textit{Helly's Theorem}: let $C_1,\dots,C_m$ be convex sets in $V$
such that any $n+1$ of them have non-empty intersection. 
Prove that the whole collection has non-empty intersection. \\
\hint induction on $m \ge n+1$. Pick $s_j$ in $\bigcap_{i\ne j} C_i$ for $1 \le j \le m$.  Apply (d).
\end{parts}



\end{Ex}
\end{document}