I had a look at the eigenvalues of the matrix, I called it Prime Index Matrix (is there a better name?), constructed like the following: $$ P_{k,p_k}=P_{p_k,k}=1, $$ where $p_k$ is the $k$th prime. $P$ is symmetric and for $k_\max=6000$ looks like the left figure:
The maximal eigenvalue behaves strange, since from time to time I get bumps, which I can't explain (see right figure). The largest value I got was $1.9021$ for $k_\max=6000$.
I had a closer look at the bumps. Funnily I recognized that they happen to happen at: $1,2,3,5,11,31,127,709,5381,...$, but what funny about that?
I was just about to post a question about the following recursion $\Phi: k \mapsto p_k$, which gives you $1 \mapsto p_1=2 \mapsto p_2=3\mapsto p_3=5\mapsto p_5=11\mapsto p_{11}=31\mapsto p_{31}=127\mapsto p_{127}=709\mapsto p_{709} $
How can this be explained?
And how this help to answer my original question?
EDIT The sequence is known: OEIS/A007097. It relates to the Matula-Goebel number of the rooted path tree on n+1 vertices. Does this give anybody a hint?
EDIT 2.0 The same behaviour appears when you restrict to primes $\bmod 4 \equiv 1$ or $\bmod 4 \equiv 3$: The jumps in eigenvalues appear for primes $5 \mapsto p_{4,1;5}= 37 \mapsto p_{4,1;37}= 397\mapsto p_{4,1;397}= 6229$. For the other case it's $3, 11, 71, 787,...$. I also checked primes $\bmod 6\equiv 1$: same result...
As I just realized, the problem has nothing special to do with primes. The question boils down to a subset of equation of the overall eigenvalue equation: $$ P\cdot \vec x - \lambda \vec x =0 $$ You can restrict this problem by picking the kind of connected (via reflection on the diagonal) vector components: $$ \begin{eqnarray} x_2-\lambda x_1&=0\\ x_3+ x_1-\lambda x_2&=0\\ x_5+ x_2-\lambda x_3&=0\\ \vdots\\ x_{p_{r}}+x_{p_{t}}-\lambda x_{p_{s}}&=0\\ x_{p_{s}}-\lambda x_{p_{t}}&=0\\ \end{eqnarray} $$ Let's say we reached a new maximal eigenvalue at prime $p_k$. The system of equation grows again when we reach prime $p_{p_k}$, generating the next maximal eigenvalue.