If $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ is the cost-matrix of an assignment problem, then the usual statement of the problem of finding an optimal assignment is to identify $n$ elements $a\_{i,\,\pi(i)},\ i=1\cdots n$ of least cost-sum, i.e. to *directly* determine the solution set from $\boldsymbol{A}$ by modifying its entries e.g. according to the Hungarian algorithm.



> 
> **Question:**
> 
> 
> can the following interpretation of the assignment problem fail to report the optimal solution:
> 
> 
> `determine the sequence of line-exchanges that renders the sum of the diagonal-elements optimal`?
> 
> 
> 


  

If the permutation-formulation also generates the optimal solution to the assignment problem, that would yield a greedy algorithm:


Exchanging two lines also exchanges two on-diagonal elements with two off-diagonal elements with known effect on the cost-sum of the elements on the diagonal.  



**Addendum:**  

as the counter example of Brendan McKay shows, swapping pairs of rows or columns may not suffice to find the optimal assignment.  

A preprocessing step that can deal with the counter example would be to first rotate the columns until the diagonal-elements have optimal cost-sum and only then strive for further improvements via swapping pairs of rows or columns.  

It may even be necessary to interleave line-swapping with column-rotations frequently so that the elements on the principal diagonal always have better cost-sum than the elements on other diagonals.



Interpreting optimal matchings as permutations
$$\pmatrix{ 2&3&0&0\\0&2&3&0\\0&0&2&3\\3&0&0&2}$$


Every swap of two columns or swap of two rows decreases the trace. However, there is a permutation putting all the 3s on the diagonal.


