Linear indexing in symmetric matrices

Question

We can access matrices using linear indexing, which follows this pattern

0 1 2

3 4 5

6 7 8

It's easy to get the i,j coordinates for this case (n is the matrix dimension). For 0-index based, it would be.

i = index / n

j = index % n

Now, what if my matrix is symmetric and I only want to access the upper part

0 1 2 3

.. 4 5 6

..... 7 8

........ 9

I know the linear index will be given by

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

but I want to know i,j given idx. Do you guys know of any way of doing this?. I looked up this here, but I couldn't find an answer. Thanks in advance.

Answer 1

If you want to use the indexing that you used, and you want to avoid the loop you can invert the function for the indexing. I will use k to denote the linear index, and all indices are zero based. As you have noted

k = j + n*i - i*(i-1) /2.

Seeing as we are working with positive integers here, and the fact that all combinations (i,j) map onto a distinct k means that the function is invertible. The way in which I would do this is to note first of all that

j = k - n*i + i*(i-1)/2

such that if you can find the row which you are on, the column is defined by the above equation. Now consider you want the row, which is defined as

row = min{ i | k - ni + i(i-1)/2 >= 0 }.

If you solve the quadratic equation k - ni + i(i-1)/2 = 0 and take the floor of the i, this gives you the row, i.e.

row = floor( (2n+1 - sqrt( (2n+1)^2 - 8k ) ) / 2 )

then

j = k - row * n + row * (row-1)/2.

In pseudocode this would be

//Given linear index k, and n the size of nxn matrix
i = floor( ( 2*n+1 - sqrt( (2n+1)*(2n+1) - 8*k ) ) / 2 ) ;
j = k - n*i + i*(i-1)/2 ;

This removes the need for the loop, and will be a lot quicker for large matrices

Answer 2

Since nobody has posted a Matlab solution yet, here's a simple one-liner:

idxs = find(triu(true(size(A))))

Given matrix A, this will return a vector of all your indices, such that idxs(k) returns the k-th linear index into the upper triangular portion of the matrix.

Answer 3

This is comment to Keeran Brabazon answer. k = j + ni - i(i-1) /2 - this is equation from your post and it's wrong, the correct equation is k = j + (2*n -1 -i)*i/2. But we can't use it for finding i.

Equation from your post could be used to find i(row index), but we can't substitue i into your equation and get j, therefore formula for j in your post is wrong, so the final result will be looks like this:

i = floor( ( 2*n+1 - sqrt( (2n+1)*(2n+1) - 8*k ) ) / 2 ) ;(exactly like yours)

j = k - (2*n-1- i)*i/2; (different from your version, and i'm getting it by substituting i into my equation)