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.

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

For each $(i,j)\in \mathbb{N}^2$, $a(i,j)=1$ or $0$, and 1) $a(i,i)=0$ for all $i$; 2)for fixed $i$, there is at most one $j$ such that $a(i,j)=1$. Suppose we know that there is a finite $\kappa$ such that \begin{equation} \sum_{i\in S, j\in S^{C}}a(i,j)\le\kappa\end{equation} for any subset $S$ of $\mathbb{N}$,then one can show $\sum a(i,j)$ is bounded by $3\kappa$.

I am asking what is the largest possible value of $\sum a(i,j)$.

For people who are interested in the background, I am considering an operator $T\in\mathcal{L}(\ell^2)$. With respect to the natural basis, the entries of $T$ are $a(i,j)$. The existence of $\kappa$ in the first inequality is the same as \begin{equation}rank(TP-PTP)\le\kappa\end{equation} for all orthogonal projections $P$ in the masa (maximal abelian, self-adjoint subalgebra) of diagonal operators.

In a recent paper by Popov, Marcoux and Radjavi (Almost Invariant Halfspaces and Approximate Commutation), they have shown $\sum a(i,j)$ is bounded by $3\kappa$ (Thm 4.7), but in almost all examples I can think of, $\sum a(i,j)\le 2\kappa$, so I wonder whether the coefficient can be improved.

Again, I think the problem has been reduced to a purely algebraic or number theoretic problem in the first two paragraph of this post.

Thanks very much!

share|cite|improve this question
Do you mean $\sum_{i\neq j} a(i,j)$? Else why couldn't $a(i,i)=1$ for all $i$? – Erick Wong Jun 22 '12 at 22:32
@ErickWong Thanks! I have corrected my post by imposing $a(i,i)=0$ for all $i$. This corresponds to a trivial case in the original problem. – Hui Yu Jun 23 '12 at 0:17
Citation for the Popov et al. paper? – Gerry Myerson Jun 23 '12 at 0:31
When you write, "in almost all the examples I can think of...," can you give an example where $2k$ doesn't work? – Gerry Myerson Jun 23 '12 at 0:32
Cross post on MO… – user17762 Jun 23 '12 at 3:12
up vote 1 down vote accepted

I believe there is a small counterexample with $\kappa=3$: $$\left( \begin{array}{ccccc} 0&1&1&0&0\\ 0&0&1&1&0\\ 0&0&0&1&1\\ 1&0&0&0&1\\ 1&1&0&0&0 \end{array} \right).$$ More generally, it is easy to prove an upper bound of $4 \kappa$, and I am inclined to believe it is asymptotically best possible (I guess the Alon paper cites a bound of the form $4 \kappa - O(\sqrt{\kappa}))$.

For the modified problem, where each row can have at most one 1, the stated upper bound $3\kappa$, assuming it is now accurate, is achieved by taking multiple disjoint copies of $\left( \begin{array}{ccc} 0&1&0\\ 0&0&1\\ 1&0&0\\ \end{array} \right)$. This satisfies the constraint using $\kappa$ copies for a total of $3\kappa$.

share|cite|improve this answer
Yes. You are right. I was thinking about the original problem in the paper and forgot some other cases. I now realize that my problem here is not equivalent to the one I was thinking. Anyway, thanks! – Hui Yu Jun 23 '12 at 4:27
Hi, I changed the problem a little bit. I made "for each $i$, there is at most one $j$ such that $a(i,j)=1$" a restriction on the matrix. I think know the problem is equivalent to the problem in the paper. So we have $3\kappa$ as an upper bound. I wonder whether this can be improved. Thanks! – Hui Yu Jun 23 '12 at 4:34
@HuiYu I still don't see how this additional condition changes the $3 \times 3$ example I posted in the comments above. – Erick Wong Jun 23 '12 at 5:14
That still works. But in that case we have $\sum a(i,j)\le 2\kappa+1$, so maybe the bound is $2\kappa+1$. Asymptotically it might be $2\kappa+const$. – Hui Yu Jun 23 '12 at 14:08
@HuiYu In the $6\times 6$ version formed from two copies of the $3\times 3$ example, I get $\kappa = 2$ with the matrix adding up to $6$. How do you arrive at $2\kappa+1$? – Erick Wong Jun 23 '12 at 17:52

Your Answer


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.