For given block sizes $a<b<c<d$, consider the complete 4-partite graph $K\_{a,b,c,d }$. 



> 
> * Can such a graph be integral, i.e. have only integer eigenvalues?
> 
> 
> 


It is easy to see that the four nonzero eigenvalues of $K\_{a,b,c,d }$ are the same as those of $$\begin{pmatrix} 0&b&c&d\\ a&0&c&d\\ a&b&0&d\\ a&b&c&0 \end{pmatrix}$$ because the corresponding eigenvectors must have the same entry inside each block.  

So we can consider instead the characteristic polynomial of this matrix, $$\lambda^4-(ab+ac+ad+bc+bd+cd) \lambda^2- 2( a b c+abd+acd+bcd) \lambda-3 a b c d.$$ 


Though not related, it reminds me of the question about the existence of [perfect Euler bricks](https://en.wikipedia.org/wiki/Euler_brick#Perfect_cuboid).  

The corresponding question for tripartite graphs with pairwise different block sizes has been settled [here](https://mathoverflow.net/questions/225448/why-are-some-solutions-of-these-diophantine-equations-off-the-usual-patterns). 


I have done an exhaustive computer search for all quadruples with $d\leqslant 200$ and found none with four integer eigenvalues. Many of them have exactly one integer eigenvalue, and a few have *two*, e.g. $K\_{8,15,32,40}$. The complete list of the latter solutions (that is, the coprime ones) follows, including each time the two integer eigenvalues $λ1 <λ2$. 



```
        d     c     b    a       λ1    λ2   

       40    32    15    8      -36   -20
       42    28    15    7      -35    63
       56    41    32   24      -36   112
       64    44    24    9      -54   -96
       72    18     9    2      -12    54 
       77    48    35    3      -63   -40
       79    75    35   11      -77   -45   
       91    89    40   15      -90   -52                   
       93    75    40    7      -84   -50 
      102    70    63   50      -54   210                              
      104    56    48   39      -84   -52
      105    96    70   55      -80   -60
      112    56    40    7      -84   140 
      112    57    30   21      -84   -24   
      112   100    99   84     -108   -88  
      117    83    40   25     -100   -54 
      117    90    40   18      -54   180  
      117    91    48   13     -104   182 
      119    54    24   14      -84   -34
      128    80    63   12      -70   192 
      130    39    18   13      -78   -26
      130    91    67   32     -112   -39
      133    47    40   15      -90   -19
      135   110    72   54      -60   270
      144    54    14    9      -24   126
      145    70    33   15     -105   -45 
      160    40     8    7      -84   -16   
      160   104    65   40      -80   260   
      165    22    21    7      -77    -9   
      165   102    44   12     -132   -60   
      168    40    15   12      -90   -24   
      168    40    32   25     -100   -36   
      168    57    25   15     -105   -36   
      175    80    69   63     -135   -75
      175    85    63   60     -135   -75
      175    87    63   55     -135   -75
      175    90    63   45     -135   -75
      175    93    63   30     -135   -75
      175    95    63   15     -135   -75
      175    96    63    5     -135   -75
      175   111    55   39     -143   -75
      175   141   130   63     -135   -75
      175   150   125   63     -135   -75
      175   155   123   63     -135   -75
      175   165   120   63     -135   -75
      176    40    15    4      -90   -22   
      180   175   117   63     -135   -75
      187   163    75   35     -175   -99
      192    88    33   12      -48   198
      195    57    48   35     -126   -39
      195   117   104   69      -78   351
      195   144   116  104     -174  -130
      195   175   115   63     -135   -75
      200    52    48   35     -126   -50
      200    98    35    2      -50   196

```

* Note that in those quadruples, a few primes do occur. But among the eigenvalues... the first prime ($-19$) only appears at $d=133$ and is so far the only one!
* So far, all prime factors of the eigenvalues divide at least one of $a,b,c,d$.
* Moreover, if the two eigenvalues have a common prime factor, it divides most often (but sadly not always) three of $a,b,c,d$.
* And now: What is happening for $d=175$? All solutions except $(175, 111,55, 39)$ not only have the same two integer eigenvalues $-135$ and $-75$, but also have $63$ among the block sizes. This includes as well the solutions $(180, 175, 117, 63 )$ and $(195, 175, 115, 63)$ and possibly more with larger $d$'s. **How to explain such a "cluster"?**  

Similarly, the pair of block sizes $(40,7)$ co-occurs several times
with the eigenvalue $-84$.


This all is obviously intriguing and raises the following question, which is interesting on its own, whether or not integral graphs exist: 



> 
> * In terms of elliptic functions, is it possible to characterize the solutions $(a,b,c,d)$ with two integer nonzero eigenvalues?
> 
> 
> 



Integral complete 4-partite graphs

> 
> * Can such a graph be integral, i.e. have only integer eigenvalues?
> 
> 
> 


Yes. Two examples are $(a,b,c,d) = (441, 744, 1225, 5635)$,
with eigenvalues $-945$, $-525$, $-3038$, $4058$, and
$(a,b,c,d) = (1575, 1900, 4500, 33516)$,
with eigenvalues $-1710$, $-2940$, $-14250$, $18900$.
There are infinitely many others, even if we require that
they be "primitive" (no common factors other than $\pm 1$)
so one cannot claim new examples just be scaling $(a,b,c,d)$ to $(ka,kb,kc,kd)$.



> 
> * In terms of elliptic functions, is it possible to characterize the solutions (a,b,c,d) with two integer nonzero eigenvalues?
> 
> 
> 


For general $(x,y,a)$, the triples $(b,c,d) \in {\bf Q}^3$ such that $x,y$ are
eigenvalues of $K\_{a,b,c,d}$ are parametrized by an elliptic curve.
Most rational points on this curve don't yield integer solutions,
but rational solutions with $b,c,d>0$ are enough because we can
clear denominators to make them integral, and then permute to get
$a<b<c<d$ as long as they're pairwise distinct.




---


Let $P(a,b,c,d;\lambda)$ be the characteristic polynomial
$$
 \lambda^4
 - (ab+ac+ad+bc+bd+cd) \lambda^2
 - 2 (abc+abd+acd+bcd) \lambda - 3 a b c d.
$$
of $K\_{a,b,c,d}$, as exhibited in the problem statement.
Given two eigenvalues $x,y$, we can eliminate one of the block sizes,
say $d$, from the simultaneous linear equations
$$P(a,b,c,d;x) = P(a,b,c,d;y) = 0.$$
This gives a surface $Q(a,b,c) = 0$ that is of degree $2$ in each of the
variables $a,b,c$; choosing one of them, say $a$, yields a curve of degree $2$
in each of the others, which is typically an elliptic curve. That curve
always has a few automatic points such as those with $b=0$ and $c=0$;
starting from those and using the group law on an elliptic curve
we can produce infinitely many others.


This curve has a somewhat special form $C^2 = D\_1(a,b) D\_2(a,b) D\_3(a,b)$
where $D\_1,D\_2,D\_3$ have bidegrees $(1,1)$, $(1,1)$, $(2,2)$ in $a$ and $b$.
This form is obtained by factoring the discriminant of $Q(a,b,c)$
as a quadratic in $c$; explicitly
$$
D\_1 = x^3 + (x^2 + 2(a+b)x + 3ab)y - abx,
\quad
D\_2 = y^3 + (y^2 + 2(a+b)y + 3ab)x - aby,
$$
$$
D\_3 = x^2 y^2 + 2(a+b)(x+y)xy + ab(3x^2 + 4xy + 3y^2) - 3(ab)^2.
$$
For most $(x,y,a)$, the quartic $D\_1,D\_2,D\_3$ in $b$ has distinct roots;
but for some special choices there are repeated roots, and then
the curve $C^2 = D\_1 D\_2 D\_3$ can be rational. It turns out that
if $3(x+3y)(3x+y)$ is a square then we can choose $a$ so that
$D\_1 D\_2 D\_3$ is a perfect square; explicitly we find that this happens for
$$
(x:y:a) = 
 (3 (r-s) (r+3s) (r^2-s^2) : (r-s) (r+3s) (9s^2-r^2) : (r+s) (r-3s) (r^2+3s^2))
$$
for some $r,s$. This gives a one-parameter family of $(b,c,d)$ such that
$P(a,b,c,d;\lambda)$ factors as $(\lambda-x) (\lambda-y)$ times
some quadratic in $\lambda$, and we can then require *that* quadratic
to have square discriminant, which yields a new elliptic curve that has
a few automatic rational points such as those with $c=0$; again we cannot
use those solutions directly but can combine them using the group law.
This yields complicated parametric families; instead of carrying out
such a computation, I just searched for simple rational points on
the curves arising from $(r:s) = (2:-1)$ and $(4:1)$, and found
in each case the point giving rise to one of the solutions at the top of
this answer.


