Linear Indexing in Symmetric Matrices

Question

We can access matrices using the linear indexing that follows this pattern.

0 1 2

3 4 5

6 7 8

It is easy to obtain the coordinates i, j for this case (n is the size of the matrix). For a 0-based index, this will be.

i = index / n

j = index% n

Now, what if my matrix is ​​symmetrical and I want to access the top

0 1 2 3

.. 4 5 6

..... 7 8

........ nine

I know that a linear index will be given

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

but I want to know that i, j is given by idx. Do you guys know any way to do this? I looked at it here, but I could not 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 indexing. I will use k to denote a linear index, and all indices are zero based. As you noted

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

Seeing that we are working with positive integers here, and the fact that all combinations (i, j) are mapped to a separate k means that the function is invertible. The way I do this is, first of all, to note that

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

so if you can find the row you are in, the column is determined by the equation above. Now consider that you need a string that 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 occupy the floor i, this gives you a line, i.e.

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

then

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

In pseudo code it will 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 eliminates the need for a loop and will be much faster for large matrices.

Answer 2

Since no one has published the Matlab solution yet, here is a simple one-liner:

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

Given a matrix A this will return the vector of all your indices, so idxs(k) returns the kth linear index to the upper triangular part of the matrix.

Answer 3

Scroll through the lines, tracking the offset of each of them and the starting index for each:

 offset = 0; startOfRow = 0; for(i=0;i<height;i++){ endOfRow = startOfRow + (width - offset); if(idx < endOfRow){ j = (idx - endOfRow) + width; return {i,j}; } else { startOfRow = endOfRow; offset++; } } 

I don't know Matlab, so it is just pseudo-code, but it should work. As horchler says, make sure your indexing is correct. I used i,j here, as in your example, but it seems strange to me.

Answer 4

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

The equation from your message can be used to search for i (the row index), but we cannot substitute i in your equation and get j, so the formula for j in your message is incorrect, so the final result will look like this:

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

j = k - (2 * n-1-i) * i / 2; (unlike your version, and I get it, replacing me with my equation)

Answer 5

Here is the simplest method I could think of:

 int i = 1, j, x=n; while (idx > x) { i++; idx=idx-x; x--; } j=idx+(i-1); return i, j; 

Answer 6

For an index based on 0:

 int j = 0; int x = (n-1); while (idx > x) { j++; idx=idx-x; x--; } i=idx; 

Answer 7

You can use this

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

which is an update of Matt's answer. B because you want a string representation.