\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\mbg#1#2{\mathbf{#1}(#2)} \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, 2004 \hspace*{0.4cm} CIS 700-05}}\\ \vspace{1cm} {Special Topics in Machine Perception\\ \vspace{0.5cm} Homework 1}\\[10pt] February 27, 2004; Due March 26\\ \end{center} You may work in groups of 2 or 3. Please, write up your solutions as clearly and concisely as possible. Be rigorous! You will have to present your solutions of the problems during a special problem session. \vspace {0.5cm}\noindent {\bf Problem B1 (20).} (a) If $K = \reals$ or $K = \complex$, recall that the projective space, $\projs{K^{n+1}}$, is the set of equivalence classes of the equivalence relation, $\sim$, on $K^{n + 1} - \{0\}$, defined so that, for all $u, v \in K^{n + 1} - \{0\}$, \[ u \sim v\quad\hbox{iff}\quad v = \lambda u, \quad\hbox{for some}\quad\lambda \in K - \{0\}. \] The map, $\mapdef{p}{(K^{n+1} - \{0\})}{\projs{K^{n+1}}}$, is the projection mapping any nonzero vector in $K^{n+1}$ to its equivalence class modulo $\sim$. We let $\rprospac{n} = \projs{\reals^{n+1}}$ and $\cprospac{n} = \projs{\complex^{n+1}}$. \medskip Prove that for any $n\geq 0$, there is a bijection between $\projs{K^{n+1}}$ and $K^{n} \cup \projs{K^{n}}$ (which allows us to identify them). \medskip (b) Prove that $\rprospac{n}$ and $\cprospac{n}$ are connected and compact. \medskip \hint If \[S^n = \{(x_1,\ldots,x_{n+1})\in K^{n+1}\ |\ x_1^2 + \cdots + x_{n+1}^2 = 1\},\] prove that $p(S^n) = \projs{K^{n+1}}$, and recall that $S^n$ is compact for all $n\geq 0$ and connected for $n\geq 1$. For $n = 0$, $\projs{K}$ consists of a single point. \vspace {0.25cm}\noindent {\bf Problem B2 (20).} Recall that $\reals^2$ and $\complex$ can be identified using the bijection $(x, y) \mapsto x + iy$. Also recall that the subset $U(1)\subseteq \complex$ consisting of all complex numbers of the form $\cos\theta + i\sin\theta$ is homeomorphic to the circle $S^1 = \{(x, y)\in \reals^2\ |\ x^2 + y^2 = 1\}$. If $\mapdef{c}{U(1)}{U(1)}$ is the map defined such that \[c(z) = z^2,\] prove that $c(z_1) = c(z_2)$ iff either $z_2 = z_1$ or $z_2 = -z_1$, and thus that $c$ induces a bijective map $\mapdef{\hli{c}}{\rprospac{1}}{S^1}$. Prove that $\hli{c}$ is a homeomorphism (remember that $\rprospac{1}$ is compact). \vspace {0.25cm}\noindent {\bf Problem B3 (40).} \label{pb5.3} (i) In $\reals^3$, the sphere $S^2$ is the set of points of coordinates $(x, y, z)$ such that $x^2 + y^ 2 + z^2 = 1$. The point $N = (0, 0, 1)$ is called the {\it north pole\/}, and the point $S = (0, 0, -1)$ is called the {\it south pole\/}. The {\it stereographic projection map\/} $\mapdef{\sigma_N}{(S^2 - \{N\})}{\reals^2}$ is defined as follows: For every point $M\not= N$ on $S^2$, the point $\sigma_N(M)$ is the intersection of the line through $N$ and $M$ and the plane of equation $z = 0$. Show that if $M$ has coordinates $(x, y, z)$ (with $x^2 + y^2 + z^2 = 1$), then \[\sigma_N(M) = \biggl(\frac{x}{1 - z},\, \frac{y}{1 - z}\biggr).\] Prove that $\sigma_N$ is bijective and that its inverse is given by the map $\mapdef{\tau_N}{\reals^2}{(S^2 - \{N\})}$, with \[(x, y) \mapsto \biggl(\frac{2x}{x^2 + y^2 + 1},\, \frac{2y}{x^2 + y^2 + 1},\, \frac{x^2 + y^2 - 1}{x^2 + y^2 + 1}\biggr).\] Similarly, $\mapdef{\sigma_S}{(S^2 - \{S\})}{\reals^2}$ is defined as follows: For every point $M\not= S$ on $S^2$, the point $\sigma_S(M)$ is the intersection of the line through $S$ and $M$ and the plane of equation $z = 0$. Show that \[\sigma_S(M) = \biggl(\frac{x}{1 + z},\, \frac{y}{1 + z}\biggr).\] Prove that $\sigma_S$ is bijective and that its inverse is given by the map $\mapdef{\tau_S}{\reals^2}{(S^2 - \{S\})}$, with \[(x, y) \mapsto \biggl(\frac{2x}{x^2 + y^2 + 1},\, \frac{2y}{x^2 + y^2 + 1},\, \frac{1 - x^2 - y^2}{x^2 + y^2 + 1}\biggr).\] \medskip Using the complex number $u = x + i y$ to represent the point $(x, y)$, the maps $\mapdef{\tau_N}{\reals^2}{(S^2 - \{N\})}$ and $\mapdef{\sigma_N}{(S^2 - \{N\})}{\reals^2}$ can be viewed as maps from $\complex$ to $(S^2 - \{N\})$ and from $(S^2 - \{N\})$ to $\complex$, defined such that \[\tau_N(u) = \biggl(\frac{2u}{|u|^2 + 1},\, \frac{|u|^2 - 1}{|u|^2 + 1}\biggr)\] and \[\sigma_N(u, z) = \frac{u}{1 - z},\] and similarly for $\tau_S$ and $\sigma_S$. Prove that if we pick two suitable orientations for the $xy$-plane, we have \[\sigma_N(M)\sigma_S(M) = 1,\] for every $M \in S^2 - \{N, S\}$. \medskip (ii) Identifying $\complex^2$ and $\reals^4$, for $z = x + i y$ and $z' = x' + i y'$, we define \[\smnorme{(z, z')} = \sqrt{x^2 + y^2 + x'^2 + y'^2}.\] The sphere $S^3$ is the subset of $\complex^2$ (or $\reals^4$) consisting of those points $(z, z')$ such that $\smnorme{(z, z')}^2 = 1$. \medskip Prove that $\projs{\complex^2} = p(S^3)$, where $\mapdef{p}{(\complex^2 - \{(0, 0)\})}{\projs{\complex^2}}$ is the projection map. If we let $u = z/z'$ (where $z, z'\in \complex$) in the map \[u \mapsto \biggl(\frac{2u}{|u|^2 + 1},\, \frac{|u|^2 - 1}{|u|^2 + 1}\biggr)\] and require that $\smnorme{(z, z')}^2 = 1$, show that we get the map $\mapdef{HF}{S^3}{S^2}$ defined such that \[HF((z, z')) = (2 z\overline{z'},\, |z|^2 - |z'|^2).\] Prove that $\mapdef{HF}{S^3}{S^2}$ induces a bijection $\mapdef{\hli{HF}}{\projs{\complex^2}}{S^2}$, and thus that $\cprospac{1} = \projs{\complex^2}$ is homeomorphic to $S^2$. \medskip (iii) Prove that the inverse image $HF^{-1}(s)$ of every point $s\in S^2$ is a circle. Thus $S^3$ can be viewed as a union of disjoint circles. The map $HF$ is called the {\it Hopf fibration\/}. \vspace {0.25cm}\noindent {\bf Problem B4 (60).} (a) Consider the map $\mapdef{\s{H}}{\reals^3}{\reals^4}$ defined such that \[(x, y, z) \mapsto (xy, yz, xz, x^2 - y^2).\] Prove that when it is restricted to the sphere $S^2$ (in $\reals^3$), we have $\s{H}(x, y, z) = \s{H}(x', y', z')$ iff $(x', y', z') = (x, y, z)$ or $(x', y', z') = (-x, -y, -z)$. In other words, the inverse image of every point in $\s{H}(S^2)$ consists of two antipodal points. \medskip Prove that the map $\s{H}$ induces an injective map from the projective plane onto $\s{H}(S^2)$, and that it is a homeomorphism. \medskip (b) The map $\s{H}$ allows us to realize concretely the projective plane in $\reals^4$ as an embedded manifold. Consider the three maps from $\reals^2$ to $\reals^4$ given by \begin{eqnarray*} \psi_1(u, v) & = & \left( \frac{uv}{u^2 + v^2 + 1}, \frac{u}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1}, \frac{u^2 - v^2}{u^2 + v^2 + 1} \right), \\ \psi_2(u, v) & = & \left( \frac{u}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1}, \frac{uv}{u^2 + v^2 + 1}, \frac{u^2 - 1}{u^2 + v^2 + 1} \right), \\ \psi_3(u, v) & = & \left( \frac{u}{u^2 + v^2 + 1}, \frac{uv}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1}, \frac{1 - u^2}{u^2 + v^2 + 1} \right). \end{eqnarray*} % Observe that $\psi_1$ is the composition $\s{H} \circ \alpha_1$, where $\alpha_1\co \reals^2 \longrightarrow S^2$ is given by \[ (u, v) \mapsto \left(\frac{u}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1}, \frac{1}{u^2 + v^2 + 1} \right), \] that $\psi_2$ is the composition $\s{H} \circ \alpha_2$, where $\alpha_2\co \reals^2 \longrightarrow S^2$ is given by \[ (u, v) \mapsto \left(\frac{u}{u^2 + v^2 + 1}, \frac{1}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1} \right). \] and $\psi_3$ is the composition $\s{H} \circ \alpha_3$, where $\alpha_3\co \reals^2 \longrightarrow S^2$ is given by \[ (u, v) \mapsto \left(\frac{1}{u^2 + v^2 + 1}, \frac{u}{u^2 + v^2 + 1}, \frac{v}{u^2 + v^2 + 1} \right), \] Prove that each $\psi_i$ is injective, continuous and nonsingular (i.e., the Jacobian is never zero). \medskip Prove that $\psi_i(\reals^2)$ is an open subset, $U_i$, of $\s{H}(S^2)$ for $i = 1, 2, 3$ and that the union of the $U_i$'s covers $\s{H}(S^2)$. \medskip Prove that each $\mapdef{\psi_i^{-1}}{U_i}{\reals^2}$ is continuous. This is a little tricky. For example, for $\psi_1$, first prove that if the coordinates in $\reals^4$ are $(x, y, z, t)$, then \[ yzt = x(y^2 - z^2). \] Then, $\psi_1^{-1}$ is defined as follows: If $y\not= 0$ and $z \not= 0$, \[ u = \frac{x}{z} = \frac{yt}{y^2 - z^2}, \quad v = \frac{x}{y} = \frac{zt}{y^2 - z^2}. \] If $y = 0$ and $z \not= 0$, then \[ u = 0, \quad v = -\frac{t}{z}, \] if $y\not= 0$ and $z = 0$, then \[ u = \frac{t}{y}\quad v = 0, \] and if $y = z = 0$, then \[ u = 0,\quad v = 0. \] Finally, you have to show continuity of the above functions, and do a similar thing for $\psi_2^{-1}$ and $\psi_3^{-1}$. \medskip Conclude that $\psi_1, \psi_2, \psi_3$ are parametrizations of $\rprospac{2}$ as a manifold in $\reals^4$. \medskip (c) Investigate the surfaces in $\reals^3$ obtained by dropping one of the four coordinates. Show that there are only two of them (the ``Steiner Roman surface'' and the ``crosscap'', up to a rigid motion). \vspace {0.25cm}\noindent {\bf Problem B5 (30).} (i) Prove that the {\it Veronese map\/} $\mapdef{V_2}{\reals^3}{\reals^6}$ defined such that \[V_2(x, y, z) = (x^2,\, y^2,\, z^2,\, yz,\, zx,\, xy)\] induces a homeomorphism of $\rprospac{2}$ onto $V_2(S^2)$. Show that $V_2(S^2)$ is a subset of the hyperplane $x_1 + x_2 + x_3 = 1$ in $\reals^6$, and thus that $\rprospac{2}$ is homeomorphic to a subset of $\reals^5$. Prove that this homeomorphism is smooth. \medskip (ii) Prove that the {\it Veronese map\/} $\mapdef{V_3}{\reals^4}{\reals^{10}}$ defined such that \[V_3(x, y, z, t) = (x^2,\, y^2,\, z^2,\, t^2,\, xy,\, yz,\, xz,\, xt,\, yt,\, zt)\] induces a homeomorphism of $\rprospac{3}$ onto $V_3(S^3)$. Show that $V_3(S^3)$ is a subset of the hyperplane $x_1 + x_2 + x_3 + x_4 = 1$ in $\reals^{10}$, and thus that $\rprospac{3}$ is homeomorphic to a subset of $\reals^9$. Prove that this homeomorphism is smooth. \vspace {0.25cm}\noindent {\bf Problem B6 (20 pts).} Given any matrix \[ B = \matta{a}{b}{c}{-a}\in \mfrac{sl}(2, \complex), \] if $\omega^2 = a^2 + bc$ and $\omega$ is any of the two complex roots of $a^2 + bc$, prove that if $\omega\not= 0$, then \[ e^B = \cosh \omega\, I + \frac{\sinh\, \omega}{\omega}\, B, \] and $e^B = I + B$, if $a^2 + bc = 0$. Observe that $\mathrm{tr}(e^B) = 2\cosh\,\omega$. \medskip Prove that the exponential map, $\mapdef{\exp}{\mfrac{sl}(2, \complex)}{\mathbf{SL}(2, \complex)}$, is {\it not\/} surjective. For instance, prove that \[ \matta{-1}{1}{0}{-1} \] is not the exponential of any matrix in $\mfrac{sl}(2, \complex)$. \vspace {0.25cm}\noindent {\bf Problem B7 (10 pts).} Prove that the kernel of the homomorphism, \\ $\mapdef{\varphi}{\mathbf{SL}(2, \complex)}{{\bf SO}_0(1, 3)}$, given on page 26 of the notes on Group actions, Manifolds, etc., is indeed $\{-I, I\}$. \vspace {0.25cm}\noindent {\bf Problem B8 (20 pts).} Prove that $\mbg{GL}{n, \complex}$, $\mbg{SL}{n, \complex}$, $\mbg{SL}{n, \reals}$, $\mbg{U}{n}$, $\mbg{SU}{n}$ and $\mbg{SO}{n}$ and are arcwise-connected if $n \geq 1$. What about $\mbg{GL}{n, \reals}$ and $\mbg{O}{n}$? \hint Use the polar form and/or various exponential maps. \vspace {0.25cm}\noindent {\bf Problem B9 (50 pts).} Let $A$ and $B$ be the following $4\times 4$-matrices: \medskip $$ A = \pmatrice{ 0 & -\theta_1 & 0 & 0 \cr \theta_1 & 0 & 0 & 0 \cr 0 & 0 & 0 & -\theta_2 \cr 0 & 0 & \theta_2 & 0 \cr } \qquad B = \pmatrice{ \cos\theta_1 & -\sin\theta_1 & 0 & 0 \cr \sin\theta_1 & \cos\theta_1 & 0 & 0 \cr 0 & 0 & \cos\theta_2 & -\sin\theta_2 \cr 0 & 0 & \sin\theta_2 & \cos\theta_2 \cr } $$ \medskip\noindent where $\theta_1, \theta_2 \geq 0$. \medskip (i) Compute $A^2$, and prove that $$B = e^A,$$ where $$e^A = I_n + \sum_{p\geq 1} \frac{A^{p}}{p!} = \sum_{p\geq 0} \frac{A^{p}}{p!},$$ letting $A^0 = I_n$. Use this to prove that for every orthogonal $4\times 4$-matrix $B$, there is a skew symmetric matrix $A$ such that $$B = e^A.$$ \medskip (ii) Given a skew-symmetric $4\times 4$-matrix $A$, prove that there are two skew symmetric matrices $A_1$ and $A_2$ and some $\theta_1, \theta_2 \geq 0$, such that $$\eqaligneno{ A &= A_1 + A_2,\cr A_1^3 &= -\theta_1^2 A_1,\cr A_2^3 &= -\theta_2^2 A_2,\cr A_1A_2 &= A_2A_1 = 0,\cr tr(A_1^2) &= -2\theta_1^2,\cr tr(A_2^2) &= -2\theta_2^2,\cr }$$ and where $A_i = 0$ if $\theta_i = 0$ and $A_1^2 + A_2^2 = -\theta_1^2 I_4$ if $\theta_2 = \theta_1$. Using the above, prove that $$e^A = I_4 + \frac{\sin\theta_1}{\theta_1} A_1 + \frac{\sin\theta_2}{\theta_2} A_2 + \frac{(1 - \cos\theta_1)}{\theta_1^2} A_1^2 + \frac{(1 - \cos\theta_2)}{\theta_2^2} A_2^2.$$ \medskip (iii) Given an orthogonal $4\times 4$-matrix $B$, prove that there are two skew symmetric matrices $A_1$ and $A_2$ and some $\theta_1, \theta_2 \geq 0$, such that $$B = I_4 + \frac{\sin\theta_1}{\theta_1} A_1 + \frac{\sin\theta_2}{\theta_2} A_2 + \frac{(1 - \cos\theta_1)}{\theta_1^2} A_1^2 + \frac{(1 - \cos\theta_2)}{\theta_2^2} A_2^2.$$ where $$\eqaligneno{ A_1^3 &= -\theta_1^2 A_1,\cr A_2^3 &= -\theta_2^2 A_2,\cr A_1A_2 &= A_2A_1 = 0,\cr tr(A_1^2) &= -2\theta_1^2,\cr tr(A_2^2) &= -2\theta_2^2,\cr }$$ and where $A_i = 0$ if $\theta_i = 0$ and $A_1^2 + A_2^2 = -\theta_1^2 I_4$ if $\theta_2 = \theta_1$. Prove that $$\eqaligneno{ 1/2(B - \transpos{B}) &= \frac{\sin\theta_1}{\theta_1} A_1 + \frac{\sin\theta_2}{\theta_2} A_2,\cr 1/2(B + \transpos{B}) &= I_4 + \frac{(1 - \cos\theta_1)}{\theta_1^2} A_1^2 + \frac{(1 - \cos\theta_2)}{\theta_2^2} A_2^2,\cr tr(B) &= 2\cos\theta_1 + 2\cos\theta_2.\cr }$$ \medskip (iv) Prove that if $\sin\theta_1 = 0$ or $\sin\theta_2 = 0$, then $A_1, A_2$ and the $\cos\theta_i$ can be computed from $B$. Prove that if $\theta_2 = \theta_1$, then $$B = \cos\theta_1 I_4 + \frac{\sin\theta_1}{\theta_1} (A_1 + A_2),$$ and $\cos\theta_1$ and $A_1 + A_2$ can be computed from $B$. \medskip (v) Prove that $$\frac{1}{4} tr((B - \transpos{B})^2) = 2\cos^2\theta_1 + 2\cos^2\theta_2 - 4.$$ Prove that $\cos\theta_1$ and $\cos\theta_2$ are solutions of the equation $$x^2 - sx + p = 0,$$ where $$s = \frac{1}{2} tr(B),\quad p = \frac{1}{8} \left(tr(B)\right)^2 -\frac{1}{16} tr((B - \transpos{B})^2) - 1.$$ \medskip Prove that we also have $$\cos^2\theta_1\cos^2\theta_2 = \det\left(1/2(B + \transpos{B})\right).$$ \medskip If $\sin\theta_i\not= 0$ for $i = 1, 2$ and $\cos\theta_2 \not= \cos\theta_1$, prove that the system $$\eqaligneno{ 1/2(B - \transpos{B}) &= \frac{\sin\theta_1}{\theta_1} A_1 + \frac{\sin\theta_2}{\theta_2} A_2,\cr 1/4(B + \transpos{B})(B - \transpos{B}) &= \frac{\sin\theta_1\cos\theta_1}{\theta_1} A_1 + \frac{\sin\theta_2\cos\theta_2}{\theta_2} A_2,\cr }$$ has a unique solution for $A_1$ and $A_2$. \medskip (vi) Prove that $A = A_1 + A_2$ has an orthonormal basis of eigenvectors such that the first two are a basis of the plane w.r.t. which $B$ is a rotation of angle $\theta_1$, and the last two are a basis of the plane w.r.t. which $B$ is a rotation of angle $\theta_2$. \medskip {\it Remark\/}: I don't know a simple way to compute such an orthonormal basis of eigenvectors of $A = A_1 + A_2$, but it should be possible! \vspace{0.5cm}\noindent {\bf TOTAL: 270 points.} \end{document} \vspace {0.5cm}\noindent {\bf Problem B8 (50 pts).} The motion of a rigid body in space can be described using rigid motions. Given a fixed Euclidean frame $(O, (\novect{e_1}, \novect{e_2}, \novect{e_3}))$, we can assume that some moving frame $(C, (\novect{u_1}, \novect{u_2}, \novect{u_3}))$ is attached (say glued) to a rigid body $B$ (for example, at the center of gravity of $B$) so that the position and orientation of $B$ in space is completely (and uniquely) determined by some rigid motion $(R, U)$, where $U$ specifies the position of $C$ w.r.t. $O$, and $R$ is a rotation matrix specifying the orientation of $B$ w.r.t. the fixed frame $(O, (\novect{e_1}, \novect{e_2}, \novect{e_3}))$. For simplicity, we can separate the motion of the center of gravity $C$ of $B$ from the rotation of $B$ around its center of gravity. Then, a motion of $B$ in space corresponds to two curves, the trajectory of the center of gravity, and a curve in $\mSO{3}$ representing the various orientations of $B$. Given a sequence of ``snapshots'' of $B$, say $B_0, B_1, \ldots, B_m$, we may want to find an interpolating motion passing through the given snapshots. \medskip Assuming that a rigid body $B$ (say, a square box) spins around its center of gravity, which remains {\bf fixed}, write a computer program to display an interpolated motion of $B$, given a sequence $B_0, B_1, \ldots, B_m$ of rotations specifying the orientation of $B$. \medskip The problem is to ensure that the motion is smooth enough. You may use a cubic spline curve in the appropriate space, and either use quaternion interpolation, or the exponential map and Rodrigues' formula. \vspace { .5cm}\noindent {\bf Extra credit (40 points)\/}: Also assume that the center of gravity is moving, and write a program performing motion interpolation.