Optimal choice of matrix element subset

42 Views Asked by At

Let's suppose that we have an $n \times n$ matrix $M$ containing only strictly positive elements $m_{ij}$. Is there a fast algorithm/procedure that finds the subset of elements $$m_{i_{\nu}j_{\nu}}$$ $$i_{\nu}=i_{\mu} \text{, } j_{\nu}=j_{\mu} \iff \nu = \mu$$ $$ \nu \in [1, n]$$ that minimizes the sum $$\sum_{\nu=1}^{n} m_{i_{\nu}j_{\nu}}$$ So with words: how can I choose $n$ elements out of a positive matrix, such that I only use one element from each row and column and the sum of these elements is minimal?