\documentclass[]{book}

%These tell TeX which packages to use.
\usepackage{array,epsfig}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsxtra}
\usepackage{amsthm}
\usepackage{mathrsfs}
\usepackage{color}

%Here I define some theorem styles and shortcut commands for symbols I use often
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem*{rmk}{Remark}
\newtheorem{lem}{Lemma}
\newtheorem*{joke}{Joke}
\newtheorem{ex}{Example}
\newtheorem*{soln}{Solution}
\newtheorem{prop}{Proposition}

\newcommand{\lra}{\longrightarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\surj}{\twoheadrightarrow}
\newcommand{\graph}{\mathrm{graph}}
\newcommand{\bb}[1]{\mathbb{#1}}
\newcommand{\Z}{\bb{Z}}
\newcommand{\Q}{\bb{Q}}
\newcommand{\R}{\bb{R}}
\newcommand{\C}{\bb{C}}
\newcommand{\N}{\bb{N}}
\newcommand{\M}{\mathbf{M}}
\newcommand{\m}{\mathbf{m}}
\newcommand{\MM}{\mathscr{M}}
\newcommand{\HH}{\mathscr{H}}
\newcommand{\Om}{\Omega}
\newcommand{\Ho}{\in\HH(\Om)}
\newcommand{\bd}{\partial}
\newcommand{\del}{\partial}
\newcommand{\bardel}{\overline\partial}
\newcommand{\textdf}[1]{\textbf{\textsf{#1}}\index{#1}}
\newcommand{\img}{\mathrm{img}}
\newcommand{\ip}[2]{\left\langle{#1},{#2}\right\rangle}
\newcommand{\inter}[1]{\mathrm{int}{#1}}
\newcommand{\exter}[1]{\mathrm{ext}{#1}}
\newcommand{\cl}[1]{\mathrm{cl}{#1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\vol}{\mathrm{vol}}
\newcommand{\cnt}{\mathrm{ct}}
\newcommand{\osc}{\mathrm{osc}}
\newcommand{\LL}{\mathbf{L}}
\newcommand{\UU}{\mathbf{U}}
\newcommand{\support}{\mathrm{support}}
\newcommand{\AND}{\;\wedge\;}
\newcommand{\OR}{\;\vee\;}
\newcommand{\Oset}{\varnothing}
\newcommand{\st}{\ni}
\newcommand{\wh}{\widehat}

%Pagination stuff.
\setlength{\topmargin}{-.3 in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.in}
\setlength{\textwidth}{6.5in}
\pagestyle{empty}



\begin{document}


\begin{center}
{\Large Machine Learning\\Assignment 1's Solutions}\\
\textbf{Luan.Dinh}
Due: Nov 8
\end{center}

\vspace{0.2 cm}


\subsection*{Exercises for Section 1.1: Norm and Inner Product}

\begin{enumerate}
\item\label{norms}
Define the \textdf{$\ell^1$-norm} on $\R^n$ by
$$\|x\|_1 = \sum_{i=1}^n |x^i|,$$
and define the \textdf{sup-norm} on $\R^n$ by
$$\|x\|_\infty = \sup\left\{|x^i|\right\}.$$
Show that these satisfy Theorem~1.
\begin{proof}
% WRITE YOUR PROOF HERE.
\end{proof}

\item Prove that $\ds \|x\|\leq \sum_{i=1}^n |x^i|$.  In other words, the usual norm is no greater than the $\ell^1$-norm.
\begin{proof}
% WRITE YOUR PROOF HERE.
\end{proof}

\item Prove that $\|x-y\| \leq \|x\| + \|y\|$.  (Compare this with part (2) of
Theorem~1.)  When does equality hold?

\item Prove that $\ds \bigg| \, \|x\|-\|y\| \, \bigg| \leq \|x-y\|$.

\item The quantity $\|y-x\|$ is called the \textdf{distance} between $x$ and
$y$.  Prove and interpret the ``triangle inequality'':
$$\|z-x\| \leq \|z-y\| + \|y-x\|.$$

\item\label{caushw} Let $f$ and $g$ be integrable on $[a,b]$.
\begin{enumerate}
\item Prove the integral version of the Cauchy-Schwarz inequality:
$$\left|\int_a^b fg\right| \leq \left(\int_a^b
f^2\right)^{1/2}\left(\int_a^b g^2\right)^{1/2}.$$
Hint:  Consider separately the cases $0 = \int_a^b(f-t g)^2$ for
some $t\in\R$, and $0<\int_a^b(f-t g)^2$ for all
$t\in\R$.
\item If equality holds, must $f=t g$ for some $t\in\R$?
What if $f$ and $g$ are continuous?
\item Show that the Cauchy-Schwarz inequality is a special case of
(a).

\end{enumerate}

\item A linear transformation $T:\R^n\lra\R^n$ is \textdf{norm preserving} if
$$\|T(x)\|=\|x\|,$$ for all $x\in\R^n$, and \textdf{inner product preserving} if
$$\ip{Tx}{Ty} = \ip xy,$$ for all $x,y\in\R^n$.
\begin{enumerate}
\item Prove that $T$  is norm preserving if and only if it is inner
product preserving.

\item Prove that such a linear transformation is 1-1, and $T^{-1}$ is
norm preserving (and inner product preserving).
\end{enumerate}

\item\label{bddlin} If $T:\R^m\lra\R^n$ is a linear transformation, show that there is a
number $M$ such that $\|T(h)\|\leq M\|h\|$ for all $h\in\R^m$.  Hint: Estimate
$\|T(h)\|$ in terms of $\|h\|$ and the entries in the matrix for $T$.

\item If $x,y\in\R^n$, and $z,w\in\R^m$, show that $\ds\ip{(x,z)}{(y,w)} = \ip xy
+ \ip zw$, and $\ds\|(x,z)\| = \sqrt{\|x\|^2 + \|z\|^2}$.  Note that $(x,z)$ and
$(y,w)$ denote points in $\R^{n+m}$.

\item If $x,y\in\R^n$, then $x$ and $y$ are called \textdf{perpendicular} (or
\textdf{orthogonal}), and we write $x\perp y$, if $\ip xy = 0$.  If $x\perp y$,
prove that $\|x+y\|^2 = \|x\|^2 + \|y\|^2$.

\end{enumerate}


\subsection*{Exercises for Section~1.2: More Topology: Open and Closed Sets in
$\R^n$}
\begin{enumerate}
\item\label{topology} Prove that the union of any (even infinite) number of open sets is open.
Prove that the intersection of two (and hence of finitely many) open sets is
open.  Give a counterexample for the intersection of infinitely many open sets.

\item\label{clAB}If $A\subset B\subset\R^n$, prove that
$$\cl{A}\subset\cl{B},\quad\mbox{ and }\quad\inter{A}\subset\inter{B}.$$

\item Prove that if $B$ is an open subset of $A$, then $B\subset \inter(A)$.  Note that this says that $\inter(A)$ is the largest open subset of $A$.

\item \label{openset}Prove that the $n$-dimensional ball centered at $a$ of radius $r$,
$$\ds B^n(a;r) = \left\{x\in\R^n:\|x-a\|< r\right\}$$ is open.

\item Find the interior, exterior, and boundary of the sets:
$$B^n = \left\{x\in\R^n : \|x\| \leq 1\right\},$$
$$S^{n-1} = \left\{x\in\R^n : \|x\| = 1\right\},$$
$$\Q^n = \left\{x\in\R^n : \mbox{ each } x^i\mbox{ is rational}\right\}.$$
\begin{soln}
% Put your answers here.
\end{soln}


\item If $A\subset[0,1]$ is the union of open intervals $(a_i,b_i)$ such that
each rational number in $(0,1)$ is contained in some $(a_i,b_i)$, show that
$\bd A = [0,1] - A$.

\item If $A$ is a closed set that contains every rational number $r\in[0,1]$,
show that $[0,1]\subset A$.

\item Graph generic open balls in $\R^2$ with respect to each of the ``non-Euclidean'' norms, $\|\cdot\|_1$ and $\|\cdot\|_\infty$.
What shapes are they?
\begin{soln}
% Put your figure and your write-up here.  See the website on how to
% add a figure.
\end{soln}

\end{enumerate}



\end{document}