Accessing elements of packed symmetric distance matrix

Question

Suppose you have a symmetric distance matrix A. For example A is 4*4 (the numbers above and on the left of matrix are the indices of elements between which the distance is measured, and we use only the lower triangle):

   0   1   2   3  
   _____________
0 |0   0   0   0
1 |a10 0   0   0
2 |a20 a21 0   0
3 |a30 a31 a32 0

So, basically, if A is n*n, we have only n*(n-1)/2 useful entries. Eliminating zeros on the diagonal, we have the following matrix (similar to what Matlab and R have):

A=     0   1   2  
       _________
    1 |a10 0   0
    2 |a20 a21 0
    3 |a30 a31 a32

Next, we can efficiently store this matrix in one-dimensional array in packed format having np = n*(n-1)/2 elements:

Ap = {a10, a20, a21, a30, a31, a32}

This can speed up many searches (e.g. searching for the pair of closest elements, etc) and save a lot of space (useful when n is large)

Accessing the distance between elements i and j is equivalent to accessing element j+i(i-1)/2 in packed matrix, i.e. A[i,j] = Ap[j+i(i-1)/2] for i>0, j<n-1, j<i.

The question is if we are in the opposite situation, i.e. we have the index of element in packed matrix Ap, how do we recover the original two indices: Given Ap[x], what are i and j in A, such that Ap[x] = A[i,j].

Thanks!

Answer 1

OK, I've found the answer:

i = floor{ (1 + sqrt[1 + 8*x])/2 }
j = x - i