\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 Fall, 2003 \hspace*{0.4cm} CIS 610}}\\ \vspace{1cm} {Advanced geometric methods\\ \vspace{0.5cm} Homework 4}\\[10pt] November 25, 2003; Due December 11, beginning of class\\ \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} ``B problems'' must be turned in. \vspace {0.5cm}\noindent {\bf Problem B1 (50 pts).} The purpose of this problem is to prove that given any self-adjoint linear map $\mapdef{f}{E}{E}$ (i.e., such that $\dual{f} = f$), where $E$ is a Euclidean space of dimension $n\geq 3$, given an orthonormal basis $(\novect{e_1}, \ldots, \novect{e_n})$, there are $n-2$ isometries $h_i$, hyperplane reflections or the identity, such that the matrix of $$h_{n-2} \circ \cdots \circ h_1 \circ f\circ h_1 \circ \cdots \circ h_{n-2}$$ is a symmetric tridiagonal matrix. \medskip (1) Prove that for any isometry $\mapdef{f}{E}{E}$, we have $f = \dual{f} = f^{-1}$ iff $f\circ f = \id$. \medskip Prove that if $f$ and $h$ are self-adjoint linear maps ($\dual{f} = f$ and $\dual{h} = h$), then $h\circ f\circ h$ is a self-adjoint linear map. \medskip (2) Proceed by induction, taking inspiration from the proof of the triangular decomposition given in the class notes. Let $V_k$ be the subspace spanned by $(\novect{e_{k+1}}, \ldots, \novect{e_n})$. For the base case, proceed as follows. \medskip Let $$f(\novect{e_1}) = a_1^0 \novect{e_1} + \cdots + a_n^0\novect{e_n},$$ and let $$r_{1,\, 2} = \norme{a_2^0 \novect{e_2} + \cdots + a_n^0\novect{e_n}}.$$ Find an isometry $h_1$ (reflection or $\id$) such that $$h_1(f(\novect{e_1}) - a_1^0\novect{e_1}) = r_{1,\, 2}\, \novect{e_2}.$$ Observe that $$\novect{w_1} = r_{1,\, 2}\, \novect{e_2} + a_1^0\novect{e_1} - f(\novect{e_1}) \in V_1,$$ and prove that $h_1(\novect{e_1}) = \novect{e_1}$, so that $$h_1\circ f \circ h_1(\novect{e_1}) = a_1^0\novect{e_1} + r_{1,\, 2}\, \novect{e_2}.$$ Let $f_1 = h_1\circ f \circ h_1$. \medskip Assuming by induction that $$f_k = h_k \circ \cdots \circ h_1 \circ f\circ h_1 \circ \cdots \circ h_k$$ has a tridiagonal matrix up to the $k$th row and column, $1\leq k \leq n - 3$, let $$f_k(\novect{e_{k+1}}) = a^k_{k}\novect{e_{k}} + a^k_{k+1}\novect{e_{k+1}} + \cdots + a^k_{n}\novect{e_{n}},$$ and let $$r_{k+1,\, k+2} = \norme{a^k_{k+2}\novect{e_{k+2}} + \cdots + a^k_{n}\novect{e_{n}}}.$$ Find an isometry $h_{k+1}$ (reflection or $\id$) such that $$h_{k+1}(f_k(\novect{e_{k+1}}) - a^k_{k}\novect{e_{k}} - a^k_{k+1}\novect{e_{k+1}}) = r_{k+1,\, k+2}\, \novect{e_{k+2}}.$$ Observe that $$\novect{w_{k+1}} = r_{k+1,\, k+2}\, \novect{e_{k+2}} + a^k_{k}\novect{e_{k}} + a^k_{k+1}\novect{e_{k+1}} - f_k(\novect{e_{k+1}})\in V_{k+1},$$ and prove that $h_{k+1}(\novect{e_{k}}) = \novect{e_{k}}$ and $h_{k+1}(\novect{e_{k+1}}) = \novect{e_{k+1}}$, so that $$h_{k+1}\circ f_k \circ h_{k+1}(\novect{e_{k+1}}) = a^k_{k}\novect{e_{k}} + a^k_{k+1}\novect{e_{k+1}} + r_{k+1,\, k+2}\, \novect{e_{k+2}}.$$ Let $f_{k+1} = h_{k+1}\circ f_k \circ h_{k+1}$, and finish the proof. \medskip Do $f$ and $f_{n-2}$ have the same eigenvalues? If so, explain why. \medskip (3) Prove that given any symmetric $n\times n$-matrix $A$, there are $n - 2$ matrices $H_1, \ldots, H_{n-2}$, Householder matrices or the identity, such that $$B = H_{n-2} \cdots H_1 A H_1 \cdots H_{n-2}$$ is a symmetric tridiagonal matrix. \vspace {0.5cm}\noindent {\bf Problem B2 (40 pts).} Write a computer program implementing the method of problem 1(3). \vspace {0.5cm}\noindent {\bf Problem B3 (40 pts).} Let $A$ be a symmetric tridiagonal $n\times n$-matrix \medskip $$A = \pmatrice{ b_1 & c_1 & & & & \cr c_1 & b_2 & c_2 & & & \cr & c_2 & b_3 & c_3 & & \cr & &\ddots &\ddots &\ddots & \cr & & & c_{n-2} & b_{n-1} & c_{n-1} \cr & & & & c_{n-1} & b_{n} \cr }$$ \medskip\noindent where it is assumed that $c_i\not= 0$ for all $i$, $1\leq i \leq n-1$, and let $A_k$ be the $k\times k$-submatrix consisting of the first $k$ rows and columns of $A$, $1\leq k \leq n$. We define the polynomials $P_k(x)$ as follows ($0\leq k \leq n$). $$\eqaligneno{ P_0(x) &= 1,\cr P_1(x) &= b_1 - x,\cr P_{k}(x) &= (b_k - x)P_{k-1}(x) - c_{k-1}^2 P_{k - 2}(x),\cr }$$ where $2\leq k \leq n$. \medskip (1) Prove the following properties: \medskip (i) $P_k(x)$ is the characteristic polynomial of $A_k$, where $1\leq k \leq n$. \medskip (ii) $\lim_{x\rightarrow -\infty} P_k(x) = +\infty$, where $1\leq k \leq n$. \medskip (iii) If $P_k(x) = 0$, then $P_{k-1}(x)P_{k+1}(x) < 0$, where $1\leq k \leq n-1$. \medskip (iv) $P_k(x)$ has $k$ distinct real roots that separate the $k + 1$ roots of $P_{k+1}$, where $1\leq k \leq n-1$. \medskip (2) ({\bf Extra Credit 20 pts}) Given any real number $\mu > 0$, for every $k$, $1 \leq k \leq n$, define the function $sg_k(\mu)$ as follows: $$sg_k(\mu) = \cases{ \hbox{sign of}\> P_k(\mu) & if $P_k(\mu) \not= 0$,\cr \hbox{sign of}\> P_{k-1}(\mu) & if $P_k(\mu) = 0$.\cr }$$ \medskip We encode the sign of a positive number as $+$, and the sign of a negative number as $-$. Then, let $E(k, \mu)$ be the ordered list $$E(k, \mu) = \left<+,\, sg_1(\mu),\, sg_2(\mu),\, \ldots,\, sg_k(\mu)\right>,$$ and let $N(k, \mu)$ be the number changes of sign between consecutive signs in $E(k, \mu)$. \medskip Prove that $sg_k(\mu)$ is well defined, and that $N(k, \mu)$ is the number of roots $\lambda$ of $P_k(x)$ such that $\lambda < \mu$. \medskip {\it Remark\/}: The above can be used to compute the eigenvalues of a (tridiagonal) symmetric matrix (the method of Givens-Householder). \vspace {0.5cm}\noindent {\bf Problem B4 (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 Problem B5 (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. \vspace{0.5cm}\noindent {\bf TOTAL: 230 points.} \end{document}