\documentclass[a4paper,12pt]{scrartcl}

% \usepackage[english,german]{babel} % [verfuegbare Sprachen, letzgenannte ist aktiv]
\usepackage{tikz}
\usetikzlibrary{arrows,positioning} 

\usepackage{graphicx} % include eps graphics
\usepackage{psfrag} % .eps properly aligned, scaled, and rotated
\usepackage{wrapfig} % WRAP FIGURE [text umfliest das Bild]
\usepackage[ngerman,english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
\usepackage{mathtools}
\usepackage{ngerman} % Silbentrennung ect. in neuer-Rechtschreibung-deutsch
\usepackage{eurosym} % Das euro Symbol [nicht mehr]
\usepackage{color} % textcolors [RGB oder auch 68 Standardfarben]
\usepackage{soul}
\usepackage{enumerate} % aufzaehlungen
\usepackage{paralist} % kuerzere Aufzaehlungen
\usepackage{url} % bessere Darstellung (hyperref: auch anklickbar)
\usepackage{alltt} % ermoeglicht uninterpretierten Text (sozusagen String)
\usepackage{ae,aecompl} % ecFonts auf cmFonts zurueckfuehren
\usepackage{ifthen}
\usepackage{amsmath} % MATH allignment[Matrix,Brueche,Gleichungen]
\usepackage{amssymb} % Mathe SYMBOLE
\usepackage{amsthm} % Mathe THEOREM [theorem,lemma,proof] Gliederung
\usepackage{verbatim} % multiline comment
\usepackage{paralist}
%\parindent =0pt
\usepackage{geometry}
\graphicspath{{../../figures/}}
\geometry{
  body={},
  left=1.2in,
  right = 1.2 in,
  top=1.25in
}
\hypersetup{
  colorlinks = true,
  urlcolor = red,
  pdfauthor = {},
  pdfkeywords = {albert haase, mathematics, mathematik},
  pdfsubject = {},
  pdfpagemode = UseNone
}

\newcommand{\R}{\mathbb{R}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\s}{\mathbb{S}}
\newcommand{\su}{\mathcal{S}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ti}{\mathcal{T}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\dd}{\mathcal{D}}
\newcommand{\E}{\mathbf{E}}
\newcommand{\HRule}{\rule{1.03\textwidth}{0.5mm}}
\renewcommand\O{\mbox{\rm O}}
%\renewcommand{\subset}{\subseteq}
\newcommand{\V}{\mathcal{V}}
\DeclareMathOperator{\im}{im}
\newcommand\Stack{\mathrm{Stack}}
\renewcommand{\to}{\longrightarrow}


\newcommand{\red}{\textcolor{red}} %Farben
\newcommand{\green}{\textcolor{green}}
\newcommand{\ink}{\textcolor[rgb]{0,.2,.8}}
\newcommand{\purp}{\textcolor[rgb]{0.9,0,.5}}
\newcommand{\sky}{\textcolor[rgb]{0,.5,.7}}
\newcommand{\tree}{\textcolor[rgb]{0,.4,.1}}
\newcommand\Emph[1]{\emph{\color{blue}#1}}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\VV}{\mathcal{V}}

\newcommand{\set}[1]{\ensuremath{ \left\{ #1 \right\}}}
\newcommand{\mset}[2]{\ensuremath{\left\{ #1  :  #2 \right\}}}
\renewcommand{\mapsto}{\longmapsto}
\newcommand{\inner}[1]{\left\langle \, #1  \,\right\rangle}
\newcommand{\linspan}[1]{\ensuremath{\text{span}\left\{ #1 \right \} }}
\newcommand{\ma}{\begin{smallmatrix} } \newcommand{\trix}{\end{smallmatrix}} % Matrix
\newcommand\aff{\operatorname{aff}}
\newcommand\conv{\operatorname{conv}}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\inter}{int}
\linespread{1.2}

\selectlanguage{german}
\tikzset{
>=stealth',
pil/.style={
           ->,
           shorten <=1pt,
           shorten >=1pt,}
}

\begin{document}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushleft}
\includegraphics[scale=0.09]{bms-logo-eff}\\[5pt]
{\small Prof.~G\"unter M.~Ziegler} \\
{\small Albert Haase, Miriam Schlöter}
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushright}
\includegraphics[scale=0.4]{fu-logo}\\[5pt]
{\small Institut f"ur Mathematik }\\
{\small Arbeitsgruppe Diskrete Geometrie}\\
\end{flushright}
\end{minipage}

\enlargethispage{5mm}
\vspace{20pt}
\centerline{\Large {Discrete Geometry II -- Problem Sheet 6}}
\centerline{\large \bf Solution to Problem 1c}
\vspace{20pt}
\noindent {\large\bf Problem 1: }\textit{Convex bodies, polars, and ellipsoids}\hfill (8(+2) Points)
\begin{compactenum}[\normalfont (a)]
\item[(c)] Let $E$ be an ellipsoid centered at the origin given by $E = \{x \in \R^d \colon \langle Qx, x \rangle \le 1 \}$, where $Q$ is a positive definite matrix. Show that $E^* =  \{y \in \R^d \colon \langle Q^{-1}y, y \rangle \le 1 \}.$
\end{compactenum}
\begin{proof}
To begin with, we will prove two facts:
\begin{compactitem}
\item Fact 1: Given a nonempty set $K \subseteq \R^d$ and an invertible linear transformation $A$ on $\R^d$, we have
\[
(AK)^* = (A^t)^{-1} K^*,
\]
where the asterisk denotes the polar.
\item Fact 2: If $B_d$ denotes the $d$-dimensional unit ball, then 
\[
B_d^* = B_d.
\] 
\end{compactitem}

\begin{proof}[Proof of Fact 1] 
This was shown in class on Thursday, June 5. Let us recall it:
\begin{align*}
(AK)^* &= \{ y \in \R^d \, : \, y^t A x \le 1 \; \forall x \in K \} \\
&=\{ y \in \R^d \, : \, (A^t y)^t x \le 1 \; \forall x \in K \} \\
&=\{ (A^t)^{-1} A^t y  \, : \, y \in \R^d, \; (A^t y)^t x \le 1 \; \forall x \in K \} \\
&=\{ (A^t)^{-1} z \, : \, z\in \R^d, \; z^t x \le 1 \; \forall x \in K \} \\
&=(A^t)^{-1} \{  z\in \R^d, \, : \,  z^t x \le 1 \; \forall x \in K \} \\
&=(A^t)^{-1}K^*.
\end{align*}
\end{proof} 
\begin{proof}[Proof of Fact 2]
\begin{align*}
B_d^* &= \{ y \in \R^d \, : \, y^t x \le 1 \; \forall x \in B_d \} \\
&= \{ y \in \R^d \, : \, \underset{\| x \|\le 1}{\mathrm{max}} \; y^t x \le 1 \} \\
&\subseteq \{ y \in \R^d \, : \, \underset{\| x \|\le 1}{\mathrm{max}} \; \| y \| \| x \| \le 1 \} \\
&=\{ y \in \R^d \, : \, \| y \| \le 1 \} \\
&= B_d,
\end{align*}
where the (third) inclusion is due to the Cauchy--Schwarz inequality. For the reverse inclusion, let $x_0 \in B_d$ and let $x \in \R^d$ such that $ \| x \| \le 1$, then $x_0^t x \le \| x_0 \| \|x \| \le 1$ and hence, $x \in B_d^*$.
\end{proof}

The matrix $Q$ can be written as $Q=U^tDU$ for an orthogonal matrix $U$ and a diagonal matrix $D$ with (strictly) positive entries. Hence $Q$ can be written as $Q=L^t L$, where $L= \sqrt{D}U$. 

Finally, let's prove the original claim in 1(c). Let
\[
S := \{y \in \R^d \colon \langle Q^{-1}y, y \rangle \le 1 \}.
\]

Let $A := L^{-1}$ and $K := B_d$ in Fact 1. Then,
\begin{align*}
E^* &= (L^{-1} B_d)^* \\
&= L^t B_d^* \\
&= L^t B_d \\
&= S,
\end{align*}
where the first equality is a simple calculation, the second is due to Fact 1, the third is due to Fact 2, and the last is again a simple calculation. For the simple calculations use that the inverse of a transpose is the transpose of its inverse, and the fact that inverses of symmetric matrices are symmetric.
\end{proof}

\end{document}