iterate matrix without nested loop

Question

I want to iterate the entries above the main diagonal of a square matrix of size n without using nested loops.

For example if the matrix M is of size n=3, then there are choose(3,2)=3 entries above the diagonal. where choose is the binomial coefficient.

for(i=1 to choose(n,2))
  row = getRow(i)
  col = getCol(i)
  M[row,col] = some value

I have not been able to come up with a formula for getting row and col based on index i.

For example:

for a matrix of size = 3 and indexes starting at 1,

i=1 corresponds to row = 1 and col = 2

i=2 corresponds to row = 1 and col = 3

i=3 corresponds to row = 2 and col = 3

Answer 1

You can use triu command of MATLAB as follows:

n=5; %user input

mat=magic(n);
nRows=size(mat,1);
nCols=size(mat,2);  

%extract the elements above the main diagonal  
u=triu(mat).*(~eye(n));
uT=u.'; %transpose to get the indices in the order you mentioned

%arrange it in a vector
u_ind=uT(uT~=0);

u_ind will contain the elements above the upper triangle in the desired format i.e. u_ind(3) will contain the element at row=1 and col=4.

To get these row and column indices, you can get them as follows:

%You can easily get this if you make simple observations. For a matrix of size 5x5
%the number of total elements above main diagonal are: (4+3+2+1)
%i.e. sum of first n-1 elements -> hence the formula below
totalIndices=0.5*n*(n-1);

%number of elements per row you get
indicesPerRow=n-1:-1:1

%I observed that there is some relation between its index and its (row,col) subscript.
%If the index is 5 in a 5x5 matrix, then you can imagine that it is the first non-zero 
%element in the second row -> because first row has 4 elements. If the index was 8, 
%similarly, it would have been first non-zero element in the third row in the upper 
%triangular matrix we have formed. This is what I have translated into code below.

ind1=cumsum(indicesPerRow);
ind2=ind1;

%Enter the number whose (row,col) index you want to find.
myInd=9;
ind2(ind1<myInd)=[];
pos=find(ind1<myInd,1,'last');
ind2=ind2(1);
ind3=rem(ind2,myInd);
detRow=pos+1;
detCol=nCols-ind3;

fprintf('Index %d corresponds to (row,col)=(%d,%d)\n',myInd,detRow,detCol);

Answer 2

So you want a formula ! Ok ! Lets go for some simple maths:

The number of entry of the r first rows is r*(r+1)/2. Therefore row is the largest integer number such that row*(row+1)/2 <= i. So row is the integer part of the positive solution of the equation

row*(row+1)/2 = i

it rewrites as

row^2 + row - 2*i = 0

This is a 2nd degree equation so you can solve it using square roots. The positive solution is (sqrt(1+8*i) - 1)/2.

So you have:

row(i) = floor((sqrt(1+8*i) - 1)/2)
col(i) = i - row*(row+1)/2

Demo in Python:

def rc(i):
    r = floor((-1 + sqrt(1+8*i))/2)
    return (r, i-r*(r+1)/2)

Test:

print [rc(i) for i in range(20)]
[(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2), (3, 3), 
 (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4)]

With the correct presentation

(0, 0), 
(1, 0), (1, 1), 
(2, 0), (2, 1), (2, 2), 
(3, 0), (3, 1), (3, 2), (3, 3), 
(4, 0), (4, 1), (4, 2), (4, 3), (4, 4), 
...

Note: I'm starting all my indices with 0. You have to shift i, r and c by one if you want to stick with the usual numbering.

Answer 3

You can try:

n = 3;

for(int i = 1; i <= n; i++) 
{
    for(int j=i+1; j<=n; j++) 
    {
        row = i;
        col = j;
    }
}

result:
1,2
1,3
2,3