Distance Between Two Ellipsoids

Find the shortest distance between \begin{align} &\frac{x_1^2}{a_1^2}+...+\frac{x_n^2}{a_n^2}=1\\ &\frac{x_1^2}{a_1^2}+...+\frac{x_n^2}{a_n^2}=2 \end{align}.

My thinking is when $n=2$, we have two ellipses where the axes of the second are the same as the first scaled by a factor of $\sqrt{2}$. WLOG, assume $|a_1|<|a_2|$. Then the shortest distance would be $|a_1|(\sqrt{2}-1)$. For the ellipsoid case, I would say the shortest distance is $|a_{\text{min}}|(\sqrt{2}-1)$. I don't know how to prove this formally. I thought about using Lagrange multipliers but had difficulties even setting it up. Any suggestions?

In general, the minimum and the maximum distances (with respect to the standard norm $\|\bullet\|$ on $\mathbb{R}^n$) between two $n$-dimensional ellipsoids given by $$A:=\Biggl\{\left(x_1,x_2,\ldots,x_n\right)\in\mathbb{R}^n\,\Big|\,\sum_{i=1}^n\,\frac{x_i^2}{a_i^2}=1\Biggr\}$$ and $$B:=\Biggl\{\left(x_1,x_2,\ldots,x_n\right)\in\mathbb{R}^n\,\Big|\,\sum_{i=1}^n\,\frac{x_i^2}{b_i^2}=1\Biggr\}\,,$$ where $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_n$ are positive real numbers such that $a_i\geq b_i$ for every $i=1,2,\ldots,n$, are $$\min\big\{a_1-b_1,a_2-b_2,\ldots,a_n-b_n\big\}$$ and $$\max\big\{a_1+b_1,a_2+b_2,\ldots,a_n+b_n\big\}\,,$$ respectively. (Of course, the minimum distance is $0$ if there exist $j,k\in\{1,2,\ldots,n\}$ such that $a_j\geq b_j$ and $a_k<b_k$, whilst the maximum distance is still given by the same formula above.) To show this, one only needs to observe that, if $\textbf{u}\in A$ and $\textbf{v}\in B$ are such that $\|\textbf{u}-\textbf{v}\|$ is optimal, then $\textbf{u}-\textbf{v}$ is parallel to the normal vector of $A$ at $\textbf{u}$ as well as the normal vector of $B$ at $\textbf{v}$.

• Can you explain a bit further why $||u-v||$ optimal $\implies$ $u-v$ parallel to "..."? Visually, I can believe it though – user124910 Aug 2 '16 at 1:00
• If $\textbf{u}-\textbf{v}$ is not parallel to the normal $\textbf{n}_A$ of $A$ at $\textbf{u}$, then let $C$ be the curve on $A$ that is made by the intersection with the $2$-dimensional plane containing $\textbf{u}$, $\textbf{v}$, and $\textbf{u}+\textbf{n}_A$. Observe that $C$ is indeed a curve (i.e., it is not degenerate, consisting of a single point). Then, what happens if perturb $\textbf{u}$ by moving a little bit on $C$? – Batominovski Aug 2 '16 at 1:07
• *if we perturb $\textbf{u}$ [...] – Batominovski Aug 2 '16 at 1:15

Let $\frac{x_1^2}{a_1^2}+\dots+\frac{x_n^2}{a_n^2} = 1$ and $\frac{y_1^2}{a_1^2}+\dots+\frac{y_n^2}{a_n^2} = 2$. Then by Cauchy-Schwarz $$1 = \sum\limits_{k=1}^{n}{\frac{y_k^2-x_k^2}{a_k^2}} = \sum\limits_{k=1}^{n}{(y_k-x_k)\frac{y_k+x_k}{a_k^2}}\le\left(\sum\limits_{k=1}^{n}{(y_k-x_k)^2}\right)^{\frac{1}{2}}\left(\sum\limits_{k=1}^{n}{\frac{(y_k+x_k)^2}{a_k^4}}\right)^{\frac{1}{2}}.$$ Since $a_k^4\ge(\min{|a_i|})^2a_k^2$ for all $k$, it follows that $\left(\sum\limits_{k=1}^{n}{\frac{(y_k+x_k)^2}{a_k^4}}\right)^{\frac{1}{2}}\le \frac{1}{\min{|a_i|}}\left(\sum\limits_{k=1}^{n}{\frac{(y_k+x_k)^2}{a_k^2}}\right)^{\frac{1}{2}}$, and applying the triangle inequality to the vectors $\vec{x} = \left(\frac{x_1}{a_1},\dots,\frac{x_k}{a_k}\right)$ and $\vec{y} = \left(\frac{y_1}{a_1},\dots,\frac{y_k}{a_k}\right)$ yields $$\left(\sum\limits_{k=1}^{n}{\frac{(y_k+x_k)^2}{a_k^2}}\right)^{\frac{1}{2}} = \|\vec{x}+\vec{y}\|\le\|\vec{x}\|+\|\vec{y}\| = 1+\sqrt{2}.$$ Hence, $1\le\frac{1+\sqrt{2}}{\min{|a_i|}}\left(\sum\limits_{k=1}^{n}{(y_k-x_k)^2}\right)^{\frac{1}{2}}$, i.e. $\left(\sum\limits_{k=1}^{n}{(y_k-x_k)^2}\right)^{\frac{1}{2}}\ge(\sqrt{2}-1)\min{|a_i|}$.

If we assume w.l.o.g. that $\min{|a_i|} = |a_1|$, then $(x_1,x_2,\dots,x_n) = (a_1,0,\dots,0)$ and $(y_1,y_2,\dots,y_n) = (\sqrt{2}a_1,0,\dots,0)$ attains equality in the above inequality.

• I was thinking that there may be a Cauchy-Schwarz proof of my generalized version, but was not successful with finding one. Do you care to try? – Batominovski Aug 2 '16 at 1:09
• Well, replacing $2$ with any $r$ will also give the desired result, but I'll need more time for more general coefficients. – Joey Zou Aug 2 '16 at 1:15

Here is a solution using Lagrange multipliers: The key is to note that if $(x,y)$ solves the problem (with $x,y$ being on the two ellipses), then $x$ is a closest point to the '$y$'-ellipse, and $y$ is a closest point to the '$x$'-ellipse.

Let $f(x) = \sum_k ({x_k \over a_k } ) ^2$. Let $E_k = f^{-1} (\{ k \})$, $k=1,2$ The $E_k$ are compact, so we know there are minimisers. Suppose $(x,y)$ is a minimiser with $x \in E_1, y \in E_2$.

Since $y$ minimises the distance to $E_1$, we have $x-y\parallel \nabla f(y)$. Similarly, since $x$ minimises the distance to $E_2$, we have $y-x \parallel \nabla f(x)$.

Hence $\nabla f(y) = \lambda \nabla f(x)$ for some $\lambda$, and so $y = \lambda x$. Since $y \in E_2, x \in E_1$, we find that $\lambda = \sqrt{2}$.

Hence any minimiser $(x',y')$ satisfies $y' = \sqrt{2} x'$. If $x' \in E_1$, we see that $\sqrt{2}x' \in E_2$, hence we can restrict our search to minimising the distance between $x'$ and $\sqrt{2} x'$, with $x' \in E_1$.

That is, we need to solve $\min \{ (\sqrt{2}-1) \|x'\| | x' \in E_1 \}$, and it is clear that the minimising point is a closest point on $E_1$ to the origin. It is clear that if $i$ is such that $|a_i| = \min_k |a_k|$, then $x'=a_i e_i$ is a minimiser, from which we conclude that the minimum distance is $(\sqrt{2}-1) \min_k |a_k|$.

We begin by switching to parametric coordinates.

Recall that expressing in spherical coordinates:

https://en.wikipedia.org/wiki/N-sphere#Spherical_coordinates

We have that a general ellipse can be expressed as

$$\begin{matrix} x_1 = a_1 r \cos(\theta_1) \\ x_2 = a_2 r \sin(\theta_1)\cos(\theta_2) \\ x_3 = a_3 r \sin(\theta_1 )\sin(\theta_2) \cos(\theta_3) \\ \vdots \\ x_n = a_nr \sin(\theta_1) ... \sin(\theta_{n-1}) \cos(\theta_n)\end{matrix}$$

Now if we let $\theta_n = 0$, then we effectively have a series of equations for the surface of the n-dimensional ellipse given parametrically.

$$\begin{matrix} x_1 = a_1 r \cos(\theta_1) \\ x_2 = a_2 r \sin(\theta_1)\cos(\theta_2) \\ x_3 = a_3 r \sin(\theta_1 )\sin(\theta_2) \cos(\theta_3) \\ \vdots \\ x_n = a_nr \sin(\theta_1) ... \sin(\theta_{n-1}) \end{matrix}$$

The equation of the first ellipsoid will be:

$$\begin{matrix} x_1 = a_1 \cos(\theta_1) \\ x_2 = a_2 \sin(\theta_1)\cos(\theta_2) \\ x_3 = a_3 \sin(\theta_1 )\sin(\theta_2) \cos(\theta_3) \\ \vdots \\ x_n = a_n \sin(\theta_1) ... \sin(\theta_{n-1}) \end{matrix}$$ The equation of the second ellipsoid then will be

$$\begin{matrix} x_1 = \sqrt{2} a_1 \cos(\theta_1) \\ x_2 = \sqrt{2} a_2 \sin(\theta_1)\cos(\theta_2) \\ x_3 = \sqrt{2} a_3 \sin(\theta_1 )\sin(\theta_2) \cos(\theta_3) \\ \vdots \\ x_n =\sqrt{2} a_n \sin(\theta_1) ... \sin(\theta_{n-1}) \end{matrix}$$

Now we wish to show that we minimize the distance between points on each surface. Of course we need not use the "distance" formula from Euclidean space, we can also use the polar distance formula, where naturally it follows that (we can't change $r$ which is fixed to 1 and $\sqrt{2}$) that getting the angles as close as possible, gets the points as close as possible.

Thus points on the exact same angle, would only differ by $\sqrt{2}-1$ and we conclude that is the min distance between the ellipsoids.

• "$r$ ... is fixed to 1 and $\sqrt2$"? I think you forgot about all the $a_1, \ldots, a_n$ factors. – Rahul Aug 2 '16 at 12:42