1
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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}$? $\endgroup$
    – Felix Goldberg
    Commented May 17, 2012 at 8:30
  • $\begingroup$ What precisely do you mean by $x_i \approx 1/n$ when $n$ is fixed? $\endgroup$
    – Robert Israel
    Commented May 18, 2012 at 5:30
  • $\begingroup$ Never mind, I've seen the light already! :) (The question was a fragment of a larger investigation; what I am really interested in is the sum of sums over certain ubmatrices; your first reply got me out of trying to estimate each sum independently, which is rather a dead-end and into estimating the sum of sums; but that is a different story, which doesn't belong here). Thanks again. $\endgroup$
    – Felix Goldberg
    Commented May 18, 2012 at 11:15
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, I've got this far. You are right that without further information this is more or less the end of the story... Thanks! $\endgroup$
    – Felix Goldberg
    Commented May 18, 2012 at 11:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .