arxiv: 2605.11998 · v1 · submitted 2026-05-12 · 💻 cs.IT · math.IT

Recognition: no theorem link

From Submodularity to Matrix Determinants: Strengthening Han's, Sz\'asz's, and Fischer's Inequalities

Gowtham R. Kurri, Gunank Jakhar, Suryajith Chillara, Vinod M. Prabhakaran

Authors on Pith no claims yet

Pith reviewed 2026-05-13 04:55 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords submodular functionsdeterminantal inequalitiesHan's inequalitySzász's inequalityFischer's inequalitypositive definite matricesdifferential entropyKy Fan inequality

0 comments

The pith

Conditional strengthenings of subadditivity for submodular functions produce tighter upper bounds on log-determinants of positive definite matrices.

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

The paper extends the Dembo-Cover-Thomas framework by showing that submodular functions obey conditional versions of Han's inequality and partition subadditivity. These conditional properties give strictly tighter upper bounds on the joint value than the classical unconditional versions. Specializing to differential entropy of Gaussian vectors then yields improved determinantal inequalities: a strengthened Szász inequality that recovers Ky Fan's inequality as a special case and is strictly stronger for any non-diagonal positive definite matrix, plus a corresponding strengthening of Fischer's inequality.

Core claim

We establish conditional strengthenings of Han's inequality and partition subadditivity in the general setting of submodular functions. Specializing these results to differential entropy produces strengthened versions of Szász's and Fischer's inequalities for positive definite matrices. The strengthened Szász inequality recovers Ky Fan's inequality as a special case and is strictly stronger than the classical Szász inequality for any non-diagonal positive definite matrix. We also derive an eigenvalue inequality that generalizes and strictly strengthens a corresponding inequality of Ky Fan.

What carries the argument

Conditional subadditivity of submodular functions, which supplies a tighter upper bound on the joint value than unconditional subadditivity while still obeying a chain rule.

Load-bearing premise

The chosen definition of conditioning for submodular functions satisfies both the chain rule and the property that conditioning reduces the function value, so that the same properties translate directly from differential entropy to log-determinants.

What would settle it

A positive definite matrix for which the determinant exceeds the new upper bound given by the strengthened Szász inequality, or a submodular function where the conditional strengthening fails to improve on the unconditional version.

read the original abstract

Dembo, Cover, and Thomas (1991) developed an elegant information-theoretic framework for proving determinantal inequalities for positive definite matrices, which relies on the structural inequalities of differential entropy. Submodular functions, which subsume entropy, inherently satisfy these structural inequalities because they obey generalized forms of the fundamental properties of entropy -- a chain rule and the property that conditioning reduces the function's value (under an appropriate definition of conditioning). Applying subadditivity, Han's inequality (1978), and partition subadditivity (i.e., subadditivity over a partition) yields Hadamard's, Sz\'asz's, and Fischer's inequalities, respectively. Furthermore, this framework recovers Ky Fan's inequality (1955), a strengthening of Hadamard's inequality. This improvement fundamentally arises because conditional subadditivity yields a tighter upper bound on the joint entropy than the one obtained via unconditional subadditivity. In this paper, we establish conditional strengthenings of Han's inequality and partition subadditivity in the general setting of submodular functions. We derive equality conditions for these strengthened bounds and characterize when they strictly improve their unconditional counterparts. We specialize these results to differential entropy and apply them to establish strengthened versions of Sz\'asz's and Fischer's inequalities. The strengthening of Sz\'asz's inequality recovers Ky Fan's inequality as a special case, and is strictly stronger than the classical Sz\'asz's inequality for any non-diagonal positive definite matrix. We also derive an inequality concerning eigenvalues, which generalizes and strictly strengthens a corresponding eigenvalue inequality of Ky Fan. We provide numerical examples to explicitly illustrate the tightness of our proposed matrix determinantal bounds.

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.

Desk Editor's Note private letter to a colleague

Conditional strengthenings of Han's and partition subadditivity for submodular functions give strictly tighter Szász's and Fischer's matrix inequalities.

read the letter

The main point is that they define conditional versions of Han's inequality and partition subadditivity that work for any submodular function, then use those to get stronger bounds on determinants of positive definite matrices. The Szász strengthening recovers Ky Fan's inequality as a special case and beats the classical version whenever the matrix is not diagonal. Equality cases are stated clearly and the improvement is checked numerically for Gaussians via the entropy-log-det link.

Referee Report

0 major / 1 minor

Summary. The paper develops a submodular-function framework that yields conditional strengthenings of Han's inequality and partition subadditivity. These strengthenings are specialized to differential entropy of jointly Gaussian variables, producing strictly improved versions of Szász's and Fischer's determinantal inequalities for positive definite matrices. The Szász strengthening recovers Ky Fan's inequality as a special case and is shown to be strictly tighter than the classical bound whenever the matrix is non-diagonal. Equality cases are characterized explicitly, an eigenvalue inequality generalizing Ky Fan's is derived, and numerical examples illustrate the improvement.

Significance. The results supply a unified, axiomatically grounded route from submodularity to tighter matrix bounds, with explicit equality conditions and a clear demonstration of strict improvement. Because the derivations rest only on standard submodular properties plus a consistent definition of conditioning, the work strengthens classical inequalities without introducing free parameters or ad-hoc assumptions, and the Gaussian specialization directly translates the abstract bounds into concrete determinantal statements.

minor comments (1)

The numerical examples in the final section would benefit from an explicit statement of the matrix dimensions and conditioning sets used to generate the reported gaps.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, the assessment of its significance, and the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity; derivations self-contained from axioms

full rationale

The paper derives conditional strengthenings of Han's inequality and partition subadditivity directly from the axioms of submodular functions together with an explicit definition of conditioning. These are then specialized via the standard entropy-log-det correspondence for jointly Gaussian variables to obtain strengthened determinantal inequalities. All steps are proven from first principles within the submodular setting, with equality cases and strict-improvement conditions characterized independently. External citations (Dembo-Cover-Thomas 1991, Han 1978, Ky Fan 1955) supply the classical framework and are not load-bearing for the new conditional results. No fitted parameters, self-definitional reductions, or self-citation chains appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definition and properties of submodular functions (diminishing returns and the chain rule under conditioning) plus the known fact that differential entropy satisfies these properties. No free parameters or new entities are introduced.

axioms (2)

domain assumption Submodular functions satisfy a chain rule and the property that conditioning reduces the function value.
Invoked throughout the derivation of conditional strengthenings.
standard math Differential entropy of jointly Gaussian vectors equals (1/2) log det of the covariance matrix.
Used to translate entropy inequalities into determinantal inequalities.

pith-pipeline@v0.9.0 · 5625 in / 1422 out tokens · 32559 ms · 2026-05-13T04:55:55.993299+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Fujishige,Submodular functions and optimization

S. Fujishige,Submodular functions and optimization. Elsevier, 2005

work page 2005
[2]

Near-optimal observation selection using submodular functions,

A. Krause and C. Guestrin, “Near-optimal observation selection using submodular functions,” inAAAI, vol. 7, 2007, pp. 1650–1654

work page 2007
[3]

Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem,

M. Conforti and G. Cornuéjols, “Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem,”Discrete Applied Mathematics, vol. 7, no. 3, pp. 251–274, 1984

work page 1984
[4]

Combinatorial auctions with decreasing marginal utilities,

B. Lehmann, D. Lehmann, and N. Nisan, “Combinatorial auctions with decreasing marginal utilities,” inProceedings of the 3rd ACM conference on Electronic Commerce, 2001, pp. 18–28

work page 2001
[5]

Maximizing the spread of influence through a social network,

D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” inProceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 2003, pp. 137–146

work page 2003
[6]

Regularity properties and pathologies of position-space renormalization-group transforma- tions: Scope and limitations of Gibbsian theory,

A. C. Van Enter, R. Fernández, and A. D. Sokal, “Regularity properties and pathologies of position-space renormalization-group transforma- tions: Scope and limitations of Gibbsian theory,”Journal of Statistical Physics, vol. 72, pp. 879–1167, 1993

work page 1993
[7]

Bach,Learning with Submodular Functions: A Convex Optimization Perspective

F. Bach,Learning with Submodular Functions: A Convex Optimization Perspective. Now Publishers Inc., 2013

work page 2013
[8]

Generalized submod- ular information measures: Theoretical properties, examples, optimiza- tion algorithms, and applications,

R. Iyer, N. Khargonkar, J. Bilmes, and H. Asnani, “Generalized submod- ular information measures: Theoretical properties, examples, optimiza- tion algorithms, and applications,”IEEE Transactions on Information Theory, vol. 68, no. 2, pp. 752–781, 2022

work page 2022
[9]

Nonnegative entropy measures of multivariate symmetric correlations,

T. S. Han, “Nonnegative entropy measures of multivariate symmetric correlations,”Information and Control, vol. 36, no. 2, pp. 133–156, 1978

work page 1978
[10]

Boucheron, G

S. Boucheron, G. Lugosi, and P. Massart,Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013

work page 2013
[11]

Information inequalities via submodularity and a problem in extremal graph theory,

I. Sason, “Information inequalities via submodularity and a problem in extremal graph theory,”Entropy, vol. 24, no. 5, 2022. [Online]. Available: https://www.mdpi.com/1099-4300/24/5/597

work page 2022
[12]

Information theory methods in communication complexity,

Z. Bar-Yossef, T. Jayram, R. Kumar, and D. Sivakumar, “Information theory methods in communication complexity,” inProceedings 17th IEEE Annual Conference on Computational Complexity, 2002, pp. 93– 102

work page 2002
[13]

The capacity of robust private information retrieval with colluding databases,

H. Sun and S. A. Jafar, “The capacity of robust private information retrieval with colluding databases,”IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2361–2370, 2018

work page 2018
[14]

Subadditivity of the entropy and its relation to Brascamp–Lieb type inequalities,

E. A. Carlen and D. Cordero-Erausquin, “Subadditivity of the entropy and its relation to Brascamp–Lieb type inequalities,”Geometric and Functional Analysis, vol. 19, no. 2, pp. 373–405, Sep 2009

work page 2009
[15]

An information-theoretic method in combinatorial the- ory,

N. Pippenger, “An information-theoretic method in combinatorial the- ory,”Journal of Combinatorial Theory, Series A, vol. 23, no. 1, pp. 99–104, 1977

work page 1977
[16]

Information inequalities for joint distri- butions, with interpretations and applications,

M. Madiman and P. Tetali, “Information inequalities for joint distri- butions, with interpretations and applications,”IEEE Transactions on Information Theory, vol. 56, no. 6, pp. 2699–2713, 2010

work page 2010
[17]

An information-theoretic proof of Hadamard’s inequality (corresp.),

T. Cover and A. Gamal, “An information-theoretic proof of Hadamard’s inequality (corresp.),”IEEE Transactions on Information Theory, vol. 29, no. 6, pp. 930–931, 1983

work page 1983
[18]

Information theoretic inequalities,

A. Dembo, T. Cover, and J. Thomas, “Information theoretic inequalities,” IEEE Transactions on Information Theory, vol. 37, no. 6, pp. 1501– 1518, 1991

work page 1991
[19]

R. A. Horn and C. R. Johnson,Matrix analysis. Cambridge university press, 2012

work page 2012
[20]

Some inequalities concerning positive-definite Hermitian matri- ces,

K. Fan, “Some inequalities concerning positive-definite Hermitian matri- ces,”Mathematical Proceedings of the Cambridge Philosophical Society, vol. 51, no. 3, p. 414–421, 1955

work page 1955
[21]

Polymatroidal dependence structure of a set of random variables,

S. Fujishige, “Polymatroidal dependence structure of a set of random variables,”Information and Control, vol. 39, no. 1, pp. 55–72, 1978

work page 1978
[22]

A cost function property for plant location problems,

A. M. Frieze, “A cost function property for plant location problems,” Mathematical Programming, vol. 7, no. 1, pp. 245–248, Dec 1974. [Online]. Available: https://doi.org/10.1007/BF01585521

work page doi:10.1007/bf01585521 1974
[23]

Fractional subadditivity of submodular functions: Equality conditions and their applications,

G. Jakhar, G. R. Kurri, S. Chillara, and V . M. Prabhakaran, “Fractional subadditivity of submodular functions: Equality conditions and their applications,” in2025 IEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6

work page 2025
[24]

On a theorem of weyl concerning eigenvalues of linear transformations. ii,

K. Fan, “On a theorem of weyl concerning eigenvalues of linear transformations. ii,”Proceedings of the National Academy of Sciences of the United States of America, vol. 36, no. 1, pp. 31–35, 1950. APPENDIXA PROOF OFTHEOREM4 LetU⊆[1 :n]such that|U|=k. Note thatUcan be uniquely partitioned intoU=S∪T, whereS⊆[1 :p], T⊆ [p+ 1 :n]such that|S|=m,|T|=k−m, for s...

work page 1950