Functions to pick up orderly the elements on the SW-NE half diagonals in a half matrix (lower triangular part)

Question

I wish to write a program that does the following, and I need some math help figuring out a simple formula to pick up elements in the lower triangular part of a matrix.

Consider the lower bottom-left half of a N x N matrix C, including the diagonal.

Starting from the top-left cell (1,1) and ending with the bottom right cell (N,N) consider all the cells C(i,j) on the oblique patterns "/" (do they have a name, half SW-NE diagonal maybe?):

(1,1)
(2,1)
(3,1) (2,2)
...
(r,1)(r-2,2) ... (r-h,h)     h <= r - h    (half SW-NE diagonal)
...
(N,N)

I wish to write a program to put all these cells - exactly in the order just described - into a unique uni-dimensional array A(u), u=1,... and I want to do that, with only one index u, using a formula like:

       i = f(u)
       j = g(u)  [ or, in case, even  j = g(u, i) ]

I'd like to understand the simplest way to find some simple explicit formula for f() and g().

So, in brief, the final program should look like:

for u = 1 to CountOfCellsInHalfMatrix
       i = f(u)
       j = g(u) 
       A(u) = C(i,j)
next

There should be a pretty simple formula for them, but I am confused. Could you outline a simple method to find them ?

I hope I explained clearly enough the goal (feel free to edit at will to make it clearer).

Answer 1

The easiest way to fill the array seems to be as follows:

u = 1
for i = 1 to N
     for j = 1 to ceiling(i/2)
          A(u) = C(i+1-j,j)
          u = u + 1

[This only does the top half; you can fill the rest similarly.]

However, if you really want to compute the $i$ and $j$ values, you can: the $u$-th term lies on the $k$-th diagonal, where $k=\lfloor\sqrt{4u-3}\rfloor$; then $j=u-\lfloor k^2/4\rfloor$ and $i=k+1-j$. Hint: start by computing $u$ in terms of $k$ and $j$: $u=\lfloor k^2/4\rfloor + j$.

Again, this only handles the diagonals which emanate from the left side of the matrix. The rest of the diagonals emanate from the bottom; they can be handled easily (without doing any more math) by using the fact that the last diagonals look just like the first ones, but we do them in the opposite order.

m = n(n+1)/2                 # total number of cells to fill
m0 = int ((n+1)^2/4)         # number we can do in the forward direction

for u = 1 to m
   if u <= m0
      k = int(sqrt(4u-3))
      j = u - int(k^2/4)
   else
      v = m - u + 1          # number of cells left to fill
      k0 = int(sqrt(4v-3))   # the earlier diagonal it looks like
      k = 2n - k0            # the actual diagonal we're on
      j = int((k0+1)^2/4) - v + k - n + 1
   end if
   i = k - j + 1
   assign A(i,j)
end for

The sequences of $k$ values and $j$ values both appear in Sloane's Online Encyclopedia of Integer Sequences, as A000267 and A122197 respectively. The above formula for the $j$'s appears to be new.