From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Matrix Paths
Date: 7 Jan 1998 08:08:54 GMT

In article <68uqlh$6vg$1@geraldo.cc.utexas.edu>,
Bruce W. Colletti <bcolletti@mail.utexas.edu> wrote:
>Given an nXn matrix with integer entries x(i,j) and zero diagonal.  
>
>For p a permutation on {1..n}, let length(p) be the sum of the 
>x(i,p(i))’s.
>
>What results from matrix theory, if any, will establish the 
>existence of (or find) a negative length path? 

The problem 
minimize sum_{i,j} x(i,j) y(i,j)
subject to
  sum_i y(i,j) = 1 for all j
  sum_j y(i,j) = 1 for all i
  each y(i,j) in {0,1}
is called an "assignment problem", and there are well-known algorithms
for solving it. See any good linear programming text, e.g. Chvatal.

Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Z2