\documentclass[a4paper,12pt]{scrartcl}

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

\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{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 = blue,
  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{\cc}{\mathcal{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}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\V}{\mathcal{V}}
\DeclareMathOperator{\im}{im}

\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{\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{pmatrix}} \newcommand{\trix}{\end{pmatrix}} % Matrix
\newcommand\aff{\operatorname{aff}}
\newcommand\conv{\operatorname{conv}}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\inter}{int}
%\linespread{1.2}

\selectlanguage{german}

\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, Marie Litz}
\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}

\vspace{20pt}
\centerline{\Large \bf{Discrete Geometry 1 -- Problem Sheet 5}}
\vspace{15pt}

Please hand in your solutions to Prof.~Ziegler on \textbf{Wednesday, Nov.~20, 2013} before the lecture begins. Please put your name and student ID (if you have one) on the first page of your solutions and staple the sheets together.

\vspace{20pt}

{\large\bf Problem 1: }\textit{Vertices and Facets of a Direct Sum} \hfill (4+3+1(+2) Points)\\[5pt]
Let $\Delta_d \subset \R^d$ denote a $d$-simplex with the origin in its interior. The \Emph{direct sum} or \Emph{free sum} of $\Delta_d$ with itself is defined as
\[
\Delta_d \oplus \Delta_d \coloneqq \conv \big( \mset{(p,0) \in \R^{2d}}{p \in \Delta_d} \cup \mset{(0,p') \in \R^{2d}}{p' \in \Delta_d} \big) \subset \R^{2d}.
\]
\begin{enumerate}[\normalfont (a) ]
\item Is $\Delta_d \oplus \Delta_d$ a polytope? How many vertices and how many facets does $\Delta_d \oplus \Delta_d$ have? What is its dimension?
\item State the vertex-facet incidence Matrix $I = I(\Delta_d \oplus \Delta_d)$ of $\Delta_d \oplus \Delta_d$.
\item Which combinatorial properties does $\Delta_d \oplus \Delta_d$ have that can be immediately determined from $I$?
\item \emph{Bonus:} What does $I^t$ describe? Explain.
\end{enumerate}

\vspace{15pt}

{\large\bf Problem 2: }\textit{Polarity} \hfill (4+2 Points)
\begin{enumerate}[\normalfont (a) ]
\item Compute explicitly and draw the polars of the following rectangles in the plane:
\begin{compactenum}[(i)]
		\item $R_1$ with vertices $(0,0), (M,0), (M,1)$ and $(0,1)$, for $M>0$ large.
		\item $R_2$ with vertices $(-\epsilon,-\epsilon), (M, - \epsilon), (M,1)$ and $(-\epsilon,1)$, for $M>0$ large and $\epsilon>0$ small.
		\item $R_3$ with vertices $(\epsilon,\epsilon), (M, \epsilon), (M,1)$ and $(\epsilon,1)$, for $M>0$ large and $\varepsilon>0$ small. 
	\end{compactenum}
\item What happens in (ii) and (iii) if $\varepsilon\rightarrow0$ or $M\rightarrow\infty$? Give an explanation.
\end{enumerate}

\newpage

{\large\bf Problem 3: }\textit{A vertex-facet incidence matrix} \hfill (6 Points)\\[5pt]
Is this the vertex-facet incidence matrix of a convex polytope? If yes, how many vertices and how many
facets does it have? What is its dimension? What else can you say about it? 
Can you draw it?
\[
I= 
\left(
\begin{matrix}
1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 
1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 
1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 
0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 
0 & 0 & 0 & 1 & 0 & 1 & 1 \\  
0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 
1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 
0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 
0 & 1 & 1 & 0 & 0 & 0 & 1 
\end{matrix}
\right)
\]

\vspace{15pt}

{\large\bf Problem 4: }\textit{\emph{Bonus Problem:} Farkas Lemma} \hfill ((6) Points)\\[5pt]
Given a vector $x \in \R^d$, the relation $x \geq 0$ means that all components $x_i$ for $i =1, \ldots, d$ are non-negative. Consider the following version of Farkas' Lemma:\\[3pt]
Let $A \in \R^{m \times d}$ and $a \in \R^m$. \emph{Either} there is an $x \in \R^d$ such that $Ax = a$ and $x \geq 0$, \emph{or} there is a vector $c \in \R^m$ %with $c\geq 0$ 
such that $c^t A \geq 0$ and $c^t a < 0$, but not both.\\[3pt]
Show that this version of Farkas' Lemma is equivalent to the one stated in the lecture (Proposition 2.61 of the lecture notes).
\\
\emph{(Note: This is a corrected version -- the vector $c$ need not satisfy $c\ge0$.)}

\end{document}
