An exact method for triangularizing input-output matrixes

Let M be a non-negative square matrix. To each permutation P of its rows and columns we associate the sum S(P)of the cells that lie above the diagonal. By triangularization of the matrix M we mean the combinatorial problem of finding a permutation that minimizes S(P). The problem is NP hard, except that the case of an order matrix. Up to now only heiristic techiques existed, but it only very bad estimates on their goodness were available. The technique presented here finds in many cases of economical interest the optimal solution joining graph technique and integer programming. Releasing integrity condition and passing to the dual problem allows a powerful simplification through a proper analysis of intersectorial cycles. Mostly the released solution happens to be integer, thus solving the problem. Otherwise it supplies a very good upper estimate of the degree of linearity. Application is then made for Leontief's input-output matrixes of EU counties.