\documentclass[12pt]{article} \usepackage{amsfonts} %\documentstyle[12pt,amsfonts]{article} %\documentstyle{article} \setlength{\topmargin}{-.5in} \setlength{\oddsidemargin}{0 in} \setlength{\evensidemargin}{0 in} \setlength{\textwidth}{6.5truein} \setlength{\textheight}{8.5truein} %\input ../basicmath/basicmathmac.tex % %\input ../adgeomcs/lamacb.tex \input ../adgeomcs/mac.tex \input ../adgeomcs/mathmac.tex \def\fseq#1#2{(#1_{#2})_{#2\geq 1}} \def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}} \def\qleq{\sqsubseteq} % \begin{document} \begin{center} \fbox{{\Large\bf Summer 1, 2009 \hspace*{0.4cm} CIS 610}}\\ \vspace{1cm} {\Large\bf Advanced Geometric Methods in Computer Science\\ Jean Gallier \\ \vspace{0.5cm} Homework 2}\\[10pt] June 9, 2009; Due June 18, 2009\\ \end{center} \vspace {0.5cm} ``B problems'' must be turned in. \vspace{0.5cm}\noindent {\bf Problem B1 (30 pts)}. The purpose of this problem is to study certain affine maps of $\affreal^2$. \medskip (1) Consider affine maps of the form % %\smallskip \[\binvec{x_1}{x_2} \mapsto \matta{\cos\theta}{-\sin\theta}{\sin\theta}{\cos\theta}\binvec{x_1}{x_2} + \binvec{b_1}{b_2}.\] % Prove that such maps have a unique fixed point $c$ if $\theta \not= 2k\pi$, for all integers $k$. Show that these are rotations of center $c$, which means that with respect to a frame with origin $c$ (the unique fixed point), these affine maps are represented by rotation matrices. \medskip (2) Consider affine maps of the form % %\smallskip \[\binvec{x_1}{x_2} \mapsto \matta{\lambda\cos\theta}{-\lambda\sin\theta} {\mu\sin\theta}{\mu\cos\theta}\binvec{x_1}{x_2} + \binvec{b_1}{b_2}.\] % Prove that such maps have a unique fixed point iff $(\lambda + \mu)\cos\theta \not= 1 + \lambda\mu$. Prove that if $\lambda\mu = 1$ and $\lambda > 0$, there is some angle $\theta$ for which either there is no fixed point, or there are infinitely many fixed points. \nsindex{fixed point} \medskip (3) Prove that the affine map % \[\binvec{x_1}{x_2} \mapsto \matta{{8}/{5}}{-{6}/{5}}{{3}/{10}}{{2}/{5}}\binvec{x_1}{x_2} + \binvec{1}{1}\] % has no fixed point. \medskip (4) Prove that an arbitrary affine map % %\smallskip \[\binvec{x_1}{x_2} \mapsto \matta{a_1}{a_2}{a_3}{a_4}\binvec{x_1}{x_2} + \binvec{b_1}{b_2}\] % has a unique fixed point iff the matrix % %\smallskip \[ \matta{a_1 - 1}{a_2}{a_3}{a_4 - 1} \] % is invertible. \vspace{0.5cm}\noindent {\bf Problem B2 (30 pts)}. Prove Proposition 2.3 of the notes on {\sl Convex Sets, Polytopes, Polyhedra, ...\/}, that is: \medskip\noindent If $K$ is any compact subset of $\affreal^m$, then the convex hull, $\mathrm{conv}(K)$, of $K$ is also compact. \vspace{0.5cm}\noindent {\bf Problem B3 (30 pts)}. Prove the version of Carath\'eodory's theorem for cones (Theorem 2.4 of notes on {\sl Convex Sets, Polytopes, Polyhedra, ...\/}), that is: \medskip\noindent Given any vector space, $E$, of dimension $\mdeg$, for any (nonvoid) family $S = (v_i)_{i\in L}$ of vectors in $E$, the cone, $\mathrm{cone}(S)$, spanned by $S$ is equal to the set of positive combinations of families of $\mdeg$ vectors in $S$. \vspace{0.5cm}\noindent {\bf Problem B4 (30 pts)}. (i) Show that if $E$ is an affine space of dimension $m$ and $S$ is a finite subset of $E$ with $n$ elements, if either $n \geq m + 3$ or $n = m + 2$ and some family of $m + 1$ points of $S$ is affinely dependent, then $S$ has at least two Radon partitions. \medskip (ii) Prove the version of Radon's theorem for cones (Theorem 2.11 of {\sl Convex Sets, Polytopes, Polyhedra, ...\/}), namely: \medskip\noindent Given any vector space $E$ of dimension $\mdeg$, for every subset $X$ of $E$, if $\mathrm{cone}(X)$ is a pointed cone such that $X$ has at least $\mdeg + 1$ nonzero vectors, then there is a partition of $X$ into two nonempty disjoint subsets, $X_1$ and $X_2$, such that the cones, $\mathrm{cone}(X_1)$ and $\mathrm{cone}(X_2)$, have a nonempty intersection not reduced to $\{0\}$. \medskip (iii) ({\bf Extra Credit (30 pts)}) Does the converse of (i) hold? \vspace{0.5cm}\noindent {\bf Problem B5 (30 pts)}. Let $S$ be any nonempty subset of an affine space $E$. Given some point $a\in S$, we say that $S$ is {\it star-shaped with respect to $a$\/} iff the line segment $[a, x]$ is contained in $S$ for every $x\in S$, i.e. $(1 - \lambda)a + \lambda x \in S$ for all $\lambda$ such that $0\leq \lambda \leq 1$. We say that $S$ is {\it star-shaped\/} iff it is star-shaped w.r.t. to some point $a\in S$. \medskip (1) Prove that every nonempty convex set is star-shaped. \medskip (2) Show that there are star-shaped subsets that are not convex. Show that there are nonempty subsets that are not star-shaped (give an example in $\affreal^n$, $n = 1, 2, 3$). \medskip (3) Given a star-shaped subset $S$ of $E$, let $N(S)$ be the set of all points $a\in S$ such that $S$ is star-shaped with respect to $a$. Prove that $N(S)$ is convex. \vspace{0.5cm}\noindent {\bf Problem B6 (50 pts)}. (a) Let $E$ be a vector space, and let $U$ and $V$ be two subspaces of $E$ so that they form a direct sum $E = U \oplus V$. Recall that this means that every vector $x \in E$ can be written as $x = u + v$, for some unique $u\in U$ and some unique $v \in V$. Define the function $\mapdef{p_U}{E}{U}$ (resp. $\mapdef{p_V}{E}{V}$) so that $p_U(x) = u$ (resp. $p_V(x) = v$), where $x = u + v$, as explained above. Check that that $p_U$ and $p_V$ are linear. \medskip (b) Now assume that $E$ is an affine space (nontrivial), and let $U$ and $V$ be affine subspaces such that $\vector{E} = \vector{U} \oplus \vector{V}$. Pick any $\Omega\in V$, and define $\mapdef{q_U}{E}{\vector{U}}$ (resp. $\mapdef{q_V}{E}{\vector{V}}$, with $\Omega\in U$) so that \[ q_U(a) = p_{\vecsmal{U}}(\libvecbo{\Omega}{a}) \quad(\hbox{resp.}\quad q_V(a) = p_{\vecsmal{V}}(\libvecbo{\Omega}{a})), \quad\hbox{for every $a\in E$}. \] Prove that $q_U$ does not depend on the choice of $\Omega\in V$ (resp. $q_V$ does not depend on the choice of $\Omega\in U$). Define the map $\mapdef{p_U}{E}{U}$ (resp. $\mapdef{p_V}{E}{V}$) so that \[ p_U(a) = a - q_V(a)\quad(\hbox{resp.}\quad p_V(a) = a - q_U(a)), \quad\hbox{for every $a\in E$}. \] Prove that $p_U$ (resp. $p_V$) is affine. \medskip The map $p_U$ (resp. $p_V$) is called the {\it projection onto $U$ parallel to $V$ (resp. projection onto $V$ parallel to $U$)\/}. \medskip (c) Let $(a_0, \ldots, a_n)$ be $n + 1$ affinely independent points in $\affreal^n$, and let $\Delta(a_0, \ldots, a_n)$ denote the convex hull of $(a_0, \ldots, a_n)$ (an $n$-simplex). Prove that if $\mapdef{f}{\affreal^n}{\affreal^n}$ is an affine map sending $\Delta(a_0, \ldots, a_n)$ inside itself, i.e., \[f(\Delta(a_0, \ldots, a_n)) \subseteq \Delta(a_0, \ldots, a_n),\] then, $f$ has some fixed point $b\in \Delta(a_0, \ldots, a_n)$, i.e., \[f(b) = b.\] {\it Hint\/}: Proceed by induction on $n$. First, treat the case $n = 1$. The affine map is determined by $f(a_0)$ and $f(a_1)$, which are affine combinations of $a_0$ and $a_1$. There is an explicit formula for some fixed point of $f$. For the induction step, compose $f$ with some suitable projections. \vspace{0.5cm}\noindent {\bf TOTAL: 200 (+ 30) points.} \end{document}