This is my first post. I’m testing out the Hugo framework and the PaperMod theme, and getting familiar with the setup along the way (mostly code highlighting, markdown formatting, and equations 😆).

For this very first post — on the website I built right after graduating high school — I want to share an interesting problem underlying an AP Computer Science A question a friend asked me during senior year.

True or false: will i sometimes equal 3?

i = 3
j = 2
for _ in range(100):
  	i -= j	
  	j += i

The answer is true. This operation is actually periodic, with a period of $6$, regardless of the initial values of i and j!

Matrix Representation of a Linear Transformation

Here, i and j are updated linearly, so it’s natural to write the operation as a linear transformation — and therefore as a matrix transformation.

First, write out the iteration equations:

$$ i_{k+1} = i_{k} - j_k,\\ j_{k+1} = j_k + i_{k + 1} = j_k + (i_k - j_k) = i_k $$

or, equivalently, in vector form:

$$ \begin{pmatrix}i\\j\end{pmatrix}_{k+1} = \begin{pmatrix}i_k - j_k\\i_k\end{pmatrix} = \begin{pmatrix}1 & -1\\1 & 0\end{pmatrix}\begin{pmatrix}i\\j\end{pmatrix}_{k} $$

Denote

$$ A = \begin{pmatrix}1 & -1\\1 & 0\end{pmatrix}, \quad \boldsymbol x_k = \begin{pmatrix}i\\j\end{pmatrix}_k $$

so that

$$ \boldsymbol x_k = A^k \boldsymbol x_0 $$

Periodicity of the Linear Transformation

To show periodicity in the linear transformation $A$, we need $\boldsymbol x_p = A^p\boldsymbol{x_0} = I\boldsymbol x_0$ for some positive integer $p$ — that is, $A^p = I$.

You might quickly discover that $A^3 = -I$, which is enough on its own to show $A^6 = I$ and thus that $A$ has a period of $6$. But let’s give a more concrete proof here, using eigenvalues.

An eigenvalue of a linear transformation $T$ is a scalar $\lambda$ such that applying $T$ to some nonzero vector $\boldsymbol v$ has the same effect as multiplying $\boldsymbol v$ by $\lambda$:

$$ \lambda \in \mathbb F,\quad\text{s.t.}\quad T\boldsymbol v = \lambda \boldsymbol v $$

If an eigenvalue $\lambda$ of a linear transformation $T$ satisfies $\lambda^p=1$, then applying $T$ to $\boldsymbol v$ $p$ times returns $\boldsymbol v$ unchanged — which implies $T^p = I$. So $T$ has a period of $p$, and this holds independent of which nonzero eigenvector $\boldsymbol v$ we chose.

We can find the eigenvalues of a matrix by solving its characteristic equation:

$$ \det (A - \lambda I) = 0 $$

Plugging in our matrix $A$ gives:

$$ \begin{aligned} \det \begin{pmatrix}1 - \lambda & -1 \\ 1 & 0 - \lambda \end{pmatrix} &= 0\\ (1 - \lambda)(0 - \lambda) - (-1)(1) &= 0\\ \lambda^2 - \lambda + 1 &= 0\\ \Rightarrow \lambda_{1,2} = \frac{1 \pm \sqrt 3\mathrm i}{2} \end{aligned} $$

(where $\mathrm i$ is the imaginary unit, satisfying $\mathrm i^2 = -1$)

Recall that the $n$-th root of unity has the form $\exp(2\pi \mathrm i /n)$, namely:

$$ x^n = 1 \Rightarrow x = \exp\left(\frac{2\pi\mathrm i}{n}\right) $$

Take the root with positive imaginary part, $\lambda = \frac{1}{2} + \frac{\sqrt 3}{2}\mathrm i$, and compare it to the right-hand side of Euler’s formula:

$$ \exp (\mathrm i \theta) = \cos \theta + \mathrm i \sin \theta $$

This gives $\theta = \pi / 3$. Plugging back in:

$$ \lambda = \exp\left(\mathrm i \frac{\pi}{3}\right) = \exp\left(\frac{2\pi \mathrm i}{6}\right) $$

which is exactly a $6$-th root of unity.

Geometrically, if we place the complex number $\lambda$ on the complex plane, raising it to successive powers just spins it around:

  • on the unit circle $r = 1$, since $r = |\lambda| = \sqrt{(\frac{1}{2})^2 + (\frac{\sqrt 3}{2})^2} = 1$
  • at a fixed angle that’s a rational fraction of $2\pi$, since $\theta = \arctan (\Im \lambda / \Re \lambda) = 2\pi / 6$

which is exactly the geometric behavior of an $n$-th root of unity.

Transition matrices $A$ whose eigenvalues violate either of these properties won’t show periodicity — the vector on the complex plane will either grow or shrink in magnitude, or spin at an angle that never brings it back around to where it started.