# eigenvalues of A⊕B

Let $A_{n\times n}=(a_{ij}),B_{n\times n}=(b_{ij}) \in M_{n}(\mathbb{R})$, where $a_{ij},b_{ij} \in \lbrace 0,1\rbrace$. Boolean sum of $A,B$ denoted by $(A \oplus B)_{n\times n}=(a_{ij}\oplus b_{ij})$ is the matrix in $M_{n}(\mathbb{R})$ such that $0\oplus 0 = 0$, $0\oplus 1 = 1$, $1\oplus 0=1$ and $1\oplus 1 =1$. Is there any inequality or relation between eigenvalues of $A,B$ and $A\oplus B$? (specially, when $A,B$ are symmetric)

-
Just to be sure: the matrices $A$ and $B$ are viewed as having entries in $\mathbb{R}$ (so their eigenvalues are complex numbers) even though they have entries in $\{0,1\}$ and $A \oplus B$ is defined by taking the sum of the matrices viewed as having entries in $\mathbb{F}_2$? Could you give some motivation for this? –  Pete L. Clark Feb 6 '11 at 23:06
@Pete L. Clark: It doesn't look to me like the sum is over $\mathbb{F}_2$ since $1 \oplus 1=1$. It is rather the bit-wise "or" operation. (Having said that, motivation still would be nice.) –  Eric Naslund Feb 6 '11 at 23:20
Assuming they are symmetric, we can say a few trivial things about the largest eigenvalue. Namely that $\lambda_{A\oplus B} \leq \lambda_{A}+\lambda_B \leq 2\lambda_{A\oplus B}$ (where $\lambda_M$ refers to the largest eigenvalue) –  Eric Naslund Feb 6 '11 at 23:29
And those bounds are tight, so which eigenvalues do you care about? And what kind of inequalities are you looking for? I don't fully understand the question. –  Eric Naslund Feb 6 '11 at 23:32
***Remove the word symmetric in my above comment. It doesn't matter since the largest in magnitude (or one tied for the largest) will be real and positive for these matrices. –  Eric Naslund Feb 6 '11 at 23:45

## 1 Answer

The operation is actually element-wise maximum, and the matrices are both non-negative, so Perron-Frobenius theorem together with the Rayleigh-Ritz characterization of maximum (perron-frobenius) eigenvalue seems to indicate that $\lambda_\max(A\oplus B) \geq \max \{\lambda_\max(A), \lambda_\max(B)\}.$

I don't know why you would use the $\oplus$ notation for this.

-
Intuitively, that inequality simply says "there are asymptotically more possible walks on a graph when we add more edges", which is certainly true. Recall: The largest eigenvalue of a 0-1 matrix is the asymptomatic growth rate of number of random walks on the directed graph generated by that matrix. (Provided there exists a path from each non-zero degree vertex to itself, which is automatically satisfied for symmetric matrices) –  Eric Naslund Feb 7 '11 at 0:59
@Eric: good way to look at it! –  Igor Rivin Feb 7 '11 at 2:30
Thanks for your answering to my question, but i'm looking for a lower bound for all the eigenvalues of $A⊕B$. –  Moh514 Feb 7 '11 at 7:30