13
$\begingroup$

Question : Let $A(n)$ be a finite square $n \times n$ matrix with entries $a_{i,j}=1$ if $i+j$ is a perfect power; otherwise equals to $0$. Can we determine the numbers $n$ such that characteristic polynomial of $A(n)$ has at least two real roots: one equal to the golden ratio and the other equal to the golden conjugate ?

For an examlple consider $$A(8)= \text{ }\begin{pmatrix} 0&0&1&0&0&0&1&1\\ 0&1&0&0&0&1&1&0\\ 1&0&0&0&1&1&0&0\\ 0&0&0&1&1&0&0&0\\ 0&0&1&1&0&0&0&0\\ 0&1&1&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&1\\ \end{pmatrix}$$

I denote the characteristic polynomial of $A(n)$ by $\chi_{A(n)}(X)$. So for example

$$\chi_{A(8)}(X)=X^8-3X^7-5X^6+19X^5+2X^4-31X^3+X^2+10X-3$$

I use the standard notation $\varphi$ to denote the golden ratio and it is equal to ${1+\sqrt{5}\above 1.5pt 2}$. The "Golden Conjugate" is written as $-{1\above 1.5 pt \varphi}$ and is equal to ${1-\sqrt{5}\above 1.5pt 2}$. I use $\lambda$ to denote an eigenvalue of $\chi_{A(n)}(X)$. In the example above the characteristic polynomial $\chi_{A(8)}(X)$ has two eigenvalues $\lambda_1=-{1\above 1.5 pt \varphi}$ and $\lambda_2=\varphi$. In particular $\chi_{A(8)}(X)$ has exactly two roots: one equal to the golden ratio and the other equal to the golden conjugate.

Below is a tabulation of data for small values of $n$. Calculations were performed in WOLFRAM ALPHA. The calculations should be correct but errors are inevitable. Only real eigenvalues are listed:

\begin{array}{| l | l | l | l |l|} \hline n & \text{characteristic polynomial} &\text{eigenvalues}\\ \hline 2 & X^2-X & (0,1)\\ 3 & -X^3+X^2+X-1 & (-1,1,1)\\ 4 & X^4-2X^3+2X-1 & (-1,1,1,1)\\ 5 & -X^5+2X^4+2X^3-5X^2+X+1 &(-\lambda_1,\lambda_2,1,1,\lambda_3)\\ \color{blue}{6} & \color{blue}{X^6-2X^5-4X^4+8X^3+2X^2-4X-1} & \color{blue}{(1,-{1\above 1.5 pt \varphi},\varphi,\lambda_1,\lambda_2,\lambda_3)}\\ 7 & -X^7-2X^6+6X^5-11X^4-9X^3+15X^2+2X-4 & (1,\lambda_1,\lambda_2,\lambda_3,\lambda_4,\lambda_5,\lambda_6) \\ \color{blue}{8} & \color{blue}{X^8-3X^7-5X^6+19X^5+2X^4-31X^3+X^2+10X-3} & \color{blue}{(-{1\above 1.5 pt \varphi},\varphi,\lambda_1,\lambda_2,\lambda_3,\lambda_4,\lambda_5,\lambda_6)}\\ \color{blue}{9} & \color{blue}{-X^9+3X^8+6X^7-22X^6-5X^5+45X^4-12X^3-22X^2+5X+3} & \color{blue}{(\lambda_1,\lambda_2,\lambda_3,-\varphi,\varphi,1,-{1\above 1.5 pt \varphi},1-\varphi,\lambda_4 )}\\ \hline \end{array}

Surely $n=6,8,9$ are shown to answer the question. I am certain that if $A(n)$ has $\varphi$ as a eigenvalue then it must also have $-{1\above 1.5 pt \varphi}$ as an eigenvalue. The motivation here is an understanding of the matrix $A(n)$.

Edit 1: Correction to tabulated eigenvalues when n=6. There are actually 6 real eigenvalues and I listed only 3. Three of the eigenvalues can be written : $1$, $\varphi$ and $1-\varphi$. The other three however have exact forms that can be written with $i=\sqrt{-1}$.

$$\lambda_1 = {\sqrt[3]{\frac{1}{2}\bigg(9 + i \sqrt{687}\bigg)}\above 1.5 pt 3^{2/3}} + {4 \above 1.5pt {\sqrt[3]{\frac{3}{2} \bigg (9 + i \sqrt{687}\bigg)}}}$$

$$\lambda_2 = {\bigg(1-i\sqrt{3}\bigg)\sqrt[3]{\frac{1}{2}\bigg(9 + i \sqrt{687}\bigg)}\above 1.5 pt 2\times 3^{2/3}} - {2(1+i\sqrt{3})\above 1.5pt {\sqrt[3]{\frac{3}{2} \bigg (9 + i \sqrt{687}\bigg)}}}$$

$$\lambda_3 = -{\bigg(1+i\sqrt{3}\bigg)\sqrt[3]{\frac{1}{2}\bigg(9 + i \sqrt{687}\bigg)}\above 1.5 pt 2\times 3^{2/3}} - {2(1-i\sqrt{3})\above 1.5pt {\sqrt[3]{\frac{3}{2} \bigg (9 + i \sqrt{687}\bigg)}}}$$

Numerically the eigenvalues $\lambda_1,\lambda_2$ and $\lambda_3$ are real - in particular the imaginary terms cancel out. Explicitly $\lambda_1\approx 2.11491\ldots$, $\lambda_2\approx -.618034\ldots$,$\lambda_3\approx -.254102\ldots$

Edit 2: $A(n)$ never has complex eigenvalues for any $n$. I included the missing eigenvalues in the table. Also I corrected errors in the table for $n=5$. None of the corrections change the result/conjecture of the problem. Namely that $6,8$ and $9$ are the only integers such that $A(n)$ has a eigenvalues equal to $\varphi$ or $-{1\above 1.5 pt \varphi}$.

For $n=5$ the corrected values are numerically $\lambda_1 \approx 1.87939\ldots$, $\lambda_2\approx -1.53209\ldots$,$\lambda_3=1$,$\lambda_4=$, $\lambda_5 \approx -0.347296\ldots$ These values have exact forms similar to the radicals shown in Edit 1 above

For $n=7$ the $6$ missing values are numerically $\lambda_1 \approx 2.38839\ldots$, $\lambda_2\approx -1.9041\ldots$,$\lambda_3\approx 1.77217\ldots$,$\lambda_4\approx -1.33388\ldots$, $\lambda_5 \approx 0.0.64993\ldots$,$\lambda_6 \approx -0.572499 \ldots$.

For $n=8$ the $6$ missing values are numerically $\lambda_1 \approx 2.48767\ldots$, $\lambda_2\approx -1.98486\ldots$,$\lambda_3\approx 1.77268\ldots$,$\lambda_4\approx -1.39899\ldots$, $\lambda_5 \approx 0.827404\ldots$,$\lambda_6 \approx 0.296099 \ldots$.

For $n=9$ the $4$ missing values are numerically $\lambda_1 \approx 2.54926\ldots$, $\lambda_2\approx -2.03439\ldots$,$\lambda_3\approx 1.80552\ldots$,$\lambda_4\approx 0.320385\ldots$ These values have exact forms similar to the radicals shown in Edit 1 above.

Conjecture: $6,8$ or $9$ are the only numbers $n$ such that characteristic polynomial of $A(n)$ has eigenvalues: one equal to the golden ratio and another equal to the golden conjugate.

$\endgroup$
7
  • 2
    $\begingroup$ Interpret the matrix as the adjacency matrix of a directed graph and draw it. You are looking for a connected component of the graph that looks like two vertices, commected by a directed edge in both directions, such that one of them has a self-loop. This is the "Fibonacci graph." $\endgroup$ – Qiaochu Yuan May 31 '17 at 18:46
  • $\begingroup$ @QiaochuYuan do you have a link to paper that defines and talks about "the Fibonacci graph" ? $\endgroup$ – Antonio Hernandez Maquivar May 31 '17 at 18:57
  • 1
    $\begingroup$ Hmm, never mind, I drew the graphs and things are more complicated than that. Anyway, take a look at math.dartmouth.edu/archive/m68f11/public_html/algcomb.pdf and draw the graphs. The Fibonacci graph is the graph with adjacency matrix $\left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]$; I call it that because counting walks on it reproduces the Fibonacci numbers. Its eigenvalues are $\varphi$ and $- \frac{1}{\varphi}$ as you might expect. $\endgroup$ – Qiaochu Yuan May 31 '17 at 23:35
  • $\begingroup$ I tried for up to $500 \times 500$ and I didn't see any more examples of this. So it may be just $n = 6,8,9$. $\endgroup$ – Jair Taylor Jun 1 '17 at 1:09
  • $\begingroup$ @Jair Taylor could I persuade you to share your code ? I suspect it is a reasonable conjecture. $\endgroup$ – Antonio Hernandez Maquivar Jun 1 '17 at 1:13
3
$\begingroup$

For $n < 500$ it seems that $6,8,9$ are the only solutions. Here is some Python code to check. The algorithm works by noting that $\phi$ and $-1/\phi$ are eigenvalues of $M$ if and only if $M^2 - M - I$ is singular. I was too lazy write code to check if an integer was a perfect power, so I copied part of the list from OEIS.

import numpy as np

def is_invertible(a):
     return a.shape[0] == a.shape[1] and np.linalg.matrix_rank(a) == a.shape[0]

perfect_powers = [1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 
                  121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 
                  289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 
                  625, 676, 729, 784, 841, 900, 961, 1000, 1024, 
                  1089, 1156, 1225, 1296, 1331, 1369, 1444, 1521, 
                  1600, 1681, 1728, 1764]

A = []

for n in range(1,10):

    M = [[0]*n] *n
    M = np.matrix(M)

    for m in [m for m in perfect_powers if m <= 2*n]:
        for i in range(n):
            j = m - (i+1) -1 #find solutions to (i+1) + (j+1) = m
            if j in range(n): 
                M[i,j] = 1

    if not is_invertible(M*M - M - np.identity(n)):
        A.append(n)
    print n, n in A
print A

returns

1 False
2 False
3 False
4 False
5 False
6 True
7 False
8 True
9 True
[6, 8, 9]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.