Re: A matrix decomposition

Cleve and Alex,

    > From: CleveAshcraft <[email protected]>
    > Date: Fri, 14 Mar 2003 12:30:45 -0800
    > ...
    > I've got a n x n matrix A with a zero diagonal, and whose entries
    > are 0 or 1. I need to express A as a sum of matrices
    >
    >    A = A_1 + A_2 + ... + A_m
    >
    > such that each A_k has row sums and column sums that are bounded
    > above by 1. In other words, each row and column of A_k can have at
    > most one nonzero entry.
    >
    > I am looking for such a decomposition that has the smallest number of
    > matrices. ...

    ===== ===== ===== ===== =====
    
    > From: Alex Pothen <[email protected]>
    > Date: Fri, 14 Mar 2003 16:15:25 -0500 (EST)
    > ...
    > Consider the bipartite graph of A, then your first problem
    > is to partition the edges of A into the fewest number of
    > maximum matchings in the graph.
    > Your lower bound is the maximum degree of
    > a vertex in the bipartite graph, say D.
    > A partition into D maximum matchings can always be achieved
    > by running a maximum matching algorithm D times.
    > ...

This characterization of the problem is correct, but the algorithm is not.
For example, consider the matrix and decomposition

  [ 0 1 0 ]   [ 0 1 0 ]   [ 0 0 0 ]
  [ 1 0 0 ] = [ 0 0 0 ] + [ 1 0 0 ]
  [ 1 1 0 ]   [ 1 0 0 ]   [ 0 1 0 ]

If the first maximum matching produces {(1,2), (2,1)}, then the resulting
decomposition will be

  [ 0 1 0 ]   [ 0 1 0 ]   [ 0 0 0 ]   [ 0 0 0 ]
  [ 1 0 0 ] = [ 1 0 0 ] + [ 0 0 0 ] + [ 0 0 0 ]
  [ 1 1 0 ]   [ 0 0 0 ]   [ 1 0 0 ]   [ 0 1 0 ]

which is not optimal.
=====

    > From: CleveAshcraft <[email protected]>
    > Date: Fri, 14 Mar 2003 13:53:47 -0800
    > ...
    > Not quite, I think. Disjoint matching perhaps.
    > Here is my present algorithm.
    >
    > k = 0 ;
    > while A != 0
    >    k = k + 1
    >    find maximum matching of A and form A_k
    >    A := A - A_k
    > end
    >
    > It should be easy to find a counterexample where this does not find
    > the minimum number of A_k terms.

See the example above.

To fix the problem, do weighted matching with weights as follows:

  Let N = max (#rows, #columns)
  Let M = maximum row or column sum
  Let wr(i) = N if row_sum_i = M, else 1
  Let wc(j) = N if col_sum_j = M, else 1
  Then w(i,j) = wr(i) * wc(j) for each edge (i,j)

Although I have not written down a formal proof, I believe this ensures
that the maximum row or column sum in the "reduced" matrix is M-1, which is
sufficient to prove that M matrices A_k suffice.  (Bora Ucar obtained this
result using the equivalence to edge coloring and a theorem of Koenig.)
======

    > From: CleveAshcraft <[email protected]>
    > Date: Fri, 14 Mar 2003 12:30:45 -0800
    > ...
    > As a generalization, I also have A with a zero diagonal and whose
    > offdiagonal entries are nonnegative (not just 0 or 1), and I need
    > to find such a decomposition with close to a minimum number of terms.

    ===== ===== ===== ===== =====

    > From: Alex Pothen <[email protected]>
    > Date: Fri, 14 Mar 2003 16:15:25 -0500 (EST)
    > ...
    > I do not know the answer to  your second (weighted) problem right now,
    > but I would  look up discussions of Koenig's Lemma in the
    > Lovasz Plummer book on matching theory or in some other source.

I suspect that this can again be solved using the algorithm above, but with
maximum weighted network flow replacing maximum matching.  I will try to work
out the details.
=====

Where do these problems arise?

--Stan-