0
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ For a start it depends what you mean by "the smallest possible $\lambda_{1a}$ and $\lambda_{1b}$". Could you meand their sum? Their product? $\endgroup$ Commented Aug 28, 2014 at 1:48
  • $\begingroup$ Good question, sorry if that wasn't clear. I mean that I want to simultaneously minimize the largest eigenvalue for both matrices, and since they are dependent on each other, that would imply that the difference between $\lambda_{1a}$ and $\lambda_{1b}$ is as close to zero as possible. $\endgroup$ Commented Aug 28, 2014 at 19:02

1 Answer 1

Reset to default
1
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ Wonderful input, I hadn't thought about Paley graphs for some reason. To clarify though, Paley graphs exist if and only if $n$ is a prime power congruent to 0 or 1 mod 4, not just 1 mod 4. I appreciate the response and your time! $\endgroup$ Commented Aug 31, 2014 at 23:32
  • $\begingroup$ No, you need $n$ congruent to 1 mod 4. This is also a necessary condition for a regular graph to be self-complementary. $\endgroup$ Commented Sep 1, 2014 at 3:35
  • $\begingroup$ Oh wow, my bad. I must have gotten mixed up. I should have spent more time checking my facts before posting that comment, my apologies Chris. $\endgroup$ Commented Sep 2, 2014 at 7:56

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.