Variations on the theorem of Birkhoff-von Neumann and extensions

The theorem of Birkhoff-von Neumann (see [2]) on the decomposition of bistochastic matrices (i.e., matrix with nonnegative entries and all row sums and column sums equal to one) has found various applications in scheduling; it is in particular a basic tool in the two-phase method of the preemptive scheduling problem on various machines with different capacities (see [4],[5],[6]). Let us now formulate a variation of the theorem. Given a real matrix A with entries aij unrestricted in sign, we denote by r(A, i)(resp.c(A, j)) the sum σ aij (resp._σi aij) of the entries in row i (resp. in column j). Furthermore let T(A) be defined by T(A) = max( max i{divides}r(A,i){divides} max j{divides}c(A,j){divides}). Matrix A is called regular if {divides}r(A, i) {divides} = {divides} c(A, j){divides} = T(A) for any row i and any column j. Notice that if the entries aij are unrestricted in sign, then A need not be a square matrix.