# Select certain number of column elements of a stochastic matrix, maximum one element per row

Consider a $$m \times n$$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1. We now want to choose elements $$a_{i,j}$$ of the Matrix.
For every column $$k_j$$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.

I guess this problem is NP-hard. I didn't found an efficient solution. To prove that, I want to find a reduction from a NP-hard problem to my problem.

Hopefully someone has an idea for a reduction (or an efficient algorithm).

Duplicate the $$j$$th column $$k_j$$ times to reduce to the case in which $$k_j = 1$$. You are now looking at the assignment problem, which can be solved efficiently.