\documentclass[11pt]{amsart}
\pdfoutput=1

\usepackage[usenames,dvipsnames]{xcolor}   %

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage[letterpaper,margin=1in]{geometry}

\usepackage{lmodern}
\usepackage{microtype}
\usepackage{etoolbox}                 %
\usepackage{lettrine}

\usepackage{mathtools}
\usepackage{amsmath,amssymb,amsfonts,amsxtra,bm}
\usepackage{amsthm}
\usepackage{mathrsfs}
\usepackage{latexsym}
\usepackage{nicefrac}       %

\usepackage{booktabs}
\usepackage{makecell,multirow}       %
\usepackage{colortbl}
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage{float}
\floatstyle{plaintop}
\restylefloat{table}
\usepackage{footnote, tablefootnote}

\usepackage{enumitem}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{comment}
\usepackage{xspace}
\usepackage{url}
\usepackage[most]{tcolorbox}

\usepackage[round]{natbib}

\usepackage{hyperref}

\numberwithin{equation}{section}

\makeatletter

\definecolor{darkblue}{rgb}{0.0,0.0,0.65}
\definecolor{darkred}{rgb}{0.68,0.05,0.0}
\definecolor{darkgreen}{rgb}{0.0,0.29,0.29}
\definecolor{darkpurple}{rgb}{0.47,0.09,0.29}

\renewcommand{\topfraction}{0.85}
\renewcommand{\bottomfraction}{0.4}
\renewcommand{\textfraction}{0.1}
\renewcommand{\floatpagefraction}{0.9}

\patchcmd{\section}{\scshape}{\fontfamily{ppl}\bfseries\scshape\selectfont}{}{%
  \PackageWarning{aiproofs}{Could not bold the section font; amsart may have changed}}

\newcommand{\aiauthor}{%
  \author[Suvrit Sra]{Suvrit Sra\textsuperscript{\normalfont*}}%
  \thanks{*\,TU Munich, Dept.~of Mathematics, School of CIT; Garching, Germany.
    Email: \texttt{s.sra@tum.de}.}}

\newcommand{\preprintslink}[2]{%
  \thanks{First public release: #2, as v1 in the author's preprint repository,
    \url{https://github.com/suvrit/preprints/tree/main/preprints/#1}; every
    version is kept there with its timestamp.}}
\newcommand{\arxivlink}[1]{%
  \thanks{Also on arXiv: \url{https://arxiv.org/abs/#1}.}}
\newcommand{\preprintsfooter}[2]{%
  \def\ps@firstpage{\ps@plain
    \def\@oddfoot{\hfil\parbox[t]{\textwidth}{\centering\normalfont\scriptsize
      First public release: #2, as v1 in the author's preprint repository,
      \url{https://github.com/suvrit/preprints/tree/main/preprints/#1};
      every version is kept there with its timestamp.\\[3pt]\thepage}\hfil
      \global\topskip\normaltopskip}%
    \let\@evenfoot\@oddfoot
    \def\@oddhead{\@serieslogo\hss}%
    \let\@evenhead\@oddhead}}

\makeatother

\hypersetup{colorlinks=true,linkcolor=red!60!black,citecolor=green!48!black,urlcolor=blue!60!black}
\setlist{nosep,leftmargin=*}

\renewcommand{\bibnumfmt}[1]{{\color{darkblue}\bf\textsc{#1}}.\hskip 6pt}

\newenvironment{aiusage}{\section*{AI usage}}{}

\newcommand{\aiacknowledgements}[1][]{%
  \section*{Acknowledgements}
  \if\relax\detokenize{#1}\relax\else #1\ \fi
  The author (SS) thanks the Alexander von Humboldt (AvH) Foundation for
  their generous support via a Humboldt Professorship in AI.%
}

\newcommand{\reals}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\pp}{\mathbb{P}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\bmOne}{\bm{1}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Cc}{\mathcal{C}}
\newcommand{\Dc}{\mathcal{D}}
\newcommand{\Nc}{\mathcal{N}}
\newcommand{\Xc}{\mathcal{X}}
\newcommand{\Fc}{\mathcal{F}}
\newcommand{\symm}{\mathfrak{S}}

\newcommand{\ma}{\bm{A}}
\newcommand{\mx}{\bm{X}}
\newcommand{\my}{\bm{Y}}
\newcommand{\mz}{\bm{Z}}
\newcommand{\vx}{\bm{x}}
\newcommand{\vy}{\bm{y}}
\newcommand{\vv}{\bm{v}}
\newcommand{\vz}{\bm{z}}
\newcommand{\vr}{\bm{r}}
\newcommand{\mb}{\bm{B}}
\newcommand{\dpp}{\textsc{Dpp}}

\newcommand{\etal}{et~al.\@\xspace}

\newcommand{\half}{\tfrac{1}{2}}
\newcommand{\kron}{\otimes}
\newcommand{\inv}[1]{{#1}^{-1}}
\newcommand{\nlsum}{\sum\nolimits}
\newcommand{\nlprod}{\prod\nolimits}
\newcommand{\ip}[2]{\langle {#1},\, {#2} \rangle}
\newcommand{\iplr}[2]{\left\langle {#1},\, {#2}\right\rangle}
\newcommand{\set}[1]{\left\lbrace#1\right\rbrace}

\newcommand{\norm}[1]{\|{#1}\|}
\newcommand{\bignorm}[1]{\left\lVert #1\right\rVert}
\newcommand{\pnorm}[2]{\|#1\|_{#2}}
\newcommand{\enorm}[1]{\bigl\|#1\bigr\|_{2}}
\newcommand{\frob}[1]{\|#1\|_{\text{F}}}

\newcommand{\fdel}[2]{\frac{\partial {#1}}{\partial {#2}}}
\newcommand{\what}{\widehat}

\newcommand{\ld}{\ell{}d}

\newcommand{\gm}{\#}
\newcommand{\nf}[2]{\nicefrac{#1}{#2}}

\newcommand{\pfrac}[2]{\left(\tfrac{#1}{#2}\right)}

\def\sint{\begingroup\textstyle\int\endgroup} %

\DeclareMathOperator{\trace}{tr}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\Diag}{Diag}
\DeclareMathOperator{\real}{Re}
\DeclareMathOperator{\imag}{Im}
\DeclareMathOperator{\per}{per}
\DeclareMathOperator{\Vol}{Vol}
\DeclareMathOperator{\Imm}{Imm}
\DeclareMathOperator{\mdet}{det}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\qjsd}{QJSD}
\DeclareMathOperator{\qjrd}{QJRD}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corr}[theorem]{Corollary}
\newtheorem{rmk}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{prob}[theorem]{Problem}

\definecolor{cdarkred}{RGB}{180,70,30} %
\definecolor{cdarkgreen}{RGB}{0,130,0} %
\definecolor{azure}{RGB}{240,255,255}
\definecolor{cmidgreen}{RGB}{201,219,216}
\definecolor{clightgreen}{RGB}{200,255,200}
\definecolor{clightgray}{RGB}{240,240,240}
\definecolor{cmygreen}{RGB}{10,120,0}
\definecolor{cmyblue}{RGB}{50,50,255}
\definecolor{sblue}{RGB}{100,100,255}
\definecolor{cmypurple}{RGB}{150,50,180}
\definecolor{cmyred}{RGB}{238, 64,  0}
\definecolor{cdarkblue}{RGB}{30,75,170}
\definecolor{csharpred}{RGB}{255,0,0}

\newcommand{\sred}[1]{{\color{csharpred} #1}}
\newcommand{\darkred}[1]{{\color{cdarkred} #1}}
\newcommand{\bred}[1]{\textbf{\sred{#1}}}
\newcommand{\darkblue}[1]{{\color{cdarkblue} #1}}
\newcommand{\bblue}[1]{\textbf{\darkblue{#1}}}
\newcommand{\darkbred}[1]{\textbf{\color{cdarkred} #1}}
\newcommand{\darkgreen}[1]{{\color{cmygreen} #1}}

\tcbset{dashedrounded/.style={no borderline,borderline={0.5pt}{0pt}{dashed},arc=4pt}}
\tcbset{supporting/.style={colback=gray!8!white}}
\newtcolorbox{dashedbox}[1][]{
  before={\par\medskip\noindent},
  after={\par\medskip},
  colback=yellow!6!white,
  boxrule=0pt,
  enhanced jigsaw,
  top=2pt,
  left=2pt,
  right=2pt,
  bottom=0pt,
  dashedrounded,
  #1
}

\newtcbox{\tcbmathbox}[1][]{
  nobeforeafter,
  colback=yellow!30!white,
  boxrule=0pt,
  enhanced jigsaw,
  top=0pt,
  left=1pt,
  right=1pt,
  bottom=0pt,
  borderline horizontal={0.5pt}{0pt}{dashed},
  borderline vertical={0.5pt}{0pt}{dashed},
  #1
}

\hypersetup{pdftitle={A sharp Br\'egman--Minc bound for permanents},pdfauthor={Suvrit Sra}}
\allowdisplaybreaks[2]
\setlength{\emergencystretch}{1.5em}

\theoremstyle{plain}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\DeclareMathOperator{\Ent}{H}
\newcommand{\R}{\mathbb R}
\newcommand{\one}{\mathbf 1}
\newcommand{\Sn}{\mathfrak S_n}
\newcommand{\Deltan}{\Delta_n}
\newcommand{\HG}{\mathcal H_{\Gamma}}
\newcommand{\EG}{E_{\Gamma}}
\newcommand{\normG}[1]{\lVert #1\rVert_{\psi}}
\newcommand{\defect}{\mathfrak d}
\newcommand{\dd}{\,d}

\subjclass[2020]{Primary 15A15; Secondary 26D15, 46B20, 94A17}
\keywords{permanent, Gamma function, Orlicz norm, Br\'egman--Minc inequality, entropy bound}

\begin{document}
\title{A sharp Br\'egman--Minc bound for permanents}
\aiauthor

\begin{abstract}
  We prove a sharp Br\'egman--Minc bound for permanents of nonnegative matrices that was conjectured by
  Samorodnitsky and Gurvits. Specifically, for \(\phi(x)=\Gamma(1+1/x)^{-x}\), with \(\phi(0)=0\),
  applied entrywise, we show that every nonnegative row-stochastic square matrix \(A\) satisfies
  \(\per\phi[A]\le1\), which is the Br\'egman--Minc inequality when each row of \(A\) is uniform on its
  support. The crux of our proof is a scalar inequality on the simplex, which we prove using a carefully
  chosen yet elementary integral representation. We note brief applications to the entropy of a random
  permutation and to sharp bounds for rectangular permanents and matchings.
\end{abstract}

\preprintslink{gurvits}{31 October 2026}
\maketitle
\addtocontents{toc}{\protect\setcounter{tocdepth}{-1}}

\vspace*{-6pt}
\section{Introduction}\label{sec:intro}

The permanent of an \(n\times n\) matrix \(B=(b_{ij})\) is
\begin{equation*}
 \per B =\nlsum_{\sigma\in\Sn}\nlprod_{i=1}^n b_{i,\sigma(i)},
\end{equation*}
where \(\Sn\) denotes the permutations of \([n]:=\{1,\ldots,n\}\).
If \(B \in \{0,1\}^{n\times n}\) with positive row sums
\(r_1,\ldots,r_n\), the Br\'egman--Minc inequality \citep{Bregman1973}
states that
\begin{equation}
  \label{eq:1}
 \per B\le\nlprod_{i=1}^n(r_i!)^{1/r_i}.
\end{equation}
Seeking to extend \eqref{eq:1} to arbitrary nonnegative matrices,
\citet{Samorodnitsky2008} asked which function of a row plays the role
of \((r!)^{1/r}\). He proposed the function
\begin{equation*}
 \phi(x):=\Gamma(1+1/x)^{-x}\quad(x>0),\qquad \phi(0):=0,
\end{equation*}
as a natural extension of \(\phi(1/r)=(r!)^{-1/r}\)
and conjectured \citep[Conjecture~1.6]{Samorodnitsky2008} that
\(\per\phi[A]\le1\) (applying $\phi$ entrywise) for every \emph{row-stochastic} \(A\). 
The conjecture also appears in \citet[Conjecture~2.3]{GurvitsSamorodnitsky2014}.
We prove it, including its equality cases.

\begin{dashedbox}
\begin{theorem}[Samorodnitsky--Gurvits inequality]\label{thm:main}
Let $A\in\reals_+^{n\times n}$ be row-stochastic. Then,
\begin{equation*}
 \per\phi[A]\le1.
\end{equation*}
Equality holds if and only if independent permutations of the rows and
columns transform \(A\) into
\begin{equation*}
 \tfrac{J_{r_1}}{r_1}\oplus\cdots\oplus\tfrac{J_{r_k}}{r_k},
 \qquad r_1+\cdots+r_k=n,
\end{equation*}
where \(J_r\) is the \(r\times r\) all-ones matrix.
\end{theorem}
\end{dashedbox}
There is a valuable reformulation of Theorem~\ref{thm:main} using Orlicz norms. Consider the function $\psi=\phi^{-1}$ on $[0,1]$ (increasing and convex by Lemma~\ref{lem:concavity}); using $\psi$ one defines the \emph{Orlicz norm}:
\begin{equation}\label{eq:orlicznorm}
  \normG{b} := \min\bigl\{r\ge\max\nolimits_j|b_j| : \nlsum_j\psi(|b_j|/r)\le1\bigr\},
\end{equation}
where we set $\normG{b}=0$ for $b=0$. Normalizing each row of a nonnegative matrix in this norm gives an equivalent bound that was conjectured by
\citet[\S1.2]{Samorodnitsky2008}, and also stated by \citet[\S2.2]{GurvitsSamorodnitsky2014} within a general family of Orlicz permanent bounds.

\begin{corollary}[Orlicz permanent inequality]\label{cor:orlicz}
For every \(B \in \reals_+^{n\times n}\), with rows \(b_i\),
\begin{equation}\label{eq:orliczper}
 \per B\le\nlprod_{i=1}^n\normG{b_i}.
\end{equation}
If all rows are nonzero, equality holds precisely when independent row
and column permutations make \(B\) block diagonal with square blocks,
each of whose rows is a positive constant across that block.
\end{corollary}

The Orlicz norm is the function of a row that replaces \((r!)^{1/r}\):
for \(b=c\one_S\) with \(|S|=r\ge1\),
\begin{equation}\label{eq:indicatornorm}
 \normG{b}=|c|(r!)^{1/r},
\end{equation}
so on zero-one matrices Corollary~\ref{cor:orlicz} is the
Br\'egman--Minc inequality.
\citet[Theorem~1]{Soules2005} extends that inequality to nonnegative
matrices by writing each row as a nonnegative combination of nested
zero-one rows and taking the same combination of their Br\'egman--Minc
constants. By the triangle inequality and \eqref{eq:indicatornorm}, each
row factor in Soules's bound is at least the Orlicz norm of the row,
so Corollary~\ref{cor:orlicz} refines Soules's bound row by row.

Other row norms lead to different sharp problems. For prescribed
\(\ell_p\) row norms,
\citet[Corollary~1.14 in the arXiv version]{BristielCaputo2024} proved
\[
 \per B\le
 \max\bigl\{1,\tfrac{n!}{n^{n/p}}\bigr\}\nlprod_i\|b_i\|_p,
 \qquad p\ge1,
\]
resolving \citet[Conjecture~1.1]{Samorodnitsky2008}. There the constant
depends on \(n\), whereas the bound \eqref{eq:orliczper} uses the same
norm in every dimension and is an equality at every block size in
Theorem~\ref{thm:main}. For other Orlicz functions \(\psi\),
\citet[Theorem~4.1]{GurvitsSamorodnitsky2014} proved
\eqref{eq:orliczper} under three conditions on \(\psi\), met for instance
by \(\psi(x)=1-(1-x)a^x\) with \(a\approx1.54\). These results leave
Samorodnitsky's conjecture open.

We prove Theorem~\ref{thm:main} by induction on \(n\). Deleting a row
and a column and renormalizing the remaining rows leaves a row-stochastic
minor, and H\"older's inequality reduces the induction step to a scalar
inequality: for each row \(a\) of \(A\), the weights of these minors sum
to at most one. For
\(n\ge2\) and \(a\) in the relative interior of the simplex
\(\Delta_n=\{a\in[0,1]^n:\sum_i a_i=1\}\), the weights \(q_i(a)\) and their sum
\(Q_n(a)\) are
\begin{equation}\label{eq:scalarq}
 q_i(a)=
 \frac{\phi(a_i)^n}
 {\nlprod_{j\ne i}\phi\!\left(\frac{a_i}{1-a_j}\right)},
 \qquad Q_n(a)=\nlsum_{i=1}^n q_i(a).
\end{equation}
These expressions extend continuously to the closed simplex
(Section~\ref{sec:scalarboundary}).

\begin{theorem}[Scalar simplex inequality]\label{thm:scalar}
Let $n\ge 2$. For every \(a\in\Delta_n\),
\begin{equation*}
 Q_n(a)\le1.
\end{equation*}
Equality holds if and only if the positive coordinates of \(a\) are all
equal. %
\end{theorem}

We prove Theorem~\ref{thm:scalar} in Section~\ref{sec:scalarproof}
through a positive integral representation of \(-\log\phi\), suggested by
the integral representations of subentropy in \citet[Section~3]{Sra2019},
which build on \citet{JozsaMitchison2015}; \(Q_n\) itself is not a
subentropy.
The proof also gives a strict form of Theorem~\ref{thm:main} that is
computable from one-dimensional integrals (Proposition~\ref{prop:deficit}).

Beyond Br\'egman--Minc, Corollary~\ref{cor:orlicz} gives sharp bounds for
rectangular permanents and for the total weights of \(k\)-matchings in
weighted bipartite graphs (Theorem~\ref{thm:rectangular},
Corollary~\ref{cor:matching}). Theorem~\ref{thm:main} also has an entropy
form, which bounds the entropy of a random permutation by
the sum of \(\HG\) over its row marginals, where
\(\HG\) is the entropy functional dual to the Orlicz norm
(Theorem~\ref{thm:entropy}).

\section{The Gamma function and the Orlicz norm}\label{sec:prelim}

A positive integral representation of \(-\log\phi\) gives both the
concavity needed for the norm \eqref{eq:orlicznorm} and the integrals used
to prove Theorem~\ref{thm:scalar}. Put
\[
 h(x)=-\log\phi(x)=x\log\Gamma(1+1/x),
 \qquad
 \omega(t)=t\lfloor1/t\rfloor\quad(0<t<1).
\]
On \((0,1)\) we have \(0<1-t\le\omega(t)\le1\), and we set \(\omega=0\)
outside \((0,1)\) when necessary.

\begin{lemma}[Integral representation and recurrence]\label{lem:gamma}
For \(x>0\),
\begin{equation}\label{eq:hrep}
 h(x)=-\gamma+\int_0^1\frac{\omega(t)}{x+t}\dd t,
\end{equation}
where \(\gamma\) is Euler's constant. For \(0<x<1\),
\begin{equation}\label{eq:phirecurrence}
 \phi(x)=x^x
 \phi\!\left(\frac{x}{1-x}\right)^{1-x}.
\end{equation}
\end{lemma}

\begin{proof}
Taking logarithms in Weierstrass's product for the Gamma function
\citep[Equation~5.8.2]{DLMF} gives
\[
 h(x)=-\gamma+\nlsum_{m=1}^{\infty}
 \left\{\frac1m-x\log\left(1+\frac1{mx}\right)\right\}.
\]
The \(m\)-th summand equals
\[
 \int_0^{1/m}\frac{t}{x+t}\dd t.
\]
All summands are nonnegative, so Tonelli's theorem and
\(\sum_{m\ge1}\one_{\{t\le1/m\}}=\lfloor1/t\rfloor\)
prove \eqref{eq:hrep}. The recurrence
\(\Gamma(1+1/x)=x^{-1}\Gamma(1/x)\) proves
\eqref{eq:phirecurrence}.
\end{proof}

The concavity of \(\phi\) is known; \citet{Samorodnitsky2008} attributes it
to D.~Moews. Lemma~\ref{lem:concavity} rederives it from \eqref{eq:hrep},
since the same representation drives the proof of
Theorem~\ref{thm:scalar}.

\begin{lemma}[Monotonicity and concavity]\label{lem:concavity}
The function \(\phi\) is strictly increasing and strictly concave on
\((0,\infty)\), and it satisfies
\[
 \phi(0+)=0,\qquad \phi(1)=1,\qquad
 \lim_{x\to\infty}\phi(x)=e^\gamma.
\]
In particular, \(\phi(x)\ge x\) for \(0\le x\le1\), strictly for
\(0<x<1\).
\end{lemma}

\begin{proof}
Let \(L=\log\phi\). Differentiating \eqref{eq:hrep} gives
\[
 L'(x)=\int_0^1\frac{\omega(t)}{(x+t)^2}\dd t>0,
 \qquad
 -L''(x)=2\int_0^1\frac{\omega(t)}{(x+t)^3}\dd t.
\]
After the substitution \(u=1/(x+t)\), the two integrals become
\[
 L'(x)=\int_0^\infty f_x(u)\dd u,\qquad
 -L''(x)=2\int_0^\infty u f_x(u)\dd u,
\]
where \(0\le f_x\le1\), and \(f_x\) is supported in
\([1/(x+1),1/x]\). Every integrable \(0\le f\le1\) with finite first
moment satisfies, on writing the square as a double integral,
\[
 \left(\int_0^\infty f\right)^2
 =2\int_0^\infty f(u)\left(\int_0^u f(v)\dd v\right)\dd u
 \le2\int_0^\infty u f(u)\dd u.
\]
The inequality is strict for \(f_x\), since it is nonzero with support
bounded away from zero. Consequently
\[
 \frac{\phi''(x)}{\phi(x)}=L''(x)+L'(x)^2<0.
\]
The lower bound \(\omega(t)\ge1-t\) gives
\[
 h(x)\ge-\gamma+(1+x)\log(1+1/x)-1\longrightarrow+\infty
 \quad(x\downarrow0).
\]
The remaining endpoint assertions follow from \(\Gamma(2)=1\) and
\eqref{eq:hrep}, and strict concavity together with the endpoint values
at \(0\) and \(1\) gives the final assertion.
\end{proof}

\begin{proposition}[Norm properties]\label{prop:norm}
The expression \eqref{eq:orlicznorm} defines an absolute, coordinatewise
monotone norm on every finite-dimensional real or complex vector space.
It is consistent under adjoining zero coordinates. Its unit ball is
\[
 \bigl\{b:\ |b_j|\le1\ \text{for all }j,\quad
                  \nlsum_j\psi(|b_j|)\le1\bigr\}.
\]
For a nonzero vector \(b\), \(\normG{b}\ge\|b\|_\infty\), and
\eqref{eq:indicatornorm} holds.
\end{proposition}

\begin{proof}
The inverse \(\psi:[0,1]\to[0,1]\) is continuous, increasing, and convex.
The displayed unit ball is therefore convex, balanced, and bounded, and
it contains a neighborhood of zero, so its Minkowski functional is a norm.
For nonzero \(b\) and \(r\ge\|b\|_\infty\), the sum in \eqref{eq:orlicznorm} is continuous
and strictly decreasing, starts at a value at least \(1\), and tends to
zero, which proves the normalization and uniqueness. The remaining
claims follow from the unit ball. For \(c\ne0\) and \(|S|=r\), the identity
\(r\psi(|c|/\normG{c\one_S})=1\) proves \eqref{eq:indicatornorm}.
For \(c=0\), the formula follows from \(\normG{0}=0\).
\end{proof}

\begin{remark}
One may instead define \(\psi=\phi^{-1}\) on \([0,e^\gamma)\) and
\(\psi=+\infty\) on \([e^\gamma,\infty)\). The usual Luxemburg
functional then gives the same norm, because a sum of \(\psi\)-values at
most \(1\) forces each argument to be at most \(1\). No increasing convex
extension past \(1\) affects the statements here.
\end{remark}

\section{The scalar inequality}\label{sec:scalarproof}

The induction of Section~\ref{sec:perproof} closes once every row
satisfies \(Q_n\le1\), so we prove Theorem~\ref{thm:scalar} first.

\subsection{Reduction to two variables}

Each factor in the denominator of \eqref{eq:scalarq} compares \(h\) at
\(a_i\) and at \(a_i/(1-a_j)\). For \(0<x,b<1\) we therefore set
\begin{equation}\label{eq:gdef}
 g_x(b)=\frac{h(x)-h(x/(1-b))}{b},
 \qquad R_b(x)=\exp\{g_x(x)-g_x(b)\}.
\end{equation}
Substituting \eqref{eq:hrep} gives the positive integral representation
\begin{equation}\label{eq:grep}
 g_x(b)=\int_0^1
 \frac{\omega(t)x}{(x+t)(x+(1-b)t)}\dd t,
\end{equation}
and the recurrence \eqref{eq:phirecurrence} gives
\begin{equation}\label{eq:gdiag}
 (1-x)g_x(x)=-h(x)-\log x.
\end{equation}
In particular, \(R_x(x)=1\).

\begin{lemma}[Two-variable comparison]\label{lem:pair}
If \(a,b>0\) and \(a+b\le1\), then
\begin{equation}\label{eq:pair}
 R_b(a)+R_a(b)\le2,
\end{equation}
with equality if and only if \(a=b\).
\end{lemma}

Lemma~\ref{lem:pair} is proved in Section~\ref{sec:secant}; we first show
that it implies the scalar theorem in the interior of the simplex. For
\(a\) in the relative interior of \(\Delta_n\), \eqref{eq:gdef} and
\eqref{eq:gdiag} yield
\[
 \begin{split}
 \log\frac{q_i(a)}{a_i}
 &=-h(a_i)-\log a_i-\nlsum_{j\ne i}a_jg_{a_i}(a_j)\\
 &=\nlsum_{j=1}^n a_j\bigl(g_{a_i}(a_i)-g_{a_i}(a_j)\bigr).
 \end{split}
\]
Exponentiating gives
\begin{equation*}
 q_i(a)=a_i\nlprod_{j=1}^n R_{a_j}(a_i)^{a_j}.
\end{equation*}
Weighted AM--GM and Lemma~\ref{lem:pair} imply
\begin{align}
 Q_n(a)
 &\le\nlsum_{i,j}a_i a_j R_{a_j}(a_i)\notag\\
 &=\nlsum_i a_i^2+
    \nlsum_{i<j}a_i a_j\bigl(R_{a_j}(a_i)+R_{a_i}(a_j)\bigr)\notag\\
 &\le\nlsum_i a_i^2+2\nlsum_{i<j}a_i a_j=1. \label{eq:amgmfinish}
\end{align}
Lemma~\ref{lem:pair} applies because \(a_i+a_j\le1\) for distinct indices,
and by its equality case the last inequality is strict if two coordinates
of \(a\) differ.

\subsection{A common positive measure}

To compare \(R_b(a)\) with \(R_a(b)\), we write the logarithm of each as
an integral against the same positive measure. Subtracting the kernels in
\eqref{eq:grep} gives
\begin{equation}\label{eq:Kdef}
 \log R_b(a)=(a-b)K(a,b),\qquad
 K(a,b)=\int_0^1
 \frac{\omega(t)\,a t}
 {(a+t)(a+(1-a)t)(a+(1-b)t)}\dd t.
\end{equation}
In particular \(K(a,b)>0\). Now, fix \(0<a<b\), \(a+b\le1\), and write $d=b-a$, $s=a+b$, and $c=s/3$. 
The substitution \(y=a/t\) in \eqref{eq:Kdef} gives
\begin{equation*}
 K(a,b)=\int_0^\infty
 \frac{a\lfloor y/a\rfloor}
 {y(y+1)(y+1-a)(y+1-b)}\dd y.
\end{equation*}
We name the denominator and its tail integral:
\[
 P(y)=y(y+1)(y+1-a)(y+1-b),\qquad
 F(z)=\int_z^\infty\frac{\dd y}{P(y)}.
\]
The polynomial \(P\) is symmetric in \(a,b\), and Tonelli's theorem gives
\begin{equation}\label{eq:Kseries}
 K(a,b)=a\nlsum_{m\ge1}F(ma),\qquad
 K(b,a)=b\nlsum_{m\ge1}F(mb).
\end{equation}

The identity
\[
 \frac1{y+\lambda}=\int_0^\infty e^{-yt}e^{-\lambda t}\dd t
 \qquad(\lambda\ge0)
\]
shows that \(1/P\) is the Laplace transform of a nonnegative density
\(\rho\), namely the convolution on \([0,\infty)\) of
\(1,e^{-t},e^{-(1-a)t},e^{-(1-b)t}\). Therefore
\[
 F(z)=\int_0^\infty e^{-zt}\dd\nu(t),
 \qquad \dd\nu(t)=\frac{\rho(t)}t\dd t.
\]
Summing the geometric series in \eqref{eq:Kseries}, we obtain
\begin{equation}\label{eq:commonmeasure}
 A:=K(a,b)=\int_0^\infty k_a(t)\dd\nu(t),\qquad
 B:=K(b,a)=\int_0^\infty k_b(t)\dd\nu(t),
 \quad k_x(t)=\frac{x}{e^{xt}-1}.
\end{equation}
The same positive measure \(\nu\) occurs in both expressions. The
original integrals in \eqref{eq:Kdef} are finite, and every exchange
above involves nonnegative integrands.

\subsection{Proof of the two-variable comparison}\label{sec:secant}

By \eqref{eq:Kdef}, \(R_b(a)=e^{-dA}\) and \(R_a(b)=e^{dB}\), so
Lemma~\ref{lem:pair} compares the two exponents \(dA\) and \(dB\).
The inequality \(A>B\) alone would not suffice; the
next lemma bounds \(1/B-1/A\) from below, using the common measure of
\eqref{eq:commonmeasure}.

\begin{lemma}\label{lem:inversegap}
With the notation above,
\begin{equation}\label{eq:inversegap}
 \frac1B-\frac1A\ge2d.
\end{equation}
\end{lemma}

\begin{proof}
For fixed \(t>0\),
\[
 \frac1{k_x(t)}=t\int_0^1e^{xtv}\dd v.
\]
Subtracting, and writing the difference of exponentials as an integral
over \(u\in[0,1]\), we obtain
\[
 \frac1{k_b(t)}-\frac1{k_a(t)}
 =d\,t^2\int_0^1\int_0^1 v e^{(a+du)tv}\dd u\dd v.
\]
The measure \(\dd u\,2v\dd v\) is a probability measure on the unit
square, under which \((a+du)v\) has mean
\[
 (a+d/2)(2/3)=s/3=c.
\]
Jensen's inequality gives
\begin{equation*}
 \frac1{k_b(t)}-\frac1{k_a(t)}
 \ge\frac{d\,t^2}{2}e^{ct}.
\end{equation*}
In particular \(k_a>k_b\), so \(A>B>0\).

Cauchy--Schwarz turns this pointwise bound into a bound for
\(AB/(A-B)\):
\begin{align}
 \frac{AB}{A-B}
 &=B+\frac{B^2}{A-B}\notag\\
 &\le\int_0^\infty
 \left(k_b+\frac{k_b^2}{k_a-k_b}\right)\dd\nu
 =\int_0^\infty
 \frac{\dd\nu}{1/k_b-1/k_a}\notag\\
 &\le\frac2d\int_0^\infty\frac{e^{-ct}}{t^2}\dd\nu(t)
 =\frac Jd, \label{eq:cauchysecant}
\end{align}
where, by Tonelli's theorem and
\(\int_c^\infty(y-c)^2e^{-yt}\dd y=2e^{-ct}/t^3\), the constant \(J\) is
\begin{equation}\label{eq:Jintegral}
 J=2\int_0^\infty\frac{e^{-ct}}{t^2}\dd\nu(t)
  =\int_c^\infty
       \frac{(y-c)^2}{y(y+1)(y+1-a)(y+1-b)}\dd y.
\end{equation}

It remains to show that \(J\le1/2\). Since \(a+b=3c\),
\[
 (y+1-a)(y+1-b)
 =(y+1)^2-3c(y+1)+ab
 \ge(y+1)(y+1-3c).
\]
Set \(y=z+c\). The denominator in \eqref{eq:Jintegral} is at least
\[
 (z+c)(z+1+c)^2(z+1-2c)\ge z(z+1)^3
 \qquad(z\ge0,\ 0\le c\le1/3).
\]
To verify the second inequality, put \(r=z+1\); the difference of its
two sides equals
\begin{equation*}
 c\bigl(r^2(r-3c)+c(3-5c)r+2c^2(1-c)\bigr)\ge0,
\end{equation*}
which is nonnegative because \(r\ge1\) and \(c\le1/3\). Hence
\[
 J\le\int_0^\infty\frac{z}{(z+1)^3}\dd z=\frac12.
\]
Combining this bound with \eqref{eq:cauchysecant} proves
\(AB/(A-B)\le1/(2d)\), which is \eqref{eq:inversegap}.
\end{proof}

\begin{proof}[\textbf{Proof of Lemma~\ref{lem:pair}}]
The case \(a=b\) is immediate. By symmetry assume \(a<b\), and set
\(u=dA\) and \(v=dB\). Lemma~\ref{lem:inversegap} implies
\[
 \frac1v-\frac1u\ge2,\qquad
 0<v\le\frac{u}{1+2u}<\frac12.
\]
The elementary exponential inequalities \(e^v-1\le v/(1-v)\) for
\(0\le v<1\) and \(1-e^{-u}\ge u/(1+u)\) for \(u\ge0\) give the chain
\[
 e^v-1\le\frac{v}{1-v}
          \le\frac{u}{1+u}\le1-e^{-u}.
\]
Since \(R_b(a)=e^{-u}\) and \(R_a(b)=e^v\), this chain proves
\eqref{eq:pair}. If \(a\ne b\), then \(u,v>0\), and the elementary
exponential inequalities are strict.
\end{proof}

\subsection{Boundary continuity and equality}\label{sec:scalarboundary}

\begin{proof}[\textbf{Completion of the proof of Theorem~\ref{thm:scalar}}]
In the relative interior, the inequality was proved in \eqref{eq:amgmfinish}.
Since \(\phi\) is increasing and \(a_i/(1-a_j)\ge a_i\), one has
\begin{equation*}
 0\le q_i(a)\le\phi(a_i).
\end{equation*}
Thus a summand tends to zero when its coordinate tends to zero.
For a positive coordinate, each zero coordinate elsewhere supplies a
factor \(\phi(a_i)\) in its denominator, cancelling one numerator
factor. Consequently \(Q_n\) restricts to \(Q_r\) on a face with \(r\)
positive coordinates. At a vertex the nonzero-coordinate summand tends
to \(1\), and all others tend to zero. These limits prove continuity and
the inequality on the closed simplex.

If two positive coordinates differ, the corresponding term in
\eqref{eq:amgmfinish} is strict. Conversely, at a vector uniform on \(r\)
coordinates, \(r\ge2\), each nonzero summand equals
\[
 \frac{\phi(1/r)^r}{\phi(1/(r-1))^{r-1}}
 =\frac{1/r!}{1/(r-1)!}=\frac1r,
\]
and vertices give equality as well.
\end{proof}

\section{The permanent inequality}\label{sec:perproof}

To deduce Theorem~\ref{thm:main} from Theorem~\ref{thm:scalar}, we use
H\"older's inequality to separate the rows. Each resulting factor is a
sum of values of \(\per\phi\) on normalized minors, weighted by the
summands \(q_{ij}\) of \eqref{eq:scalarq}. Induction bounds these
values, and Theorem~\ref{thm:scalar} bounds the sum of
their weights.

\subsection{Induction via H\"older's inequality}

Let \(M_n\) be the maximum of \(\per\phi[A]\) over row-stochastic
\(n\times n\) matrices, which exists by compactness.
For \(n\ge2\) and a positive row-stochastic matrix \(A\), put
\[
 q_{ij}=
 \frac{\phi(a_{ij})^n}
 {\displaystyle\nlprod_{\ell\ne j}
          \phi\!\left(\frac{a_{ij}}{1-a_{i\ell}}\right)}.
\]
Then \(\sum_jq_{ij}=Q_n(a_i)\), where \(a_i\) is row \(i\).
For \(\sigma\in\Sn\), define
\[
 W(\sigma)=\nlprod_k\phi(a_{k,\sigma(k)}),\qquad
 V_i(\sigma)=\nlprod_{k\ne i}
       \phi\!\left(\frac{a_{k,\sigma(k)}}{1-a_{k,\sigma(i)}}\right).
\]
For a fixed row \(k\), the values \(\sigma(i)\), \(i\ne k\), run over
all columns except \(\sigma(k)\), so
\begin{equation*}
 W(\sigma)^n
 =\nlprod_{i=1}^n\bigl(q_{i,\sigma(i)}V_i(\sigma)\bigr).
\end{equation*}
H\"older's inequality gives
\begin{equation}\label{eq:holder}
 \per\phi[A]
 \le\nlprod_{i=1}^n
      \left(\nlsum_{\sigma\in\Sn}q_{i,\sigma(i)}V_i(\sigma)\right)^{1/n}.
\end{equation}
For fixed \(i,j\), the sum of \(V_i(\sigma)\) over
\(\sigma(i)=j\) is \(\per\phi[A^{(i,j)}]\) for the matrix
\begin{equation*}
 A^{(i,j)}_{k\ell}=\frac{a_{k\ell}}{1-a_{kj}}
 \qquad(k\ne i,\ \ell\ne j),
\end{equation*}
which is row-stochastic. Therefore
\begin{equation*}
 \per\phi[A]
 \le M_{n-1}\nlprod_{i=1}^n Q_n(a_i)^{1/n}
 \le M_{n-1}.
\end{equation*}
Approximation by positive matrices and Section~\ref{sec:scalarboundary} extend the
first inequality to every row-stochastic matrix. Since \(M_1=1\),
induction gives \(M_n\le1\), proving Theorem~\ref{thm:main}. In particular,
\begin{equation}\label{eq:rowrefinement}
 \per\phi[A]\le\nlprod_{i=1}^nQ_n(a_i)^{1/n}.
\end{equation}

\subsection{The equality cases}

Every block \(J_r/r\) in Theorem~\ref{thm:main} has
\(\per\phi[J_r/r]=r!\phi(1/r)^r=1\), so their direct sums give equality.
We prove necessity by induction on \(n\); the case \(n=1\) is immediate.

Suppose \(\per\phi[A]=1\). By \eqref{eq:rowrefinement} and
Theorem~\ref{thm:scalar}, every row is uniform on its positive support.
Let \(S_i\) be that support and \(r_i=|S_i|\).

If \(r_i=1\), let \(j\) be its unique column. Expansion along row \(i\)
shows that the minor \(A'\) obtained by deleting row \(i\) and column
\(j\) has \(\per\phi[A']=1\), and its
surviving row sums \(1-a_{kj}\) are positive. If some \(a_{kj}>0\),
normalizing the surviving rows strictly increases that positive
permanent, because every positive matching term uses a positive entry in
row \(k\) and \(\phi\) is strictly increasing. Such an increase
contradicts the inequality already proved. Thus column \(j\) has no other positive
entries, and an isolated \(1\times1\) block can be removed.

It remains to consider \(r_i\ge2\) for every row. All entries are then
at most \(1/2\), so the H\"older argument applies directly even when some
entries vanish. On row \(i\),
\[
 q_{ij}=
 \begin{cases}
  1/r_i,&j\in S_i,\\
  0,&j\notin S_i.
 \end{cases}
\]
Each factor on the right of \eqref{eq:holder} is at most \(1\), so
equality of the full permanent forces
\begin{equation}\label{eq:allequalityminors}
 \per\phi[A^{(i,j)}]=1\qquad(j\in S_i).
\end{equation}
By induction, the support graph of every such minor is a disjoint
union of complete balanced bipartite graphs, one for each block of
Theorem~\ref{thm:main}.

Choose a row \(i\) of minimum degree \(r=\min_k r_k\), and choose
\(j\in S_i\). Let \(G\) be the bipartite support graph of \(A\).
In \(G-i-j\), every remaining row has degree at least \(r-1\), so every
complete balanced block has size at least \(r-1\).
Column \(j\) has another neighbor \(k\ne i\): otherwise an edge
\(i\ell\), \(\ell\in S_i\setminus\{j\}\), could not extend to a perfect
matching, contrary to \eqref{eq:allequalityminors}.

In \(G-k-j\), row \(i\) has degree \(r-1\), so it belongs to a complete
balanced block of size \(r-1\). For
\(\ell\in S_i\setminus\{j\}\), let the block containing \(\ell\) in
\(G-i-j\) have size \(m\ge r-1\). Its column degree in \(G-k-j\) is
\(m\) if \(k\) belongs to that block and \(m+1\) otherwise, and it must
equal \(r-1\). Thus \(m=r-1\) and \(k\) belongs to the
block, so all \(r-1\) columns in \(S_i\setminus\{j\}\) form the same
block \(C\), with \(r-1\) rows. Every row of \(C\) must also meet column \(j\), since its original
degree is at least \(r\). No row outside \(C\cup\{i\}\) can meet \(j\):
deleting such a row and \(j\) would leave every column of \(C\) with
degree \(r\), whereas the surviving row \(i\) must lie in a block of
size \(r-1\). Thus \(C\), row \(i\), and column \(j\) form an isolated
complete balanced block of size \(r\), whose stochastic matrix is
\(J_r/r\). Removing it and continuing proves the equality case of Theorem~\ref{thm:main}.

The normalization in \eqref{eq:orlicznorm} converts the stochastic
inequality into a bound for nonnegative rows.

\begin{proof}[\textbf{Proof of Corollary~\ref{cor:orlicz}}]
The case of a zero row is immediate. Otherwise let
\(r_i=\normG{b_i}\) and set
\[
 a_{ij}=\psi(b_{ij}/r_i).
\]
Then \(A\) is row-stochastic and \(\phi(a_{ij})=b_{ij}/r_i\). Hence
\[
 \frac{\per B}{\nlprod_i r_i}=\per\phi[A]\le1,
\]
and the equality classification follows from Theorem~\ref{thm:main}.
\end{proof}

\subsection{A strict form}\label{sec:deficit}

In the relative interior, the proof of Theorem~\ref{thm:scalar} discards
the nonnegative terms \(a_ia_j(2-R_{a_j}(a_i)-R_{a_i}(a_j))\) in the last
step of \eqref{eq:amgmfinish}. Keeping them gives a strict form of
Theorem~\ref{thm:main} that is computable from one-dimensional integrals.

For positive \(a,b\) with \(a+b\le1\), define
\[
 D(a,b)=2-R_b(a)-R_a(b).
\]
By Lemma~\ref{lem:pair}, this symmetric function is nonnegative and
vanishes exactly when \(a=b\). For a probability vector \(a\), put
\begin{equation*}
 \defect(a)=\nlsum_{i<j}a_i a_jD(a_i,a_j),
\end{equation*}
where terms with a zero coordinate are defined to be zero.

\begin{proposition}[Explicit strict refinement]\label{prop:deficit}
For every \(a\in\Delta_n\),
\begin{equation}\label{eq:Qdeficit}
 Q_n(a)\le1-\defect(a).
\end{equation}
Consequently every row-stochastic \(A\) satisfies
\begin{equation}\label{eq:matrixdeficit}
 \per\phi[A]
 \le\nlprod_{i=1}^n(1-\defect(a_i))^{1/n}
 \le\exp\left\{-\frac1n\nlsum_{i=1}^n\defect(a_i)\right\}.
\end{equation}
If \(0<a<b\), \(a+b\le1\), and \(u=(b-a)K(a,b)\), then
\begin{equation}\label{eq:pairdeficit}
 D(a,b)\ge\frac1{1+u}-e^{-u}
 \ge\frac{u^2}{2(1+u)(1+u+u^2/2)}.
\end{equation}
\end{proposition}

\begin{proof}
Keeping these terms in \eqref{eq:amgmfinish} gives
\eqref{eq:Qdeficit}; then \eqref{eq:rowrefinement} and
\(\log(1-t)\le-t\) give \eqref{eq:matrixdeficit}.
For \eqref{eq:pairdeficit}, put \(v=(b-a)K(b,a)\). The proof of
Lemma~\ref{lem:pair} gives
\[
 e^v\le\frac1{1-v}\le1+\frac{u}{1+u}.
\]
Thus \(2-e^{-u}-e^v\ge1/(1+u)-e^{-u}\), and
\(e^u\ge1+u+u^2/2\) gives the rational lower bound.
Boundary statements follow from \(0\le D(a,b)\le2\) and
Section~\ref{sec:scalarboundary}.
\end{proof}

The deficit is computed row by row. If
\(\per\phi[A]\ge1-\varepsilon>0\), for example, then
\[
 \frac1n\nlsum_i\defect(a_i)\le-\log(1-\varepsilon),
\]
so near equality forces the average row deficit to be small.

\section{Consequences}\label{sec:consequences}

The formula \eqref{eq:indicatornorm} and the entropy functional dual
to the Orlicz norm give consequences for weighted matchings and
random permutations.

\subsection{Br\'egman--Minc, rectangular permanents, and matchings}

By \eqref{eq:indicatornorm}, Corollary~\ref{cor:orlicz} contains the
Br\'egman--Minc inequality with its equality cases, and its proof does
not use Br\'egman's theorem. On a general nonnegative matrix, the
bound \eqref{eq:orliczper} sits below the Br\'egman--Minc bound scaled by the
row maxima. Suppose every row is nonzero, with support size \(r_i\)
and maximum \(m_i\). Coordinatewise monotonicity gives
\begin{equation*}
 \per B\le\nlprod_i\normG{b_i}
       \le\nlprod_i m_i(r_i!)^{1/r_i}.
\end{equation*}
The comparison between row factors is strict unless all positive
entries in that row are equal. Thus the Orlicz norm retains information
about the entries beyond their support and maximum.
Transposition gives a corresponding column bound, and for a real or
complex matrix the elementary inequality \(|\per B|\le\per|B|\) extends
the norm bound to absolute permanents. Column scaling multiplies
\(\per B\) by \(\prod_jy_j\), so Corollary~\ref{cor:orlicz} also gives
\(\per B\le\inf_{y>0}\prod_i\normG{b_i\odot y}/\prod_jy_j\), where
\(\odot\) is the coordinatewise product; a supplement to this paper shows
that the logarithm of this bound is a convex program with an exact
entropy dual.

Appending all-ones rows allows us to apply Corollary~\ref{cor:orlicz} to
a rectangular matrix, with an explicit cost determined by
\(\normG{\one_n}=(n!)^{1/n}\). For an \(m\times n\) matrix \(B\) with
\(m\le n\), its permanent is
\[
 \per_{\mathrm{inj}}B
 =\nlsum_{\sigma:[m]\hookrightarrow[n]}\nlprod_{i=1}^m b_{i,\sigma(i)}.
\]

\begin{theorem}[Sharp rectangular bound]\label{thm:rectangular}
For every nonnegative \(m\times n\) matrix \(B\), \(m\le n\),
\begin{equation}\label{eq:rectangular}
 \per_{\mathrm{inj}}B
 \le
 \frac{(n!)^{(n-m)/n}}{(n-m)!}
 \nlprod_{i=1}^m\normG{b_i}.
\end{equation}
The constant is best possible. If \(m<n\) and every row is nonzero,
equality holds if and only if each row is a positive constant across
all \(n\) columns.
\end{theorem}

\begin{proof}
Append \(n-m\) all-ones rows to obtain a square matrix \(\widetilde B\).
Every injection \([m]\hookrightarrow[n]\) extends to exactly \((n-m)!\)
permutations of \([n]\), so
\[
 \per\widetilde B=(n-m)!\per_{\mathrm{inj}}B.
\]
Since \(\normG{\one_n}=(n!)^{1/n}\), Corollary~\ref{cor:orlicz} applied to
\(\widetilde B\) proves
\eqref{eq:rectangular}, and constant rows give equality.
If \(m<n\), an appended all-ones row has full support, so the equality
cases of Corollary~\ref{cor:orlicz} force a single
block of size \(n\), proving the equality assertion.
\end{proof}

For an arbitrary nonnegative \(m\times n\) matrix and
\(0\le k\le\min(m,n)\), let
\[
 M_k(B)=
 \nlsum_{\substack{I\subseteq[m],\ J\subseteq[n]\\|I|=|J|=k}}
 \per B[I,J],\qquad M_0(B)=1,
\]
the total weight of all \(k\)-matchings in the bipartite graph with edge
weights \(b_{ij}\). Bounding every \(M_k(B)\) also bounds the weighted
rook polynomial \(\nlsum_k M_k(B)z^k\) at every \(z\ge0\). Let \(e_k\)
denote the \(k\)-th elementary symmetric polynomial.

\begin{corollary}[Coefficientwise matching bound]\label{cor:matching}
Put \(r_i=\normG{b_i}\). Then
\begin{equation*}
 M_k(B)\le
 \frac{(n!)^{(n-k)/n}}{(n-k)!}\,e_k(r_1,\ldots,r_m)
 \qquad(0\le k\le\min(m,n)).
\end{equation*}
All these coefficient bounds are attained simultaneously by matrices
whose rows are constant.
\end{corollary}

\begin{proof}
For a fixed \(k\)-element row set \(I\), the sum over the \(k\)-element
column sets \(J\) is \(\per_{\mathrm{inj}}B[I,:]\).
Apply Theorem~\ref{thm:rectangular} and sum over \(I\).
If \(b_{ij}=c_i\), simultaneous equality follows from
\begin{equation*}
 M_k(B)=\frac{n!}{(n-k)!}e_k(c_1,\ldots,c_m),\qquad
 r_i=(n!)^{1/n}c_i.\qedhere
\end{equation*}
\end{proof}

\subsection{Entropy of random permutations}\label{sec:entropy}

The entropy bound from the introduction follows by optimizing the
Gibbs variational inequality over the rows of a stochastic matrix.
This optimization defines the entropy functional dual to the
Orlicz norm. For a probability
vector \(p\in\Delta_n\), define
\begin{equation*}
 \HG(p)=\inf_{a\in\Delta_n}\nlsum_jp_jh(a_j),\qquad
 \EG(p)=\nlsum_jp_jh(p_j)
       =\nlsum_jp_j^2\log\Gamma(1+1/p_j).
\end{equation*}
All logarithms are natural. The convention is \(0\cdot h(0)=0\), and a positive coefficient
multiplying \(h(0)\) gives \(+\infty\). Zero coordinates can equivalently
be deleted, since \(h\) is decreasing and putting positive mass on a zero
coordinate of \(p\) cannot improve the infimum.

\begin{proposition}[Properties of \(\HG\) and \(\EG\)]\label{prop:entropyprops}
The function \(\HG\) is symmetric and concave. The function \(\EG\) is
symmetric and strictly concave on each nontrivial simplex. Moreover,
\begin{equation*}
 0\le\HG(p)\le\EG(p)\le\Ent(p),
 \qquad \Ent(p)=-\nlsum_jp_j\log p_j.
\end{equation*}
If \(p\) has support size \(r\), then
\begin{equation}\label{eq:entropyuniform}
 \EG(p)\le\frac{\log(r!)}r,
\end{equation}
strictly unless \(p\) is uniform on its support. At that uniform vector,
both \(\HG\) and \(\EG\) equal \(\log(r!)/r\).
\end{proposition}

\begin{proof}
Approximating boundary competitors \(a\) by positive vectors shows that
the infimum defining \(\HG\) can be restricted to the relative interior
of the simplex. It is therefore an infimum of finite affine functions
of \(p\), which proves concavity. By \eqref{eq:hrep},
\(xh(x)=-\gamma x+\int_0^1\omega(t)\,x/(x+t)\dd t\), and hence
\begin{equation*}
 \frac{d^2}{dx^2}(xh(x))
 =-2\int_0^1\frac{\omega(t)t}{(x+t)^3}\dd t<0.
\end{equation*}
The function \(xh(x)\) extends continuously to zero with value zero.
Hence \(\EG\) is strictly concave, and Jensen's inequality yields
\eqref{eq:entropyuniform}. Testing \(a=p\) proves \(\HG\le\EG\).
Since \(\phi(x)\ge x\) on \([0,1]\), \(h(x)\le-\log x\), giving
\(\EG\le\Ent\), and nonnegativity follows from \(h\ge0\) on \((0,1]\).
For a uniform vector, convexity of \(h\) proves that the infimum defining
\(\HG\) occurs at the same uniform vector.
\end{proof}

\begin{theorem}[Entropy of a random permutation]\label{thm:entropy}
For a random permutation \(\Sigma\) of \([n]\), put
\[
 p_{ij}=\mathbb P\{\Sigma(i)=j\},\qquad p_i=(p_{ij})_j.
\]
Then, with \(\Ent(\Sigma)\) the Shannon entropy of the law of \(\Sigma\),
\begin{equation}\label{eq:permentropy}
 \Ent(\Sigma)\le\nlsum_i\HG(p_i)
 \le\nlsum_i\EG(p_i)
 =\nlsum_{i,j}p_{ij}^2\log\Gamma(1+1/p_{ij}).
\end{equation}
The first inequality is equivalent to Theorem~\ref{thm:main}.
The bounds are sharp for independent uniform permutations within
disjoint blocks.
\end{theorem}

\begin{proof}
For a positive row-stochastic \(A\), let
\[
 w(\sigma)=\nlprod_i\phi(a_{i,\sigma(i)}),
 \qquad Z=\nlsum_\sigma w(\sigma)\le1.
\]
Nonnegativity of the relative entropy of the law of \(\Sigma\) with
respect to \(w/Z\) gives
\[
 \Ent(\Sigma)\le\nlsum_{i,j}p_{ij}h(a_{ij})+\log Z
              \le\nlsum_{i,j}p_{ij}h(a_{ij}).
\]
Taking the infimum over each row independently, with approximation to
permit zero coordinates in the minimizers, gives the first bound, and
Proposition~\ref{prop:entropyprops} gives the second.

Conversely, if the first bound holds, apply it to the distribution
\(w/Z\). Its entropy identity yields
\[
 \log Z
 =\Ent(w/Z)-\nlsum_{i,j}p_{ij}h(a_{ij})
 \le\nlsum_i\left(\HG(p_i)-\nlsum_jp_{ij}h(a_{ij})\right)\le0.
\]
Since \(Z=\per\phi[A]\), this bound on \(\log Z\) is the permanent bound
for positive \(A\), and continuity handles the boundary. For a block
of size \(r\), a uniform permutation
has entropy \(\log(r!)\), and its \(r\) row contributions are each
\(\log(r!)/r\); independent blocks therefore give equality.
\end{proof}

Counting is the special case of a uniform law on a family of
permutations, where the entropy is the logarithm of the family's size.

\begin{corollary}[A bound using marginal frequencies]\label{cor:counting}
Let \(\mathcal F\) be a nonempty family of permutations, and let
\(p_{ij}\) be the marginal frequencies of the uniform distribution on
\(\mathcal F\). Then
\begin{equation*}
 |\mathcal F|
 \le\nlprod_{i,j:\,p_{ij}>0}
       \Gamma(1+1/p_{ij})^{p_{ij}^2}.
\end{equation*}
If row \(i\) uses \(r_i\) possible columns, this bound is at most
\(\prod_i(r_i!)^{1/r_i}\), and is strictly smaller whenever some row
marginal is nonuniform on its support.
\end{corollary}

\begin{proof}
Use \(\Ent(\Sigma)=\log|\mathcal F|\) in
Theorem~\ref{thm:entropy}, followed by \eqref{eq:entropyuniform}.
\end{proof}

Entropy methods for Br\'egman's inequality go back to
\citet{Radhakrishnan1997}; Corollary~\ref{cor:counting} uses the marginal
frequencies to refine the bound based on support sizes.

\begin{aiusage}
  The results were developed with GPT-6 (Pro) after extensive back and forth; none were obtained
  zero-shot. The author chose the problem, directed its Orlicz formulation, and suggested seeking
  positive integral representations as in subentropy \citep{Sra2019}, which was decisive to unlocking
  the proof---Section~\ref{sec:scalarproof}. GPT~Pro supplied derivations, literature searches, and
  repeated checks; GPT and Claude helped polish the writing.
\end{aiusage}

\aiacknowledgements

\begin{thebibliography}{9}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Br{\'e}gman(1973)]{Bregman1973}
L.~M. Br{\'e}gman.
\newblock Some properties of nonnegative matrices and their permanents.
\newblock \emph{Soviet Math. Dokl.}, 14:\penalty0 945--949, 1973.
\newblock Translated from Dokl. Akad. Nauk SSSR \textbf{211} (1973), no.~1,
  27--30.

\bibitem[Bristiel and Caputo(2024)]{BristielCaputo2024}
Alexandre Bristiel and Pietro Caputo.
\newblock Entropy inequalities for random walks and permutations.
\newblock \emph{Ann. Inst. Henri Poincar{\'e} Probab. Stat.}, 60\penalty0
  (1):\penalty0 54--81, 2024.
\newblock \doi{10.1214/22-AIHP1267}.
\newblock Preprint: \href{https://arxiv.org/abs/2109.06009}{arXiv:2109.06009}.

\bibitem[Gurvits and Samorodnitsky(2014)]{GurvitsSamorodnitsky2014}
Leonid Gurvits and Alex Samorodnitsky.
\newblock Bounds on the permanent and some applications.
\newblock In \emph{2014 IEEE 55th Annual Symposium on Foundations of Computer
  Science}, pages 90--99. IEEE Computer Society, 2014.
\newblock \doi{10.1109/FOCS.2014.18}.
\newblock Extended version:
  \href{https://arxiv.org/abs/1408.0976}{arXiv:1408.0976}; conjecture numbering
  refers to that version.

\bibitem[Jozsa and Mitchison(2015)]{JozsaMitchison2015}
Richard Jozsa and Graeme Mitchison.
\newblock Symmetric polynomials in information theory: entropy and subentropy.
\newblock \emph{J. Math. Phys.}, 56\penalty0 (6):\penalty0 062201, 2015.
\newblock \doi{10.1063/1.4922317}.
\newblock Preprint: \href{https://arxiv.org/abs/1404.7694}{arXiv:1404.7694}.

\bibitem[{National Institute of Standards and Technology}(2026)]{DLMF}
{National Institute of Standards and Technology}.
\newblock {NIST} digital library of mathematical functions.
\newblock \url{https://dlmf.nist.gov/5.8}, 2026.
\newblock Chapter~5, especially \S5.8. Accessed 30 October 2026.

\bibitem[Radhakrishnan(1997)]{Radhakrishnan1997}
Jaikumar Radhakrishnan.
\newblock An entropy proof of {B}r{\'e}gman's theorem.
\newblock \emph{J. Combin. Theory Ser. A}, 77\penalty0 (1):\penalty0 161--164,
  1997.
\newblock \doi{10.1006/jcta.1996.2727}.

\bibitem[Samorodnitsky(2008)]{Samorodnitsky2008}
Alex Samorodnitsky.
\newblock An upper bound for permanents of nonnegative matrices.
\newblock \emph{J. Combin. Theory Ser. A}, 115\penalty0 (2):\penalty0 279--292,
  2008.
\newblock \doi{10.1016/j.jcta.2007.05.010}.
\newblock Preprint:
  \href{https://arxiv.org/abs/math/0605147}{arXiv:math/0605147}.

\bibitem[Soules(2005)]{Soules2005}
George~W. Soules.
\newblock Permanental bounds for nonnegative matrices via decomposition.
\newblock \emph{Linear Algebra Appl.}, 394:\penalty0 73--89, 2005.
\newblock \doi{10.1016/j.laa.2004.06.022}.

\bibitem[Sra(2019)]{Sra2019}
Suvrit Sra.
\newblock Logarithmic inequalities under a symmetric polynomial dominance
  order.
\newblock \emph{Proc. Amer. Math. Soc.}, 147\penalty0 (2):\penalty0 481--486,
  2019.
\newblock \doi{10.1090/proc/14023}.
\newblock Preprint, with a slightly different title:
  \href{https://arxiv.org/abs/1509.05902}{arXiv:1509.05902}.

\end{thebibliography}

\end{document}