pith. sign in

arxiv: 1906.11227 · v1 · pith:URGLDR2Mnew · submitted 2019-06-26 · 🧮 math.OC · math.CO

Nonnegative sum-symmetric matrices, optimal-score partitions, and optimal resource allocation

Iosif Pinelis This is my paper

Pith reviewed 2026-05-25 15:20 UTC · model grok-4.3

classification 🧮 math.OC math.CO
keywords nonnegative matricessum-symmetric matricescircuit matricesoptimal-score partitionsresource allocationmatrix decompositionoptimal partitions
0
0 comments X

The pith

Any nonnegative square matrix with equal row and column sums decomposes into a sum of circuit matrices, which directly yields descriptions of optimal-score partitions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that every nonnegative square matrix whose row sums equal the corresponding column sums can be written as a sum of circuit matrices. This representation is then used to characterize certain optimal-score partitions of a set. The partitions admit a direct interpretation as optimal resource allocations. A reader would care because the result supplies an explicit construction for these optima that relies only on the matrix decomposition and requires no extra conditions on the underlying score function.

Core claim

Any nonnegative square matrix whose column sums equal the corresponding row sums can be represented as the sum of circuit matrices; this fact produces explicit descriptions of optimal-score partitions that model optimal resource allocations.

What carries the argument

The decomposition of nonnegative sum-symmetric matrices into sums of circuit matrices, which supplies the explicit construction for the optimal partitions.

If this is right

  • Optimal resource allocations correspond exactly to partitions obtained from the circuit decomposition of the associated sum-symmetric matrix.
  • The same matrix representation works for any score function that defines the partitions, without additional hypotheses.
  • The construction gives a concrete method for identifying the optimal partitions once the matrix is given.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The circuit decomposition may admit efficient computational procedures when the matrix is sparse.
  • The result could apply to allocation problems on directed graphs where circuits represent feasible cycles of resource movement.
  • Similar decompositions might exist for matrices with additional symmetry or sign constraints.

Load-bearing premise

Every nonnegative sum-symmetric matrix admits a decomposition into circuit matrices that directly produces the claimed optimal-score partitions without further restrictions.

What would settle it

Exhibit a nonnegative square matrix with equal row and column sums that cannot be expressed as any finite sum of circuit matrices, or produce an optimal-score partition that fails to arise from such a decomposition.

read the original abstract

The main result of the note describes certain optimal-score partitions, which can be interpreted as optimal resource allocations. This result is based on the fact that any nonnegative square matrix whose column sums are the same as the corresponding row sums can be represented as the sum of circuit matrices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims that any nonnegative square matrix with equal row and column sums admits a decomposition as a sum of circuit matrices (nonnegative matrices whose support is a directed cycle). This decomposition is then used to characterize certain optimal-score partitions, which are interpreted as optimal resource allocations.

Significance. The decomposition result is a direct consequence of the flow-decomposition theorem for circulations and therefore standard; its application to optimal-score partitions supplies a combinatorial reduction of a linear optimization problem over partitions to a selection over supporting cycles. The resource-allocation interpretation follows immediately once the score is expressed as a linear functional on the decomposition. No additional conditions on the score function or underlying graph are required beyond nonnegativity and sum-symmetry.

minor comments (2)
  1. The abstract and introduction should explicitly cite the flow-decomposition theorem (or an equivalent reference such as Ahuja et al., Network Flows, §3.5) to clarify that the circuit decomposition is not a new result but a standard tool being applied.
  2. Notation for circuit matrices and the precise definition of 'optimal-score partition' should be introduced with a short formal paragraph early in the note rather than left implicit.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive recommendation to accept the manuscript and for the accurate summary of its contributions.

Circularity Check

0 steps flagged

Derivation is self-contained; no circular steps identified

full rationale

The paper establishes a representation of any nonnegative sum-symmetric matrix as a sum of circuit matrices and applies it to optimal-score partitions. This representation is a direct consequence of the standard flow-decomposition theorem for circulations on digraphs, which is an external, independently verifiable result not derived from the paper's own definitions or data. The subsequent description of partitions follows by linearity of the score functional over the decomposition, without any self-definitional equivalence, fitted inputs renamed as predictions, or load-bearing self-citations. No step in the chain reduces to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are identifiable.

pith-pipeline@v0.9.0 · 5553 in / 1000 out tokens · 20890 ms · 2026-05-25T15:20:59.722894+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    In: The Rate and Direction of Inventive Activity: Economic and Social Fa ctors, pp

    Arrow, K.: Economic welfare and the allocation of resourc es for invention. In: The Rate and Direction of Inventive Activity: Economic and Social Fa ctors, pp. 609–626. National Bureau of Economic Research, Inc (1962)

    work page 1962

  2. [2]

    European J

    Azaiez, M.N., Bier, V.M.: Optimal resource allocation fo r security in reliability systems. European J. Oper. Res. 181(2), 773–786 (2007). DOI 10.1016/j.ejor.2006.03.057. URL https://doi.org/10.1016/j.ejor.2006.03.057

    work page doi:10.1016/j.ejor.2006.03.057 2007

  3. [3]

    Bapat, R.B., Raghavan, T.E.S.: Nonnegative matrices and applications, En- cyclopedia of Mathematics and its Applications , vol. 64. Cambridge Uni- versity Press, Cambridge (1997). DOI 10.1017/CBO97805115 29979. URL https://doi.org/10.1017/CBO9780511529979

    work page doi:10.1017/cbo97805115 1997

  4. [4]

    Risk Anal

    Bier, V., Haphuriwat, N., Menoyo, J., Zimmerman, R., Culp en, A.: Optimal resource allocation for defense of targets based on differing measure s of attractiveness. Risk Anal. 28, 763–770 (2008)

    work page 2008

  5. [5]

    Journal of Transport Econom ics and Policy 5(2), 184–200 (1971)

    Dafermos, S., Sparrow, F.T.: Optimal resource allocatio n and toll patterns in user- optimised transport networks. Journal of Transport Econom ics and Policy 5(2), 184–200 (1971). URL http://www.jstor.org/stable/20052229

    work page arXiv 1971

  6. [6]

    Dantzig, G.B., Eaves, B.C., Rothblum, U.G.: A decomposit ion and scaling-inequality for line-sum-symmetric nonnegative matrices. SIAM J. Algebra ic Discrete Methods 6(2), 237–241 (1985). DOI 10.1137/0606021. URL https://doi.org/10.1137/0606021

    work page doi:10.1137/0606021 1985

  7. [7]

    Invasive computing: An overview,

    Dudley, R.M., Norvaiša, R.: Concrete functional calculu s. Springer Monographs in Mathematics. Springer, New York (2011). DOI 10.1007/978-1 -4419-6950-7. URL https://doi.org/10.1007/978-1-4419-6950-7

    work page doi:10.1007/978-1 2011

  8. [8]

    Proceedings of the National Academy of Sciences 111(49), 17,486–17,491 (2014)

    Govern, C.C., ten W olde, P.R.: Optimal resource allocati on in cellular sensing systems. Proceedings of the National Academy of Sciences 111(49), 17,486–17,491 (2014). DOI 10.1073/pnas.1411524111. URL https://www.pnas.org/content/111/49/17486

    work page doi:10.1073/pnas.1411524111 2014

  9. [9]

    Gravett, K.A.H.: Ordered abelian groups. Quart. J. Math. Oxford Ser. (2) 7, 57–63 (1956). DOI 10.1093/qmath/7.1.57. URL https://doi.org/10.1093/qmath/7.1.57

    work page doi:10.1093/qmath/7.1.57 1956

  10. [10]

    Sitzungsberichte der Kaiser- lichen Akademie der Wissenschaften, Wien, Mathematisch – N aturwissenschaftliche Klasse (Wien

    Hahn, H.: Über die nichtarchimedischen Größensysteme. Sitzungsberichte der Kaiser- lichen Akademie der Wissenschaften, Wien, Mathematisch – N aturwissenschaftliche Klasse (Wien. Ber.) 116, 601–655 (1907)

    work page 1907

  11. [11]

    Blaisdell Publishi ng Co

    Hall Jr., M.: Combinatorial theory. Blaisdell Publishi ng Co. Ginn and Co., W altham, Mass.-Toronto, Ont.-London (1967)

    work page 1967

  12. [12]

    Russian Mathematical Surveys 42, 233–270 (1987)

    Kantorovich, L.V.: My journey in science (proposed repo rt to the Moscow Mathe- matical Society). Russian Mathematical Surveys 42, 233–270 (1987). DOI 10.1070/ RM1987v042n02ABEH001311

    work page 1987

  13. [13]

    T he American Economic Re- view 67(3), 261–274 (1977)

    Koopmans, T.C.: Concepts of optimality and their uses. T he American Economic Re- view 67(3), 261–274 (1977). URL http://www.jstor.org/stable/1831399

    work page arXiv 1977

  14. [14]

    Levi, F.W.: Ordered groups. Proc. Indian Acad. Sci., Sec t. A. 16, 256–263 (1942)

    work page 1942

  15. [15]

    IEEE Transactions on In formation Theory 47(3), 1103–1127 (2001)

    Li, L., Goldsmith, A.J.: Capacity and optimal resource a llocation for fading broadcast channels—Part ii: Outage capacity. IEEE Transactions on In formation Theory 47(3), 1103–1127 (2001). DOI 10.1109/18.915667

    work page doi:10.1109/18.915667 2001

  16. [16]

    Pinelis, I.: An extension of Hall’s theorem. Ann. Comb. 6(1), 103–106 (2002). MR1923091

    work page 2002

  17. [17]

    Pinelis, I.: A discrete mass transportation problem for infinitely many sites, and general representant systems for infinite families. Math. Methods O per. Res. 58(1), 105–129 (2003). MR2002566

    work page 2003

  18. [18]

    Richter, A., Brandeau, M., Owens, D.: An analysis of opti mal resource allocation for prevention of infection with human immunodeficiency virus ( HIV) in injection drug users and non-users. Med. Decis. Making 19, 167–179 (1999)

    work page 1999

  19. [19]

    In: 2006 IEEE International Symposium on Informat ion Theory, pp

    Seong, K., Mohseni, M., Cioffi, J.M.: Optimal resource all ocation for OFDMA downlink systems. In: 2006 IEEE International Symposium on Informat ion Theory, pp. 1394–1398 (2006). DOI 10.1109/ISIT.2006.262075

    work page doi:10.1109/isit.2006.262075 2006

  20. [20]

    URL https://patents.google.com/patent/US6877035

    Shahabuddin, J.S., et al.: System for optimal resource a llocation and planning for host- ing computing services (2005). URL https://patents.google.com/patent/US6877035. US Patent US6877035

    work page 2005