# How many $1$'s could there be in this sequence? Matrix, operator?

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 $$\sum_{i\in S, j\in S^{C}}a(i,j)\le\kappa$$ 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 $$rank(TP-PTP)\le\kappa$$ 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!

-
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 mathoverflow.net/questions/100417/… –  user17762 Jun 23 '12 at 3:12

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$.
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