Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The following question was posed to me a while ago. No one I know has a given a satisfactory (or even a complete) proof:

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

What is the smallest that the sum of all the entries in $M$ can be?

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.

[I'm guessing that there should be a "suppose that" in describing M. -- GJK]

share|improve this question
    
Cute problem! I'm reminded of en.wikipedia.org/wiki/Ore%27s_theorem which says in this setting that if M is an adjacency matrix the underlying graph is Hamiltonian, although this isn't close to strong enough as far as I can see. –  Harrison Brown Dec 2 '09 at 2:26
    
I don't think "Combinatorial question" is a descriptive, useful title for this question (that information is already in the tag). –  Daniel Moskovich Dec 2 '09 at 2:29
    
The conjecture is only for even n. –  Kevin O'Bryant Dec 2 '09 at 2:46
    
No, it's new to me, but `the diagonal matrix with $n/2$ in all diag entries' is only a matrix of non-negative integers if $n$ is even. –  Kevin O'Bryant Dec 2 '09 at 6:31
    
But if n^2/2 is a lower bound just for even n, it's a lower bound for all n, since otherwise we'd just glue together four mxm matrices into a (2m)x(2m) matrix. –  Harrison Brown Dec 2 '09 at 7:00
show 1 more comment

7 Answers 7

up vote 11 down vote accepted

The following looks too simple, so perhaps there's a mistake, but here goes.

Let $m$ be the smallest among all row sums and column sums. If $m\geq n/2$, we are done.

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

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

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.

Now what about the case when $n$ is odd?

Edit: 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$. When $n$ is odd, this is the only extremal example up to column and row permutations. Here is a proof.

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.

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.

share|improve this answer
    
That does look too simple, but if there's a mistake I can't find it! –  Harrison Brown Dec 2 '09 at 15:31
    
Hi Konrad, that looks great to me. In fact, your quadratic form is minimized at c = 1/2, and achieves 1/2 there. –  Ben Weiss Dec 2 '09 at 15:34
    
That is nice. I did not see your post when I was editing my (much more circuitous) answer. –  Boris Bukh Dec 2 '09 at 15:46
    
By the way, I think for odd n essentially the same argument will work, although you may have to be slightly more careful with the final analysis. (Asymptotically it's the same, though.) –  Harrison Brown Dec 2 '09 at 20:59
add comment

Again, very nice question!

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

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.

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.

  1. My original plan of attack was to use the existence of a vertex of degree < 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 very 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.

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

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

share|improve this answer
    
Again consider the bipartite graph formulation. Call a vertex "sparse" if it has degree strictly less than n/2; if the bipartite graph has < n^2/2 edges, there will be at least one sparse vertex in each partite set. Note that every pair of sparse vertices in different partite sets must be adjacent; we can use this to show that there are fewer than n/2 sparse vertices in each partite set. Question: Can we now use a divide-and-conquer approach to get the desired lower bound? –  Harrison Brown Dec 2 '09 at 7:35
add comment

[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. ]

This is modification of Harrison Brown's argument.

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&\geq (1-s)(1-t)n^2+\max_r c_r(1-s_r)n^2\\\\ cn^2&\geq (1-s)(1-t)n^2+\sum_r (t-c_r)n\\\\ cn^2&\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&\geq (1-c)(1-t)+T\\\\ c&\geq (1-c)(1-t)+(1-p)(c-T)\\\\ c&\geq p(1-T/c)+(1-p)s\\\\ t&\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&= (1-c)(1-s)+T\\\\ c&= (1-c)(1-s)+(1-p)(c-T)\\\\ c&\geq p(1-T/c)+(1-p)s\\\\ s&\leq c \end{align*}$$ Eliminating $T$ we obtain $$\begin{align*} c&=(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<1$, the inequality $c\geq 1/2$ follows.

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

share|improve this answer
1  
Do you mean to write "Consider any other row $r$, which has $c_rn$ zeros at places that $r_1$ does not"? –  Ben Weiss Dec 2 '09 at 12:45
2  
Hi Boris, Do you think it might be possible to abstract the method you mention in the last line and show that the coefficients obtained tend to 1/2? This would be enough by the argument I mention in my second edit. –  Harrison Brown Dec 2 '09 at 12:56
1  
@Ben: Yes, I fixed it. @Harrison: I do not see how to do it. The resulting argument should be sharp for all the examples in which equality is attained (see Kevin's post), which imposes a lower bound on argument's complexity. –  Boris Bukh Dec 2 '09 at 13:58
add comment

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

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.

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.

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

share|improve this answer
    
I suspect that this isn't quite enough. The reason is that if you frame the question in terms of bipartite graphs, this transformation says that you can shunt around pairs of parallel multiple edges, but it never changes the underlying adjacency structure. But it may be possible to very cleverly take advantage of the distinguished basis... –  Harrison Brown Dec 2 '09 at 7:12
    
When he replaces m_{i',j} by m_{i',j}+1, he may be connecting two vertices which were not connected before –  Mariano Suárez-Alvarez Dec 2 '09 at 9:04
    
Yeah, you're right, which I noticed shortly after posting the comment. But this process can never make the adjacency structure more like what it is in the case where everything's along the diagonal. –  Harrison Brown Dec 2 '09 at 9:06
add comment

The odd case.

Cobbling together some posts that have already appeared, we get:

Claim: For $n$ odd, the minimum is $\frac{n^2 + 1}{2}$.

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.

The checkerboard pattern (with ones in the corners) achieves this bound.

What does the set of all extremal matrices look like?

share|improve this answer
    
I've updated my answer to cover the odd case too. –  Konrad Swanepoel Dec 4 '09 at 16:19
add comment

A partial result: Let $T$ be the total of the entries of $M$. Define a new matrix $M'$ by the formula $$M'_{jk} = nM_{jk} + \sum_{\ell \ne j} M_{\ell k} + \sum_{\ell \ne k} M_{j \ell} \ge n.$$ 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.$$ Edit: When I finally got the formulas right, it just looks like a weaker version of Harrison Brown's argument. Alas.

share|improve this answer
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.