Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question
    
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
1  
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 1

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.

share|improve this answer
4  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.