9

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.

2
  • In Matlab at least, matrices are row dominant so your indexing is off. Can you not use Matlab's native triu function or do you really only need those indices as opposed to an upper triangular matrix? And why both c++ and Matlab tags? What are you actually looking for?
    – horchler
    Commented Oct 2, 2013 at 18:15
  • There's a function in MATLAB called ind2sub. You can try that out. Commented Oct 2, 2013 at 18:59

8 Answers 8

10

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

2
  • 1
    +1 Awww, I was just adding something along these lines to my loop answer. Note that this gives j as relative to the row. For instance, with n=4,k=8 I get i=2,j=1. If you want j relative to the matrix as a whole, add i to the result.
    – Geobits
    Commented Oct 2, 2013 at 18:58
  • Yeah, the problem is that my index expression is wrong, it should be: "k = j + n*i - i*(i-1) /2 - i", but now obtaining the equation is not as straightforward because the solution of the quadratic equation is: i = floor( ( 2*n-1 - sqrt( (2n-1)*(2n-1) - 8*k ) ) / 2 ) ; and it can have imaginary roots.
    – balborian
    Commented May 1, 2017 at 18:15
4

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.

0
2

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)

1

Loop through your rows, keeping track of the offset of each one 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's just pseudocode, but it should work. As horchler says, make sure your indexing is correct. I used i,j here as you had it in your example, but it just feels weird to me.

0

Here's 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;
0

For 0-index based:

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

You can use this

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

which is an update on the answer of Matt. B, because you want row-wise representation.

0

MATLAB ships with built in functions ind2sub and sub2ind. Please check the documentation of MATLAB.

Please note that in MATLAB the linear indexing is going down the rows and indexing starts with 1

Example: for a 3 x 3 matrix

1 4 7

2 5 8

3 6 9

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.