Solution to the ARML Scrimmage Power Question « The Unapologetic Mathematician

Solution to the ARML Scrimmage Power Question

Today I’ll give my own solution to the power question I posted last week. I’m going to present it as I always wished I could have: as a whole with answers to the specific questions spun off as they naturally arise, rather than separated part by part.

First I’ll restate the setup into a more natural language. This is really a question about certain endomorphisms on vector spaces over the field $\mathbb{Z}_2$ . This is the quotient of the ring of integers by the maximal ideal generated by $2$ . If you haven’t seen it before, you should be able to construct it by all I’ve said so far.

Anyhow, the “arrangements” are just vectors in the vector space $\mathbb{Z}_2^n$ . Such a space comes with a basis $\{e_i\}_{i=1}^n$ , where $e_i$ has a $1$ in place $i$ and ${}0$ elsewhere. Each of these spaces of course has the identity endomorphism $I_n$ , and it also has a “left rotation” endomorphism $L_n$ sending $e_i$ to $e_{i-1}$ and $e_1$ to $e_n$ , and its inverse $R_n$ — right rotation. The transformation we are concerned with is $T_n=I_n+L_n$ .

Since we are given bases we are justified in writing out matrices for transformations, and even for vectors (because $V\cong\hom(\mathbb{Z}_2,V)$ ). The transformation $T_n$ has the matrix $(t_{i,j})$ where $t_{i,j}$ is $1$ if $j=i$ or $j=i+1$ and ${}0$ otherwise. A vector of length $n$ will be an $n\times1$ matrix.

Numbers 1 and 2 are just calculations, so I’ll omit them.

We can write $T_2$ as the matrix $\begin{pmatrix}1&1\\1&1\end{pmatrix}$ , so $T_2^2$ has matrix $\begin{pmatrix}1&1\\1&1\end{pmatrix}\begin{pmatrix}1&1\\1&1\end{pmatrix}=\begin{pmatrix}0&0\\ 0&0\end{pmatrix}$ , which sends every vector to the zero vector. This is part 4.

Now one interesting property we can see straight off. We can tell whether there are an even or an odd number of ones in a given arrangement by adding up all the entries. That is, we can take the product with the $1\times n$ matrix $p$ consisting of all ones. If we first transform an arrangement $a$ , then measure the number of ones, this is like taking the product $pT_na$ . But each column of the matrix for $T_n$ has exactly two ones in it, so the product $pT_n$ consists of all zeroes, and thus $pT_na$ is always zero. That is, the image of any arrangement after a transformation always has an even number of ones. That’s number 10.

What arrangements are fixed by the transformation? This amounts to solving the equation
$a=T_na=I_na+L_na=a+L_na$
so we must have $0=L_na$ or $a=R_n0=0$ . The zero vector is the only fixed point.

What vectors get sent to this fixed point? This is the kernel of the transformation — the vectors $a$ such that $0=a+L_na$ . Equivalently, these satisfy $a=L_na$ (why?). Thus all the entries must be the same, and the vector must consist of all zeroes or all ones. That’s number 9.

Now we see that if $T_n^ka=0$ then $T_n^{k-1}a$ is in the kernel of $T_n$ , and is thus either all zeroes or all ones. But if $n$ is odd, the vector consisting of all ones is not in the image of $T_n$ . Thus if we don’t start with a vector in the kernel we’ll never land in the kernel, and we’ll never get to the vector of all zeroes. That’s number 11. As a special case we have number 3.

Let’s consider $T_n^2$ . We expand this as $(I_n+L_n)(I_n+L_n)=I_n+L_n+L_n+L_n^2=I_n+L_n^2$ , since we’re working over $\mathbb{Z}_2$ . Similarly, if we square this we get $I_n+L_n^4$ . In fact, we have that $T_n^{2^k}=I_n+L_n^{2^k}$ . Indeed, this is true by definition for $k=0$ , and if it’s true for $k$ then
$T_n^{2^{k+1}}=(T_n^{2^k})^2=(I_n+L_n^{2^k})^2=I_n+(L_n^{2^k})^2=I_n+L_n^{2^{k+1}}$
so the claim is true by induction.

This means that after $2^k$ transformations a vector is sent to the sum (in $\mathbb{Z}_2$ ) of itself with its left-rotation by $2^k$ places. Thus if $2^k|n$ we can divide the entries in $a$ into $2^k$ vectors of length $\frac{n}{2^k}$ each — just pick the entries spaced out by separations of $2^k$ . Then $T_n^{2^k}$ acts on $a$ the same way $T_{\frac{n}{2^k}}$ acts on each of the subvectors, since the shift by $2^k$ places fixes the subvectors. That’s number 7. Parts 5 and 6 are now special cases.

Also, if $n=2^k$ then $L_n^{2^k}=I_n$ , so $T_n^{2^k}=0$ , so $2^k$ transformations send every vector of length $2^k$ to zero. That’s number 8.

Finally, let $n$ be any even number that is not a power of $2$ . Now the result of $T_n^{q2^k}a$ is the same as applying $T_n^q$ to each of the $2^k$ subvectors as described above. But now each subvector has odd length. If $a$ has a single $1$ in it, then one of these subvectors must contain it. By number 11 this subvector can never be sent to zero, so $T_n^{q2^k}a$ is never zero. If $T_n^ma$ were ever zero then $T_n^{qn^k}a$ would be for a large enough $q$ , which will never happen. That’s part 12.

May 31, 2007 - Posted by John Armstrong | Uncategorized | | 2 Comments

2 Comments »

I think there is an ‘a’ missing in the first sentence of 10. paragraph. There should be $T_n^{k-1}a$ .

Comment by mattiast | May 31, 2007 | Reply
[...] John, the Unapologetic Mathematician, Goes to a Grown-up math competition (ARML) and Gives a solution to a power question. [...]

Pingback by Carnival of Mathematics IX « JD2718 | June 2, 2007 | Reply

« Previous | Next »

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

Blogroll
Archives

May 2007

M T W T F S S

« Apr Jun »

1 2 3 4 5 6

7 8 9 10 11 12 13

14 15 16 17 18 19 20

21 22 23 24 25 26 27

28 29 30 31
Search for:
a

The Unapologetic Mathematician

Mathematics for the interested outsider