\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 2}\\[10pt] October 27, 2003; Due November 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} ``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).} (1) If an upper triangular $n\times n$ matrix $R$ is invertible, prove that its inverse is also upper triangular. \medskip (2) If an upper triangular matrix is orthogonal, prove that it must be a diagonal matrix. \medskip If $A$ is an invertible $n\times n$ matrix and if $A = Q_1R_1 = Q_2R_2$, where $R_1$ and $R_2$ are upper triangular with positive diagonal entries and $Q_1, Q_2$ are orthogonal, prove that $Q_1 = Q_2$ and $R_1 = R_2$. \vspace{0.5cm}\noindent {\bf Problem B2 (30 pts)}. Consider the Euclidean space $\eucreal^n$, and let $O = (0,\ldots, 0)$. Given any $x\in \eucreal^n$, $x\not= O$, let $H(x)$ be the affine hyperplane perpendicular to $Ox$ and passing through the point $x'$ on the line $Ox$ and such that $\libvecbo{Ox}\cdot \libvecbo{Ox'} = 1$. Equivalently, $H(x)$ is the affine hyperplane defined by \[H(x) = \{y\in \eucreal^n\mid x\cdot y = 1\}.\] We call $H(x)$ the {\it polar\/} or {\it dual\/} of $x$. Conversely, given any affine hyperplane $H$ not passing through $O$, there is clearly a unique $x\in \eucreal^n$ so that $H(x) = H$, and we call $x$ the {\it pole\/} or {\it dual\/} of $H$. \medskip Given a subset $A$ of $\eucreal^n$, let \[A^* = \{y\in \eucreal^n\mid x\cdot y \leq 1,\> \forall x\in A\}.\] We call $A^*$ the {\it polar\/} or {\it reciprocal\/} of $A$. \medskip (a) Check that $A^*$ is the intersection of all the closed half-spaces containing $O$ determined by the polar hyperplanes of points of $A$. Thus, conclude that $A^*$ is convex. \medskip Let $B^n(r)$ be the ball of radius $ r> 0$ and center $O$, i.e., \[B^n(r) = \{x\in \eucreal^n\mid \norme{x} \leq r\}.\] Show that $B^n(r)^* = B^n(1/r)$. \medskip 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 (b) A {\it convex polyhedron\/} or {\it convex body\/} $P$ is a bounded subset of $\eucreal^n$ with nonempty interior obtained as the intersection of a finite number of closed half--spaces. We will prove in class that a convex polyhedron $P$ is the convex hull of a finite set of points with nonempty interior and conversely. We will also prove that the dual of a convex polyhedron containing $O$ is a convex polyhedron. Observe that the duality exchanges vertices of $P$ and the faces of $P^*$. \medskip What is the dual of an $n$-simplex? \medskip (c) 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 B3 (50 pts)}. (1) Review the modified Gram--Schmidt method. Recall that to compute $\novect{Q_{k+1}'}$, instead of projecting $\novect{A_{k+1}}$ onto $\novect{Q_1}, \ldots, \novect{Q_{k}}$ in a single step, it is better to perform $k$ projections. We compute $\novect{Q_{k+1}^{1}}, \novect{Q_{k+1}^{2}}, \ldots$, $\novect{Q_{k+1}^{k}}$ as follows: \[\eqaligneno{ \novect{Q_{k+1}^{1}} &= \novect{A_{k+1}} - (\dotprod{\novect{A_{k+1}}}{\novect{Q_{1}}})\,\novect{Q_{1}},\cr \novect{Q_{k+1}^{i+1}} &= \novect{Q_{k+1}^{i}} - (\dotprod{\novect{Q_{k+1}^{i}}}{\novect{Q_{i+1}}})\,\novect{Q_{i+1}},\cr }\] where $1\leq i\leq k - 1$. %\medskip Prove that $\novect{Q_{k+1}'} = \novect{Q_{k+1}^{k}}$. \medskip (2) Write two computer programs to compute the $QR$-decomposition of an invertible matrix. The first one should use the standard Gram--Schmidt method, and the second one the modified Gram--Schmidt method. Run both on a number of matrices, up to dimension at least $10$. Do you observe any difference in their performance in terms of numerical stability? \medskip Run your programs on the Hilbert matrix $H_n = (1/(i + j - 1))_{1\leq i, j\leq n}$. What happens? \medskip\noindent {\bf Extra Credit.} (20 points) Write a program to solve linear systems of equations $Ax = b$, using your version of the $QR$-decomposition program, where $A$ is an $n\times n$ matrix. \vspace{0.5cm}\noindent {\bf Problem B4 (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 B5 (80 pts)}. Let $\mapdef{\varphi}{E\times E}{\reals}$ be a symmetric bilinear form on a real vector space $E$ of finite dimension $n$. Two vectors $\novect{x}$ and $\novect{y}$ are said to be {\it conjugate w.r.t. $\varphi$\/} if $\varphi(\novect{x}, \novect{y}) = 0$. The main purpose of this problem is to prove that there is a basis of vectors that are pairwise conjugate w.r.t. $\varphi$. \medskip (a) Prove that if $\varphi(\novect{x}, \novect{x}) = 0$ for all $\novect{x}\in E$, then $\varphi$ is identically null on $E$. \medskip Otherwise, we can assume that there is some vector $\novect{x}\in E$ such that $\varphi(\novect{x}, \novect{x}) \not= 0$. Use induction to prove that there is a basis of vectors that are pairwise conjugate w.r.t. $\varphi$. \medskip For the induction step, proceed as follows. Let $(\novect{e_1}, \novect{e_2}, \ldots, \novect{e_n})$ be a basis of $E$, with $\varphi(\novect{e_1}, \novect{e_1}) \not= 0$. Prove that there are scalars $\lambda_2, \ldots, \lambda_n$ such that each of the vectors \[\novect{v_{i}} = \novect{e_{i}} + \lambda_i\novect{e_1}\] is conjugate to $\novect{e_1}$ w.r.t. $\varphi$, where $2 \leq i \leq n$, and that $(\novect{e_1}, \novect{v_2}, \ldots, \novect{v_n})$ is a basis. \medskip (b) Let $(\novect{e_1}, \ldots, \novect{e_n})$ be a basis of vectors that are pairwise conjugate w.r.t. $\varphi$, and assume that they are ordered such that \[\varphi(\novect{e_i}, \novect{e_i}) = \cases{ \theta_i \not= 0 & if $1\leq i \leq r$, \cr 0 & if $r+1 \leq i \leq n$,\cr }\] where $r$ is the rank of $\varphi$. Show that the matrix of $\varphi$ w.r.t. $(\novect{e_1}, \ldots, \novect{e_n})$ is a diagonal matrix, and that \[\varphi(\novect{x}, \novect{y}) = \sum_{i = 1}^r \theta_i x_i y_i,\] where $\novect{x} = \sum_{i= 1}^n x_i \novect{e_i}$ and $\novect{y} = \sum_{i= 1}^n y_i \novect{e_i}$. \medskip Prove that for every symmetric matrix $A$, there is an invertible matrix $P$ such that \[\transpos{P}A P = D,\] where $D$ is a diagonal matrix. \medskip (c) Prove that there is an integer $p$, $0 \leq p \leq r$ (where $r$ is the rank of $\varphi$), such that $\varphi(\novect{u_i}, \novect{u_i}) > 0$ for exactly $p$ vectors of every basis $(\novect{u_1}, \ldots, \novect{u_n})$ of vectors that are pairwise conjugate w.r.t. $\varphi$ ({\it Sylvester's inertia theorem\/}). \medskip Proceed as follows. Assume that in the basis $(\novect{u_1}, \ldots, \novect{u_n})$, for any $\novect{x}\in E$, we have \[\varphi(\novect{x}, \novect{x}) = \alpha_1 x_1^2 + \cdots + \alpha_p x_p^2 - \alpha_{p+1} x_{p+1}^2 - \cdots - \alpha_r x_{r}^2,\] where $\novect{x} = \sum_{i=1}^n x_i \novect{u_i}$, and that in the basis $(\novect{v_1}, \ldots, \novect{v_n})$, for any $\novect{x}\in E$, we have \[\varphi(\novect{x}, \novect{x}) = \beta_1 y_1^2 + \cdots + \beta_q y_q^2 - \beta_{q+1} y_{q+1}^2 - \cdots - \beta_r y_{r}^2,\] where $\novect{x} = \sum_{i=1}^n y_i \novect{v_i}$, with $\alpha_i > 0$, $\beta_i > 0$, $1\leq i \leq r$. \medskip Assume that $p > q$ and derive a contradiction. First, consider $\novect{x}$ in the subspace $F$ spanned by \[(\novect{u_1}, \ldots, \novect{u_p}, \novect{u_{r+1}}, \ldots, \novect{u_n}),\] and observe that $\varphi(\novect{x}, \novect{x}) \geq 0$ if $\novect{x} \not= \novect{0}$. Next, consider $\novect{x}$ in the subspace $G$ spanned by \[(\novect{v_{q+1}}, \ldots, \novect{v_r}),\] and observe that $\varphi(\novect{x}, \novect{x}) < 0$ if $\novect{x} \not= \novect{0}$. Prove that $F\cap G$ is nontrivial (i.e., contains some nonnull vector), and derive a contradiction. This implies that $p \leq q$. Finish the proof. \medskip The pair $(p, r - p)$ is called the {\it signature\/} of $\varphi$. \medskip (d) A symmetric bilinear form $\varphi$ is {\it definite\/} if for every $\novect{x}\in E$, if $\varphi(\novect{x}, \novect{x}) = 0$, then $\novect{x} = 0$. \medskip Prove that a symmetric bilinear form is definite iff its signature is either $(n, 0)$ or $(0, n)$. In other words, a symmetric definite bilinear form has rank $n$ and is either positive or negative. \medskip (e) The {\it kernel\/} of a symmetric bilinear form $\varphi$ is the subspace consisting of the vectors that are conjugate to all vectors in $E$. We say that a symmetric bilinear form $\varphi$ is {\it nondegenerate\/} if its kernel is trivial (i.e., equal to $\{\novect{0}\}$). \medskip Prove that a symmetric bilinear form $\varphi$ is nondegenerate iff its rank is $n$, the dimension of $E$. Is a definite symmetric bilinear form $\varphi$ nondegenerate? What about the converse? \medskip Prove that if $\varphi$ is nondegenerate, then there is a basis of vectors that are pairwise conjugate w.r.t. $\varphi$ and such that $\varphi$ is represented by the matrix \[\matta{I_p}{0} {0}{-I_q}\] % where $(p, q)$ is the signature of $\varphi$. \medskip (f) Given a nondegenerate symmetric bilinear form $\varphi$ on $E$, prove that for every linear map $\mapdef{f}{E}{E}$, there is a unique linear map $\mapdef{\covec{f}}{E}{E}$ such that % \[\varphi(f(\novect{u}),\, \novect{v}) = \varphi(\novect{u},\, \covec{f}(\novect{v})),\] for all $\novect{u}, \novect{v}\in E$. The map $\covec{f}$ is called the {\it adjoint of $f$ (w.r.t. to $\varphi$)\/}. Given any basis $(\novect{u_1}, \ldots, \novect{u_n})$, if $\Omega$ is the matrix representing $\varphi$ and $A$ is the matrix representing $f$, prove that $\covec{f}$ is represented by $\Omega^{-1} \transpos{A}\Omega$. \medskip Prove that Lemma 6.2.4 of my book also holds, i.e., the map $\mapdef{\flat}{E}{\dual{E}}$ is a canonical isomorphism. \medskip A linear map $\mapdef{f}{E}{E}$ is an {\it isometry w.r.t. $\varphi$\/} if \[\varphi(f(\novect{x}),\, f(\novect{y})) = \varphi(\novect{x},\, \novect{y})\] for all $\novect{x}, \novect{y}\in E$. Prove that a linear map $f$ is an isometry w.r.t. $\varphi$ iff \[\dual{f}\circ f = f \circ \dual{f} = \id.\] Prove that the set of isometries w.r.t. $\varphi$ is a group. This group is denoted by $\mO{\varphi}$, and its subgroup consisting of isometries having determinant $+1$ by $\mSO{\varphi}$. Given any basis of $E$, if $\Omega$ is the matrix representing $\varphi$ and $A$ is the matrix representing $f$, prove that $f\in \mO{\varphi}$ iff \[\transpos{A}\Omega A = \Omega.\] \medskip Given another nondegenerate symmetric bilinear form $\psi$ on $E$, we say that $\varphi$ and $\psi$ are {\it equivalent\/} if there is a bijective linear map $\mapdef{h}{E}{E}$ such that \[\psi(\novect{x},\, \novect{y}) = \varphi(h(\novect{x}),\, h(\novect{y})),\] for all $\novect{x}, \novect{y}\in E$. Prove that the groups of isometries $\mO{\varphi}$ and $\mO{\psi}$ are isomomorphic (use the map $f \mapsto h\circ f \circ h^{-1}$ from $\mO{\psi}$ to $\mO{\varphi}$). \medskip If $\varphi$ is a nondegenerate symmetric bilinear form of signature $(p, q)$, prove that the group $\mO{\varphi}$ is isomorphic to the group of $n\times n$ matrices $A$ such that \[\transpos{A} \matta{I_p}{0} {0}{-I_q} A = \matta{I_p}{0} {0}{-I_q}.\] \remark In view of question (f), the groups $\mO{\varphi}$ and $\mSO{\varphi}$ are also denoted by $\mOpq{p}{q}$ and $\mSOpq{p}{q}$ when $\varphi$ has signature $(p, q)$. They are Lie groups. In particular, the group $\mSOpq{3}{1}$, known as the {\it Lorentz group\/}, plays an important role in the theory of special relativity. \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: 270 points.} \end{document}