1 1 1 ...

0 1 1

1 0 1

0 0 1

1 1 0

0 1 0

1 0 0

0 0 0

:

:

Some of the most common applications/interpretations of this matrix are:

i) For any natural number N (of columns), the rows of the matrix (of which there is 2

^{N}) represent the set of all functions N→{0,1}., were N is a finite subset of the Natural numbers.

ii) The rows of a table thus generated, exhaust all truth value assignments to a propositional variable appearing in a formula of Propositional Calculus.

iii) Equivalently each row can be interpreted as the image of the characteristic function of a power set of some set S (we don't need to assume the axiom of countable choice since here we're dealing with finite sets). In other words each row of the matrix corresponds to a distinct combination of the elements of S. In fact the map

*f*:

*℘(S)→ ROWS (of the matrix) is a bijection:*

*(X)=r iff*

**f***r*(

*i*)=1 iff

*i*∈X, where we identify the matrix column indecies with the wellordering of the elements of S.

So clearly this matrix is a big deal, and subsequently the result here is an important one, since it basically compresses the entire matrix to a simple function of its rows and columns.

*i*has a 2

^{i-1 }iteration of 1's and 0's (starting with 1's in each column).

Below is the proof for the explicit formula of such matrices recurrence relations, i.e. as a function of the matrix' row and column number. That is, given only the row and column numbers, the formula gives the value that appears in the matrix on those 'coordinates'. That is, the formula takes the following functional form:

**: 2**

*θ*^{n}×

*n*→ {0,1}

EXAMPLE:

**(***θ**k*,*i*), where the row number is*k*= 7 and column number is*i*= 2, i.e.**(7,2) = 0.***θ*
Now for the proof, which I have only given a sketch of in a previous post. Subsequently I lost the proof, and only had the formula, which bothered me, so I re-proved it last week. So here we go. Most of the pattern recognition which underlies the solution is obviously to be found in the matrix itself, and the diagram below intends to capture and make salient those patterns which may not be so obvious at first glance. The

**, i.e. columns 1, 2, 3, 4,..., are the***integer numbered columns***of the matrix A.***actual columns*
To the right of each

*actual matrix*column*i*, I list*k*(mod 2^{i}), which is the first pattern that ought to be observed. Can you see how a single cycle of*k*(mod 2^{i}) matches the length of the pair of iterated 1's and 0's, in column*i*? The next key observation, and perhaps the crucial one, is that the pattern of out actual matrix columns is basically a function of*k*(mod 2^{i}). More precisely, note how each*i*'th actual column has the same pattern as*k*(mod 2^{i})−*k*(mod 2^{i-}^{1}), with the exception of being slightly 'misaligned' and having some product of 2 in the place there 1's ought to be. I have indicated the*k*(mod 2^{i})−*k*(mod 2^{i-}^{1}) rows with a yellow heading. Have a look for a while, and the pattern* should 'jump out'. Once you're convinced that it is so, all we need to do is (i) to rectify the 'misalignment', and (ii) the multiples of 2 integers instead of 1's. By noting that the 'misalignment' is also a function of column number, we see that adding 2^{i-}^{1}−1 to*k*, does the trick. Finally divide all values in each*i*'th column by 2^{i-}^{1}and we're basically done. That is, our formula can be expressed as the function:
This formula is good enough and does the trick, but using the identity below, relating the

**mod**and**floor**functions, it can make it more concise.
Giving the formula its final form. I guess it could be rendered even more concise and elegant with further algebraic fiddling, but I shall leave it there.

*Admittedly, a more rigorous proof is required than merely conjecturing that this pattern ought to hold in general. I may get around to it soon. But it does seem obvious that the proof is correct, since no surprises will arise in the relationship of the values of

If we switch the order of 1's and 0's in the table, i.e. if we let 0's precede 1's, like so (call this matrix B):

000...

100

010

110

001

101

011

111

:

:

Then the same reasoning yields a more elegant formula:

*k*(mod 2^{i}) and*k*(mod 2^{i-}^{1}) as both*k*and*i*increase.If we switch the order of 1's and 0's in the table, i.e. if we let 0's precede 1's, like so (call this matrix B):

000...

100

010

110

001

101

011

111

:

:

Then the same reasoning yields a more elegant formula:

## No comments:

Post a Comment