# small sums of entries in submatrices - strange phenomenon

Suppose that $x \in \mathbb{R}^{n}$ is a vector of small positive fractions, i.e. $x_{i} \approx \frac{1}{n}$. The exact values are unknown. I form the matrix $M=diag(x)-\frac{xx^{T}}{2}$ which is a Stieltjes matrix and is diagonally dominant (at least in the cases of interest).

Now what I am interested in are the sums of the entries of small rectangular submatrices of $M$. These sums turn out to be very small in absolute value in practice, however my efforts to estimate them yield bounds that are too crude. This makes me suspect that some phenomenon is at work under the hood, about which I do not know, and I am hoping that somebody can point out a direction in which to look. (Does this situation/property has a name?)

More formally, take a set of $d$ rows and $d$ columns and look at the $d \times d$ submatrix of $M$ that they induce. Call this submatrix $M_{0}$. My reasoning goes like this: at the worst case, each row of $M_{0}$ contains at most one diagonal entry of $M$. The rest of the entries in the row push it down but we do not know by how much exactly. Rows of $M_{0}$ that do not contain a diagonal entry of $M$ sum to at most the value of the diagonal entry. Therefore the best bound I come up with is $dC$, where $C=max_{1 \leq i \leq n}\{x_{i}\}$.

As I said, in practice this bound is off by an order of magnitude and I would very much like to improve it. But how?

Does this sound like a problem of extremal combinatorics type perhaps? Any other places to look for apppropriate tools?

Perhaps there's something I don't understand, but your bound is asymptotically best possible. That is, by taking all $x_i = c$ and the same set for the $d$ rows and the $d$ columns the sum of entries in $M_0$ is $d c - d^2 c^2/2 = d c (1 - d c/2)$. For any $d$ and any $\epsilon > 0$, take $0 < c < 2 \epsilon/d$ and the true value is more than $1-\epsilon$ times your estimate.
• First of all, thanks a lot for devoting thought to this! Now, I'm almost convinced, but please recall that I also have the extra condition that $x_{i} \approx \frac{1}{n}$. Although for $n$ large enough your argument stilll takes the biscuit, what happens when $n$ is fixed and not terribly big and we have little control on $x_{i}$? – Felix Goldberg May 17 '12 at 8:30
• What precisely do you mean by $x_i \approx 1/n$ when $n$ is fixed? – Robert Israel May 18 '12 at 5:30
Unless I don't understand the question: Consider the submatrix formed by rows $R$ and columns $C$. Then the sum of this submatrix is $$\sum_{k\in R\cap C} x_k - \tfrac12 \biggl(\sum_{i\in R} x_i\biggr) \biggl(\sum_{j\in C} x_j\biggr).$$ The question is a bit too vague to say more, as this expression is pretty simple.