While messing around with a spectral approach to a graph coloring question, I happened upon a type of problem I hadn't seen before.
Suppose you have two symmetric $n$ x $n$ matrices in the form $$A= \begin{pmatrix} &0&x_{1,1}&...&...&x_{1,(n-1)}\\ &x_{1,1}&0&x_{2,1}&\ddots&x_{2,(n-2)}\\ &\vdots &x_{2,1}&0&\ddots&\vdots\\ &\vdots &\ddots &\ddots&0&x_{(n-1),1}\\ &x_{1,(n-1)}&x_{2,(n-2)}&...&x_{(n-1),1}&0 \end{pmatrix}$$ and $$B=\begin{pmatrix} &0&\left|x_{1,1}-1 \right|&...&...&\left|x_{1,(n-1)}-1 \right|\\ &\left|x_{1,1}-1 \right|&0&\left|x_{2,1}-1 \right|&\ddots&\left|x_{2,(n-2)}-1 \right|\\ &\vdots &\left|x_{2,1}-1 \right|&0&\ddots&\vdots \\ &\vdots &\ddots &\ddots&0&\left|x_{(n-1),1}-1 \right|\\ &\left|x_{1,(n-1)}-1 \right|&\left|x_{2,(n-2)}-1 \right|&...&\left|x_{(n-1),1}-1 \right|&0 \end{pmatrix}$$ with any $x_{i,j}=\begin{cases} & 1\\ & 0 \end{cases}$, or, that is to say, $A+B$ is a matrix in the form $$A+B= \begin{pmatrix} &0&1&...&...&1\\ &1&0&\ddots&\ddots&\vdots\\ &\vdots &\ddots &0&\ddots&\vdots\\ &\vdots &\ddots &\ddots&0&1\\ &1&...&...&1&0 \end{pmatrix}$$
Suppose that $\lambda_{1a}$ is the largest eigenvalue for matrix $A$ and $\lambda_{1b}$ the largest eigenvalue for matrix $B$. How can I obtain the smallest possible $\lambda_{1a}$ and $\lambda_{1b}$ by manipulating the values of the entries in $A$ (which correspondingly change $B$)?
I know that for larger matrices, this will probably be impossible to analytically determine, but an approach for a numerical method has been difficult for me to come up with. Considering that, if $A$ is empty, then $\lambda_{1b}$ will be its maximum value, it seems that the smallest largest eigenvalues for this system of matrices will be when $\lambda_{1a}\approx\lambda_{1b}$. What confuses me, though, is how to change the values in $A$ to most efficiently affect the desired changes in eigenvalues. Is there a name for this type of problem, or a best practice for approaching it numerically?
Thanks in advance for any info, input or ideas you can provide!
Suppose $\overline{G}$ is the complement of the graph $G$. Then \[ A(G)+A(\overline{G}) = J-I \] (where $J$ is the matrix with all entries equal to one). If $n=|V(G)|$, this implies that \[ \lambda(G)+\lambda(\overline{G}) \ge n-1. \] We get equality here if $G$ is a regular self-complementary graph. In particular if we take $G$ to be the Paley graph on $n$ vertices then \[ \lambda(G) = \lambda(\overline{G}) = (n-1)/2 \] and your difference is zero. (Note that Paley graphs exist if and only if $n$ is a prime power congruent to 1 mod 4.)