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: 
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);

```
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.