\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}.}}

\makeatother

\hypersetup{colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=red!65!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}}

\newtcolorbox{dashedbox}[1][]{
  before={\par\medskip\noindent},
  after={\par\medskip},
  colback=yellow!10!white,
  boxrule=0pt,
  enhanced jigsaw,
  top=2pt,
  left=2pt,
  right=2pt,
  bottom=0pt,
  borderline horizontal={0.5pt}{0pt}{dashed},
  borderline vertical={0.5pt}{0pt}{dashed},
  #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
}

\newcommand{\opnorm}[1]{\norm{#1}}
\newcommand{\one}{\mathbf{1}}   %
\newcommand{\uinorm}[1]{\lvert\kern-0.25ex\lvert\kern-0.25ex\lvert #1\rvert\kern-0.25ex\rvert\kern-0.25ex\rvert}  %
\tcbset{dashedrounded/.style={no borderline,borderline={0.5pt}{0pt}{dashed},arc=4pt}}

\allowdisplaybreaks

\subjclass[2020]{15A42, 15A60, 15B48, 05C50}
\keywords{nonnegative matrices, Blakley--Roy inequality, spectral radius of product}

\hypersetup{
  pdftitle={A spectral Blakley-Roy inequality for nonnegative matrices},
  pdfauthor={Suvrit Sra}
}

\makeatletter
\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.}}
\makeatother
\begin{document}
\title[A spectral Blakley--Roy inequality for nonnegative matrices]{\kern-4.53pt\mbox{A Spectral Blakley--Roy Inequality for Nonnegative Matrices}}
\aiauthor
\begin{abstract}
  Let $A$ and $B$ be real symmetric matrices with nonnegative entries.  We prove that
  $\rho(AB)^k\leqslant\rho(A^kB^k)$ for the spectral radius $\rho(\cdot)$ and every integer $k\geqslant1$; for
  $B=uu^T$ this is the Blakley--Roy inequality.  We prove it via the more general inequality
  $\opnorm{(AB)^m}^{k}\leqslant\opnorm{(A^kB^k)^m}$ in the spectral norm, valid for all integers
  $k,m\geqslant1$. The even exponents case follows from standard tools; for odd exponents $k=2r+1$ the claim
  follows via the more general product inequality,
  $(u^TC_1\cdots C_tv)^k\leqslant(u^Tu)^r(v^Tv)^r\,u^TC_1^k\cdots C_t^kv$ for nonnegative symmetric $C_i$ and
  nonnegative $u,v$.  Its proof is an entropy argument on paths that traverse each edge $k$ times, back
  and forth.
\end{abstract}
\preprintslink{pourya-rho}{15 October 2026}
\maketitle

\vspace*{-8pt}
\section{Introduction}\label{sec:intro}
For positive semidefinite $A$ and $B$, the powers $(AB)^k$ and $A^kB^k$ satisfy numerous spectral
inequalities. Two classical examples are: (i) the Cordes inequality $\opnorm{A^tB^t}\leqslant\opnorm{AB}^t$
for $0\leqslant t\leqslant1$ \citep{cordes1987spectral,furuta1989norm} which implies the operator norm inequality
$\opnorm{AB}^k\leqslant\|A^kB^k\|$; (ii) and the Araki--Lieb--Thirring inequality
$\trace(B^{1/2}AB^{1/2})^{kq}\leqslant\trace(B^{k/2}A^kB^{k/2})^q$ for $q>0$ \citep{araki1990inequality}, which in the limiting case as $q\to\infty$ gives the spectral radius inequality $\rho(AB)^k\leqslant\rho(A^kB^k)$.

\emph{But what about such inequalities without assuming semidefiniteness?} Pourya Habibzadeh conjectured
(personal communication, \emph{ca.}~2019) that $\rho(AB)^k\leqslant\rho(A^kB^k)$ remains true when $A$
and $B$ are symmetric with nonnegative entries. When $B$ is a rank-one semidefinite matrix $B=uu^T$ with
$u\geqslant 0$, we have $\rho(AB)^k=(u^TAu)^k$ and $\rho(A^kB^k)=(u^Tu)^{k-1}u^TA^ku$. So the conjecture
contains the Blakley--Roy inequality \citep{blakley1965holder} as a special case. The Blakley--Roy
inequality is also in \citet{mulholland1959inequality} and \citet{london1966inequalities}, as
\citet{erdos1982compactness} note, and it is the path case of Sidorenko's conjecture
\citep{sidorenko1993correlation}.

If instead of the spectral radius $\rho(\cdot)$, we ask the same question for operator norms, then already Cordes' inequality supplies a proof. Indeed, with $|A|=(A^2)^{1/2}$, we have
$\opnorm{AB}=\opnorm{|A|B}=\opnorm{B|A|}=\opnorm{|B|\,|A|}$, and
$|A^k|=|A|^k$; so the Cordes inequality with $t=1/k$ yields
\begin{equation}\label{eq:cordes}
 \norm{(AB)^k}\leqslant\norm{AB}^k\leqslant\norm{A^kB^k}
 \qquad(A=A^T,\ B=B^T).
\end{equation}
But merely symmetry does not suffice to prove the corresponding spectral-radius inequality. For instance, choosing $A=\one\one^T$ and $B=\begin{psmallmatrix}-1&1\\1&0\end{psmallmatrix}$,
a quick calculation shows that $\rho{(AB)^3}=1$ while $\rho(A^3B^3)=0$. Habibzadeh's conjecture asks whether requiring nonnegativity in addition suffices. We call a real matrix or vector $M$ nonnegative, and write
$M\geqslant0$, if every entry of $M$ is nonnegative.

The first main result of this paper resolves the conjecture via a more general inequality.
\begin{dashedbox}[dashedrounded]
\begin{theorem}\label{thm:main}
Let $A$ and $B$ be nonnegative symmetric matrices. Then, for all integers $k,m\geqslant1$,
\begin{equation}\label{eq:main}
 \opnorm{(AB)^m}^{k}\leqslant \norm{(A^kB^k)^m},
\end{equation}
and in particular $\rho(AB)^k\leqslant\rho(A^kB^k)$ for every integer $k\geqslant1$.
\end{theorem}
\end{dashedbox}
\noindent For even $k=2r$, Cordes' inequality combined with $\opnorm{AB}^2=\rho(A^2B^2)$ gives
$\opnorm{AB}^{2r}\leqslant\rho(A^{2r}B^{2r})$ (Lemma~\ref{lem:two}). Moreover, for even $k$, Theorem~\ref{thm:main} may omit the nonnegativity assumption. %

For odd $k=2r+1$, we deduce Theorem~\ref{thm:main} from Theorem~\ref{thm:path} (our second main result) that proves a ``Blakley--Roy''-type inequality for a product of arbitrary symmetric nonnegative matrices. %
\begin{dashedbox}[dashedrounded]
\begin{theorem}[Path inequality]\label{thm:path}
Let $k=2r+1$ be a positive odd integer, let $t\geqslant1$, and let
$C_1,\dots,C_t$ be nonnegative symmetric matrices of the same order. For nonnegative vectors $u,v$,
\begin{equation}\label{eq:path}
 \bigl(u^TC_1C_2\cdots C_t v\bigr)^k
 \leqslant
 (u^Tu)^r(v^Tv)^r\,
 u^TC_1^kC_2^k\cdots C_t^k v.
\end{equation}
\end{theorem}
\end{dashedbox}
Our proof of Theorem~\ref{thm:path} is an entropy argument built on the Gibbs variational principle:
the two matrix products in \eqref{eq:path} are partition functions of weighted paths, and we compare
them through a trial law that traverses each edge $k$ times, back and forth (Section~\ref{sec:path}).

\medskip
\noindent\textbf{More results.} Theorem~\ref{thm:path} also gives the many-matrix form of the spectral conjecture for
odd $k$, $\rho(C_1\cdots C_t)^k\leqslant\rho(C_1^k\cdots C_t^k)$ (Corollary~\ref{cor:rho-many}).  For
even $k$ and $t\geqslant3$ this fails
(Remark~\ref{rmk:even}).  %
The entropy argument leaves an exact remainder that can characterize equality: for strictly positive $A$
and $B$ and odd $k\geqslant3$, equality in \eqref{eq:main} holds exactly when $A$ and $B$ share a Perron
eigenvector (Corollary~\ref{cor:main-equality}), and likewise for the product inequality
(Section~\ref{sec:equality-sub}).  Section~\ref{sec:extensions} and Appendix~\ref{app:trees} record an extension of our path based arguments to trees, and other minor generalizations. %

\section{Proof of the path inequality Theorem~\ref{thm:path}}\label{sec:path}

For $t=1$ and $u=v$, inequality~\eqref{eq:path} is the Blakley--Roy inequality
$(u^TCu)^k\leqslant(u^Tu)^{k-1}u^TC^ku$, and for $t=1$ and $u\ne v$ it is the inequality
$(u^TCv)^k\leqslant(u^Tu)^r(v^Tv)^r\,u^TC^kv$ of \citet{pate2012extending}.  For one symmetric
nonnegative matrix $C$ and unit vectors $u,v$, \citet[Theorem~I.3]{saglam2018heat} proves
$(u^TC^\ell v)^k\leqslant(u^TC^kv)^\ell$ for positive integers $k\geqslant\ell$ of the same parity,
which for $\ell=1$ is Pate's inequality.  Our comparison permits a different matrix on each edge of the
path.

In \eqref{eq:path}, $u^TC_1\cdots C_tv$ and $u^TC_1^k\cdots C_t^kv$ are partition functions of (short) $t$-edge
paths and (long) $tk$-edge paths.  The Gibbs variational principle lower bounds log-partition functions by
the energy plus the entropy of any law on its paths.  The proof therefore comes down to choosing a law
on the long paths whose energy and entropy we can compute.  We build this law by gluing together the
vertex and edge marginals of the Gibbs law of the short paths.  The entropy identities that make the
computation possible are those behind the proofs of Sidorenko's inequality for trees and some extensions
\citep{li2025logarithmic,szegedy2014information,conlon2018some}; see \citet[Chapter~5]{zhao2023graph}.

First, we recall Gibbs variational identity, wherein $D(\pi\|\sigma)$ denotes relative entropy as usual. %
\begin{lemma}[Gibbs variational identity]\label{lem:gibbs}
Let $w:\Omega\to(0,\infty)$ on a finite nonempty set, let
$Z=\sum_{x\in\Omega}w(x)$, and let $\mu=w/Z$.  For every probability
vector $\pi$ on $\Omega$,
\[
 \log Z=\E_\pi\log w+H(\pi)+D(\pi\|\mu).
\]
In particular, $\E_\pi\log w+H(\pi)\leqslant\log Z$, with equality exactly when
$\pi=\mu$.
\end{lemma}

Next, we recall a key property of entropy for Markov laws; this will prove useful for studying long paths. Its entropy, like its energy, is then determined by its pair laws and its one-point laws.

\begin{lemma}[Entropy of a Markov chain]\label{lem:markov}
Let $Y_0,Y_1,\dots,Y_N$ be a Markov chain on a finite state space.  Let $\eta_j$
be the law of $Y_j$, and let $\gamma_j$ be the joint law of $(Y_{j-1},Y_j)$.
Then
\[
        H(Y_0,Y_1,\dots,Y_N)
        =\nlsum_{j=1}^N H(\gamma_j)-\nlsum_{j=1}^{N-1}H(\eta_j).
\]
\end{lemma}

\begin{proof}[\textbf{Proof of Theorem~\ref{thm:path}}]~For $k=1$ the two sides of \eqref{eq:path} coincide. Let $k=2r+1\geqslant3$, and assume first that all
entries of $u$, $v$, and the $C_i$ are positive; the nonnegative case follows by continuity.

\noindent\textbf{What we must show}.  Set $Z=u^TC_1C_2\cdots C_t v$,
$Q=u^TC_1^kC_2^k\cdots C_t^k v$, $U=u^Tu$, and $V=v^Tv$; then
\eqref{eq:path} reads $\log Q\geqslant k\log Z-r\log U-r\log V$.
Lemma~\ref{lem:gibbs} lower bounds $\log Q$ by the energy plus the
entropy of any law on long paths. The proof has four steps:
(i) write $\log Z$ through the vertex and edge marginals of the Gibbs law of
the short paths; (ii) glue from these marginals a Markov law $\nu$ on the
long paths; (iii) compute the energy and entropy of $\nu$, which are $k$
times those of the short paths up to some endpoint terms; (iv) show
that $U^r$ and $V^r$ absorb the endpoint terms.

\noindent\textbf{(i) Short paths}.  Write $C(x,y)$ for the $(x,y)$ entry of a
matrix $C$.  Then
\[
 Z=\nlsum_{x_0,\dots,x_t}w(x),
 \qquad
 w(x)=u_{x_0}\nlprod_{i=1}^t C_i(x_{i-1},x_i)v_{x_t},
\]
and $\mu=w/Z$ is a probability law on the paths $x=(x_0,\dots,x_t)$.  Let
$X=(X_0,\dots,X_t)$ have law $\mu$, let $\alpha_i$ be the law of $X_i$, and
let $\beta_i$ be the law of $(X_{i-1},X_i)$.  Since $w$ factorizes along the
path, $X$ is a Markov chain, so the equality case of Lemma~\ref{lem:gibbs} and
Lemma~\ref{lem:markov} give
\begin{equation}\label{eq:logZ}
 \log Z
 =\E_{\alpha_0}\log u
  +\sum_{i=1}^t\E_{\beta_i}\log C_i
  +\E_{\alpha_t}\log v
  +H(\mu),
 \quad
 H(\mu)=\sum_{i=1}^t H(\beta_i)-\sum_{i=1}^{t-1}H(\alpha_i).
\end{equation}

\noindent\textbf{(ii) Long paths and the glued law}.  Likewise $Q=\sum_yW(y)$ over $y=(y_0,\dots,y_{tk})$, with weight
\[
 W(y)=u_{y_0}\prod_{i=1}^t\prod_{j=1}^k
 C_i\bigl(y_{(i-1)k+j-1},y_{(i-1)k+j}\bigr)\,v_{y_{tk}}:
\]
edge $i$ of the short path is traversed $k$ times.  Let $\mu_k=W/Q$ be their
Gibbs law.  By Lemma~\ref{lem:gibbs},
$\log Q=\E_\nu\log W+H(\nu)+D(\nu\|\mu_k)$ for every law $\nu$ on these
paths, and it remains to choose $\nu$.  We want $\E_\nu\log W$ and $H(\nu)$ expressed
through the $\alpha_i$ and $\beta_i$ of \eqref{eq:logZ}.  The energy is $k$
times that of the short paths if every step across edge $i$ has pair law
$\beta_i$; a step with pair law $\beta_i$ leads from $\alpha_{i-1}$ to
$\alpha_i$, so to cross the edge again the chain has to turn back.  Let
$Y=(Y_0,\dots,Y_{tk})$ be the Markov chain with
$Y_0\sim\alpha_0$ whose steps in block $i$, the steps $(i-1)k+1,\dots,ik$,
alternate between the forward and the backward transitions
\begin{equation}\label{eq:transitions}
 P_i^+(y'\mid y)=\frac{\beta_i(y,y')}{\alpha_{i-1}(y)},
 \qquad
 P_i^-(y\mid y')=\frac{\beta_i(y,y')}{\alpha_i(y')},
\end{equation}
beginning with $P_i^+$, and let $\nu$ be its law.  These are the forward and
the reversed transitions of the conditioned walk in
\citet[Section~3]{saglam2018heat}; for one matrix, his proof lengthens the
walk by two steps, with one reversed transition at a uniformly random
position, and iterates, whereas we insert all $2r$ extra steps of each block
at once, which is what lets the matrix change from edge to edge.  Since
$\beta_i$ has marginals $\alpha_{i-1}$ and $\alpha_i$, a forward step carries
$\alpha_{i-1}$ to $\alpha_i$ with pair law $\beta_i$, and a backward step
carries $\alpha_i$ to $\alpha_{i-1}$ with pair law $\beta_i^T$.  Oddness of
$k$ enters here: block $i$ starts from $\alpha_{i-1}$ and ends at $\alpha_i$,
where block $i+1$ begins, so the blocks fit together, and every block has
$r+1$ forward and $r$ backward steps.

\noindent\textbf{(iii) Energy and entropy of the glued law}.  Symmetry enters next:
as $C_i=C_i^T$, a backward traversal of edge $i$ has the same expected energy
as a forward one, $\E_{\beta_i^T}\log C_i=\E_{\beta_i}\log C_i$, so
\begin{equation}\label{eq:energy}
 \E_\nu\log W
 =\E_{\alpha_0}\log u
 +k\sum_{i=1}^t\E_{\beta_i}\log C_i
 +\E_{\alpha_t}\log v.
\end{equation}
For $H(\nu)$, Lemma~\ref{lem:markov} needs the laws of the $tk$ pairs and of
the $tk-1$ interior states.  The pairs contribute $k\sum_{i=1}^tH(\beta_i)$.
Inside block $i$, the $2r$ interior states have law $\alpha_i$ after a forward
step and $\alpha_{i-1}$ after a backward step, $r$ times each; the $t-1$
states where consecutive blocks meet have laws $\alpha_1,\dots,\alpha_{t-1}$.
Hence $\alpha_0, \alpha_t$ occur $r$ times each, and each $\alpha_i$ with
$0<i<t$ occurs $2r+1=k$ times:
\begin{equation}\label{eq:entropy}
 H(\nu)
 =k\sum_{i=1}^tH(\beta_i)
  -k\sum_{i=1}^{t-1}H(\alpha_i)
  -rH(\alpha_0)-rH(\alpha_t)
 =kH(\mu)-rH(\alpha_0)-rH(\alpha_t).
\end{equation}

\noindent\textbf{(iv) Endpoints}.  Subtracting $k$ times \eqref{eq:logZ} from the
sum of \eqref{eq:energy} and \eqref{eq:entropy}, the edge terms cancel and
only the endpoints remain:
\[
 \log Q-k\log Z
 =D(\nu\|\mu_k)
 -r\bigl(2\E_{\alpha_0}\log u+H(\alpha_0)\bigr)
 -r\bigl(2\E_{\alpha_t}\log v+H(\alpha_t)\bigr).
\]
Put $p_u(a)=u_a^2/U$.  Lemma~\ref{lem:gibbs} with
$w(a)=u_a^2$, whose Gibbs law is $p_u$, gives
$2\E_{\alpha_0}\log u+H(\alpha_0)=\log U-D(\alpha_0\|p_u)$; likewise
$2\E_{\alpha_t}\log v+H(\alpha_t)=\log V-D(\alpha_t\|p_v)$ with
$p_v(b)=v_b^2/V$.  Without the remainders, this endpoint bound is
\citet[Lemma~3.6]{saglam2018heat}.  Hence
\begin{equation}\label{eq:deficit}
 \log\frac{QU^rV^r}{Z^k}
 =D(\nu\|\mu_k)+rD(\alpha_0\|p_u)+rD(\alpha_t\|p_v).
\end{equation}
The right side is nonnegative, which is \eqref{eq:path} for positive data.
For nonnegative data, apply \eqref{eq:path} to $u+\varepsilon\one$,
$v+\varepsilon\one$, and $C_i+\varepsilon\one\one^T$, and let
$\varepsilon\downarrow0$.
\end{proof}

\begin{rmk}\label{rmk:nonsymmetric}
Symmetry enters the proof only through
$\E_{\beta_i^T}\log C_i=\E_{\beta_i}\log C_i$.  Without it, a backward
traversal of edge $i$ carries the weight $C_i^T$, and the same proof,
including \eqref{eq:deficit}, gives, for nonnegative matrices
$C_1,\dots,C_t$ of any compatible shapes and nonnegative endpoint vectors,
\begin{equation}\label{eq:path-rectangular}
 (u^TC_1\cdots C_tv)^k
 \leqslant(u^Tu)^r(v^Tv)^r\,
 u^TF_k(C_1)\cdots F_k(C_t)\,v,
 \qquad F_k(C)=(CC^T)^rC,
\end{equation}
with $Q=u^TF_k(C_1)\cdots F_k(C_t)v$ in \eqref{eq:deficit}.
For $t=1$ this is Pate's inequality~\citep[Theorem~4]{pate2012extending}.
\end{rmk}

\section{Proof of Theorem~\ref{thm:main} and related norm inequalities}\label{sec:all}

Nonnegative maximizing singular vectors turn the endpoint comparison into
a norm comparison.  Repeating the factors then gives the spectral radius
and the odd part of Theorem~\ref{thm:main}.

\begin{corr}\label{cor:norm-many}
Let $k$ be a positive odd integer, and let $C_1,\dots,C_t$ be real symmetric matrices with
nonnegative entries.  Then
\begin{equation}\label{eq:norm-many}
 \opnorm{C_1C_2\cdots C_t}^k
 \leqslant
 \opnorm{C_1^kC_2^k\cdots C_t^k}.
\end{equation}
\end{corr}

\begin{proof}
Set $D=C_1C_2\cdots C_t$ and $E=C_1^kC_2^k\cdots C_t^k$, both entrywise
nonnegative, and assume $D\ne0$.  Since $D^TD\geqslant0$, every real vector $y$
satisfies $|y|^TD^TD|y|\geqslant y^TD^TDy$, so $D^TD$ has a unit eigenvector
$y\geqslant0$ for its largest eigenvalue $\opnorm{D}^2$.
Set $x=Dy/\opnorm{D}$; this is a unit vector with $x\geqslant0$ and
$x^TDy=\opnorm{D}$.  Theorem~\ref{thm:path}
gives
\[
        \opnorm{D}^k=(x^TDy)^k\leqslant x^TEy\leqslant \opnorm{E}.
\qedhere
\]
\end{proof}

\begin{corr}\label{cor:rho-many}
Let $k$ be a positive odd integer, and let $C_1,\dots,C_t$ be real symmetric matrices with
nonnegative entries.  Then
$\rho(C_1C_2\cdots C_t)^k\leqslant\rho(C_1^kC_2^k\cdots C_t^k)$.
\end{corr}

\begin{proof}
Applied to the $tm$ factors of $(C_1\cdots C_t)^m$, inequality
\eqref{eq:norm-many} gives
\begin{equation}
  \label{eq:1}
  \opnorm{(C_1\cdots C_t)^m}^k\leqslant\opnorm{(C_1^k\cdots C_t^k)^m}.
\end{equation}
Apply Gelfand's formula $\rho(X)=\lim_{m\to\infty}\|X^m\|^{1/m}$ to conclude $\rho(C_1\cdots C_t)^k\leqslant\rho(C_1^k\cdots C_t^k)$.
\end{proof}

\subsection{Two matrices and all exponents}
For two factors, the even exponents can be handled without the entropy
argument.  The following consequence of Cordes' inequality isolates where
entrywise nonnegativity is needed.

\begin{lemma}\label{lem:two}
Let $A=A^T$ and $B=B^T$.  Then $\opnorm{AB}^2=\rho(A^2B^2)$, and, for
all integers $q,m\geqslant1$,
\begin{equation}\label{eq:two}
 \opnorm{(AB)^m}^{2q}\leqslant\rho(A^{2q}B^{2q})^m
                       \leqslant\opnorm{(A^{2q}B^{2q})^m}.
\end{equation}
\end{lemma}

\begin{proof}
Since $XY$ and $YX$ have the same nonzero eigenvalues,
\[
 \opnorm{AB}^2=\rho\bigl((AB)^T(AB)\bigr)
             =\rho(BA^2B)=\rho(A^2B^2).
\]
Apply this identity to the symmetric matrices $A^q,B^q$ and use
\eqref{eq:cordes} to obtain
\[
 \opnorm{AB}^{2q}\leqslant\opnorm{A^qB^q}^2=\rho(A^{2q}B^{2q}).
\]
The first inequality in \eqref{eq:two} is submultiplicativity; 
the second follows from $\rho(M^m)\leqslant\opnorm{M^m}$.
\end{proof}

\begin{proof}[\textbf{Proof of Theorem~\ref{thm:main}}]
For odd $k$, apply Corollary~\ref{cor:norm-many} to the $2m$ alternating
factors $A,B,\ldots,A,B$ of $(AB)^m$.  For even $k=2q$, apply
Lemma~\ref{lem:two}.  This proves \eqref{eq:main}.  Taking $m$-th roots in
\eqref{eq:main}, Gelfand's formula gives
\[
 \rho(AB)^k=\lim_{m\to\infty}\opnorm{(AB)^m}^{k/m}
 \leqslant\lim_{m\to\infty}\opnorm{(A^kB^k)^m}^{1/m}
 =\rho(A^kB^k).
\qedhere
\]
\end{proof}

\subsection{Limits of the hypotheses}\label{sec:limits}
The two-matrix conclusion uses fewer hypotheses at even exponents than the
many-factor conclusion, and the next example separates the two.  (Positive
semidefiniteness does not replace entrywise nonnegativity in the many-factor
statements either: for three positive definite $2\times2$ factors, both
\eqref{eq:norm-many} and \eqref{eq:path} fail, as an easy example shows.
Comparisons of three or more positive semidefinite matrices require the
multivariate trace inequalities of \citet{sutter2017multivariate}; see
\citet{hiai2017generalized} for their log-majorization form.)

\begin{rmk}\label{rmk:even}
Corollaries~\ref{cor:norm-many} and~\ref{cor:rho-many} fail for even $k$.
Let $E_{ij}$ be the $3\times3$ matrix
with a single $1$, in position $(i,j)$, and let $C_1=E_{23}+E_{32}$,
$C_2=E_{13}+E_{31}$, and $C_3=E_{12}+E_{21}$.  Then
\[
 C_1C_2C_3=E_{22},
 \qquad
 C_1^2C_2^2C_3^2=(E_{22}+E_{33})(E_{11}+E_{33})(E_{11}+E_{22})=0,
\]
so $\opnorm{C_1C_2C_3}=\rho(C_1C_2C_3)=1$ while $C_1^2C_2^2C_3^2=0$.
\end{rmk}

\section{Equality cases and Extensions}\label{sec:equality}

The identity \eqref{eq:deficit} writes the logarithmic gap in
\eqref{eq:path} as a sum of three relative entropies.  Equality therefore
forces the glued law to coincide with the Gibbs law of the long paths, and
a message calculation turns that coincidence into a condition on the
matrices.

\subsection{Equality}\label{sec:equality-sub}
Let $k=2r+1\geqslant3$, let $C_1,\ldots,C_t$ be strictly positive matrices of
compatible rectangular shapes, and let the endpoint vectors $u,v$ be
strictly positive.  Let $Z$, $Q$, $U$, $V$, the laws $\mu$, $\alpha_i$,
$\beta_i$, $\nu$, $\mu_k$, and the endpoint laws $p_u,p_v$ be as in the
proof of Theorem~\ref{thm:path} and Remark~\ref{rmk:nonsymmetric}, so that
\begin{equation}\label{eq:Delta}
 \Delta:=\log\frac{QU^rV^r}{Z^k}
 =D(\nu\|\mu_k)+rD(\alpha_0\|p_u)+rD(\alpha_t\|p_v).
\end{equation}

\begin{prop}\label{prop:equality}
With the positive data above, equality in
\eqref{eq:path-rectangular} holds if and only if there are positive unit
vectors $a_0,\ldots,a_t$ and positive numbers $\sigma_1,\ldots,\sigma_t$
such that
\begin{equation}\label{eq:aligned}
 C_i a_i=\sigma_i a_{i-1},\qquad C_i^Ta_{i-1}=\sigma_i a_i
 \quad(1\leqslant i\leqslant t),\qquad u\parallel a_0,\quad v\parallel a_t.
\end{equation}
For strictly positive symmetric $C_i$, this is equivalent to a common
positive Perron eigenvector proportional to both $u$ and $v$.
\end{prop}

\begin{proof}
Define the left and right messages
\[
 l_0=u,\quad l_i=C_i^T\cdots C_1^Tu,\qquad
 h_t=v,\quad h_i=C_{i+1}\cdots C_tv.
\]
Summing the weights on either side of a vertex or edge gives
\begin{equation}\label{eq:messages}
 \alpha_i(a)=\frac{l_i(a)h_i(a)}{Z},\qquad
 \beta_i(a,b)=\frac{l_{i-1}(a)C_i(a,b)h_i(b)}{Z}.
\end{equation}
Thus the transitions in \eqref{eq:transitions} are
$C_i(a,b)h_i(b)/h_{i-1}(a)$ and
$C_i(a,b)l_{i-1}(a)/l_i(b)$.
Write $y_{i,j}=y_{(i-1)k+j}$ for coordinate $j$ of block $i$, so that
$y_{i,k}=y_{i+1,0}$.  Multiplying these transitions and cancelling the
edge weights against those in $\mu_k$ gives
\begin{equation}\label{eq:law-ratio}
 \frac{\nu(y)}{\mu_k(y)}
 =\frac QZ\prod_{i=1}^t\prod_{a=1}^r
   \frac{h_i(y_{i,2a-1})}{l_i(y_{i,2a-1})}
   \frac{l_{i-1}(y_{i,2a})}{h_{i-1}(y_{i,2a})}.
\end{equation}
All interior coordinates can be varied independently and all configurations
have positive probability.  Since $r\geqslant1$, each level $i=0,\ldots,t$
appears in at least one factor of this product.  Hence the ratio in
\eqref{eq:law-ratio} is constant if and only if $l_i\parallel h_i$ at every
level.  A constant ratio is one because both laws are normalized.

If equality holds in \eqref{eq:path-rectangular}, then $\Delta=0$ and
\eqref{eq:Delta} gives $\nu=\mu_k$.  The proportionalities just
obtained follow.  Conversely, those proportionalities give $\nu=\mu_k$,
and the endpoint cases of \eqref{eq:messages} give
$\alpha_0=p_u$ and $\alpha_t=p_v$.  Thus all three terms of
\eqref{eq:Delta} vanish.

Normalize the proportional messages to unit vectors $a_i$.  The recursions
$h_{i-1}=C_ih_i$ and $l_i=C_i^Tl_{i-1}$ give
$C_ia_i=s_i a_{i-1}$ and $C_i^Ta_{i-1}=t_i a_i$ for positive scalars.
Taking the inner product with $a_{i-1}$ and $a_i$, respectively, gives
$s_i=t_i$, proving \eqref{eq:aligned}.  Conversely, \eqref{eq:aligned}
and the endpoint proportionalities imply $l_i\parallel h_i$ by recursion.

If $C_i$ is symmetric and strictly positive, both $a_{i-1}$ and $a_i$
are positive eigenvectors of $C_i^2$ with eigenvalue $\sigma_i^2$.
The Perron eigenspace of the strictly positive matrix $C_i^2$ is
one-dimensional, so the unit vectors coincide.  Equation~\eqref{eq:aligned}
then makes this common vector a Perron eigenvector of every $C_i$.
The converse follows by substituting the common eigenvector into
\eqref{eq:aligned}.
\end{proof}

\begin{corr}\label{cor:norm-equality}
For strictly positive symmetric $C_1,\ldots,C_t$ and odd $k\geqslant3$, equality
in \eqref{eq:norm-many} holds if and only if the factors share a positive
Perron eigenvector.
\end{corr}

\begin{proof}
The product $D=C_1\cdots C_t$ has strictly positive left and right unit
singular vectors $x,y$ for its largest singular value.  If equality holds
in \eqref{eq:norm-many}, both inequalities
$\opnorm D^k=(x^TDy)^k\leqslant x^TEy\leqslant\opnorm E$, with
$E=C_1^k\cdots C_t^k$, are equalities.  Proposition~\ref{prop:equality}
gives a common Perron vector.  Conversely, if $C_i a=\lambda_i a$ for
one positive unit vector $a$, symmetry gives $\opnorm{C_i}=\lambda_i$.
The eigenvector lower bound and submultiplicativity show
$\opnorm D=\prod_i\lambda_i$ and $\opnorm E=\prod_i\lambda_i^k$.
\end{proof}

\begin{corr}\label{cor:main-equality}
Let $A$ and $B$ be strictly positive symmetric matrices, let $k\geqslant3$ be
odd, and let $m\geqslant1$.  Equality holds in \eqref{eq:main} if and only if
$A$ and $B$ share a positive Perron eigenvector.
\end{corr}

\begin{proof}
For odd $k$, inequality \eqref{eq:main} is \eqref{eq:norm-many} for the
$2m$ alternating factors $A,B,\ldots,A,B$, so
Corollary~\ref{cor:norm-equality} applies.
\end{proof}

\subsection{Extensions}\label{sec:extensions}
The proof of Theorem~\ref{thm:path} uses the path only through
Lemma~\ref{lem:markov}, which is the path case of the entropy formula for
laws that factorize along a tree.  Appendix~\ref{app:trees} proves the
tree version: for a finite tree $T$ with a nonnegative rectangular matrix
$C_e$ on each edge and a nonnegative vector $u_\ell$ at each leaf $\ell$,
the partition function $Z_T$ of \eqref{eq:tree-Z} satisfies
\[
 Z_T(C;u)^k\leqslant\Bigl(\nlprod_{\ell}(u_\ell^Tu_\ell)^r\Bigr)Z_T(F_k(C);u),
\]
where $F_k(C)$ replaces each edge matrix by $(C_eC_e^T)^rC_e$
(Theorem~\ref{thm:tree}).  Its exact remainder is \eqref{eq:deficit} with
one relative entropy per leaf and an additional term
$r\sum_v(d_v-2)H(\alpha_v)$ over the internal vertices $v$, of degree $d_v$.  The leaf factors are not a
homomorphism-density normalization; under that normalization the branching
term in \eqref{eq:tree-deficit} changes sign and the comparison can fail.

The remainder also bounds the distance to equality.  By Pinsker's
inequality, with $\Delta$ as in \eqref{eq:Delta},
\[
 \|\nu-\mu_k\|_1\leqslant\sqrt{2\Delta},\qquad
 \|\alpha_0-p_u\|_1,\ \|\alpha_t-p_v\|_1
 \leqslant\sqrt{2\Delta/r}.
\]
These estimates compare laws; they do not say that the matrices are close
to a family with a common eigenvector.

The even case of Theorem~\ref{thm:main} extends in a different direction,
to all unitarily invariant norms; the odd case does not.

\begin{rmk}\label{rmk:ui}
For even exponents, Lemma~\ref{lem:two} holds in every unitarily invariant
norm $\uinorm{\cdot}$: for symmetric $A,B$ and integers $q,m\geqslant1$,
\begin{equation}\label{eq:ui}
 \uinorm{\,|(AB)^m|^{2q}}\leqslant\uinorm{(A^{2q}B^{2q})^m},
 \qquad |X|=(X^TX)^{1/2}.
\end{equation}
Indeed, the $j$-th compound matrices of $A$ and $B$ are symmetric, and
Lemma~\ref{lem:two} applied to them gives
$\prod_{i\leqslant j}\sigma_i((AB)^m)^{2q}\leqslant\prod_{i\leqslant j}\sigma_i((A^{2q}B^{2q})^m)$
for every $j$, where $\sigma_1(X)\geqslant\sigma_2(X)\geqslant\cdots$ are the singular
values; this weak log-majorization implies \eqref{eq:ui}
\citep[Theorems~6.5 and~6.23]{hiai2014introduction}.  The power must stand
inside the norm: for $A=B=I_n$ the trace norms give $n^{2q}>n$.  For odd
$k$ under entrywise nonnegativity there is no such extension, since the
compound matrices of a nonnegative matrix need not be nonnegative.  With
$J=\one\one^T$ and $Q=\begin{psmallmatrix}-1&1\\1&0\end{psmallmatrix}$ from
Section~\ref{sec:intro}, write $Q=Q_+-Q_-$ with $Q_\pm\geqslant0$, and let
$A=J\oplus J$ and $B=\begin{psmallmatrix}Q_+&Q_-\\Q_-&Q_+\end{psmallmatrix}$,
both symmetric and nonnegative.  Conjugation by
$\frac1{\sqrt2}\begin{psmallmatrix}I&I\\I&-I\end{psmallmatrix}$ fixes $A$ and
takes $B$ to $(Q_++Q_-)\oplus Q$.  Since $(JQ)^2=JQ$ has rank one and
$(J^3Q^3)^2=0$, the matrix $(AB)^2$ has rank two while $(A^3B^3)^2$ has
rank one, so the cubed singular values of $(AB)^2$ are not weakly
log-majorized by those of $(A^3B^3)^2$.
\end{rmk}

\begin{aiusage}
The results in this paper were developed through extensive use of AI
assistants: GPT~Pro for the main line of argument, and 
Claude for the writing, literature search, and some examples. None of
the claims were obtained zero-shot: they emerged through sustained
back-and-forth discussion, including failed attempts, counterexamples, audits,
and repairs.  The main idea to pursue the norm inequality was introduced by the author.
\end{aiusage}

\aiacknowledgements[The author thanks Pourya Habibzadeh for formulating the
conjecture \(\rho(AB)^k\leqslant\rho(A^kB^k)\) that is the origin of this work.]

\begin{thebibliography}{17}
\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[Araki(1990)]{araki1990inequality}
Huzihiro Araki.
\newblock On an inequality of {L}ieb and {T}hirring.
\newblock \emph{Letters in Mathematical Physics}, 19\penalty0 (2):\penalty0
  167--170, 1990.
\newblock \doi{10.1007/BF01045887}.

\bibitem[Blakley and Roy(1965)]{blakley1965holder}
G.~R. Blakley and Prabir Roy.
\newblock A {H}\"older type inequality for symmetric matrices with nonnegative
  entries.
\newblock \emph{Proceedings of the American Mathematical Society}, 16\penalty0
  (6):\penalty0 1244--1245, 1965.
\newblock \doi{10.1090/S0002-9939-1965-0184950-9}.

\bibitem[Conlon et~al.(2018)Conlon, Kim, Lee, and Lee]{conlon2018some}
David Conlon, Jeong~Han Kim, Choongbum Lee, and Joonkyung Lee.
\newblock Some advances on {S}idorenko's conjecture.
\newblock \emph{Journal of the London Mathematical Society}, 98\penalty0
  (3):\penalty0 593--608, 2018.
\newblock \doi{10.1112/jlms.12142}.

\bibitem[Cordes(1987)]{cordes1987spectral}
Heinz~Otto Cordes.
\newblock \emph{Spectral Theory of Linear Differential Operators and Comparison
  Algebras}, volume~76 of \emph{London Mathematical Society Lecture Note
  Series}.
\newblock Cambridge University Press, Cambridge, 1987.
\newblock \doi{10.1017/CBO9780511662836}.

\bibitem[Erd{\H o}s and Simonovits(1982)]{erdos1982compactness}
Paul Erd{\H o}s and Mikl{\'o}s Simonovits.
\newblock Compactness results in extremal graph theory.
\newblock \emph{Combinatorica}, 2\penalty0 (3):\penalty0 275--288, 1982.
\newblock \doi{10.1007/BF02579234}.

\bibitem[Furuta(1989)]{furuta1989norm}
Takayuki Furuta.
\newblock Norm inequalities equivalent to {L}\"owner--{H}einz theorem.
\newblock \emph{Reviews in Mathematical Physics}, 1\penalty0 (1):\penalty0
  135--137, 1989.
\newblock \doi{10.1142/S0129055X89000079}.

\bibitem[Hiai and Petz(2014)]{hiai2014introduction}
Fumio Hiai and D{\'e}nes Petz.
\newblock \emph{Introduction to Matrix Analysis and Applications}.
\newblock Universitext. Springer, Cham, 2014.
\newblock \doi{10.1007/978-3-319-04150-6}.

\bibitem[Hiai et~al.(2017)Hiai, K{\"o}nig, and Tomamichel]{hiai2017generalized}
Fumio Hiai, Robert K{\"o}nig, and Marco Tomamichel.
\newblock Generalized log-majorization and multivariate trace inequalities.
\newblock \emph{Annales Henri Poincar{\'e}}, 18\penalty0 (7):\penalty0
  2499--2521, 2017.
\newblock \doi{10.1007/s00023-017-0569-y}.

\bibitem[Li and Szegedy(2025)]{li2025logarithmic}
Xiang Li and Bal{\'a}zs Szegedy.
\newblock On the logarithmic calculus and {S}idorenko's conjecture.
\newblock \emph{Acta Mathematica Hungarica}, 177\penalty0 (2):\penalty0
  450--463, 2025.
\newblock \doi{10.1007/s10474-026-01582-2}.

\bibitem[London(1966)]{london1966inequalities}
David London.
\newblock Inequalities in quadratic forms.
\newblock \emph{Duke Mathematical Journal}, 33\penalty0 (3):\penalty0 511--522,
  1966.
\newblock \doi{10.1215/S0012-7094-66-03360-6}.

\bibitem[Mulholland and Smith(1959)]{mulholland1959inequality}
H.~P. Mulholland and C.~A.~B. Smith.
\newblock An inequality arising in genetical theory.
\newblock \emph{The American Mathematical Monthly}, 66\penalty0 (8):\penalty0
  673--683, 1959.
\newblock \doi{10.1080/00029890.1959.11989387}.

\bibitem[Pate(2012)]{pate2012extending}
Thomas~H. Pate.
\newblock Extending the {H}\"older type inequality of {B}lakley and {R}oy to
  non-symmetric non-square matrices.
\newblock \emph{Transactions of the American Mathematical Society},
  364\penalty0 (8):\penalty0 4267--4281, 2012.
\newblock \doi{10.1090/S0002-9947-2012-05501-2}.

\bibitem[Sa{\u g}lam(2018)]{saglam2018heat}
Mert Sa{\u g}lam.
\newblock Near log-convexity of measured heat in (discrete) time and
  consequences.
\newblock In \emph{2018 IEEE 59th Annual Symposium on Foundations of Computer
  Science (FOCS)}, pages 967--978. IEEE, 2018.
\newblock \doi{10.1109/FOCS.2018.00095}.

\bibitem[Sidorenko(1993)]{sidorenko1993correlation}
Alexander Sidorenko.
\newblock A correlation inequality for bipartite graphs.
\newblock \emph{Graphs and Combinatorics}, 9\penalty0 (2):\penalty0 201--204,
  1993.
\newblock \doi{10.1007/BF02988307}.

\bibitem[Sutter et~al.(2017)Sutter, Berta, and
  Tomamichel]{sutter2017multivariate}
David Sutter, Mario Berta, and Marco Tomamichel.
\newblock Multivariate trace inequalities.
\newblock \emph{Communications in Mathematical Physics}, 352\penalty0
  (1):\penalty0 37--58, 2017.
\newblock \doi{10.1007/s00220-016-2778-5}.

\bibitem[Szegedy(2014)]{szegedy2014information}
Bal{\'a}zs Szegedy.
\newblock An information theoretic approach to {S}idorenko's conjecture.
\newblock arXiv:1406.6738 [math.CO], 2014.

\bibitem[Zhao(2023)]{zhao2023graph}
Yufei Zhao.
\newblock \emph{Graph Theory and Additive Combinatorics: Exploring Structure
  and Randomness}.
\newblock Cambridge University Press, Cambridge, 2023.
\newblock \doi{10.1017/9781009310956}.

\end{thebibliography}

\appendix

\section{Trees}\label{app:trees}

Lemma~\ref{lem:markov} is the path case of the gluing lemma below, and the
proof of Theorem~\ref{thm:path} is the path case of the proof of
Theorem~\ref{thm:tree}.  The vertex and edge marginals of a Gibbs law on a
tree can be glued without a compatibility condition around cycles, and the
glued law has an explicit entropy.

\begin{lemma}[Gluing on a tree]\label{lem:tree-gluing}
Let $T=(V,E)$ be a finite tree, with a finite nonempty state space
$\Omega_v$ at each vertex.  Suppose $\alpha_v$ is a strictly positive
probability vector on $\Omega_v$, and for each edge $\{v,w\}$ the strictly
positive pair law $\beta_{vw}$ has marginals $\alpha_v,\alpha_w$, with
$\beta_{wv}=\beta_{vw}^T$.
There is a probability law $\eta$ with these marginals given by
\begin{equation}\label{eq:tree-law}
 \eta(x)=\frac{\prod_{\{v,w\}\in E}\beta_{vw}(x_v,x_w)}
                  {\prod_{v\in V}\alpha_v(x_v)^{d_v-1}},
 \qquad d_v=\deg_T(v).
\end{equation}
It satisfies
\begin{equation}\label{eq:tree-entropy}
 H(\eta)=\sum_{\{v,w\}\in E}H(\beta_{vw})
          -\sum_{v\in V}(d_v-1)H(\alpha_v).
\end{equation}
Every strictly positive law that factorizes into vertex and edge weights
on $T$ has the form \eqref{eq:tree-law} for its own marginals.
\end{lemma}

\begin{proof}
Choose a root $o$.  Sample its state with law $\alpha_o$, and, independently
along the branches conditional on their parent states, sample each child
$w$ of $v$ with transition $\beta_{vw}(x_v,x_w)/\alpha_v(x_v)$.
Each transition sums to one, and induction from the root verifies the
prescribed vertex and edge marginals.  Multiplying the transitions and
$\alpha_o(x_o)$ gives \eqref{eq:tree-law}; in particular, the law is
independent of the root.  Taking the expectation of $-\log\eta$ proves
\eqref{eq:tree-entropy}.

For a law that factorizes into positive vertex and edge weights, conditioning
on the state at a vertex separates the components left after deleting that
vertex: their conditional weights are products over disjoint variables.
Thus each child subtree is conditionally independent of the other subtrees
and of the ancestors, given its parent state.  Factoring the law from the
root therefore gives the same transitions and \eqref{eq:tree-law}.
\end{proof}

\subsection{Partition functions and their odd expansions}
Let $T=(V,E)$ have at least one edge, let $L=\{v:d_v=1\}$ be its leaves,
and assign a finite nonempty state space $\Omega_v$ to each vertex.
Choose an orientation for each edge $e=(v,w)$ and a nonnegative matrix
$C_e$ of shape $|\Omega_v|\times|\Omega_w|$.  At each leaf choose a
nonnegative vector $u_\ell$ indexed by $\Omega_\ell$, and put
$U_\ell=u_\ell^Tu_\ell$.  There are no
additional vertex weights at the internal vertices.  Define
\begin{equation}\label{eq:tree-Z}
 Z_T(C;u)=\sum_{x\in\prod_{v\in V}\Omega_v}
          \prod_{e=(v,w)\in E}C_e(x_v,x_w)
          \prod_{\ell\in L}u_\ell(x_\ell).
\end{equation}
All sums use counting measure.  Reversing an edge orientation transposes
its matrix and leaves this partition function unchanged.

For a positive odd integer $k=2r+1$, let $F_k(C)=(CC^T)^rC$ as in
Remark~\ref{rmk:nonsymmetric}.
Replace each edge $e=(v,w)$ by a path of length $k$.  Its successive state
spaces alternate between copies of $\Omega_v$ and $\Omega_w$, and its
matrices alternate between $C_e$ and $C_e^T$.  The $2r$ inserted vertices
have new coordinates, even when their state spaces are copies of the same
$\Omega_v$.  Keep the original leaf weights.  Summing over the inserted
coordinates contracts this path to $F_k(C_e)$, so the expanded tree has
partition function
\[
 Q=Z_T(F_k(C);u),\qquad F_k(C)=(F_k(C_e))_{e\in E}.
\]
The identity $F_k(C^T)=F_k(C)^T$ makes the expansion independent of the
chosen edge orientations.

For strictly positive data, let $\mu$ be the Gibbs law of
$Z=Z_T(C;u)$, with vertex marginals $\alpha_v$ and edge marginals $\beta_e$.
Let $\mu_k$ be the Gibbs law on the expanded tree.  Give each copy of
$\Omega_v$ the marginal $\alpha_v$, and give the successive edges in the
expansion of $e$ pair laws $\beta_e,\beta_e^T,\ldots,\beta_e$.
These marginals agree at every shared vertex.  Lemma~\ref{lem:tree-gluing}
defines a law $\nu$ on the expanded tree from them.  Finally, set
\[
 p_\ell(a)=\frac{u_\ell(a)^2}{U_\ell}.
\]

The entropy comparison distinguishes the leaves, where a boundary factor
is needed, from the branching vertices, which give a nonnegative remainder.

\begin{theorem}\label{thm:tree}
For the tree and nonnegative data in \eqref{eq:tree-Z}, and every odd
integer $k=2r+1\geqslant3$,
\begin{equation}\label{eq:tree}
 Z_T(C;u)^k\leqslant
 \left(\prod_{\ell\in L}U_\ell^r\right)Z_T(F_k(C);u).
\end{equation}
If all entries of the edge matrices and leaf vectors are strictly positive,
the laws defined above satisfy the exact identity
\begin{equation}\label{eq:tree-deficit}
 \log\frac{Q\prod_{\ell\in L}U_\ell^r}{Z^k}
 =D(\nu\|\mu_k)
  +r\sum_{\ell\in L}D(\alpha_\ell\|p_\ell)
  +r\sum_{v\in V\setminus L}(d_v-2)H(\alpha_v).
\end{equation}
\end{theorem}

\begin{proof}
First assume strict positivity.  Denote the weights of the original and
expanded configurations by $w$ and $W$, respectively.  By the Gibbs identity,
\begin{equation}\label{eq:tree-logZ}
 \log Z=\sum_{e\in E}\E_{\beta_e}\log C_e
       +\sum_{\ell\in L}\E_{\alpha_\ell}\log u_\ell+H(\mu).
\end{equation}
Each forward traversal of edge $e$ has expected log weight
$\E_{\beta_e}\log C_e$; a backward traversal has the same expectation
because both the pair law and the matrix are transposed.  The original
leaves retain their marginals.  Thus
\begin{equation}\label{eq:tree-energy}
 \E_\nu\log W
 =k\sum_{e\in E}\E_{\beta_e}\log C_e
  +\sum_{\ell\in L}\E_{\alpha_\ell}\log u_\ell.
\end{equation}

To compute $H(\nu)$, apply Lemma~\ref{lem:tree-gluing} to both trees.
The expanded edges contribute $k\sum_e H(\beta_e)$.  Each original vertex
retains degree $d_v$ and marginal $\alpha_v$, and each incident edge
introduces $r$ degree-two vertices with that marginal.  Consequently,
\begin{align}
 H(\nu)
 &=k\sum_e H(\beta_e)
   -\sum_v(d_v-1)H(\alpha_v)-r\sum_v d_vH(\alpha_v)\notag\\
 &=kH(\mu)+r\sum_v(d_v-2)H(\alpha_v).
 \label{eq:tree-entropy-count}
\end{align}
The second equality uses $k-1=2r$.

Apply Lemma~\ref{lem:gibbs} to $W$ with trial law $\nu$, and subtract
$k$ times \eqref{eq:tree-logZ}.  Equations~\eqref{eq:tree-energy} and
\eqref{eq:tree-entropy-count} give
\begin{align*}
 \log Q-k\log Z
 &=D(\nu\|\mu_k)+r\sum_{v\notin L}(d_v-2)H(\alpha_v)\\
 &\quad-r\sum_{\ell\in L}
       \bigl(H(\alpha_\ell)+2\E_{\alpha_\ell}\log u_\ell\bigr).
\end{align*}
For each leaf, the definition of $p_\ell$ gives
\[
 H(\alpha_\ell)+2\E_{\alpha_\ell}\log u_\ell
 =\log U_\ell-D(\alpha_\ell\|p_\ell).
\]
Substitution proves \eqref{eq:tree-deficit}.  Its right side is nonnegative,
since $d_v\geqslant2$ at every internal vertex, proving \eqref{eq:tree} for
positive data.  Adding $\varepsilon>0$ to every matrix and vector entry and
letting $\varepsilon\downarrow0$ proves \eqref{eq:tree} for nonnegative data.
\end{proof}

For the path with vertices $0,\ldots,t$, the matrix $C_i$ on edge $(i-1,i)$,
and leaf vectors $u,v$, inequality \eqref{eq:tree} is
\eqref{eq:path-rectangular}, and \eqref{eq:tree-deficit} is
\eqref{eq:deficit}, since every internal vertex has degree two.  For
strictly positive data and $k\geqslant3$, a vertex of degree at least three with
at least two states makes \eqref{eq:tree} strict, by its term in
\eqref{eq:tree-deficit}.

\end{document}