{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Collatz Conjecture as an Eigenvector Problem\n", "======================\n", "\n", "https://en.wikipedia.org/wiki/3x_%2B_1_problem\n", "\n", "The sequence of integers generated the accelerated relation $$ f(x) = \\left\\{ \\begin{array} & \\frac{3x + 1}{2} & x \\text{ odd} & \\\\ \\frac{x}{2} & x \\text{ even} \\end{array} \\right.$$ can be considered a Markov chain where each number in the sequence is a state and the probability of the next state is exactly 1. Encoding the state as a 1-Hot vector we have \n", "$$ x_{n} = \\left( \\begin{array} & 0 & 0 & \\cdots & 1 & 0 & \\cdots \\end{array} \\right)^T$$\n", "where the vector is filled with zeros except at the position corresponding to the integer it is encoding where it is 1. The $x_{n}$ is natually a _normal_ vector.\n", "\n", "With this notation we can define the relatión between $x_{n}$ and $x_{n+1}$ as \n", "$$ x_{n+1} = Ax_{n} $$\n", "where \n", "$$ A = \\begin{pmatrix} \n", "0 & 1 & 0 & 1 & \\cdots \\\\\n", "1 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 0 & 1 & 0 & \\cdots \\\\\n", "0 & 0 & 0 & 0 & \\cdots \\\\\n", "\\vdots & \\vdots & \\vdots & \\vdots & \\ddots \\\\\n", "\\end{pmatrix} $$\n", "\n", "__Theorem__\n", "\n", "Let $\\upsilon_{t}$ be the average value of $x_{n}$ over $t$ steps:\n", "$$ \\upsilon_{t} = \\frac{1}{t} \\sum_{s=0}^{t} x_{s}$$. \n", "\n", "Then there is a set of eigenvectors $\\Pi$ such that $A\\pi = \\pi$ where $\\pi \\in \\Pi$.\n", "\n", "For all $x_{n}$ then $$\\pi = \\lim_{t \\to \\infty} \\upsilon_{t}$$ and can be interpreted as the stationary probability distribution of the operator A.\n", "\n", "__Proof__\n", "\n", "Show that $$\\lim_{t \\to \\infty} \\left| A\\upsilon_{t} - \\upsilon_{t} \\right| \\to 0$$\n", "\n", "Expand as $$\\lim_{t \\to \\infty} \\left| \\frac{A}{t} \\sum_{s=0}^{t} x_{s} - \\frac{1}{t} \\sum_{s=0}^{t} x_{s} \\right|$$ \n", " $$\\lim_{t \\to \\infty} \\frac{1}{t} \\left| (Ax_{0} + Ax_{1} + \\cdots + Ax_{t}) - (x_{0} + x_{0} + \\cdots + x_{t}) \\right|$$ \n", " $$\\lim_{t \\to \\infty} \\frac{1}{t} \\left| (x_{1} + x_{2} + \\cdots + x_{t+1}) - (x_{0} + x_{0} + \\cdots + x_{t}) \\right|$$ \n", " $$\\lim_{t \\to \\infty} \\frac{1}{t} \\left| x_{t+1} - x_{0} \\right|$$ \n", "\n", "But $x_{0}$ and $x_{t+1}$ are one-hot (normal) vectors so their difference can be at most 2. So the limit is satisfied.\n", "\n", "Given that in the limit as $t \\to \\infty$, $\\upsilon_{t}$ is the average value of $x_{n}$ then if the number represented by $x_{n}$ is NOT in a cycle then its average value will tend to 0. Similarly values in a cycle will tend to some non-zero value inversely proportional to the length of the cycle.\n", "\n", "The Collatz Conjecture is equivalent to requiring that the transition matrix, $A$, have exactly one real eigenvalue with value 1, i.e. the stationary probability distribution, $\\pi$, of the transition matrix settles on a single cycle $2 \\to 1 \\to 2$. To illustrate this we can use a truncated 4x4 transition matrix. We add an additional restraint on the truncated form requiring that states that would otherwise fall outside the truncated state matrix return to themselves. \n", "$$ A = \\begin{pmatrix} \n", "0 & 1 & 0 & 1 \\\\\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 \\\\\n", "0 & 0 & 0 & 0 \\\\\n", "\\end{pmatrix} $$\n", "\n", "The eigenvectors of this matrix are:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$\\left[\\begin{matrix}0 & 1 & 0 & 0\\\\1 & 0 & 0 & 1\\\\0 & 0 & 1 & 0\\\\0 & 0 & 0 & 0\\end{matrix}\\right]$$" ], "text/plain": [ "⎡0 1 0 0⎤\n", "⎢ ⎥\n", "⎢1 0 0 1⎥\n", "⎢ ⎥\n", "⎢0 0 1 0⎥\n", "⎢ ⎥\n", "⎣0 0 0 0⎦" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sympy import *\n", "init_printing()\n", "A = symbols('A')\n", "\n", "A = Matrix([[0,1,0,0], [1,0,0,1], [0,0,1,0], [0,0,0,0]])\n", "A" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$\\left [ \\left ( -1, \\quad 1, \\quad \\left [ \\left[\\begin{matrix}-1\\\\1\\\\0\\\\0\\end{matrix}\\right]\\right ]\\right ), \\quad \\left ( 0, \\quad 1, \\quad \\left [ \\left[\\begin{matrix}-1\\\\0\\\\0\\\\1\\end{matrix}\\right]\\right ]\\right ), \\quad \\left ( 1, \\quad 2, \\quad \\left [ \\left[\\begin{matrix}1\\\\1\\\\0\\\\0\\end{matrix}\\right], \\quad \\left[\\begin{matrix}0\\\\0\\\\1\\\\0\\end{matrix}\\right]\\right ]\\right )\\right ]$$" ], "text/plain": [ "⎡⎛ ⎡⎡-1⎤⎤⎞ ⎛ ⎡⎡-1⎤⎤⎞ ⎛ ⎡⎡1⎤ ⎡0⎤⎤⎞⎤\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢1 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢1⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜-1, 1, ⎢⎢ ⎥⎥⎟, ⎜0, 1, ⎢⎢ ⎥⎥⎟, ⎜1, 2, ⎢⎢ ⎥, ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢1⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎣⎝ ⎣⎣0 ⎦⎦⎠ ⎝ ⎣⎣1 ⎦⎦⎠ ⎝ ⎣⎣0⎦ ⎣0⎦⎦⎠⎦" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.eigenvects()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This transition matrix has two eigenvectors with eigenvalue equal to 1. One corresponds to the stationary distribution $(1,1,0,0)^T$ which is our main cycle $1 \\to 2 \\to 1$ and the other $(0,0,1,0)^T$ is the _artificial_ cycle introduced by truncation $3 \\to 3$.\n", "\n", "For larger matrices, say 20x20, the same applies:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$\\left[\\begin{array}{ccccccccccccccc}0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\\\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\end{array}\\right]$$" ], "text/plain": [ "⎡0 1 0 0 0 0 0 0 0 0 0 0 0 0 0⎤\n", "⎢ ⎥\n", "⎢1 0 0 1 0 0 0 0 0 0 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 1 0 0 0 0 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 1 0 0 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 1 0 0 0 0 0 0 1 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 0 0 1 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 1 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 1 0 0 0 0 0 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 1 0 0 0 1 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 1 0 0⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 1 0 0 0 0 0 0⎥\n", "⎢ ⎥\n", "⎣0 0 0 0 0 0 0 0 0 0 0 0 0 0 1⎦" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "array = []\n", "size = 15;\n", "for i in range(1, size+1):\n", " array.append([0]*size)\n", " j = (3*i+1)>>1 if i%2==1 else i>>1\n", " if(j>size): j=i;\n", " array[i-1][j-1] = 1\n", "\n", "A = Matrix(array).transpose()\n", "A" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "scrolled": true }, "outputs": [ { "data": { "text/latex": [ "$$\\left [ \\left ( -1, \\quad 1, \\quad \\left [ \\left[\\begin{matrix}-1\\\\1\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\end{matrix}\\right]\\right ]\\right ), \\quad \\left ( 0, \\quad 10, \\quad \\left [ \\left[\\begin{matrix}-1\\\\0\\\\0\\\\1\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\end{matrix}\\right], \\quad \\left[\\begin{matrix}0\\\\0\\\\-1\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\1\\\\0\\\\0\\\\0\\\\0\\\\0\\end{matrix}\\right], \\quad \\left[\\begin{matrix}0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\-1\\\\0\\\\0\\\\0\\\\1\\\\0\\\\0\\\\0\\\\0\\end{matrix}\\right]\\right ]\\right ), \\quad \\left ( 1, \\quad 4, \\quad \\left [ \\left[\\begin{matrix}1\\\\1\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\end{matrix}\\right], \\quad \\left[\\begin{matrix}0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\1\\\\0\\\\0\\\\0\\\\0\\end{matrix}\\right], \\quad \\left[\\begin{matrix}0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\1\\\\0\\\\0\\end{matrix}\\right], \\quad \\left[\\begin{matrix}0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\0\\\\1\\end{matrix}\\right]\\right ]\\right )\\right ]$$" ], "text/plain": [ "⎡⎛ ⎡⎡-1⎤⎤⎞ ⎛ ⎡⎡-1⎤ ⎡0 ⎤ ⎡0 ⎤⎤⎞ ⎛ ⎡⎡1⎤ ⎡0⎤ ⎡0⎤ ⎡0⎤⎤⎞⎤\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢1 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢1⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢-1⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢1 ⎥ ⎢0 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢-1⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜-1, 1, ⎢⎢0 ⎥⎥⎟, ⎜0, 10, ⎢⎢0 ⎥, ⎢0 ⎥, ⎢0 ⎥⎥⎟, ⎜1, 4, ⎢⎢0⎥, ⎢0⎥, ⎢0⎥, ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢1 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢1 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢1⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢1⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢0 ⎥⎥⎟ ⎜ ⎢⎢0 ⎥ ⎢0 ⎥ ⎢0 ⎥⎥⎟ ⎜ ⎢⎢0⎥ ⎢0⎥ ⎢0⎥ ⎢0⎥⎥⎟⎥\n", "⎢⎜ ⎢⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟ ⎜ ⎢⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎥⎟⎥\n", "⎣⎝ ⎣⎣0 ⎦⎦⎠ ⎝ ⎣⎣0 ⎦ ⎣0 ⎦ ⎣0 ⎦⎦⎠ ⎝ ⎣⎣0⎦ ⎣0⎦ ⎣0⎦ ⎣1⎦⎦⎠⎦" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.eigenvects()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This continues to show the main cycle as the first eigenvector (stationary distribution) and cycles also at 15, 17 and 19 where the sequences go out of the range of the array. \n", "\n", "Attempting to solve directly we have:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$\\left[\\begin{array}{ccccccccccccccc}- λ & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\1 & - λ & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & - λ & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & - λ & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & - λ & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & - λ & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & - λ & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\\\0 & 0 & 0 & 0 & 1 & 0 & 0 & - λ & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & - λ & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & - λ & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & - λ + 1 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & - λ & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & - λ + 1 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & - λ & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & - λ + 1\\end{array}\\right]$$" ], "text/plain": [ "⎡-λ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ⎤\n", "⎢ ⎥\n", "⎢1 -λ 0 1 0 0 0 0 0 0 0 0 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 -λ 0 0 1 0 0 0 0 0 0 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 -λ 0 0 0 1 0 0 0 0 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 1 0 -λ 0 0 0 0 1 0 0 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 -λ 0 0 0 0 0 1 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 -λ 0 0 0 0 0 0 1 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 1 0 0 -λ 0 0 0 0 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 -λ 0 0 0 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 -λ 0 0 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 1 0 0 0 -λ + 1 0 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 0 0 -λ 0 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 -λ + 1 0 0 ⎥\n", "⎢ ⎥\n", "⎢0 0 0 0 0 0 0 0 1 0 0 0 0 -λ 0 ⎥\n", "⎢ ⎥\n", "⎣0 0 0 0 0 0 0 0 0 0 0 0 0 0 -λ + 1⎦" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "l = symbols('λ')\n", "\n", "for i in range(1, size+1):\n", " array[i-1][i-1] += -l;\n", "\n", "A = Matrix(array).transpose()\n", "A" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "ename": "NotImplementedError", "evalue": "Could not normalize the vector 0.", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[1;31mNotImplementedError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mA\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mtranspose\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mQRdecomposition\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m~\\Anaconda3\\lib\\site-packages\\sympy\\matrices\\matrices.py\u001b[0m in \u001b[0;36mQRdecomposition\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m 3689\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mQ\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mj\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnorm\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 3690\u001b[0m raise NotImplementedError(\n\u001b[1;32m-> 3691\u001b[1;33m \"Could not normalize the vector %d.\" % j)\n\u001b[0m\u001b[0;32m 3692\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mj\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 3693\u001b[0m \u001b[0mR\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mj\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mQ\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdot\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmat\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mj\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mNotImplementedError\u001b[0m: Could not normalize the vector 0." ] } ], "source": [ "A.transpose().QRdecomposition()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To prove the conjecture we'd have to show that in the limit as the size of the matrix tends to infinity then there should be only 1 eigenvalue of value 1. I don't know how to do that.\n", "\n", "One thing we cvan try is to factor the two function matrices into a matrix for even numbers and a matrix for odd numbers. For the even part we can use:\n", "$$ \n", "A_{even} = \\begin{pmatrix} \n", "1 & 0 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "1 & 0 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 0 & 1 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 1 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 0 & 0 & 0 & 1 & 0 & \\cdots \\\\\n", "0 & 0 & 1 & 0 & 0 & 0 & \\cdots \\\\\n", "\\vdots & \\vdots & \\vdots & \\vdots & \\vdots & \\vdots & \\ddots \\\\\n", "\\end{pmatrix} \n", "$$\n", "Then, because it has been separated from the odd part, we can apply it any number of times until all even factors of 2 have been removed.\n", "$$ A_{even}^\\infty = \\lim_{n \\to \\infty} A_{even}^{n} $$\n", "\n", "Which will look like this having removed all factors of 2:\n", "$$ \n", "A_{even}^\\infty = \\begin{pmatrix} \n", "1 & 0 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "1 & 0 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 0 & 1 & 0 & 0 & 0 & \\cdots \\\\\n", "1 & 0 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 0 & 0 & 0 & 1 & 0 & \\cdots \\\\\n", "0 & 0 & 1 & 0 & 0 & 0 & \\cdots \\\\\n", "\\vdots & \\vdots & \\vdots & \\vdots & \\vdots & \\vdots & \\ddots \\\\\n", "\\end{pmatrix} \n", "$$\n", "\n", "For the odd part we do something similar with $A_{odd}$. \n", "$$ \n", "A_{odd} = \\begin{pmatrix} \n", "0 & 1 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 1 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 0 & 0 & 0 & 1 & 0 & \\cdots \\\\\n", "0 & 0 & 0 & 1 & 0 & 0 & \\cdots \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & \\cdots \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & \\cdots \\\\\n", "\\vdots & \\vdots & \\vdots & \\vdots & \\vdots & \\vdots & \\ddots \\\\\n", "\\end{pmatrix} \n", "$$\n", "\n", "\n", "Now we can apply both transformations sequentially until we get the final result which should be 1.\n", "$$\n", "(A_{odd}A_{even}^\\infty)(A_{odd}A_{even}^\\infty)(A_{odd}A_{even}^\\infty)... = \\lim_{n \\to \\infty} (A_{odd}A_{even}^\\infty)^n = = \\begin{pmatrix} \n", "1 & 0 & \\cdots \\\\\n", "0 & 0 & \\cdots \\\\\n", "\\vdots & \\vdots & \\ddots \\\\\n", "\\end{pmatrix} \n", "$$\n" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "scrolled": false }, "outputs": [ { "data": { "text/latex": [ "$$\\left[\\begin{array}{cccccccccccccccccccccccccccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\\\0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\end{array}\\right]$$" ], "text/plain": [ "⎡1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎢0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \n", "⎢ \n", "⎣0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 \n", "\n", " 0 0 0 0 0 0⎤\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 1 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 1 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎥\n", " ⎥\n", " 0 0 0 0 1 0⎥\n", " ⎥\n", " 0 0 0 0 0 0⎦" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "array = []\n", "size = 32;\n", "for i in range(1, size+1):\n", " array.append([0]*size)\n", " j = i if i%2==1 else i>>1\n", " array[i-1][j-1] = 1\n", "\n", "A = Matrix(array)\n", "A" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Functional Form\n", "\n", "The same relations can be expressed in functional form:\n", "We take the long-term average of the difference of successive terms such that $$\\lim_{t \\to \\infty} \\frac{1}{t} \\sum_{s=0}^{t} \\left| f(x_{t}) - x_{t} \\right| \\to 0$$\n", "\n", "Expand as $$\\lim_{t \\to \\infty} \\frac{1}{t} \\left| \\sum_{s=0}^{t} f(x_{s}) - \\sum_{s=0}^{t} x_{s} \\right|$$ \n", " $$\\lim_{t \\to \\infty} \\frac{1}{t} \\left| (f(x_{0}) + f(x_{1}) + \\cdots + f(x_{t})) - (x_{0} + x_{1} + \\cdots + x_{t}) \\right|$$ \n", " $$\\lim_{t \\to \\infty} \\frac{1}{t} \\left| (x_{1} + x_{2} + \\cdots + x_{t+1}) - (x_{0} + x_{1} + \\cdots + x_{t}) \\right|$$ \n", " $$\\lim_{t \\to \\infty} \\frac{1}{t} \\left| x_{t+1} - x_{0} \\right|$$ \n", "\n", "(Need to be more rigourous when moving the sum inside the norm. Probably using the [triangle inequality](https://en.wikipedia.org/wiki/Triangle_inequality#Reverse_triangle_inequality).)\n", "\n", "Given that in the limit as $t \\to \\infty$, $x_{t}$ is the average value of $x_{n}$ then if the number represented by $x_{n}$ is NOT in a cycle then its average value will tend to 0. Similarly values in a cycle will tend to some non-zero value inversely proportional to the length of the cycle. For the limit to converge we need $x_{t+1} - x_{0}$ to be a constant so that $$x_{t+1} = \\lambda x_{0}$$\n", "Or, equivalently, $$f^{t}(x) = \\lambda x$$\n", "\n", "Since we are looking for $f^{n}(x) = 1$ for some value of $n$, the Collatz Conjecture is equivalent to requiring that the function, $f^{t}(x)$, have exactly one positive real eigenvalue with value $\\lambda$. It must be exactly one because more than one real eigenvalue would imply the existence of other cycles.\n", "\n", "For example take the easiest solution where $f(x)$ is always even giving us $f^n(x)=\\frac{x}{2^{n}}$. The eigenvalues of this function are $\\frac{x}{2^{n}}=\\lambda x \\to \\lambda=\\frac{1}{2^{n}}$ proving that there is only one real eigenvalue and since $f^{n}(x) = \\lambda x = 1$ we have $x=2^{n}$ as expected.\n", "\n", "In the general case $f(x)$ takes the form $f^n(x)=\\frac{3^{m}x+\\Omega}{2^{n}}$ where $m