1
$\begingroup$

Maximize $\operatorname{tr}(A^k)$ over binary symmetric $n$ by $n$ matrices subject to $$a_{ii}=0, \sum_{j=1}^n a_{ij}=d, \sum_{i=1}^na_{ij}=d,$$ where $d,k$ are fixed positive integers.

I am having trouble even for the case where $k=5$ and $d=4,$ so even some help here would be greatly appreciated.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Are you looking for an exact formula or just asymptotic behavior as $n\to \infty$? Also this is the same as maximizing the number of closed walks of lenght $k$ in a simple $d$-regular graph on $n$ vertices. $\endgroup$
    – Antoine Labelle
    Commented Oct 20, 2023 at 14:40
  • $\begingroup$ Very similar question: mathoverflow.net/questions/420301/… (The difference is cycles vs closed walks) $\endgroup$
    – Tobias Fritz
    Commented Oct 20, 2023 at 14:45
  • 1
    $\begingroup$ This question is very close (at least for $k$ large when $n$ is fixed) to asking for the largest possible second largest eigenvalue $\lambda_2$. There is a big literature on second largest eigenvalues of graphs. In particular, $\lambda_2$ can be arbitrarily close to $\lambda_1=d$ according to the answer of LeechLattice at mathoverflow.net/questions/333361. $\endgroup$
    – Richard Stanley
    Commented Oct 20, 2023 at 15:11

0

Reset to default

You must log in to answer this question.