What is known about optimization of spectral properties of matrices over finite fields?

Question

[I am solving the characteristic polynomial over complex numbers but since the matrices are symmetric all eigenvalues are real]

• Like for symmetric $d-$regular matrices over 0/1 or 0/1/-1 what are some known optimization results about their possible spectral radius or spectral gap? [..I am calling a symmetric matrix to be $d-$regular if it has $d$ non-zero entries in each row and column..]

• We do not know of a method to exactly calculate the roots of a polynomial and hence we can't calculate the eigenvalues of a matrix exactly. Given then I suppose determining the spectral gap of a graph is also not possible to do exactly. Is that right?

Answer 1

Here's an example of determining whether a graph is Ramanujan using Maple. I'll take a random $5$-regular connected graph with $20$ vertices.

with(GraphTheory):
G:= RandomGraphs:-RandomRegularGraph(20,5,connected);
A:= AdjacencyMatrix(G);
P:= factor(LinearAlgebra:-CharacteristicPolynomial(A,t));

$$ \left( t-5 \right) \left( {t}^{19}+5\,{t}^{18}-25\,{t}^{17}-153\,{t} ^{16}+172\,{t}^{15}+1730\,{t}^{14}+158\,{t}^{13}-9144\,{t}^{12}-5832\, {t}^{11}+23788\,{t}^{10}+22275\,{t}^{9}-28621\,{t}^{8}-33055\,{t}^{7}+ 12253\,{t}^{6}+19109\,{t}^{5}+315\,{t}^{4}-3321\,{t}^{3}-557\,{t}^{2}+ 79\,t+15 \right) $$

P2:= op(2,P);
sturm(sturmseq(P2,t),t,4,5);

$$ 0 $$

No eigenvalues in this interval, so yes, it is Ramanujan.