MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} with a $(1,-1)$ matrix $M_f$ of size $|X|\times |Y|$. We know the log of rank of $M_f$ is lower bound of deterministic communication complexity of $f$ and the log of approximation rank of $M_f$ is lower bound of randomized communication complexity. The largest gap between deterministic communication complexity and randomized communication complexity is exponential. So how about the largest gap between rank and approximation rank?

share|cite|improve this question
How about comparing the zero matrix with ${\epsilon}I$ ? Or am I missing something? Gerhard "Ask Me About System Design" Paseman, 2011.04.14 – Gerhard Paseman Apr 15 '11 at 6:08
@Gerhard No 0's. But what about $J$ vs $\epsilon I+J$ With $J$ the all $1$'s matrix of the appropriate shape and $I$ the usual identity maxtrix with possible rows or columns of all $0$ to pad it to the correct size. – Aaron Meyerowitz Apr 15 '11 at 6:28
@Aaron, the way I read the problem, $M$ is to have $\pm1$ entries, and the matrix $A$ differing from $M$ by at most $\epsilon$ is to have as small a rank as possible. Your example goes the other way. – Gerry Myerson Apr 15 '11 at 6:36
For example, suppose $M$ has rank 2. $M$ must have a $2 \times 2$ submatrix $S$ that has rank 2. We can assume wlog this is $\left(\matrix{1 & 1\cr 1 & -1\cr}\right)$. It is then easy to see that any $2 \times 2$ matrix that differs by less than 1 from this in each entry has rank 2, so if $\epsilon < 1$ the $\epsilon$-approximation rank is 2. – Robert Israel Apr 15 '11 at 7:05
One could derive this bound from one on 0/1 matrices. Suppose M is a square full-rank -1/1 submatrix; suppose wlog that the first column is all ones; subtract this first column from all the other ones, and you remain with a $(n-1)\times (n-1)$ 0-2 matrix. By going backward we see that an entrywise-$\leq\varepsilon$ perturbation of the initial matrix becomes a $\leq 2\varepsilon$ perturbation of the modified matrix. So, if we can bound the distance from singularity of full-rank, square 0/1 matrices then we can extend this result to -1/1 matrices. – Federico Poloni Apr 15 '11 at 8:13

Your Answer


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

Browse other questions tagged or ask your own question.