Condensed matrix function to find pairs

The formula for an index of the condensed matrix is

index = d * (d - 1) / 2 - (d - i) * (d - i - 1) / 2 + j - i - 1

Where i is the row index, j is the column index, and d is the row length of the original (d X d) upper triangular matrix.

Consider the case when the index refers to the leftmost, non-zero entry of some row in the original matrix. For all the leftmost indices,

j == i + 1

so

index = d * (d - 1) / 2 - (d - i) * (d - i - 1) / 2 + i + 1 - i - 1
index = d * (d - 1) / 2 - (d - i) * (d - i - 1) / 2

With some algebra, we can rewrite this as

i ** 2 + (1 - (2 * d)) * i + 2 * index == 0

Then we can use the quadratic formula to find the roots of the equation, and we only are going to care about the positive root.

If this index does correspond to leftmost, non-zero cell, then we get a positive integer as a solution that corresponds to the row number. Then, finding the column number is just arithmetic.

j = index - d * (d - 1) / 2 + (d - i) * (d - i - 1)/ 2 + i + 1

If the index does not correspond to the leftmost, non-zero cell, then we will not find an integer root, but we can take the floor of the positive root as the row number.

def row_col_from_condensed_index(d,index):
    b = 1 - (2 * d) 
    i = (-b - math.sqrt(b ** 2 - 8 * index)) // 2
    j = index + i * (b + i + 2) // 2 + 1
    return (i,j)  

If you don't know d, you can figure it from the length of the condensed matrix.

((d - 1) * d) / 2 == len(condensed_matrix)
d = (1 + math.sqrt(1 + 8 * len(condensed_matrix))) // 2 

You may find triu_indices useful. Like,

In []: ti= triu_indices(5, 1)
In []: r, c= ti[0][5], ti[1][5]
In []: r, c
Out[]: (1, 3)

Just notice that indices starts from 0. You may adjust it as you like, for example:

In []: def f(n, c):
   ..:     n= ceil(sqrt(2* n))
   ..:     ti= triu_indices(n, 1)
   ..:     return ti[0][c]+ 1, ti[1][c]+ 1
   ..:
In []: f(len(c), 5)
Out[]: (2, 4)

Cleary, the function f you are searching for, needs a second argument: the dimension of the matrix - in your case: 5

First Try:

def f(dim,i): 
  d = dim-1 ; s = d
  while i<s: 
    s+=d ; d-=1
  return (dim-d, i-s+d)