\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 2}\\[10pt]
February 20, 2006; Due March 13, 2006\\
\end{center}

``A problems'' are for practice only, and should not
be turned in.


\vspace {0.5cm}\noindent
{\bf Problem A1.} 
Let $\lbasis{e}{n}$ be an orthonormal basis for $E$.
If $X$ and $Y$ are arbitrary $n\times n$ matrices, 
denoting as usual the $j$th column of $X$ by $X_j$, and similarly
for $Y$, show that
\[\transpos{X}Y = (\dotprod{X_i}{Y_j})_{1\leq i, j\leq n}.\]
Use this to prove that
\[\transpos{A}A = A\,\transpos{A} = I_n\] iff
the column vectors $(A_1,\ldots,A_n)$ form an orthonormal basis.
Show that the conditions
$A\,\transpos{A} = I_n$, $\transpos{A}A = I_n$, and
$A^{-1} = \transpos{A}$ are equivalent.

\vspace{0.5cm}\noindent
{\bf Problem A2}. 
Compute the real Fourier coefficients
of the function $id(x) = x$ 
over $[-\pi, \pi]$ and prove that
%
\[x = 2\left(\frac{\sin x}{1} -  \frac{\sin 2x}{2} + 
\frac{\sin 3x}{3} - \cdots \right).\]

\medskip
What is the value of the Fourier series at $\pm\pi$?
What is the value of the Fourier near $\pm\pi$?
Do you find this surprising?

\vspace{0.5cm}\noindent
{\bf Problem A3}. 
Prove Lemma 6.2.2 from my book.

\vspace {0.5cm}
``B problems'' must be turned in.

\vspace {0.5cm}\noindent
{\bf Problem B1 (30 pts).} 
(a)
Prove that the dual $C^*$ of the cube $C = [-1, 1]^n$
is the convex hull of the $2n$ points
$\{e_i, -e_i\mid 1\leq i \leq n\}$, where
$e_i = (0, \ldots, 0, 1, 0, \ldots, 0)$, the $ith$
vector in the standard basis.
The dual of a cube is called a {\it cross-polytope\/}.
Check that the cube $C$ has $2^n$ vertices and $2n$ faces,
whereas its dual $C^*$ has $2n$ vertices and $2^n$ faces.
Draw $C^*$ for $n = 3$.


\medskip
What is the dual of an $n$-simplex?

\medskip
(b)
Consider in $\eucreal^3$ the polyhedron $I$ defined
as follows. If $\tau = (\sqrt{5} + 1)/2$, then
the vertices of $I$ are the twelve points 
\[
(0,\> \pm\tau,\> \pm 1),\quad
(\pm 1,\> 0,\> \pm\tau),\quad
(\pm\tau,\> \pm 1,\> 0).
\]
This polyhedron is called an {\it icosahedron\/}.
Check that the icosahedron has $20$ faces.
Draw an icosahedron (or better, make a cardboard model).

\medskip
Prove that the dual $D$ of the icosahedron is
a convex polyhedron whose twenty vertices are
\[
(\pm 1,\> \pm 1,\> \pm 1),\quad
(0,\> \pm 1/\tau,\> \pm\tau),\quad
(\pm\tau,\> 0,\> \pm 1/\tau),\quad
(\pm 1/\tau,\> \pm\tau,\> 0).
\]
This polyhedron $D$ is called a {\it dodecahedron\/}.
Observe that it is ``built up'' on the cube
$[-1, 1]^3$. Can you explain how?
Check that the dodecahedron has $12$ faces.
Draw a dodecahedron (or better, make a cardboard model).


\vspace{0.5cm}\noindent
{\bf Problem B2 (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 B3 (30 pts)}. 
Let $\mapdef{\varphi}{E\times E}{\reals}$
be a bilinear form on a real vector space $E$
of finite dimension $n$. Given any basis
$(\novect{e_1}, \ldots, \novect{e_n})$ of $E$, let 
$A = (\alpha_{i\, j})$ be the matrix defined such that
\[\alpha_{i\, j} = \varphi(\novect{e_i}, \novect{e_j}),\]
$1\leq i, j \leq n$. We call $A$ {\it the matrix of $\varphi$
w.r.t. the basis $(\novect{e_1}, \ldots, \novect{e_n})$\/}.

\medskip
(a) 
For any two vectors $\novect{x}$ and
$\novect{y}$, if $X$ and $Y$ denote the column vectors
of coordinates of $\novect{x}$ and $\novect{y}$ w.r.t.
the basis $(\novect{e_1}, \ldots, \novect{e_n})$, 
prove that
\[\varphi(\novect{x}, \novect{y}) = \transpos{X} A Y.\]

\medskip
(b) Recall that $A$ is a {\it symmetric\/} matrix if
$A =  \transpos{A}$.
Prove that $\varphi$ is symmetric if $A$ is a symmetric matrix.

\medskip
(c) If $(\novect{f_1}, \ldots, \novect{f_n})$ is another basis
of $E$ and $P$ is the change of basis matrix from
$(\novect{e_1}, \ldots, \novect{e_n})$ to 
$(\novect{f_1}, \ldots, \novect{f_n})$, prove that the matrix
of $\varphi$ w.r.t. the basis 
$(\novect{f_1}, \ldots, \novect{f_n})$ is
\[\transpos{P}A P.\]
The common rank of all matrices representing $\varphi$ is called
the {\it rank\/} of $\varphi$.

\vspace{0.5cm}\noindent
{\bf Problem B4 (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.


\vspace {0.5cm}\noindent
{\bf Problem B5 (30 pts).} 
In $\eucreal^3$, consider the closed convex set (cone), $A$, defined
by the inequalities
\[
x\geq 0,\quad y\geq 0,\quad z\geq 0, \quad z^2 \leq xy,
\]
and let $D$ be the line given by
$x = 0, z = 1$. Prove that $D \cap A = \emptyset$, both $A$ and $D$ are convex
and closed, yet every plane containing $D$ meets $A$.
Therefore, $A$ and $D$ give another counter-example to the Hahn-Banach
theorem where $A$ is closed
(one cannot relax the hypothesis that $A$ is open).


\vspace{0.5cm}\noindent
{\bf Problem B6 (50 pts)}. 
(a)
Let $C$ be a circle of radius $R$ and center $O$, 
and let $P$ be any point 
in the Euclidean plane $\eucreal^2$.
Consider the lines $\Delta$ through $P$ that intersect the circle
$C$, generally in two points $A$ and $B$.
Prove that for all such lines,
\[\libvecbo{P}{A}\cdot \libvecbo{P}{B} = \smnorme{\libvecbo{P}{O}}^2 - R^2.\]

\hint If $P$ is not on $C$,
let $B'$ be the antipodal of $B$ (i.e., 
$\libvecbo{O}{B'} = - \libvecbo{O}{B}$). 
Then $\libvecbo{A}{B}\cdot \libvecbo{A}{B'} = 0$ and
\[\libvecbo{P}{A}\cdot \libvecbo{P}{B} = \libvecbo{P}{B'}\cdot \libvecbo{P}{B} = 
(\libvecbo{P}{O} - \libvecbo{O}{B})\cdot (\libvecbo{P}{O} + \libvecbo{O}{B})
= \smnorme{\libvecbo{P}{O}}^2 - R^2.\]

%\medskip
The quantity $\smnorme{\libvecbo{P}{O}}^2 - R^2$ is called
the {\it power of $P$ w.r.t. $C$\/}, and it is denoted
by $\s{P}(P, C)$. 
\index{power of $P$ w.r.t. $C$}%
\indsym{\s{P}(P, C)}{power of $P$ w.r.t. $C$}%

%\medskip
Show that if $\Delta$ is tangent to $C$, then
$A = B$ and 
\[\smnorme{\libvecbo{P}{A}}^2 = \smnorme{\libvecbo{P}{O}}^2 - R^2.\]

%\medskip
Show that $P$ is inside $C$ iff  $\s{P}(P, C) < 0$,
on $C$ iff  $\s{P}(P, C) = 0$,  outside $C$ if
$\s{P}(P, C) > 0$.

%\medskip
If the equation of $C$ is
\[x^2 + y^2 -2ax -2by + c = 0,\]
prove that the power of $P = (x, y)$ w.r.t. $C$ is given by
\[\s{P}(P, C) = x^2 + y^2 -2ax -2by + c.\]

%\medskip
(b)
Given two nonconcentric circles $C$ and $C'$, show that the set of points
having equal power w.r.t. $C$ and $C'$ is a line
orthogonal to the line through the centers of $C$ and $C'$.
If the equations of $C$ and $C'$ are
\[x^2 + y^2 -2ax -2by + c = 0\quad\hbox{and}\quad 
x^2 + y^2 -2a'x -2b'y + c' = 0,\]
show that the equation of this line is
\[2(a - a')x + 2(b - b')y + c' - c = 0.\]
This line is called the {\it radical axis\/} of $C$ and $C'$.
\index{radical axis}%

%\medskip
(c) 
Given three distinct nonconcentric circles $C$, $C'$, and $C''$,
prove that either the three pairwise radical axes of these circles
are parallel or that they intersect in a single point $\omega$
that has equal power w.r.t. $C$, $C'$, and $C''$.
In the first case, the centers of $C$, $C'$, and $C''$
are collinear. 
In the second case, if the power of $\omega$ is positive,
prove that $\omega$ is the center
of a circle $\Gamma$ orthogonal to $C$, $C'$, and $C''$,
and if the power of $\omega$ is negative, $\omega$ is inside
$C$, $C'$, and $C''$.

%\medskip
(d)
Given any $k\in\reals$ with $k\not= 0$ and any point $a$,
recall that an {\it inversion of pole $a$ and power $k$\/} is a map 
$\mapdef{h}{(\eucreal^n-\{a\})}{\eucreal^n}$
defined such that for every $x\in \eucreal^n - \{a\}$,
\[h(x) = a + k\frac{\libvecbo{a}{x}}{\smnorme{\libvecbo{a}{x}}^2}.\]
For example, when $n = 2$, chosing any orthonormal frame with 
origin $a$, $h$ is defined by the map
\[(x,\, y) \mapsto \left(\frac{kx}{x^2  + y^2},\, \frac{ky}{x^2  + y^2}\right).\] 
When the centers of $C$, $C'$ and $C''$ are not collinear
and the power of $\omega$ is positive, prove that
by a suitable inversion, $C$, $C'$ and $C''$ are mapped
to three circles whose centers are collinear.

%\medskip
Prove that if three distinct 
nonconcentric circles $C$, $C'$, and $C''$ have collinear centers,
then there are at most eight circles simultaneously tangent 
to $C$, $C'$, and $C''$, and at most two for those
exterior to $C$, $C'$, and $C''$.

%\medskip
(e)
Prove that an inversion in $\eucreal^3$ maps 
a sphere to a sphere or to a plane. \index{inversion}%
Prove that inversions preserve tangency and orthogonality
of planes and spheres.




\vspace{0.5cm}\noindent
{\bf TOTAL: 280 points.}

\end{document}