Partitioning a matrix with bounded row sums - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T03:14:50Z http://mathoverflow.net/feeds/question/49532 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49532/partitioning-a-matrix-with-bounded-row-sums Partitioning a matrix with bounded row sums Pradipta 2010-12-15T14:30:50Z 2011-03-02T00:00:19Z <p>Let $A$ be a $n \times n$ matrix with non-negative entries $a_{ij}$, where $a_{ij}$ is the entry in the $i^{th}$ row and $j^{th}$ column. Assume $\sum_{1 \leq j \leq n} a_{ij} \leq 1$ for all $1 \leq i \leq n$. Also assume $a_{ii} = 0$ for all $1 \leq i \leq n$. </p> <p>I want to partition the index set <code>$I = \{1, 2 \ldots n\}$</code> into minimum number of sets $I_1, I_2, \ldots I_t$ so that the column sum is bounded by $1$ in each sub-matrix defined by the sets, or more formally:</p> <ol> <li>$\cup_{1 \leq k \leq t} I_k = I$</li> <li>For all $1 \leq k \leq t$, $\sum_{i \in I_k}a_{ij} \leq 1$ for all $j \in I_k$</li> <li>The number $t$ is minimized</li> </ol> <p>I can construct examples where $t$ has to be at least $2$, on the other hand, $t = \Theta(\log n)$ would suffice for all such matrices. I am wondering if a tighter bound exists.</p> <p>Motivation: this is a sort of generalization of the coloring problem in bounded out-degree digraphs. If a di-graph has out-degree upper bounded by $k$ it can be colored with $k + 1$ colors.</p> http://mathoverflow.net/questions/49532/partitioning-a-matrix-with-bounded-row-sums/49556#49556 Answer by Grant Izmirlian for Partitioning a matrix with bounded row sums Grant Izmirlian 2010-12-15T19:26:24Z 2010-12-15T19:26:24Z <p>Why the qualification "bounded row-sums" for a matrix of finite dimension? </p> http://mathoverflow.net/questions/49532/partitioning-a-matrix-with-bounded-row-sums/49657#49657 Answer by Pradipta for Partitioning a matrix with bounded row sums Pradipta 2010-12-16T15:58:01Z 2010-12-16T16:14:35Z <p>Ok, I think there are examples where $\Omega(\log n)$ colors are needed. </p> <p>Here’s an example, let $a_{ij} = \frac{1}{i}$ for $j &lt; i$ and $a_{ij} = \frac{1}{j^2}$ for $j > i$. Then $\sum_{j} a_{ij} = \frac{i-1}{i} + \sum_{j > i} \frac{1}{j^2} = O(1)$. Of course, the bound is $O(1)$ instead of $1$, but that can be normalized and all that. </p> <p>However, note that $\sum_j a_{j1} = \Omega(\log n)$ and if we only have $o(\log n)$ partitions, this sum cannot be "distributed" into small enough parts.</p>