# Partitioning a matrix with bounded row sums

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

I want to partition the index set $I = \{1, 2 \ldots n\}$ 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:

1. $\cup_{1 \leq k \leq t} I_k = I$
2. For all $1 \leq k \leq t$, $\sum_{i \in I_k}a_{ij} \leq 1$ for all $j \in I_k$
3. The number $t$ is minimized

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.

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.

• So to rephrase the question, you take an edge-weighted digraph with maximum in-degree $k$, and you want to $t$-colour the vertices such that the maximum out-degree to any colour is $k$, right? (I guess you know about the Alon-Tarsi list colouring theorem.) – Andrew D. King Dec 15 '10 at 15:08
• Look at A remark on finite-dimensional $P\sb{\lambda }$-spaces by J. Bourgain Studia Mathematica [0039-3223] Bourgain yr: 1982 vol: 72 iss: 3 pg: 285 -289. – Bill Johnson Dec 15 '10 at 16:08
• Well, when you say "the maximum out-degree to any colour" if you mean, the maximum weighted out-degree from any node to nodes of the same color, they yes. I actually didn’t know about the theorem you mention :) – Pradipta Dec 15 '10 at 16:09
• Yes, that's what I mean. Here is the link for the original Alon-Tarsi paper springerlink.com/content/u627qn50r7013363 , but you might get more out of it by looking at the papers which cite it, for example onlinelibrary.wiley.com/doi/10.1002/jgt.20500/abstract . The proof of their result, which relates to list colourings, uses combinatorial nullstellensatz, which is useful but intimidating. Better to look at what you can do using their theorem as a black box, first. – Andrew D. King Dec 15 '10 at 16:21
• Thanks to both Andrew and Bill. I’ll take a look at both papers. – Pradipta Dec 15 '10 at 16:24

Ok, I think there are examples where $\Omega(\log n)$ colors are needed.
Here’s an example, let $a_{ij} = \frac{1}{i}$ for $j < 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.
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.