Welcome to MathOverflow

Question

1

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)

edited Feb 7 2011 at 1:16

Harry Gindi

community wiki

4 revisions, 4 users
Mohsen 50%

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 2011 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 2011 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 2011 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 2011 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 2011 at 23:45

show 2 more comments

Igor Rivin · Answer 1 · 2011-02-07 00:11:45Z UTC

5

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.

answered Feb 7 2011 at 0:11

Igor Rivin

community wiki

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 2011 at 0:59

@Eric: good way to look at it! – Igor Rivin Feb 7 2011 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$. – Mohsen Feb 7 2011 at 7:30

eigenvalues of A⊕B

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.