From: Tamas Lengyel <atom@uni-paderborn.de>
Subject: matrix ordering
Date: Fri, 18 Feb 2000 17:17:21 +0100
Newsgroups: sci.math
Summary: [missing]

I have the following problem:

There is an NxM matrix (N<=M). The elements of the matrix are 0 and 1. In
each row there is at least one 1. 
Give an order of the matrix, that results an NxN matrix with 1s in the
diagonal. (The ordering: you can change two coloumns and you can remove a
coloumn)
There is enough to know that this ordering is available, I don't need the
ordering self.
The algorithm must be so fast as possible.


Thanks,
Tom


Ps: Sorry for my bad english.
==============================================================================

From: Christof Vomel <voemel@cerfacs.fr>
Subject: Re: matrix ordering
Date: Fri, 18 Feb 2000 22:27:02 +0100
Newsgroups: sci.math

Your problem is known under (at least) two names:
-finding a maximum transversal
-finding a maximum matching in a bipartite graph
(treat the set of rows and the set of columns as disjoint sets)
AFAIK the fastest algorithm for this is in
Hopcroft and Karp : A n^(5/2) algorithm for maximum matchings in
bipartite graphs, SIAM J. Comput., 2:225-231,1973
Regards,
Christof
==============================================================================

From: israel@math.ubc.ca (Robert Israel)
Subject: Re: matrix ordering
Date: 18 Feb 2000 22:16:49 GMT
Newsgroups: sci.math

In article <Pine.SOL.4.21.0002181716560.3390-100000@widder>,
Tamas Lengyel  <atom@uni-paderborn.de> wrote:

>There is an NxM matrix (N<=M). The elements of the matrix are 0 and 1. In
>each row there is at least one 1. 
>Give an order of the matrix, that results an NxN matrix with 1s in the
>diagonal. (The ordering: you can change two coloumns and you can remove a
>coloumn)
>There is enough to know that this ordering is available, I don't need the
>ordering self.
>The algorithm must be so fast as possible.

This is one version of the "Assignment Problem".  See
e.g. Chvatal's book "Linear Programming".  There are well-known
fast algorithms for solving it.  

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2