Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading a proof regarding the eigenvalue bound in communication complexity (in Arora and Barak book on computational complexity), and the proof uses the fact that for all unit vectors $x,y$, where $M$ is symmetric real matrix the following inequality holds: $$ x^T M y \leq \lambda_\max(M) \big| x \cdot y \big|, $$ where $x\cdot y$ is the dot product of the two vectors.

I don't see this fact immediately. The closest trace I could find is about matrix norms, but matrix norm is about $x^T M x$ not $x^T M y$. Another problem also is that the vectors the proof actually uses are binary vectors (characteristic function of a certain set), not unit vectors as the hypothesis of this claim.

Edit: Every entry in $M$ will either be 1 or -1, so it can not be diagonal (as in paul garrett's comment below).

The statement is used in proof of Lemma 12.13 (Eigenvalue bound) in this chapter draft of the book.

share|improve this question
3  
If the max eigenvalue can be negative, this cannot be right. OTOH, the unit vector condition is irrelevant. –  Phira Aug 27 '11 at 9:05
    
@thei : For the purpose of this method, $M$ will only contain elements from $\{-1,1\}$, but I am not sure if this excludes the possibility of negative eigenvalues or not. –  M. Alaggan Aug 27 '11 at 10:11
    
Actually for $M=\left[ \begin{matrix}1&-1\\1&1\end{matrix} \right]$, the eigenvalues are complex numbers. –  M. Alaggan Aug 27 '11 at 11:01
2  
There is something wrong with the question as posed: for $x=(1,1)/\sqrt{2}$ and $y=(-1,1)/\sqrt{2}$ and $M$ diagonal with $1,-1$ on the diagonal, $x^TMy=1$, $x\cdot y=0$, and the eigenvalues of $M$ are obviously $\pm 1$. –  paul garrett Aug 27 '11 at 11:40
2  
Apropos of @paul's counterexample, here is another with all entries $1$ or $-1$. Take $M = \begin{bmatrix}1 & 1 \\ 1 & 1\end{bmatrix}$, $x = (1, 0)$, and $y = (0, 1)$. Then $x^T M y = 1$ but $x \cdot y = 0$, so the stated inequality cannot hold. –  Rahul Aug 27 '11 at 18:47

2 Answers 2

up vote 2 down vote accepted

Ok. I took a look at the book via the link provided by the OP. As I suspected to some extent the inequality they are using is actually the familiar one $$ X^TMY\le \lambda_{max}|X|\cdot |Y|, $$ but they have bungled up the presentation by adding an errorneous intermediate step that may easily confuse the reader. The ingredients are the following. $M$ is, indeed, a symmetric real matrix. The symmetricity is not listed in the statement of this Lemma, but holds for all the matrices $M(f)$ defined earlier. I can only assume that this is an omission, for otherwise it should be easy to find counterexamples. Anyway, $\lambda_{max}$ is the magnitude of the largest eigenvalue (i.e. the largest absolute value). Given this (assuming that it matches with all the uses of this result), the proof is easy. Because $M$ is real and symmetric, its eigenvalues are all real, and we can find an orthonormal set of eigenvectors $\{\vec{x}_1,\ldots,\vec{x}_n\}$ such that $M\vec{x}_i=\lambda_i\vec{x}_i$. We can write $Y$ using this eigenbasis as follows $Y=\sum_i b_i\vec{x}_i$, so $MY=\sum_i b_iM\vec{x}_i=\sum_i \lambda_ib_i\vec{x}_i$. Then by Cauchy-Schwarz we get $$ X^TMY=\langle X, MY\rangle\le |X||\sum_i \lambda_ib_i\vec{x}_i|= |X|\sqrt{\sum_i \lambda_i^2b_i^2}\le|X|\lambda_{max}\sqrt{\sum_i b_i^2}=\lambda_{max}|X||Y|, $$ as claimed.

In that proof we have $X=1_A$ = the characteristic function of a set $A$, so $|X|=\sqrt{|A|}$ as the authors claim. Similarly $Y=1_B$, so $|Y|=\sqrt{|B|}$. Putting these pieces together we get $$ X^TMY=1_A^TM1_B\le \lambda_{max}\sqrt{|A|\cdot|B|} $$ recovering the claim of the authors. Their intermediate step does, indeed, involve the inner product $1_A^T1_B$, but the value of that inner product is $|A\cap B|$, and we don't see that anywhere in the final claim, so this is IMVHO a booboo. This is a draft version after all.

I obviously didn't read all of the chapter, just skimmed thru it to see the definition of $M(f)$ = a symmetric matrix with entries in $\{0,1\}$. If they apply the lemma to non-symmetric matrices as well, then we need to take a closer look.

=================================================

Edit: To make it clear. IMHO the authors made a mistake in claiming the sequence of inequalities:

$$ 1_A^TM1_B\le\lambda_{max}|1_A^T1_B|\le\lambda_{max}\sqrt{|A|\cdot|B|}, $$

when it should have read

$$ 1_A^TM1_B\le\lambda_{max}|1_A|\cdot|1_B|=\lambda_{max}\sqrt{|A|\cdot|B|}. $$

In the end it makes no difference, because their proof only needs the inequality

$$ 1_A^TM1_B\le\lambda_{max}\sqrt{|A|\cdot|B|}. $$

IOW, my guess is that the authors knew where they were heading, and accidentally inserted an incorrect intermediate step.

share|improve this answer
    
Thank you for the detailed presentation. But I am still confused though when you reassured that they still use the scalar product, implying that it is fine. How does that avoid the counter example ? –  M. Alaggan Aug 27 '11 at 23:57
    
Their presentation in the final printed book still involves the scalar product in the same way as in the draft, and they state the "fact" in the question above verbatim as I wrote it, but with $\big|\langle x,y \rangle\big|$ instead. It is also stated before the proof as in "the next proof uses this fact", with $x$ and $y$ general vectors; no indication of them being characteristic functions. –  M. Alaggan Aug 28 '11 at 0:06
1  
@M.ALAGGAN: No, I did not imply that it is fine. Their middle estimate is wrong. But the end result is correct (provided that $M$ is real and symmetric). –  Jyrki Lahtonen Aug 28 '11 at 5:55
    
Thank you very much, it is very clear now :) ! –  M. Alaggan Aug 28 '11 at 6:26

If $\lambda_\max>0$ I have the following proof. In addition, as mentioned by thei, whether $x,y$ are unit-length does not matter.

Since $M$ is symmetric, it can be decomposed as $M=U^T\Lambda U$ with $U$ as an orthogonal matrix and $\Lambda$ as a diagonal matrix with the eigenvalues of $M$ as its diagonal entries.

$$x^TMy=x^TU^T\Lambda Uy=\bar{x}^T\Lambda \bar{y}=\sum \bar{x}_i\bar{y}_i \lambda_i\le\sum|\bar{x}_i\bar{y}_i \lambda_i|\le\sum |\bar{x}_i\bar{y}_i| \lambda_\max$$ $$=|\bar{x}\cdot \bar{y}| \lambda_\max=|x\cdot y| \lambda_\max$$

Correction: Thanks Ben and paul. $\sum|\bar{x}_i\bar{y}_i|\ne|\bar{x}\cdot\bar{y}_i|$ in general.

share|improve this answer
    
@Shiyu: Thank you :). –  M. Alaggan Aug 27 '11 at 10:24
    
@Jyrki: And if the eigenvalues were complex, we take their absolute value? –  M. Alaggan Aug 27 '11 at 11:03
2  
A propos of Paul Garret's comment, the proof has a flaw. $\sum\left|\bar{x}_i\bar{y}_i\right|$ is not guaranteed equal to $\left| \bar{x} \cdot \bar{y} \right|$ unless the entries are nonnegative. In general it may be greater. (This is the triangle inequality.) –  Ben Blum-Smith Aug 27 '11 at 12:30
    
@M.ALAGGAN: The eigenvalues of a symmetric real matrix are always real. –  Jyrki Lahtonen Aug 27 '11 at 12:59
    
I removed the earlier comment, because I was reading the r.h.s. of the original claim as the natural one of $|\lambda|_{max}|x|\,|y|$. I knew that that result could be proven along the lines of Shiyu's argument - talk about power of expectation: I was seeing what I expected to see :-). @Ben: Thanks for alerting me about Paul's observation. –  Jyrki Lahtonen Aug 27 '11 at 13:08

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.