most recent 30 from http://mathoverflow.net 2013-05-25T06:15:09Z http://mathoverflow.net/feeds/question/97175 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97175/small-sums-of-entries-in-submatrices-strange-phenomenon Felix Goldberg 2012-05-17T01:10:13Z 2012-05-18T10:12:07Z

<p>Suppose that $x \in \mathbb{R}^{n}$ is a vector of small positive fractions, <em>i.e.</em> $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 <strong>Stieltjes</strong> matrix and is <strong>diagonally dominant</strong> (at least in the cases of interest). </p> <p>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?)</p> <p>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}}$.</p> <p>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?</p> <p>Does this sound like a problem of extremal combinatorics type perhaps? Any other places to look for apppropriate tools?</p>

http://mathoverflow.net/questions/97175/small-sums-of-entries-in-submatrices-strange-phenomenon/97178#97178 Robert Israel 2012-05-17T01:52:13Z 2012-05-17T01:52:13Z

<p>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 &lt; c &lt; 2 \epsilon/d$ and the true value is more than $1-\epsilon$ times your estimate.</p>

http://mathoverflow.net/questions/97175/small-sums-of-entries-in-submatrices-strange-phenomenon/97293#97293 Brendan McKay 2012-05-18T10:12:07Z 2012-05-18T10:12:07Z

<p>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.</p>