\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 Spring, 2006 \hspace*{0.4cm} CIS 610}}\\ \vspace{1cm} {\Large\bf Advanced Geometric Methods in Computer Science\\ Jean Gallier \\ \vspace{0.5cm} Homework 1}\\[10pt] January 23, 2006; Due February 8, 2006\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace {0.5cm}\noindent {\bf Problem A1.} (a) Given a tetrahedron $(a, b, c, d)$, given any two distinct points $x, y\in \{a, b, c, d\}$, let let $m_{x,y}$ be the middle of the edge $(x, y)$. Prove that the barycenter $g$ of the weighted points $(a, 1/4)$, $(b, 1/4)$, $(c, 1/4)$, and $(d, 1/4)$, is the common intersection of the line segments $(m_{a, b}, m_{c, d})$, $(m_{a, c}, m_{b, d})$, and $(m_{a, d}, m_{b, c})$. Show that if $g_d$ is the barycenter of the weighted points $(a, 1/3), (b, 1/3), (c, 1/3)$ then $g$ is the barycenter of $(d, 1/4)$ and $(g_d, 3/4)$. \vspace{0.5cm}\noindent {\bf Problem A2}. Given any two affine spaces $E$ and $F$, for any affine map $\mapdef{f}{E}{F}$, for any convex set $U$ in $E$ and any convex set $V$ in $F$, prove that $f(U)$ is convex and that $f^{-1}(V)$ is convex. Recall that $$f(U) = \{b \in F\ |\ \exists a\in U,\, b = f(a)\}$$ is the {\it direct image of $U$ under $f$\/}, and that $$f^{-1}(V) = \{a \in E\ |\ \exists b\in V,\, b = f(a)\}$$ is the {\it inverse image of $V$ under $f$\/}. \vspace{0.5cm}\noindent {\bf Problem A3}. Let $E$ be a nonempty set and $\affvec{E}$ be a vector space and assume that there is a function $\mapdef{\Phi}{E\times E}{\affvec{E}}$, such that if we denote $\Phi(a, b)$ by $\libvecbo{a}{b}$, the following properties hold: \begin{enumerate} %\medskip \item[(1)] $\libvecbo{a}{b} + \libvecbo{b}{c} = \libvecbo{a}{c}$, for all $a, b, c \in E$; %\medskip \item[(2)] For every $a\in E$, the map $\mapdef{\Phi_a}{E}{\affvec{E}}$ defined such that for every $b\in E$, $\Phi_a(b) = \libvecbo{a}{b}$, is a bijection. \end{enumerate} %\medskip Let $\mapdef{\Psi_a}{\affvec{E}}{E}$ be the inverse of $\mapdef{\Phi_a}{E}{\affvec{E}}$. \medskip Prove that the function $\mapdef{+}{E\times \affvec{E}}{E}$ defined such that \[a + \novect{u} = \Psi_a(\novect{u})\] for all $a\in E$ and all $\novect{u}\in \affvec{E}$ makes $(E, \affvec{E}, +)$ into an affine space. %\medskip \medskip\noindent {\it Note\/}: We showed in class that an affine space $(E, \affvec{E}, +)$ satisfies the properties stated above. Thus, we obtain an equivalent characterization of affine spaces. \vspace {0.5cm} ``B problems'' must be turned in. \vspace {0.25cm}\noindent {\bf Problem B1 (30 pts).} Given any two distinct points $a, b$ in $\affreal^2$ of barycentric coordinates $(a_0, a_1, a_2)$ and $(b_0, b_1, b_2)$ with respect to any given affine frame, show that the equation of the line $\lag a, b\rag$ determined by $a$ and $b$ is \medskip $$\detc{a_0}{b_0}{x}{a_1}{b_1}{y}{a_2}{b_2}{z} = 0,$$ \medskip\noindent or equivalently $$(a_1b_2 - a_2b_1)x + (a_2b_0 - a_0b_2)y + (a_0b_1 - a_1b_0)z = 0,$$ where $(x, y, z)$ are the barycentric coordinates of the generic point on the line $\lag a, b\rag$. \medskip Prove that the equation of a line in barycentric coordinates is of the form $$ux + vy + wz = 0,$$ where $u\not= v$, or $v\not= w$, or $u\not= w$. Show that two equations $$ux + vy + wz = 0\quad\hbox{and}\quad u'x + v'y + w'z = 0$$ represent the same line in barycentric coordinates iff $(u',v', w') = \lambda (u, v, w)$ for some $\lambda\in\reals$ (with $\lambda\not= 0$). \medskip A triple $(u, v, w)$ where $u\not= v$, or $v\not= w$, or $u\not= w$, is called a system of {\it tangential coordinates\/} of the line defined by the equation $$ux + vy + wz = 0.$$ \vspace{0.25cm}\noindent {\bf Problem B2 (30 pts).} Given two lines $D$ and $D'$ in $\affreal^2$ defined by tangential coordinates $(u, v, w)$ and $(u', v', w')$ (as defined in problem B1), let \medskip $$d = \detc{u}{v}{w}{u'}{v'}{w'}{1}{1}{1} = vw' - wv' + wu' - uw' + uv' - vu'. $$ \medskip (a) Prove that $D$ and $D'$ have a unique intersection point iff $d\not= 0$, and that when it exists, the barycentric coordinates of this intersection point are $$\frac{1}{d}(vw' - wv',\, wu' - uw',\, uv' - vu').$$ \medskip (b) Letting $(O, i, j)$ be any affine frame for $\affreal^2$, recall that when $x + y + z = 0$, for any point $a$, the vector $$x\libvecbo{a}{O} + y\libvecbo{a}{i} + z\libvecbo{a}{j}$$ is independent of $a$ and equal to $$y\libvecbo{O}{i} + z\libvecbo{O}{j} = (y, z).$$ The triple $(x, y, z)$ such that $x + y + z = 0$ is called the {\it barycentric coordinates\/} of the vector $y\libvecbo{O}{i} + z\libvecbo{O}{j}$ w.r.t. the affine frame $(O, i, j)$. \medskip Given any affine frame $(O, i, j)$, prove that for $u\not= v$, or $v\not= w$, or $u\not= w$, the line of equation $$ux + vy + wz = 0$$ in barycentric coordinates $(x, y, z)$ (where $x + y + z = 1$) has for direction the set of vectors of barycentric coordinates $(x, y, z)$ such that $$ux + vy + wz = 0$$ (where $x + y + z = 0$). \medskip Prove that $D$ and $D'$ are parallel iff $d = 0$. In this case, if $D\not= D'$, show that the common direction of $D$ and $D'$ is defined by the vector of barycentric coordinates $$(vw' - wv',\, wu' - uw',\, uv' - vu').$$ \medskip (c) Given three lines $D$, $D'$, and $D''$, at least two of which are distinct, and defined by tangential coordinates $(u, v, w)$, $(u', v', w')$, and $(u'', v'', w'')$, prove that $D$, $D'$, and $D''$ are parallel or have a unique intersection point iff \medskip $$\detc{u}{v}{w}{u'}{v'}{w'}{u''}{v''}{w''} = 0.$$ \vspace{0.5cm}\noindent {\bf Problem B3 (40 pts)}. This problem uses notions and results from Problems B1 and B2. %, and \ref{pb2.8}. %\medskip In view of (a) and (b) of Problem B2, it is natural to extend the notion of barycentric coordinates of a point in $\affreal^2$ as follows. Given any affine frame $(a, b, c)$ in $\affreal^2$, we will say that the barycentric coordinates $(x, y, z)$ of a point $M$, where $x + y + z = 1$, are the {\it normalized barycentric coordinates\/} of $M$. Then, any triple $(x, y, z)$ such that $x + y + z\not= 0$ is also called a system of barycentric coordinates for the point of normalized barycentric coordinates \[ \frac{1}{x + y + z}\,(x, y, z). \] With this convention, the intersection of the two lines $D$ and $D'$ is either a point or a vector, in both cases of barycentric coordinates \[ (vw' - wv',\, wu' - uw',\, uv' - vu'). \] When the above is a vector, we can think of it as a point at infinity (in the direction of the line defined by that vector). \medskip Let $(D_0, D_0')$, $(D_1, D_1')$, and $(D_2, D_2')$ be three pairs of six distinct lines, such that the four lines belonging to any union of two of the above pairs are neither parallel nor concurrent (have a common intersection point). If $D_0$ and $D_0'$ have a unique intersection point, let $M$ be this point, and if $D_0$ and $D_0'$ are parallel, let $M$ denote a nonnull vector defining the common direction of $D_0$ and $D_0'$. In either case, let $(m, m', m'')$ be the barycentric coordinates of $M$, as explained at the beginning of the problem. We call $M$ the {\it intersection\/} of $D_0$ and $D_0'$. Similarly, define $N = (n, n', n'') $ as the intersection of $D_1$ and $D_1'$, and $P = (p, p', p'') $ as the intersection of $D_2$ and $D_2'$. \medskip Prove that %\medskip \[\detc{m}{n}{p}{m'}{n'}{p'}{m''}{n''}{p''} = 0\] % %\medskip\noindent iff either \begin{enumerate} \item[(i)] $(D_0, D_0')$, $(D_1, D_1')$, and $(D_2, D_2')$ are pairs of parallel lines; or \medskip \item[(ii)] the lines of some pair $(D_i, D_i')$ are parallel, each pair $(D_j, D_j')$ (with $j \not= i$) has a unique intersection point, and these two intersection points are distinct and determine a line parallel to the lines of the pair $(D_i, D_i')$; or \item[(iii)] each pair $(D_i, D_i')$ ($i = 0, 1, 2$) has a unique intersection point, and these points $M, N, P$ are distinct and collinear. \end{enumerate} \vspace{0.5cm}\noindent {\bf Problem B4 (40 pts)}. The purpose of this problem is to prove {\it Pascal's Theorem\/} for the nondegenerate conics. In the affine plane $\affreal^2$, a {\it conic\/} is the set of points of coordinates $(x, y)$ such that \[ \alpha x^2 + \beta y^2 + 2\gamma xy + 2\delta x + 2\lambda y + \mu = 0, \] where $\alpha\not= 0$ or $\beta\not= 0$ or $\gamma\not= 0$. We can write the equation of the conic as % %\medskip \[ (x, y, 1)\mattc{\alpha}{\gamma}{\delta} {\gamma}{\beta}{\lambda} {\delta}{\lambda}{\mu}\trivec{x}{y}{1} = 0. \] % If we now use barycentric coordinates $(x, y, z)$ (where $x + y + z = 1$), we can write %\medskip\noindent \[ \trivec{x}{y}{1} = \mattc{1}{0}{0}{0}{1}{0}{1}{1}{1}\trivec{x}{y}{z}. \] % Let % %\medskip \[ B = \mattc{\alpha}{\gamma}{\delta} {\gamma}{\beta}{\lambda} {\delta}{\lambda}{\mu},\quad C = \mattc{1}{0}{0}{0}{1}{0}{1}{1}{1},\quad X = \trivec{x}{y}{z}. \] % (a) Letting $A = \transpos{C}BC$, prove that the equation of the conic becomes \[\transpos{X}AX = 0.\] Prove that $A$ is symmetric, that $\det(A) = \det(B)$, and that $\transpos{X}AX$ is homogeneous of degree $2$. The equation $\transpos{X}AX = 0$ is called the {\it homogeneous equation\/} of the conic. \medskip We say that a conic of homogeneous equation $\transpos{X}AX = 0$ is {\it nondegenerate\/} if $\det(A) \not= 0$, and {\it degenerate\/} if $\det(A) = 0$. Show that this condition does not depend on the choice of the affine frame. \medskip (b) Given an affine frame $(A, B, C)$, prove that any conic passing through $A, B, C$ has an equation of the form \[a yz + b xz + c xy = 0.\] Prove that a conic containing more than one point is degenerate iff it contains three distinct collinear points. In this case, the conic is the union of two lines. \medskip (c) Prove {\it Pascal's Theorem\/}. Given any six distinct points $A, B, C$, $A', B'$, $C'$, if no three of the above points are collinear, then a nondegenerate conic passes through these six points iff the intersection points $M, N, P$ (in the sense of Problem B2) of the pairs of lines $(BC', CB')$, $(CA', AC')$ and $(AB', BA')$ are collinear in the sense of Problem B3. \medskip\noindent \hint Use the affine frame $(A, B, C)$, and let $(a, a', a'')$, $(b, b', b'')$, and $(c, c', c'')$ be the barycentric coordinates of $A', B', C'$ respectively, and show that $M, N, P$ have barycentric coordinates \[ (bc, cb', c''b),\quad (c'a, c'a', c''a'),\quad (ab'', a''b', a''b''). \] \vspace{0.5cm}\noindent {\bf Problem B5 (20 pts)}. (a) Let $E$ be an affine space over $\reals$, and let $\linvec{a}{n}$ be any $n\geq 3$ points in $E$. Let $\linvec{\lambda}{n}$ be any $n$ scalars in $\reals$, with $\lambda_1 + \cdots + \lambda_n = 1$. Show that there must be some $i$, $1\leq i\leq n$, such that $\lambda_i\not= 1$. To simplify the notation, assume that $\lambda_1\not= 1$. Show that the barycenter $\lambda_1 a_1 + \cdots + \lambda_n a_n$ can be obtained by first determining the barycenter $b$ of the $n-1$ points $a_2, \ldots, a_n$ assigned some appropriate weights, and then the barycenter of $a_1$ and $b$ assigned the weights $\lambda_1$ and $\lambda_2 + \cdots + \lambda_n$. From this, show that the barycenter of any $n\geq 3$ points can be determined by repeated computations of barycenters of two points. Deduce from the above that a nonempty subset $V$ of $E$ is an affine subspace iff whenever $V$ contains any two points $x, y\in V$, then $V$ contains the entire line $(1 -\lambda)x + \lambda y$, $\lambda\in \reals$. \medskip (b) Assume that $K$ is a field such that $2 = 1 + 1\not= 0$, and let $E$ be an affine space over $K$. In the case where $\lambda_1 + \cdots + \lambda_n = 1$ and $\lambda_i = 1$, for $1\leq i\leq n$ and $n\geq 3$, show that the barycenter $a_1 + a_2 + \cdots + a_n$ can still be computed by repeated computations of barycenters of two points. \medskip Finally, assume that the field $K$ contains at least three elements (thus, there is some $\mu\in K$ such that $\mu\not= 0$ and $\mu\not= 1$, but $2 = 1 + 1= 0$ is possible). Prove that the barycenter of any $n\geq 3$ points can be determined by repeated computations of barycenters of two points. Prove that a nonempty subset $V$ of $E$ is an affine subspace iff whenever $V$ contains any two points $x, y\in V$, then $V$ contains the entire line $(1 -\lambda)x + \lambda y$, $\lambda\in K$. \medskip \hint When $2 = 0$, $\lambda_1 + \cdots + \lambda_n = 1$ and $\lambda_i = 1$, for $1\leq i\leq n$, show that $n$ must be odd, and that the problem reduces to computing the barycenter of three points in two steps involving two barycenters. Since there is some $\mu\in K$ such that $\mu\not= 0$ and $\mu\not= 1$, note that $\mu^{-1}$ and $(1 - \mu)^{-1}$ both exist, and use the fact that \[\frac{-\mu}{1 - \mu} + \frac{1}{1 - \mu} = 1.\] \vspace{0.5cm}\noindent {\bf Problem B6 (30 pts)}. (i) Let $(a, b, c)$ be three points in $\affreal^2$, and assume that $(a, b, c)$ are not collinear. For any point $x\in \affreal^2$, if $x = \lambda_0 a + \lambda_1 b + \lambda_2 c$, where $(\lambda_0, \lambda_1, \lambda_2)$ are the barycentric coordinates of $x$ with respect to $(a, b, c)$, show that \[ \lambda_0 = \frac{\det(\libvecbo{x}{b}, \libvecbo{b}{c})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c})},\qquad \lambda_1 = \frac{\det(\libvecbo{a}{x}, \libvecbo{a}{c})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c})},\qquad \lambda_2 = \frac{\det(\libvecbo{a}{b}, \libvecbo{a}{x})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c})}. \] Conclude that $\lambda_0, \lambda_1, \lambda_2$ are certain signed ratios of the areas of the triangles $(a, b, c)$, $(x, a, b)$, $(x, a, c)$, and $(x, b, c)$. \medskip (ii) Let $(a, b, c)$ be three points in $\affreal^3$, and assume that $(a, b, c)$ are not collinear. For any point $x$ in the plane determined by $(a, b, c)$, if $x = \lambda_0 a + \lambda_1 b + \lambda_2 c$, where $(\lambda_0, \lambda_1, \lambda_2)$ are the barycentric coordinates of $x$ with respect to $(a, b, c)$, show that \[ \lambda_0 = \frac{\libvecbo{x}{b}\times\libvecbo{b}{c}} {\libvecbo{a}{b}\times\libvecbo{a}{c}},\qquad \lambda_1 = \frac{\libvecbo{a}{x}\times\libvecbo{a}{c}} {\libvecbo{a}{b}\times\libvecbo{a}{c}},\qquad \lambda_2 = \frac{\libvecbo{a}{b}\times\libvecbo{a}{x}} {\libvecbo{a}{b}\times\libvecbo{a}{c}}. \] Given any point $O$ not in the plane of the triangle $(a, b, c)$, prove that \[ \lambda_1 = \frac{\det(\libvecbo{O}{a}, \libvecbo{O}{x}, \libvecbo{O}{c})} {\det(\libvecbo{O}{a}, \libvecbo{O}{b}, \libvecbo{O}{c})},\quad \lambda_2 = \frac{\det(\libvecbo{O}{a}, \libvecbo{O}{b}, \libvecbo{O}{x})} {\det(\libvecbo{O}{a}, \libvecbo{O}{b}, \libvecbo{O}{c})}, \] and \[ \lambda_0 = \frac{\det(\libvecbo{O}{x}, \libvecbo{O}{b}, \libvecbo{O}{c})} {\det(\libvecbo{O}{a}, \libvecbo{O}{b}, \libvecbo{O}{c})}.\> \] \medskip (iii) Let $(a, b, c, d)$ be four points in $\affreal^3$, and assume that $(a, b, c, d)$ are not coplanar. For any point $x\in \affreal^3$, if $x = \lambda_0 a + \lambda_1 b + \lambda_2 c + \lambda_3 d$, where $(\lambda_0, \lambda_1, \lambda_2, \lambda_3)$ are the barycentric coordinates of $x$ with respect to $(a, b, c, d)$, show that \[ \lambda_1 = \frac{\det(\libvecbo{a}{x}, \libvecbo{a}{c}, \libvecbo{a}{d})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{d})},\>\> \lambda_2 = \frac{\det(\libvecbo{a}{b}, \libvecbo{a}{x}, \libvecbo{a}{d})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{d})},\>\> \lambda_3 = \frac{\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{x})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{d})}, \] and \[ \lambda_0 = \frac{\det(\libvecbo{x}{b}, \libvecbo{b}{c}, \libvecbo{b}{d})} {\det(\libvecbo{a}{b}, \libvecbo{a}{c}, \libvecbo{a}{d})}. \] Conclude that $\lambda_0, \lambda_1, \lambda_2, \lambda_3$ are certain signed ratios of the volumes of the five tetrahedra $(a, b, c, d)$, $(x, a, b, c)$, $(x, a, b, d)$, $(x, a, c, d)$, and $(x, b, c, d)$. \medskip (iv) Let $(a_0, \ldots, a_\mdeg)$ be $\mdeg + 1$ points in $\affreal^\mdeg$, and assume that they are affinely independent. For any point $x\in \affreal^\mdeg$, if $x = \lambda_0 a_0 + \cdots + \lambda_\mdeg a_\mdeg$, where $(\lambda_0, \ldots, \lambda_\mdeg)$ are the barycentric coordinates of $x$ with respect to $(a_0, \ldots, a_\mdeg)$, show that \[ \lambda_i = \frac{\det(\libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_{i-1}}, \libvecbo{a_0}{x}, \libvecbo{a_0}{a_{i+1}}, \ldots, \libvecbo{a_0}{a_{\mdeg}})} {\det(\libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_{i-1}}, \libvecbo{a_0}{a_i}, \libvecbo{a_0}{a_{i+1}}, \ldots, \libvecbo{a_0}{a_{\mdeg}})} \] for every $i$, $1\leq i \leq \mdeg$, and \[ \lambda_0 = \frac{\det(\libvecbo{x}{a_1},\libvecbo{a_1}{a_{2}}, \ldots, \libvecbo{a_1}{a_{\mdeg}})} {\det(\libvecbo{a_0}{a_1}, \ldots, \libvecbo{a_0}{a_i}, \ldots, \libvecbo{a_0}{a_{\mdeg}})}. \] Conclude that $\lambda_i$ is the signed ratio of the volumes of the simplexes $(a_0, \ldots$, $x, \ldots a_\mdeg)$ and $(a_0, \ldots, a_i, \ldots a_\mdeg)$, where $0\leq i \leq \mdeg$. \vspace{0.5cm}\noindent {\bf Problem B7 (20 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 B8 (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: 260 points.} \end{document} \vspace{0.5cm}\noindent {\bf Problem B6 (40 pts)}. Let $A$ be a nonempty convex subset of $\affreal^n$. A function $\mapdef{f}{A}{\reals}$ is {\it convex\/} if \[f((1 - \lambda)a + \lambda b) \leq (1 - \lambda) f(a) + \lambda f(b)\] for all $a, b \in A$ and for all $\lambda \in [0, 1]$. \medskip (a) If $f$ is convex, prove that \[f\biggl(\sum_{i\in I} \lambda_i a_i\biggr) \leq \sum_{i\in I} \lambda_i f(a_i)\] for every finite convex combination in $A$, i.e., any finite family $(a_i)_{i\in I}$ of points in $A$ and any family $(\lambda_i)_{i\in I}$ with $\sum_{i \in I} \lambda_i = 1$ and $\lambda_i \geq 0$ for all $i\in I$. \medskip (b) Let $\mapdef{f}{A}{\reals}$ be a convex function and assume that $A$ is convex and compact and that $f$ is continuous. Prove that $f$ achieves its maximum in some extremal point of $A$. \vspace{0.5cm}\noindent {\bf Problem B7 (100 pts)}. (a) Let $A$ be any subset of $\affreal^n$. Prove that if $A$ is compact, then its convex hull $\s{C}(A)$ is also compact. \medskip (b) Give a proof of the following version of Helly's theorem using Corollary 1.10 of the notes on convex sets (Convex sets: A deeper look): \medskip\noindent {\em Given any affine space $E$ of dimension $\mdeg$, for every family $\{K_1, \ldots, K_n\}$ of $n$ convex and compact subsets of $E$, if $n\geq \mdeg + 2$ and the intersection $\bigcap_{i \in I} K_i$ of any $\mdeg + 1$ of the $K_i$ is nonempty (where $I\subseteq \{1, \ldots, n\}$, $|I| = \mdeg + 1$), then $\bigcap_{i = 1}^{n} K_i$ is nonempty.} \medskip\noindent {\it Hint\/}: First, prove that the general case can be reduced to the case where $n = m + 2$. \medskip (c) Use (b) to prove Helly's theorem without the assumption that the $K_i$ are compact. \medskip\noindent You will need to construct some nonempty compacts $C_i \subseteq K_i$. For this, you will need to prove that the convex hull of finitely many points is compact. \medskip (d) Prove that Helly's theorem holds even if the family $(K_i)_{I\in I}$ is infinite, provided that the $K_i$ are convex and compact.