Extremal question on matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T16:44:06Z http://mathoverflow.net/feeds/question/7541 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7541/extremal-question-on-matrices Extremal question on matrices Ben Weiss 2009-12-02T02:12:07Z 2009-12-04T16:17:33Z <p>The following question was posed to me a while ago. No one I know has a given a satisfactory (or even a complete) proof:</p> <p>Suppose that $M$ is an $n$ x $n$ matrix of non-negative integers. Additionally, suppose that if a coordinate of $M$ is zero, then the sum of the entries in its row and its column is at least $n$.</p> <p>What is the smallest that the sum of all the entries in $M$ can be?</p> <p>The conjecture posed to me was that it was $\frac{n^2}{2}$ which is obtained by the diagonal matrix with $\frac{n}{2}$ in all diagonal entries.</p> <p>[I'm guessing that there should be a "suppose that" in describing M. -- GJK]</p> http://mathoverflow.net/questions/7541/extremal-question-on-matrices/7543#7543 Answer by Harrison Brown for Extremal question on matrices Harrison Brown 2009-12-02T02:45:58Z 2009-12-02T12:53:33Z <p>Again, very nice question!</p> <p>Edit: I can get a lower bound of $\frac{3 - \sqrt{5}}{2} n^2$ as follows: Set $c = \frac{3 - \sqrt{5}}{2}$ for conciseness. Assign a (not necessarily simple) bipartite graph to $M$ in the obvious way. Now if the sum of some row is less than $cn$, there must be at least $(1-c)n$ vertices in the other partite set of the graph that aren't adjacent to the corresponding vertex, which therefore must each have degree at least $(1-c)n$ and so have total degree at least $(1-c)^2n^2 \geq cn^2$.</p> <p>Unfortunately c is only about 0.38, and that's the highest constant this argument can give us. But maybe it can be modified a little bit to give us 0.5.</p> <p>Edit 2: This problem really fights back! I'm beginning to think that there's some kind of dichotomy in play here, so that we may end up needing some kind of structure theorem... I've thought about this way more than I should have, and still haven't managed to appreciably improve the above bound (actually I think I have got the constant up to $\frac{3 - \sqrt{2}}{2}$, which is a smidgen under 0.4, by a very similar argument) but I think a record of what I've tried might be useful.</p> <ol> <li><p>My original plan of attack was to use the existence of a vertex of degree &lt; n/2 to perform some clever counting argument which shows that there are at least $n^2/2$ edges. Of course, there's certainly no guarantee that this wouldn't work, but it appears that you have to be <em>very</em> careful with the counting: the disjoint union of the complete bipartite graphs $K_{m-1, m-1}$ and $K_{m+1, m+1}$ satisfies the desired property and has the maximal allowed number of low-degree vertices, but only has $n^2/2 + 2$ edges! It's not clear to me how to construct a counting argument which can handle both the above situation and more "typical" ones in which the vertices have a wide range of degrees, so this approach was put to the side.</p></li> <li><p>However, there may be a workaround: we don't actually have to show that $n^2/2$ is a lower bound! In fact if we can show a lower bound of the form $(0.5-o(1))n^2$ then the desired bound follows. Why? Because if we had a matrix with the desired property and density less than 1/2, we could stick a bunch of copies of it together to get arbitrarily large matrices with the same density. This means that we can sacrifice, for example, O(n) factors in our counting arguments.</p></li> <li><p>By the way, here's one dichotomy which I think might have a chance of leading to a proof. Consider a multigraph with the desired property; let G denote the bipartite complement of its underlying simple graph. If G has a "large" matching, i.e., one of size n-o(n), we get our weak lower bound by a simple counting argument. If G has no large matching, then maybe we can use this property to force some structure on the original multigraph, which then shows that it has density at least 1/2. </p></li> </ol> http://mathoverflow.net/questions/7541/extremal-question-on-matrices/7545#7545 Answer by Kevin O'Bryant for Extremal question on matrices Kevin O'Bryant 2009-12-02T02:49:20Z 2009-12-02T06:41:17Z <p>It's worth noting, perhaps, that the diagonal matrix is not the unique extremal matrix. A checkerboard pattern of 1's and 0's also achieves $n^2/2$.</p> <p>There are certain transformations that preserve the given properties and simplify the matrix. For example, we can transpose the matrix, we can exchange any pair of rows, we can exchange any pair of columns.</p> <p>There's another transformation whose effect is more subtle. Suppose $m_{ij}\ge2$. If any $m_{i'j'}\ge2$ with $i'\le i+1$ and $j'\ge j+1$, then we can replace $m_{ij},m_{i',j'},m_{i',j},m_{i,j'}$ with $m_{ij}-1,m_{i'j'}-1,m_{i',j}+1,m_{i,j'}+1$, respectively. This preserves all of the row and column sums, and moves mass away from the lower-left and upper-right corners, and towards the diagonal. The only reason we need $m_{ij}\ge1$ is that we have to be careful about creating 0's in the matrix.</p> <p>It feels like this is only one or two WOLOGs away from saying that we can assume the matrix is diagonal, in which case the problem is easy (sum is $n^2/2$ or $(n^2+n-2)/2$ depending on the parity of $n$).</p> http://mathoverflow.net/questions/7541/extremal-question-on-matrices/7547#7547 Answer by Greg Kuperberg for Extremal question on matrices Greg Kuperberg 2009-12-02T03:13:17Z 2009-12-02T03:21:14Z <p>A partial result: Let $T$ be the total of the entries of $M$. Define a new matrix $M'$ by the formula <code>$$M'_{jk} = nM_{jk} + \sum_{\ell \ne j} M_{\ell k} + \sum_{\ell \ne k} M_{j \ell} \ge n.$$</code> Let $T'$ be the total of $M'$. Then $T' = (3n-2)T$ and $T' \ge n^3,$ so $$T \ge \frac{n^3}{3n-2} > \frac{n^2}3.$$ <strong>Edit:</strong> When I finally got the formulas right, it just looks like a weaker version of Harrison Brown's argument. Alas.</p> http://mathoverflow.net/questions/7541/extremal-question-on-matrices/7577#7577 Answer by Boris Bukh for Extremal question on matrices Boris Bukh 2009-12-02T12:35:17Z 2009-12-02T15:41:46Z <p>[Edit: Originally, I gave the bound of $\frac{5-\sqrt{17}}{2}n^2$, but the remaining slack in the problem was easy to eliminate by considering the row with minimal sum. If my calculations are correct, this solves the problem. ]</p> <p>This is modification of Harrison Brown's argument.</p> <p>Suppose the total is less than $cn^2$. Let $r_1$ be a row with minimal sum $sn\leq cn$. Let us say that $r_1$ has $tn$ non-zero entries. Of course, $t\leq s$. Consider any other row $r$, which has $c_r n$ zeros at places that $r_1$ does not, and whose sum is $s_r n$. Then the total sum is at least $c_r(1-s_r)n^2+(1-s)(1-t)n^2$. On the other hand, the sum of $r$ restricted to columns where $r_1$ is non-zero is at least $(t-c_r) n$. Hence the total sum is at least $\sum_r (t-c_r) n + (1-s)(1-t) n^2$. To summarize \begin{align*} cn^2&amp;\geq (1-s)(1-t)n^2+\max_r c_r(1-s_r)n^2\\ cn^2&amp;\geq (1-s)(1-t)n^2+\sum_r (t-c_r)n\\ cn^2&amp;\geq \sum_r s_r n \end{align*} For a fixed value of $\sum c_r$ and $T=\max c_r(1-s_r)$ the minimum of $\sum s_r$ is achieved when all but one $c_r$ are equal to $T/(1-s)$ or $c$ (that follows by optimizing a sum of two terms of the form $\max(s,1-T/c_r)$ ). Let $p$ be the proportion of rows $r$ such that $c_r=c$. Then \begin{align*} c&amp;\geq (1-c)(1-t)+T\\ c&amp;\geq (1-c)(1-t)+(1-p)(c-T)\\ c&amp;\geq p(1-T/c)+(1-p)s\\ t&amp;\leq s\leq c \end{align*} I claim that the minimum of $c$ under these constraints occurs when the firs of these inequalities are equalities. Indeed, if the first inequality is strict, increase $T$. If the second inequality is strict, decrease $p$. Moreover, if $s\neq t$, we can decrease $s$. Thus \begin{align*} c&amp;= (1-c)(1-s)+T\\ c&amp;= (1-c)(1-s)+(1-p)(c-T)\\ c&amp;\geq p(1-T/c)+(1-p)s\\ s&amp;\leq c \end{align*} Eliminating $T$ we obtain \begin{align*} c&amp;=(2-p)(1-c)(1-s), \end{align*} Solving the equation for $s$ and substituting into the inequality $s\leq c$, we get (please check!) \begin{align*} p(1-c)^2\geq 2c^2-5c+2 \end{align*} Substituting this inequality for $p$ into $c\geq p(1-T/c)+(1-p)s$ and using the expressing for $s$ and $T$ that we have, we finally arrive (please double check!) to $$(1-2c)(2-c)(2c^3-6c^2+3c-1)\geq 0$$. Since $2c^3-6c^2+3c-1$ is negative for $c&lt;1$, the inequality $c\geq 1/2$ follows.</p> <p>[Before the edit, the answer was concluded by the following sentence, to which the comment refers]. In general it is tempting to consider arbitrary sets of $k$ rows, and if the union of their zero sets is large, use that to say that the sum over corresponding columns is large.</p> http://mathoverflow.net/questions/7541/extremal-question-on-matrices/7581#7581 Answer by Konrad Swanepoel for Extremal question on matrices Konrad Swanepoel 2009-12-02T15:16:37Z 2009-12-04T16:17:33Z <p>The following looks too simple, so perhaps there's a mistake, but here goes.</p> <p>Let $m$ be the smallest among all row sums <em>and</em> column sums. If $m\geq n/2$, we are done.</p> <p>Otherwise, $m=cn$ with $c\lt 1/2$. Suppose it is a column which has sum $m$. This column has at least $n-m$ zeroes, and each of the corresponding rows has sum $\geq n-m$. The remaining $m$ rows each has sum $\geq m$.</p> <p>In total we have a sum of at least $(n-m)^2+m^2 = ((1-c)^2+c^2)n^2$. Finally, note that $(1-c)^2+c^2\gt 1/2$ when $c\lt 1/2$.</p> <p>So this gives a lower bound of $n^2/2$, and equality requires that any row and any column sums to exactly $n/2$, so the matrix is a sum of $n/2$ permutation matrices by König's Theorem.</p> <p>Now what about the case when $n$ is odd?</p> <p><strong>Edit:</strong> Since the sum is an integer, the lower bound $n^2/2$ actually gives $(n^2+1)/2$, which can be attained by for example taking the direct sum of an $m\times m$ matrix of $1$s with an $(n-m)\times (n-m)$ matrix of $1$, where $m=(n-1)/2$. <em>When $n$ is odd, this is the only extremal example up to column and row permutations.</em> Here is a proof.</p> <p>Let $m$ now, as originally, denote the minimum over all row and column sums. If $m\geq (n+1)/2$, then the total sum is too large: at least $nm\geq n(n+1)/2$. Therefore, $m\leq(n-1)/2$, and the $(n-m)^2+m^2$ lower bound now gives a total sum of at least $(n-n(n-1)/2)^2+((n-1)/2)^2 = (n^2+1)/2$ (using the fact that $(1-c)^2+c^2$ is decreasing when $c\lt 1/2$). So up to now we have only rederived the lower bound for $n$ odd.</p> <p>However, if equality now holds, we get that $m=(n-1)/2$, that each row adds up to either $m$ ($m$ times) or $n-m$ ($n-m$ times), and that in a column that adds up to $m$, there are exactly $n-m$ $0$s, so all entries are $0$ or $1$ (and similar statements with columns and rows interchanged). By permuting the rows and columns we may assume that the first $m$ rows [columns] each add up to $m$.There can't be a $0$ in the upper left $m\times m$ submatrix, since then the sum of the row and column containing the $0$ adds up to only $2m\lt n$. We have found a direct sum of an $m\times m$ and an $(n-m)\times(n-m)$ all $1$ matrix.</p> http://mathoverflow.net/questions/7541/extremal-question-on-matrices/7693#7693 Answer by Josh Brown Kramer for Extremal question on matrices Josh Brown Kramer 2009-12-03T18:01:02Z 2009-12-03T18:01:02Z <p>The odd case.</p> <p>Cobbling together some posts that have already appeared, we get:</p> <p>Claim: For $n$ odd, the minimum is $\frac{n^2 + 1}{2}$.</p> <p>Pf: As Harrison Brown points out, since $\frac{n^2}{2}$ is a lower bound for $n$ even, it is a lower bound for $n$ odd. Hence, $\lceil\frac{n^2}{2}\rceil = \frac{n^2 + 1}{2}$ is as well.</p> <p>The checkerboard pattern (with ones in the corners) achieves this bound.</p> <p>What does the set of all extremal matrices look like?</p> http://mathoverflow.net/questions/7541/extremal-question-on-matrices/7706#7706 Answer by Kristal Cantwell for Extremal question on matrices Kristal Cantwell 2009-12-03T19:38:51Z 2009-12-03T19:38:51Z <p>If there is an $n x n$ matrix of non-negative integers satisfying if any entry is zero then the sum of its row and column is $n$ and we want the smallest sum. We start by trying to construct the longest sequence of zeros whose columns coordinates are disjoint and whose row coordinates are disjoint. Say this process stops at $m$. Then the remaining $(n-m) x (n-m)$ entries must be 1 or more. The other entries are covered covered once by a row or column if the have one coordinate equal to used rows or columns or twice if they have two coordinates used in the process thus we get $nxm-m^{2}/2 +m +(n-m)^{2}$ as a lower bound of the sum of points of all entries. Taking the derivative with respect to m gives $n-m+1/2-2n+2m = -n-m/2+1/2$ as the derivative it is always negative so the lower bound is decreasing as $m$ increases thus $m=n$ is a gives a lower bound but in that case we have $n$ zeros and every point is covered twice once for the first coordinate and once for the second so the lower bound is $n^{2}/2$. For $n$ even this can be realized by a checkerboard pattern. For n odd one half must be added and that can be realized as an odd checkerboard pattern. Then the lowest sum for even $n$ is $n^{2}/2$ and for odd $n$ is $n^{2}+1/2$</p>