plus or minus one question

rdj5933mile5math64 · **Posted:** Tue, 22 May 2012 16:16:07 UTC

Wasn't sure if this was the right forum for this problem.~

We are given a 2^k

-tuple - $(a_1, a_2, \dots , a_{2^k})$ , where a_i

is equal to either

or to

. We transform this 2^k

-tuple by replacing the original 2^k

-tuple with $(a_1a_2, a_2a_3 , \dots , a_{2^k}a_1)$ .
Prove that after a finite number of transformations we get $(1,1,1, \dots ,1)$ .

Hmmm I found an induction solution but I was wondering if there was a more tricky solution (possibly monovariants)?

outermeasure · **Posted:** Tue, 22 May 2012 16:54:46 UTC

rdj5933mile5math64 wrote:

Wasn't sure if this was the right forum for this problem.

We are given a 2^k

-tuple - $(a_1, a_2, \dots , a_{2^k})$ , where a_i

is equal to either

or to

. We transform this 2^k

-tuple by replacing the original 2^k

-tuple with $(a_1a_2, a_2a_3 , \dots , a_{2^k}a_1)$ .
Prove that after a finite number of transformations we get $(1,1,1, \dots ,1)$ .

Hmmm I found an induction solution but I was wondering if there was a more tricky solution (possibly monovariants)?

My solution: The desired result is equivalent to asserting the $2^k\times 2^k$ circulant matrix $\mathop{\mathrm{circ}}(1,1,0,\dots,0)=I+S$ over $\mathbb{F}_2$ , where

is the so-called fundamental circulant matrix of order 2^k

, is nilpotent. Now using the Frobenius homomorphism (and induct on

), we have $(I+S)^{2^k}=I+S^{2^k}=I+I=0$ , as claimed.

rdj5933mile5math64 · **Posted:** Tue, 22 May 2012 18:12:51 UTC

outermeasure wrote:

My solution: The desired result is equivalent to asserting the $2^k\times 2^k$ circulant matrix $\mathop{\mathrm{circ}}(1,1,0,\dots,0)=I+S$ over $\mathbb{F}_2$ , where

is the so-called fundamental circulant matrix of order 2^k

, is nilpotent. Now using the Frobenius homomorphism (and induct on

), we have $(I+S)^{2^k}=I+S^{2^k}=I+I=0$ , as claimed.

O.O whaaaaa? I'm not sure what most of this means.~ I looked up circulant matrices on wikipedia, but I have no clue how one can relate your first statement, to the original question. Hmmmmm I should learn algebra.

On a different note, I fail - I found out that there is a non-inductive solution (in addition to outermeasure's solution). Well, it depends on whether or not you count a certain combinatorial identity as proven by induction or not.

Shadow · **Posted:** Tue, 22 May 2012 23:53:31 UTC

rdj5933mile5math64 wrote:

outermeasure wrote:

My solution: The desired result is equivalent to asserting the $2^k\times 2^k$ circulant matrix $\mathop{\mathrm{circ}}(1,1,0,\dots,0)=I+S$ over $\mathbb{F}_2$ , where

is the so-called fundamental circulant matrix of order 2^k

, is nilpotent. Now using the Frobenius homomorphism (and induct on

), we have $(I+S)^{2^k}=I+S^{2^k}=I+I=0$ , as claimed.

O.O whaaaaa? I'm not sure what most of this means.~ I looked up circulant matrices on wikipedia, but I have no clue how one can relate your first statement, to the original question. Hmmmmm I should learn algebra.

On a different note, I fail - I found out that there is a non-inductive solution (in addition to outermeasure's solution). Well, it depends on whether or not you count a certain combinatorial identity as proven by induction or not.

Basic abstract algebra is commonly found in college-level mathematics, it's not unusual that such a solution would not occur to you.

rdj5933mile5math64 · **Posted:** Wed, 23 May 2012 02:58:33 UTC

Shadow wrote:

Basic abstract algebra is commonly found in college-level mathematics

But all of my friends are doing it.

The only 2^k

-tuples that become $(1,1,1, \dots ,1)$ are the ones described above. It's proven by working backwards.

Now, the idea behind my *improved* solution is to look at

Spoiler:

and

Spoiler:

The original solution only used induction and the first part.

Shadow · **Posted:** Wed, 23 May 2012 03:18:47 UTC

rdj5933mile5math64 wrote:

But all of my friends are doing it.

It sounds as if you need a much more diverse group of friends.

outermeasure · **Posted:** Wed, 23 May 2012 06:45:48 UTC

rdj5933mile5math64 wrote:

outermeasure wrote:

My solution: The desired result is equivalent to asserting the $2^k\times 2^k$ circulant matrix $\mathop{\mathrm{circ}}(1,1,0,\dots,0)=I+S$ over $\mathbb{F}_2$ , where

is the so-called fundamental circulant matrix of order 2^k

, is nilpotent. Now using the Frobenius homomorphism (and induct on

), we have $(I+S)^{2^k}=I+S^{2^k}=I+I=0$ , as claimed.

O.O whaaaaa? I'm not sure what most of this means.~ I looked up circulant matrices on wikipedia, but I have no clue how one can relate your first statement, to the original question. Hmmmmm I should learn algebra.

On a different note, I fail - I found out that there is a non-inductive solution (in addition to outermeasure's solution). Well, it depends on whether or not you count a certain combinatorial identity as proven by induction or not.

Write your tuples of $\pm 1$ as $((-1)^{b_1},(-1)^{b_2},\dots,(-1)^{b_{2^k}})$ and look at $\mathbf{b}=\begin{pmatrix}b_1&\dots&b_{2^k}\end{pmatrix}$ --- a vector over $\mathbb{F}_2$ due to the ambiguity in the choice of b_i

from

. The effect of your mapping on $\mathbf{b}$ is $\mathbf{b}\mapsto \mathbf{b}(I+S)$ . Hence the statement every tuple $(a_1,\dots,a_{2^k})$ will eventually end up as $(1,1,\dots,1)$ is equivalent to saying $\mathbf{b}(I+S)^{N}=\mathbf{0}$ for all $\mathbf{b}$ and large enough

--- which is the same as saying I+S

is nilpotent in $M_{2^k}(\mathbb{F}_2)$ .

rdj5933mile5math64 · **Posted:** Thu, 24 May 2012 17:50:32 UTC

Oh ok I understand now! Thanks outermeasure!

S.O.S. Mathematics CyberBoard

plus or minus one question

Who is online