I want to preface my question by mentioning that this question seems to prop up often, but as my goal here is to seek assistance and correction to my own attempts and intuition, I still find myself in need of help after spending quite sometime on this problem.
This problem is from Gilbert Strang's Book, Introduction to Linear Algebra, 5th edition. The problem is on page 232 at the end of the section on least squares and projections. The problem states:
The points $P = (x,x,x)$ and $Q=(y,3y,-1)$ are on two lines in space that don't meet. Choose $x$ and $y$ to minimize the squared distance $||P-Q||^2$. The line connecting the closest $P$ and $Q$ is perpendicular to ….?
While I've enjoyed knocking my head against this problem. I've hit walls on both two approaches I've taken.
My first approach was to employ what the chapter taught me about projections as follows:
- By guessing that this minimum-distance line is going to be the one unique line which is perpendicular two both the line spanned by $P$ and the one spanned by $Q$.
- Trying to find the $x$ and $y$ specified by this requirement.
But I'll present my second approach first, which was to use calculus at least to confirm my intuition since my first approach didn't quite work out for me.
Calculus Attempt
My second approach was to use calculus. I should be solving this problem using Linear Algebra, as that's what I'm learning, but even with this simpler approach, something didn't add up:
\begin{align*}
P-Q &= \begin{bmatrix} x \\ x \\ x
\end{bmatrix} – \begin{bmatrix} y \\ 3y \\ -1 \end{bmatrix} \\
||P-Q||^2 &= (x-y)^2 + (x-3y)^2 + (x+1)^2.
\end{align*}
Then,
\begin{align}
\frac{\partial ||P-Q||^2}{\partial x} &= 6x – 8y + 2\\
\frac{\partial ||P-Q||^2}{\partial y} &= -8x + 20.
\end{align}
Setting those two two zero gives $y=\frac{-2}{7}$ and $x=\frac{-5}{7}$. Now when I went back to verify whether my guess that "this minimum-distance line is going to be the one unique line which is parallel two both the line spanned by $P$ and the one spanned by $Q$", is correct, I get the following:
\begin{align*}
\begin{bmatrix} x & x & x \end{bmatrix} &\begin{bmatrix} -5/7 + 2/7 \\ -5/7 + 6/7 \\ -5/7 + 7/7 \end{bmatrix} =\\
\begin{bmatrix} x & x & x \end{bmatrix} &\begin{bmatrix} -3/7 \\ 1/7\\ 2/7 \end{bmatrix} = 0.
\end{align*}
That worked out as I guessed, but for the other line:
\begin{align*}
\begin{bmatrix} y & 3y &-1 \end{bmatrix} \begin{bmatrix} -3/7 \\ 1/7 \\ 2/7 \end{bmatrix} = y(-3/7 + 3/7) – 2/7,
\end{align*}
which is certainly not zero. I thought my intuitive guess about $P-Q$ being perpendicular to both $P$ and $Q$ was wrong, but upon looking for help in the official solutions manual I found just a hint stating explicitly exactly my assumption. So, my calculus must be wrong, right? I can't figure out which is of the two is correct and which is incorrect. I'd appreciate any assistance in this regard!
Linear Algebra
Ok. Back to my linear algebra approach. I only tried to use calculus because I couldn't get this approach to work. In order to find the $x$ and $y$ that make $P-Q$ perpendicular to both $P$ and $Q$, I figured I would need to determine the $x$ and $y$ that satisfy:
\begin{align*}
P_Q \begin{bmatrix} x \\ x \\ x \end{bmatrix} = \begin{bmatrix} y \\ 3y \\ -1 \end{bmatrix},
\end{align*}
and
\begin{align*}
P_P \begin{bmatrix} y \\ 3y \\ -1 \end{bmatrix} = \begin{bmatrix} x \\ x \\ x \end{bmatrix},
\end{align*}
where $P_Q$ and $P_P$ are the projection matrices to project along the lines $Q$ ( and $P$, respectively.) I figure I need to find the two points that are connected by a line perpendicular to both subspaces? In other words, two lines P and Q such that projecting Q onto P's line gives P, and projecting P onto Q's line gives Q.
The two projection matrices are given by:
\begin{align*}
P_Q &= \frac{QQ^T}{Q^TQ}, P_P = \frac{PP^T}{P^TP}.
\end{align*}
This gives us
\begin{align*}
P_Q \begin{bmatrix} x \\ x \\ x \end{bmatrix} &= \frac{1}{10 y^2 + 1}
\begin{bmatrix}
y^2 & 3y^2 & -y \\
3y^2 & 9y^2 &- 3y \\
-y & -3y & 1 \end{bmatrix} \begin{bmatrix} x \\ x \\ x \end{bmatrix} \\
&= \frac{1}{10 y^2 + 1} \begin{bmatrix} x (y^2 + 3y^2 -y) \\ x(3y^2 9y^2 – 3y) \\ x(-y -3y 1) \end{bmatrix}
\end{align*}
So setting that equal to $\begin{bmatrix} y & 3y & -1 \end{bmatrix}^T$ gives one equation we need $x,y$ to satisfy (Label this equation 1):
\begin{align}
10y^2 – 4xy + x + 1 = 0
\end{align}
Doing the same for the other point:
\begin{align*}
P_P \begin{bmatrix} y \\ 3y \\ -1 \end{bmatrix} &= \frac{1}{3}
\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} y \\ 3y \\ -1 \end{bmatrix}\\
&= \frac{1}{3} \begin{bmatrix} 4y – 1 & 4y – 1 & 4y-1 \end{bmatrix}
\end{align*}
Setting that equal to $\begin{bmatrix}x & x &x\end{bmatrix}^T$ gives $x = \frac{4}{3}y – \frac{1}{3}$, substituting for $x$ in (1) gives:
\begin{align*}
7y^2 + 4y + 1 = 0.
\end{align*}
However, this only has the complex roots $\frac{-2}{7} \pm i\frac{\sqrt{3}}{7}$. The real part is what I got from my first(calculus) approach… but the complex part makes it clear that there is something wrong about my approach, or the way in which I carried it out. I can't figure out what it is that I am doing wrong. I would appreciate any help with respect to any of the two approaches, especially the linear algebraic one as that's the subject I'm trying to improve upon by attempting this problem.
Best Answer
$$f(x,y)=\left\|P-Q\right\|^2=(x-y)^2+(x-3 y)^2+(x+1)^2$$ $$ \begin{cases} 6 x-8 y+2=0\\ 20 y-8 x=0\\ \end{cases} $$
Solutions is $$P=\left(-\frac{5}{7},-\frac{5}{7},-\frac{5}{7}\right);\;Q=\left(-\frac{2}{7},-\frac{6}{7},-1\right)$$
$x=-\frac{5}{7};\;y=-\frac{2}{7}$
is a minimum because Hessian matrix $$ H(x,y)={\begin{pmatrix}f_{xx}(x,y)&f_{xy}(x,y)\\f_{yx}(x,y)&f_{yy}(x,y)\end{pmatrix}}$$
has determinant $$\det\left| \begin{array}{cc} 6 & -8 \\ -8 & 20 \\ \end{array} \right|=56>0 $$
Edit
Forgot the second part of the problem.
$\vec{PQ}=\frac{1}{7} (-3,1,2)$
Line containing $P=(x,x,x)$ has direction $\vec{u}=(1,1,1)$
As $\vec{PQ}\cdot \vec{u}=0$ we have $\vec{PQ}\perp \vec{u}$
Line containing $Q=(y,3y,-1)$ has direction $\vec{v}=(1,3,0)$
and $\vec{PQ}$ is perpendicular to $\vec{v}$, too.
Thus the minimum vector is perpendicular to both the given lines.