1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot Tad! Yes i was aware of the fact that i could use the double loop, but i was really interested in the f(), g(), as you have been developing. Now I have tried the above and it seems (unless i got it wrong) you almost nailed it, except you are keeping out the terms on the diagonal. $\endgroup$ – Pam Jul 14 '13 at 10:04
  • $\begingroup$ For instance, for N=6, we should have: (1,1) (2,1) (3,1) (2,2) (4,1) (3,2) (5,1) (4,2) (3,3) (6,1) (5,2) (4,3) (6,2) (5,3) (4,4) (6,3) (5,4) (6,4) (5,5) (6,6) But your formula seems to give: (1,1) (2,1) (3,1) (3,2) (4,1) (4,2) (5,1) (5,2 (5,3) (6,1 (6,2) (6,3) (7,1) (7,2) (7,3) (7,4) (8,1) (8,2) (8,3 (8,4 (9,1 $\endgroup$ – Pam Jul 14 '13 at 23:39
  • 1
    $\begingroup$ Quite right -- my i was keeping track of which antidiagonal, not which row. Have edited the response accordingly, and provided more complete pseudocode. $\endgroup$ – Tad Jul 16 '13 at 5:09
  • 1
    $\begingroup$ The crux is to figure out which diagonal you're on at the u-th step. This sequence looks like 1,2,3,3,4,4,5,5,5,6,6,6,... Suppose you're given such a nondecreasing sequence {A(u): u>=0} which contains L(n) copies of n (here L(n)=floor(n/2)). Let S(n)=sum {L(k): k<n} (in your case S(n)=floor(n^2/4)). Note S(n) is the index of the first occurrence of n in the A sequence; in fact A(u)=n iff S(n) <= u < S(n+1). If S has an inverse, we conclude that A(u)=floor(S^{-1}(u)) [in your case floor(sqrt(4u-3)).] $\endgroup$ – Tad Jul 18 '13 at 4:37
  • 1
    $\begingroup$ (continued) Your j keeps track of which of the L(n) copies of n we're looking at. But S(A(u)) is the index of the first copy of A(u), so u-S(A(u)) tells us which copy we're looking at (if we index starting at 0.) The math works out easiest if you index everything starting with 0, so some touching up was required for your problem. For an exercise, you can try this out on [oeis.org/A002260], which are the j's when L(n)=n. Enjoy! $\endgroup$ – Tad Jul 18 '13 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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