Let $u_1,u_2 \in \mathbb R^n$ be two vectors in an Euclidean space. Suppose that for every integer $k \in \mathbb Z$ we have $|u_1| \le |u_2+ku_1|$. I need to show that for every $k_1, k_2 \in \mathbb Z$, (not both $0$) we have: $|u_1| \le |k_1u_1+k_2u_2|$.

I used the triangle inequality, inserted the $k_2$ in the equation but couldn't get back from a sum of norms to a norm of a sum as asked, because the triangle inequality goes one way if you know what I mean :) Also, the Cauchy-Schwarz inequality is not useful (I believe) here since we have to do with the vectors themselves and not the coordinates (but I may be worng).

If this needs a trick to be solved, can anyone provide a hint?


Let $\pi$ be the orthogonal projection along $u_1$. Then there is a $k \in \mathbb{Z}$ such that $\lVert (1-\pi)(u_2+ k u_1) \rVert = \lVert (1-\pi) u_2 + k u_1 \rVert \leq \tfrac12 \lVert u_1 \rVert$. For this $k$ we have $$\begin{eqnarray}\lVert u_1 \rVert^2 &\leq & \lVert u_2+ k u_1 \rVert^2 \\ &= & \lVert (1-\pi)(u_2+k u_1)\rVert^2 + \lVert \pi(u_2 + k u_1)\rVert^2 \\ &\leq & \tfrac14 \lVert u_1 \rVert^2 + \lVert \pi u_2 \rVert^2 \end{eqnarray}$$ and so $\lVert \pi u_2 \rVert > \tfrac12 \lVert u_1 \rVert$. Then for $k_1, k_2 \in \mathbb{Z}$ and $\lvert k_2 \rvert \geq 2$ $$\lVert k_2 u_2 + k_1 u_1\rVert \geq \lVert \pi(k_2 u_2 + k_1 u_1) \rVert \geq 2 \lVert \pi u_2 \rVert > \lVert u_1 \rVert.$$ The cases with $\lvert k_2 \rvert <2$ are easy to check.

  • $\begingroup$ Some questions: 1) Why $\pi ku_1=0$? I thought that $\pi u_1=u_1$. 2) First inequality: where that $1/2$ came from! 3) Second equality: An equality?! I understand that you add and subtrack $\pi(u_1+ku_1)$ in that case but how come splitting the norm while "on powers of two"? 4) Last line, first inequality: this is from Cauchy–Schwarz inequality, correct? $\endgroup$ – John Feb 19 '17 at 19:14
  • $\begingroup$ 1) $\pi$ projects in the direction of $u_1$ (not onto its span) so $\pi u_1=0$. 2) If you take steps of length $d$ along the span of $u_1$ then no matter where you start you can always reach a point closer than $d/2$ to the origin (make a picture). 3) That is Pythagoras. 4) An orthogonal projection cannot increase the norm of a vector. This is Pythagoras again: $\lVert v\rVert^2=\lVert \pi v\rVert^2 + \lVert (1-\pi)v\rVert^2$. $\endgroup$ – WimC Feb 19 '17 at 20:39
  • $\begingroup$ Can you provide an analog of $\pi$ in the 2-dimension space or a link that shows what's $\pi$ and $1-\pi$ and why they make a right triangle? From what you said I understood that $u_1 \bot \pi$. The span of the vector here isn't like moving on it, like in its direction? I understood what you said about reaching closer than $d/2$, but you have an $(1-\pi)u_2$ over there! Where did that go? $\endgroup$ – John Feb 19 '17 at 21:02
  • $\begingroup$ It would be very nice to really understand what $\pi$ and $1-\pi$ are. Other than that, the proof is impeccable. $\endgroup$ – John Feb 22 '17 at 16:28
  • $\begingroup$ $$\pi(v)=v-\frac{\langle v, u_1\rangle}{\lVert u_1\rVert^2} u_1$$ $\endgroup$ – WimC Feb 22 '17 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.