RE: Re: A matrix decomposition

Alex> Consider the bipartite graph of A, then your first problem
Alex> is to partition the edges of A into the fewest number of
Alex> maximum matchings in the graph.

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.