3
$\begingroup$

Let $N$ be some positive integer and $A$ be the following set

$\{ (i, j) \in \mathbb{N}^2 : 1 \le i \le j \le N\} = \{ (1, 1), (1, 2), \ldots, (1, N), (2, 2), (2, 3), \ldots, (2, N), \ldots, (N, N) \}$

I know that $A$ has $\frac{N(N+1)}{2}$ elements.

Also, let $B$ be the set $\Bigl\{1, 2, 3, \ldots, \frac{N(N+1)}{2} \Bigr\}$.

The function $f(i, j) = j + i \cdot N - \frac{i(i+1)}{2} $ is an injective function from $A$ to $B$ but I'm trying to find a injection from $B$ to $A$ and I am not having success.

I need this function to optimize a for loop in a program that only needs to care about the upper triangular part of a matrix (if you pay attention, you will see that $A$ has the indexes of a $N \times N$ upper triangular matrix...).

Does someone have any idea?

Thank you very much!

$\endgroup$
3
$\begingroup$

I will try to create a bijection for you. What we do is we count by rows. So the row $(1,1),\ldots,(1,N)$ ends on spots $1,\ldots,N$. We then start the next row at $(2,2)$ which needs to be put on $N+1$ and finish the row. So:

  • $(1,1)\mapsto 1$
  • $(2,2)\mapsto N+1$
  • $(3,3)\mapsto 2N$
  • $(4,4)\mapsto 3N-2$
  • $(5,5)\mapsto 4N-5$
  • $(6,6)\mapsto 5N-9$

etc.

What we need to do is to create a formula which determines the right starting position and adds 1 if we add one to our second coordinate. Ie \begin{equation} (i,j)\mapsto(i-1)N + (j-i+1), \end{equation} where the first term determines how many times $N$ we need and the second term starts counting from $+1$ for each step we move to the right/add 1 to $j$. However, as we see from the list we also need to subtract some value for each row from $i=3$ onward. Notice that this value equals \begin{equation} \sum_{k=1}^{i-2}k = \frac{(i-2)(i-1)}{2}. \end{equation} Therefore we add this term to get the result \begin{align*} \color{red}{(i-1)N + (j-i+1) - \frac{(i-2)(i-1)}{2}} \end{align*} Note that this function is strictly increasing in both $i$ and $j$ and that it equals $\frac{N(N+1)}{2}$ for $(i,j)=(N,N)$, making it a bijection.

$\endgroup$
  • $\begingroup$ first of all, thank you for answering. So, what is the inverse function of this bijection? This is the point: I want a injection from $B$ to $A$... $\endgroup$ – Hilder Vítor Lima Pereira Sep 7 '15 at 17:29
  • $\begingroup$ Suppose we have the number $1\le x \le \frac{N(N+1)}{2}$. We can choose $i$ the biggest integer such that $\sum_{k=1}^{i-1}(N+1-k) \le x$. Then set $j = (i-1) + x - \sum_{k=1}^{i-1}(N+1-k)$. $\endgroup$ – Marc Sep 9 '15 at 10:02
2
$\begingroup$

An injection from A to B is: $f(i,j) = i + j(j-1)/2 = n$

So solve $x^2-x-2(n-1)=0$ to find $j=\lfloor x\rfloor$ and use that to find $i$ .


In more detail, noting that we have for all (valid) $i$ and $j$: $f(1, j) \leq f(i,j)< f(1, j+1)$, then we can then assume there is some continuous function $g$ and some remainder $r_i: 0\leq r_i < 1$ where $f(i, j) = g(j+r_i)$.

Since $f(i, j) = i + j(j-1)/2 $ a candidate is simply, $g(j) = j(j-1)/2$

Then we let $x=j+r_i$, find $x$ that solves $n = g(x)$, and thus obtain $j= \lfloor x\rfloor$ .

$\endgroup$
  • $\begingroup$ Hi, @Graham Kemp. Could you please explain how you eliminated the variable $i$ to write the equation $x^2 - x - 2(n - 1) = 0$? $\endgroup$ – Hilder Vítor Lima Pereira Sep 7 '15 at 17:41
  • $\begingroup$ @Vitor added some detail. $\endgroup$ – Graham Kemp Sep 7 '15 at 23:25
0
$\begingroup$

As I said in the question

I'm trying to find a injection from B to A.

I managed to do it in the following way: Fix some value for $N$ and distribute the values of the set $B = \Bigl\{1, 2, \ldots, \frac{N(N+1)}{2} \Bigr\}$ on the upper-triangular part of a $N \times N$ matrix. For instance, to $N = 5$, $B$ is $\{1, 2, 3, ..., 15\}$, so

$$\begin{bmatrix} 1 & 2 & 4 & 7 & 11\\ * & 3 & 5 & 8 & 12\\ * & * & 6 & 9 & 13\\ * & * & * & 10 & 14\\ * & * & * & * & 15\\ \end{bmatrix}$$

Now, note that each column $j$ has exactly $j$ elements. So, the first element of a given column $j$ is equal to the number of elements in all the previous column plus one: $(1 + 2 + 3 + ... + j - 1) + 1$.

Using the following formula to the sum of elements in a arithmetic progression:

$$1 + 2 + 3 + ... + j - 1 = \frac{j(j - 1)}{2}$$

we find that the first element of a given column $j$ is the value $\frac{j(j - 1)}{2} + 1$.

With the same analysis, we can see that the second element is $\frac{j(j - 1)}{2} + 2$ and so on.

Then, a value $k \in B$ is in column $j$ if and only if $k = \frac{j(j - 1)}{2} + l$ for some $1 \le l \le j$. Using Baskara to invert this equality, we get $j(k) = \frac{1 + \sqrt{1 + 8(k - l)}}{2}$.

Since this function $j$ grows assuming non integer values for $l \not = 1$, we can use $l = 1$ and take the floor:

$$j(k) = \Big\lfloor \frac{1 + \sqrt{1 + 8(k - 1)}}{2} \Big\rfloor$$

Finally, any value $k \in B$ that lies in a column $j$ is of the form $\frac{j(j - 1)}{2} + i$, then, the index $i$ (the line) is given by

$$i(k) = k - \frac{j(k)(j(k) - 1)}{2}$$

and the injection from $B$ to $A$ is

$$f(k) = (i(k), j(k))$$

$\endgroup$

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.