Re: A matrix decomposition

Cleve,

Interesting question!
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.

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 will do this when I get back to my office next.

--Alex


On Fri, 14 Mar 2003, CleveAshcraft wrote:

> Folks,
>
> I've got a problem, and a working solution, but I've got a feeling
> this might be a well-studied case that I am unaware of.
>
> 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. It is clear that m is bounded above by the number of nonzero
> entries in A and bounded below by the maximum row or column sum of A.
>
> For most of my applications, A is sparse but not too sparse, and the
> decomposition I find has close to the lower bound of terms. It would
> be of interest to find the minimum number of terms, and an algorithm
> to find such a decomposition with this minimum number of terms.
>
> 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.
>
> Any insight I would appreciate.
>
> --Cleve Ashcraft
> _______________________________________________
> Csc mailing list
> Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
> http://list.odu.edu/listinfo/csc
>