How to find a function mapping matrix indices?

Solution 1:

In general, for an $n \times k$ matrix, the entry in row $i$, column $j$ (starting with $i = j = 1$ rather than $i = j = 0$, which is what many programming languages use), is the $$ k(i-1) + j $$ entry of the matrix, when the entries are read in left-to-right order in each row, and then top to bottom.

Why? Because to get to the $j$th entry of row $i$, you have to go through $i-1$ rows, each with $k$ entries, and then $j$ more steps.

ADDITION: the OP notes that s/he wants to index only the entries of the upper triangle, and that both indices in the matrix go from $0$ to $n-1$; in particular, the matrix is square. For the $3 \times 3$ case, the answer should look like this: $$ \begin{bmatrix} x & 0 & 1 \\ x & x & 2 \\ x & x & x \end{bmatrix} $$ where $x$s are unlabeled elements, and other entries indicate the label for the entry.

Observation: this would be a lot easier if it were a lower triangular matrix. I'm going to solve it in that case, and then swap $i$ and $j$, effectively transposing the solution. Why's the lower-triangular case easier? Because as you work forward, you've got larger and larger triangles you've accumulated, rather than larger and larger truncated triangles. So for the $4 \times 4$ case, I want to get this: \begin{bmatrix} x & x & x & x \\ 0 & x & x & x \\ 1 & 2 & x & x \\ 3 & 4 & 5 & x \end{bmatrix}

First of all, a triangle with $n$ nodes on a side has $T(n) = n(n+1)/2$ nodes in it; in this case, that means that we'll be producing outputs for exactly $k = T(n-1) = (n-1)n/2$ entries of the matrix, and these outputs will range from $0$ to $k-1$.

Let's look at the $(i, j)$ entry, (where $j < i$, because we're working in the lower triangle). When $i = 1$ (2nd row), we're working with the first row of the triangle of valid indices (which I'm going to call "the triangle" from now on). In general, when we look at $(i, j)$, we'll be in the $I$th row of the triangle.

How many entries are "used up" by the time we get to the $i$th row? Well, let's look at $i = 3$ in the example: we've used up $0, 1, 2$, i.e., 3 entries. And $3 = T(2)$. So in general, at the start of the $i$th row, we've already used up $T(i-1)$ entries, starting at 0; the outputs $$ 0, 1, \ldots, T(i-1)-1 $$ have already been allocated. That means that the first entry of the $i$th row is $T(i-1)$. The second entry (when $j = 1$) is one larger, and so on. So the $(i,j)$ entry corresponds to $$ T(i-1) + j. $$ Let's check that out for some particular values. What about $(i, j) = (2, 1)$? We have $T(1) + 1 = 1 + 1 = 2$. And that's the correct answer! (Remember that rows and cols are indexed from zero). What about $(i, j) = (1, 0)$? We get $T(0) + 0 = 0$. Yep .. that's right, too. So we're on the right track.

But for the upper triangular matrix, we have to swap the roles of $i$ and $j$, so the correct answer is $$ T(j-1) + i = \frac{(j-1) j}{2} + i = \frac{ j(j-1) + 2i }{2}. $$

And there you have it.

As OP notes, there's a problem, though: the result, in the 4x4 case, is $$ \begin{bmatrix} x & 0 & 1 & 3 \\ x & x & 2 & 4 \\ x & x & x & 5 \\ x & x & x & x \end{bmatrix} $$ because increasing row index in the lower-triangle becomes increasing column index in the upper triangle. Sigh. Let's begin again, aiming to produce this: $$ \begin{bmatrix} x & x & x & x \\ 0 & x & x & x \\ 1 & 3 & x & x \\ 2 & 4 & 5 & x \end{bmatrix} $$ which is, after all, the transpose of the thing we eventually want.

Once again, let $k = T(n-1)$; in this case, $k = 6$, and the outputs range from $0$ to $k-1$.

When we're at location $(i, j)$, the stuff in the "output triangle" that's in or to the right of column $j$ is a triangle of size $(n - j)-1$. Let's check that in our $4 \times 4$ case: the entry labeled "4" is at $(i, j) = (3, 1)$, so $j = 1$; the triangle including that row and stuff to the right (i.e., entries 3,4,5) has size $2$, which is $(n - j) - 1 = 4 - 1 - 1 = 2$; the triangle has $T(n-j-1)$ elements. That means that the last entry of the column to the left of $j$ must be $$ T(n-1) - T(n - j - 1) - 1 $$

Let's check that: $T(n-1) = T(3) = 6$, and $T(n-j-1) = T(2) = 3$; the last entry of the previous column is $2$, which is indeed $6 - 3 - 1$. Good.

(I'm doing this kind of check on each formula because it's so easy to make off-by-one errors.) Let's check one more: The entry $2$, is column $j = 0$. The formula tells us that the last entry of the previous column should be $$ T(n-1) - T(n - j - 1) - 1 = T(n-1) - T(n - 0 - 1) -1 \\ = T(n-1) - T(n-1) -1 \\ = -1. $$ and that makes sense, in that the first entry of column $0$ is a zero.

We now know that the entries of column $j$ can be written in the form $$ T(n-1) - T(n-j-1) + i + \text{something}. $$ The first two terms give the output for the first non-$x$ entry of column $j$. The $+i$ makes the value increase by one for each row-increase. The problem is that the counting shouldn't start until $i = j+1$. So when $i = j+1$, we want to add 0 to the initial value $T(n-1) - T(n-j-1)$; when $i = j+2$, we want to add $1$ to the initial value, and so on. So the general form is $$ T(n-1) - T(n-j-1) + (i - (j+1)) $$ Let's check that for the entry whose output is $3$. That's the $(i, j) = (2, 1)$ entry. The formula says that the output is \begin{align} T(n-1) - T(n-j-1) + (i - (j+1)) &= T(3) - T(4-1-1) + (2 - (1+1)) \\ &= T(3) - T(2) + (2 - 2) \\ &= 6 - 3 + (0) \\ &= 3 \end{align}

So that's the formula. We can do a little algebraic simplification to get \begin{align} T(n-1) - T(n-j-1) + (i - (j+1)) &= \frac{ (n-1)n}{2} - \frac{(n-j-1)(n-j)}{2} + \frac{2i - 2j - 2}{2} \\ &= \frac{ n^2-n}{2} - \frac{(n^2-jn-n)-(nj-j^2-j))}{2} + \frac{2i - 2j - 2}{2} \\ &= \frac{ n^2-n}{2} - \frac{n^2-2jn + j^2-n+j}{2} + \frac{2i - 2j - 2}{2} \\ &= \frac{ n^2-n - n^2+2jn - j^2+n-j}{2} + \frac{2i - 2j - 2}{2} \\ &= \frac{ -n +2jn - j^2+n-j + 2i - 2j - 2}{2}\\ &= \frac{ 2jn - j^2 -j + 2i - 2j - 2}{2}\\ &= \frac{ 2jn - j^2 + 2i - 3j - 2}{2}\\ \end{align}

Finally, because this was all done for the lower triangle, we'll transpose, to get $$ R = \frac{ 2in - i^2 + 2j - 3i - 2}{2}. $$ where $R$ is the counter-value assigned to location $(i, j)$, where $j > i$, and we're counting elements of the upper triangle of an $n \times n$ matrix, and both $i$ and $j$ indices run from $0$ to $n-1$.

Surely this is not the simplest way to do this problem -- I'm sure one can write down some magic with recursion and difference equations -- but it's fairly straightforward, and you can apply the same approach to similar problems.