% 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}