Find the length of the longest line segment contained in the given region

Question

Consider the region represented by the following in the $x-y$ plane.
$y=v$, $x=u+v$ and $u^2+v^2\leq1$
$u$ and $v$ are parameters.
What is the length of the longest segment contained in the given region?
N.B.-I gave the entrance exam to the ISI institute in India and this question was asked in it. I was not able to solve the question properly.
My try- Since $y=v$, $|y|\leq1$. That is the region is contained between $y=1$ and $y=-1$.
Also, I got $|x|\leq\sqrt2$.
It was just parts I was able to solve.Not a proper method.
Another approach was eliminating $u$ and $v$. We get the relation $x^2+2y^2-2xy-1\leq0$. This represents the equation of an ellipse with center $(0,0)$ but tilted axes (I think so!).
I actually don't know how to plot this ellipse. So wasn't able to solve the question.

Answer 1

I am not writing a complete answer but the following works.

Notice that the equation describing the region is: $$(x-y)^2+y^2\leq 1 \Rightarrow x^2+2y^2-2xy-1 \leq 0$$ Since we seek the maximum value, we consider only the boundary points i.e: $$x^2+2y^2-2xy-1=0$$ Notice that the above equation represents an ellipse centred at origin. You are lucky that it is centred at origin, it makes the calculation a lot easier to do.

The important step comes now. Switch to polar coordinates, i.e $x=r\cos\theta$ and $y=r\sin\theta$ to obtain: $$r^2=\frac{1}{\cos^2\theta+2\sin^2\theta-2\cos\theta\sin\theta}=\frac{1}{1+\sin^2\theta-\sin(2\theta)}$$ All you need to do is find the maximum value of $r$ (or minimise the denominator on RHS) which I suppose is fairly an easy task. ;)

Answer 2

If you know a little linear algebra, then the answer is easily expressed as the largest singular value of your transformation $x=u+v$, $y=v$. In general, the image of the unit circle under a linear transformation mapping ${\mathbb R}^2 \rightarrow {\mathbb R}^2$ is an ellipse and the singular values of such a transformation can be interpreted geometrically, as the lengths of the semi-major and semi-minor axes of that ellipse. Put another way, the singular values are designed precisely to solve this very problem!

Solution

You want to examine the image of the unit disk under the transformation

$$ \left( \begin{matrix} x \\ y \end{matrix} \right) = \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right) \left( \begin{matrix} u \\ v \end{matrix} \right). $$

The singular values of a real matrix $M$ can be computed as the square roots of the eigenvalues of $M^TM$, which are not at all hard to compute. We do so as follows:

$$ M^TM= \left( \begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix} \right) \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right) = \left( \begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix} \right). $$ The characteristic polynomial of this matrix is $$ \left| \begin{matrix} 1-\lambda & 1 \\ 1 & 2-\lambda \end{matrix} \right| = (1-\lambda)(2-\lambda)-1=\lambda^2-3\lambda+1 $$ The eigenvalues of $M^TM$ are the roots of this polynomial, namely $$ \lambda = \frac{1}{2} \left(3\pm\sqrt{5}\right). $$ The larger of these is clearly produced choosing the plus sign. Thus, the answer to your question is $$ 2\sqrt{\frac{1}{2}\left(3+\sqrt{5}\right)}. $$ Depending on your background, you might recognize the thing inside the square root as the square of the golden ratio - which makes this problem just that much cooler!

The full singular value decomposition

It might be nice to see some background on why this technique works. Before doing so, however, I reiterate that the simple eigenvalue computation above is the only computation that needs to be done to solve the problem. What follows is a presentation of the full singular value decomposition for this particular matrix, from which it's easy to see why the technique works. The computations are certainly much harder and, in fact, I used Mathematica to find the decomposition.

We really don't even know how to find the decomposition in general. We just need the key fact that the matrix $M$ can be rewritten as follows: $$ \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right) = \left( \begin{array}{cc} \cos (\beta ) & -\sin (\beta ) \\ \sin (\beta ) & \cos (\beta ) \\ \end{array} \right)\cdot\left( \begin{array}{cc} \varphi & 0 \\ 0 & 1/\varphi \\ \end{array} \right)\cdot\left( \begin{array}{cc} \cos (\alpha ) & -\sin (\alpha ) \\ \sin (\alpha ) & \cos (\alpha ) \\ \end{array} \right), $$ where $\varphi$ is the golden ration, $$ \alpha=-\tan ^{-1}\left(\sqrt{\frac{5+\sqrt{5}}{5-\sqrt{5}}}\right), \; \text{ and } \; \; \beta = \tan ^{-1}\left(\frac{2 \sqrt{5}}{5+\sqrt{5}}\right). $$

This is just matrix multiplication - conceptually simple though with complicated terms. It can easily be verified on a computer. With Mathematica, we get

FullSimplify[With[{
   phi = GoldenRatio,
   beta = ArcTan[(2 Sqrt[5])/(5 + Sqrt[5])],
   alpha = -ArcTan[Sqrt[(5 + Sqrt[5])/(5 - Sqrt[5])]]
   }, {
    {Cos[beta], -Sin[beta]},
    {Sin[beta], Cos[beta]}
    }.{
    {phi, 0},
    {0, 1/phi}
    }.{
    {Cos[alpha], -Sin[alpha]},
    {Sin[alpha], Cos[alpha]}
    }
  ]]

(* Out: {{1, 1}, {0, 1}} *)

I assume there's plenty of other software that could do the same thing or at least yield a numerical estimate. Armed with this matrix factorization, we can easily see the geometric effect of $M$. The outer two transformations are rotations through the angles $\alpha$ and $\beta$ respectively. The inner transformation stretches by the factor $\varphi$ in the horizontal direction and compresses by the factor $\varphi$ in the vertical. The three steps yielding the geometric effect can be illustrated as follows: