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.



Partitioning a matrix with bounded row sums
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.


