15
$\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$ Commented May 31, 2017 at 18:46
  • $\begingroup$ @QiaochuYuan do you have a link to paper that defines and talks about "the Fibonacci graph" ? $\endgroup$
    – Anthony
    Commented May 31, 2017 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$ Commented May 31, 2017 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$ Commented Jun 1, 2017 at 1:09
  • $\begingroup$ @Jair Taylor could I persuade you to share your code ? I suspect it is a reasonable conjecture. $\endgroup$
    – Anthony
    Commented Jun 1, 2017 at 1:13

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .