# Partitioning the columns of a matrix

I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here:

Suppose you have a matrix $$A\in\mathbb{N}^{n\times m}$$ with integer entries. I want to partition the columns of $$A$$ into $$k$$ groups (or $$k$$ matrices), such that the sum of the minima of every row in each group is minimized. To illustrate: Suppose $$A = \left[ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5\\ 3 & 4 & 5 & 6 & 7\\ 6 & 5 & 4 & 3 & 2\\ \end{array} \right]\text{ .}$$

If I partition the columns into the following three matrices $$A_1 = \left[ \begin{array}{cc} \color{red}1 & 2 \\ \color{red}3 & 4 \\ 6 & \color{red}5 \\ \end{array} \right],\qquad A_2 = \left[ \begin{array}{ccccc} \color{red}3 & 5\\ \color{red}5 & 7\\ 4 & \color{red}2\\ \end{array} \right],\qquad A_3 = \left[ \begin{array}{ccccc} \color{red}4\\ \color{red}6\\ \color{red}3\\ \end{array} \right],$$

the "score" would be $$(1+3+5)+(3+5+2)+(4+6+3)=32$$, the sum of all the red entries (which are the minimal entries in each row).

Also, there is a given minimum size $$M$$ for the groups, so each group must have at least $$M$$ columns.

Is there any feasible algorithm for minimizing this?

• Just to be clear, in this example $k=3$? Is there a requirement that each group is nonempty? – Albert Hendriks Jan 6 '19 at 0:57
• @Albert Hendriks yes, the example is k=3. There may be restrictions on the size of the groups, I forgot to add. I updated my question accordingly – thegentlecat Jan 6 '19 at 2:19