Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have two vectors:

$x = \{ x_1,\dots,x_n \}$


$y = \{ y_1,\dots,y_n \}$

with the following condition: $0 \leq x_i$ and $y_i \leq M$ and some value $u$ with $u > M$.

There are two numbers $a$ and $b$ defined:

  1. $a = x_1 \cdot u^n + x_2 \cdot u^{n-1} + \dots + x_n \cdot u^1$

  2. $b = y_1 \cdot u^n + y_2 \cdot u^{n-1} + \dots + y_n \cdot u^1$

I have to show that:

$a = b \Leftrightarrow x = y$ and

$a < b \Leftrightarrow x$ is lexicographically smaller then $y$.

I have troubles to give a clean proof, that both of these hold true.

For the first case, I try to do it the following way:

$a = b$


$x_1 \cdot u^n + x_2 \cdot u^{n-1} + \dots + x_n \cdot u^1 = y_1 \cdot u^n + y_2 \cdot u^{n-1} + \dots + y_n \cdot u^1$

and argue, that there has to be combination of values for that both vectors are the same, as in the absolute value $|x| = |y|$. So basically I reduce it to:

$\sqrt{x_n^2 + \dots + x_n^2} = \sqrt{y_1^2 + \dots + y_n^2}$

But that's it, I don't know how to continue.

Similiar to the second proof. I argue, that $u$ stays the same on both sides and that with the lexicographical order the values are at least the same and in the end the other vector is bigger than the other. But my whole argumentation seems to vague. Is there a more mathematical approach where I can change the equation and the logic seems more obivous?

share|improve this question
When $x=(0,1)$, $\ y=\bigl({1\over2},0\bigr)$ and $u=2$ then $a=b=2$, but $x\ne y$. therefore your first statement is wrong. By the way, do you mean $x_i$, $y_i\in[0,M]\ $? –  Christian Blatter Nov 3 '11 at 19:28
I think Christian is onto something; you probably want the $x_i$ and $y_i$ to be integers. And despite the "vectors", this isn't really a problem in linear algebra. It's a problem about representing numbers in base $u$. It's school algebra, not linear algebra. –  Gerry Myerson Nov 4 '11 at 6:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.