From Random Polygon to Ellipse: An Eigenanalysis

• Published in: SIAM review 2010-03, Vol.52 (1), p.151-170
• Main Authors: Elmachtoub, Adam N., Van Loan, Charles F.
• Format: Article
• Language: English
• Subjects: Centroids; EDUCATION; Eigenvalues; Eigenvectors; Ellipses; Exact sciences and technology; Experimentation; Geometry; Mathematical analysis; Mathematical models; Mathematical vectors; Mathematics; Matrices; Methods of scientific computing (including symbolic computation, algebraic computation); Nonlinear algebraic and transcendental equations; Numerical analysis; Numerical analysis. Scientific computation; Numerical linear algebra; Polygons; Problem solving; Sciences and techniques of general use; Studies; Vertices
• ISSN: 0036-1445; 1095-7200
• DOI: 10.1137/090746707

Suppose x and y are unit 2-norm n-vectors whose components sum to zero. Let P(x,y) be the polygon obtained by connecting $(x_{1},y_{1}),\ldots,(x_{n},y_{n}),(x_{1},y_{1})$ in order. We say that $\hat{{\cal P}}(\hat{x},\hat{y})$ is the normalized average of P(x,y) if it is obtained by connecting the midpoints of its edges and then normalizing the resulting vertex vectors x̂ and ŷ so that they have unit 2-norm. If this process is repeated starting with ${\cal P}_{0}={\cal P}(x^{(0)},y^{(0)})$, then in the limit the vertices of the polygon iterates ${\cal P}(x^{(k)},y^{(k)})$ converge to an ellipse ε that is centered at the origin and whose semiaxes are tilted forty-five degrees from the coordinate axes. An eigenanalysis together with the singular value decomposition is used to explain this phenomenon. The problem and its solution is a metaphor for matrix-based research in computational science and engineering.