Re: A matrix decomposition

I think this is an edge coloring problem. 
That is 
color edges of a graph (bipartite in this case) so that no two edges 
sharinga vertex have the same color.
And of course do this with minimum number of colors. 

Consider the bipartite graph model. 
The constraint on A_k to have one nonzero on each column and row 
correspond to the color constraints. 



----- Original Message -----
From: Alex Pothen <[email protected]>
Date: Friday, March 14, 2003 1:15 pm
Subject: Re: [Csc] 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
> >
> _______________________________________________
> Csc mailing list
> Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
> http://list.odu.edu/listinfo/csc
>

begin:vcard
n:Pinar;Ali
fn:Ali Pinar
tel;work:510 495 2997
org:Lawrence Berkeley Lab;NERSC
version:2.1
email;internet:[email protected]
end:vcard