Base-n arithmetic and multi-dimensional matrices

Question

Interesting thing about binary numbers is to find their decimal value you can represent them as a multidimensional array, where each cell is indexed, starting from 0. For simplicity, let's start with 2-digit binary numbers:

$$\begin{matrix} &0&1&\\ 0&0&1&\\ 1&2&3& \end{matrix}$$

00₂ = 0, 01₂ = 1, 10₂ = 2, 11₂ = 2. We see that number of dimensions correspond to the maximum length of a binary number, so we can only represent 2-digit binary numbers with 2D matrix. The length of all dimensions correspond to the base. Let's try ternary (base-3) numbers:

$$\begin{matrix} &0&1&2&\\ 0&0&1&2\\ 1&3&4&5&\\ 2&6&7&8 \end{matrix}$$

Again, 22₃ = 8. But what if we try non-equal dimension lengths?

$$\begin{matrix} &0&1&&&&&0&1&2\\ 0&0&1&&&&0&0&1&2\\ 1&2&3&&&&1&3&4&5\\ 2&4&5&&&&2&6&7&8\\ 3&6&7&&&&3&9&10&11\\ 4&8&9&&&&4&12&13&14\\ 5&10&11&&&&5&15&16&17\\ \end{matrix}$$

Now these matrices no longer represent base-n numbers, but something else. Nevertheless, knowing row and column index, how do I find a value in the cell? In first matrix 11 = 5*2+1, in the second 17 = 5*3+2, but I don't see the general formula that I could apply to a multidimensional array. Let's try a 3D array, where a movement across the 3rd dimension is represented as a pair:

$$\begin{matrix} &0&1&2&\\ 0&(0, 1)&(2, 3)&(4, 5)\\ 1&(6, 7)&(8, 9)&(10, 11)&\\ 2&(12, 13)&(14, 15)&(16, 17)\\ 3&(18, 19)&(20, 21)&(22, 23)& \end{matrix}$$

Let $X$, $Y$, $Z$ be indexes across 1st, 2nd, 3rd dimensions, and let $|X|$, $|Y|$, $|Z|$ be lengths of these dimensions (maximum index + 1). Then to find a number 23 under a multidimensional index 321, you must calculate $3*3*2 + 2*2 + 1$. After thinking, I find that the formula is $X*|Y|*|Z| + Y*|Z| + Z$.

I see now that formula for finding decimal value of a binary number (or number in any base), $\sum_{i=0}^n\alpha_i*2^i$, is just a particular case of the above formula, where length of a every dimension equals 2.

I found this insight, when I was trying to represent an arbitrary multi-dimensional matrix as a list of list in Haskell. My question is, how do I connect this insight with math in general? I wouldn't have had to work from scratch, if I knew relevant math beforehand, so what is that math? What formulas and theorems are relevant for this question, what should I know and where to go from here? What important ideas I missed?

Answer 1

As far as I can tell, if you have $n$ indices in sets $X_1,X_2,\dots,X_n$, i.e. a "hypermatrix" with $n$ dimensions, and you fill the elements with numbers as in your example, then, in the $(i_1,i_2,\dots, i_n)-$th position you will find the number

$$|X_1||X_2|\cdots|X_{n-1}|i_1 + |X_1||X_2|\cdots|X_{n-2}|i_2 + |X_1||X_2|i_{n-2} + |X_1|i_{n-1} + i_n$$

There isn't much theorems or anything here, just basic arithmetic.

Answer 2

Your basic observation is that in an $n$ by $n$ array, if the columns and rows are labeled $0$ through $n-1$ and the numbers $0$ through $n^2-1$ are written in "reading order" in the table, then the number in cell $(i, j)$ ($j$ is the column) is the number written $ji$ in base $n$. This is obvious in retrospect: base $n$ representation is based on the idea of tallying things up, then as soon as we hit $n$ we reset our tally and make a note in $n$'s column. Here the column of the table represents our current tally and the row represents what we have in the $n$'s column.

If the same thing is done in an $n$ by $m$ table, then what we get is that the number in cell $(i, j)$ corresponds to the number $ji$ in a mixed $m$, $n$ base. See mixed radix.

I haven't worked out the details yet, but I imagine that the argument in the first paragraph can be used to show that essentially the same thing happens with higher-dimensional tables. That is, given an $n_1$ by $n_2$ by ... $n_k$ table, if the numbers from $0$ to $\prod n_i - 1$ are written in some special order in the cells of the table, then the number in cell $(i_1, ...i_k)$ should be equal to $i_k...i_1$ in the mixed radix base $n_1$, $n_2$, ... $n_k$.