# Optimal choice of matrix element subset

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?

• This is an instance of the "assignment problem"; you can use the "Hungarian algorithm" to solve it. – kimchi lover Dec 6 '19 at 19:27
• Thank you, this is exactly what I was searching for! – fazekaszs Dec 7 '19 at 20:19