# What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the pattern continues, not that the matrix is infinite. Matrix A:

$$\begin{matrix} 1 & 1 & 1 & 1\cdots\\ 0 & 1 & 1 & 1\cdots\\ 1 & 0 & 1 & 1\cdots\\ 0 & 0 & 1 & 1\cdots\\ 1 & 1 & 0 & 1\cdots\\ 0 & 1 & 0 & 1\cdots\\ 1 & 0 & 0 & 1\cdots\\ 0 & 0 & 0 & 1\cdots\\ 1 & 1 & 1 & 1\cdots\\ 0 & 1 & 1 & 0\cdots\\ 1 & 0 & 1 & 0\cdots\\ 0 & 0 & 1 & 0\cdots\\ 1 & 1 & 0 & 0\cdots\\ 0 & 1 & 0 & 0\cdots\\ 1 & 0 & 0 & 0\cdots\\ 0 & 0 & 0 & 0\cdots\\ \vdots & \vdots & \vdots &\vdots \end{matrix}$$ I see such matrices (arrays) as rather mathematically interesting objects, which can be said to represent a number of things, e.g. it's rows can be taken to be in the images of characteristic functions of all the combinations on an $n$ element set; or as all the valuations on $n$ propositional variables, in a logical context. This is just naming a few canonical interpretations of $A$. Anyone who's done any introductory logic, discrete mathematics, or computer science would have seen such matrices.

It's columns are defined in a simple (as a recurrence relation?) manner. What interested me for sometime, was an explicit, functional representation of this matrix $A$, or it's sibling $B$ (with the $0$'s and $1$'s swapped). That is, I couldn't find anywhere the function:

$$\theta: \mathbb N \times \mathbb N \rightarrow \{0,1\}$$

Such that on row-number and column-number input, it gives the matrix value for that row-column coordinate.

Not succeeding in finding such a function, I decided to derive one myself (see below), for which I have a proof here. It's not the cleanest proof, but most of it is captured in a diagram that illustrates the key pattern, which makes it easier to follow. I'd appreciate any comments to the proof, or corrections if an error is spotted, or an obvious simple solution, which I missed, although that's not my main question here. The row "coordinate" is denoted with $k$ and the column one with $i$.

$$\theta(k,i)= \left\lfloor \frac {k-1}{2^{i-1}} \right\rfloor - 2\left\lfloor \frac {k-1}{2^{i}}+\frac 12 \right\rfloor +1$$

The solution to the sibling matrix $B$ turns out to have a simpler form (I think this is correct, but I'm not entirely sure):

$$\theta(k,i)= \left\lfloor \frac {k-1}{2^{i-1}} \right\rfloor - 2\left\lfloor \frac {k-1}{2^{i}} \right\rfloor$$

My question is this: where can I find a solution to this (perhaps someone can give a simpler one), or results that have this solution as an immediate corollary? Also, where could I read-up more about the properties of such matrices? For I can't believe that such solutions don't exist already, given the interesting nature of such mathematical objects.

I suspect that the above solutions are special cases of a more general result; even more general than merely extending the image of $\theta$ to $\{0,1,...,n\}$ for all $n \in \mathbb N$, which shouldn't be a difficult exercise (I actually have that extended solution somewhere).

• The sibling matrix formula looks right, and interesting. Likely one can get the other one from it. +1 on question... Apr 20, 2015 at 15:07
• If one choose the origin correctly, it is simply bit(y,mod(x,n)), i.e the (x modulo n)$^{th}$ bit of the number $y$. In programming language like $C$, it is equivalent to the expression (y>>(x%n))&1. Apr 20, 2015 at 16:14
• @coffeemath Thanks for the comment. Yes, just take the result from the B matrix formula, and add 1 to it modulo 2, right? Denote the theta from A or B with a subscript. So $\theta_A = (\theta_B+1)(mod\, 2)$, for all $k,i$ right? Or something like that. Apr 20, 2015 at 16:15
• @achillehui Thanks for that. I'll read up on it. Apr 20, 2015 at 16:29