Partitioning a matrix with bounded row sums - MathOverflow

Partitioning a matrix with bounded row sums

2010-12-15T14:30:50Z

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:

$\cup_{1 \leq k \leq t} I_k = I$
For all $1 \leq k \leq t$, $\sum_{i \in I_k}a_{ij} \leq 1$ for all $j \in I_k$
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.

Answer by Grant Izmirlian for Partitioning a matrix with bounded row sums

2010-12-15T19:26:24Z

Why the qualification "bounded row-sums" for a matrix of finite dimension?

Answer by Pradipta for Partitioning a matrix with bounded row sums

2010-12-16T15:58:01Z

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.