\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem*{remark}{Remark} \renewcommand{\proofname}{\normalfont\bfseries Proof} \numberwithin{equation}{section} \usepackage[letterpaper,margin=1in]{geometry} \usepackage{xcolor} \definecolor{linkblue}{RGB}{11,95,165} \usepackage[colorlinks=true,allcolors=black]{hyperref} \hypersetup{pdftitle={Vector Packing and Sharp Bounds for Matrices of Bounded Rank},pdfauthor={Yair Lavi}} \setlength{\emergencystretch}{3em} \title{Vector Packing and Sharp Bounds for Matrices of Bounded Rank} \author{Yair Lavi} \date{14 November 2026} \begin{document} \maketitle \begin{abstract} We prove a packing theorem in real and complex normed spaces. Given a possibly infinite family of vectors $(v_j)$ whose span has finite dimension $r\ge1$, let $M$ be the supremum of the norms of its finite linear combinations with coefficients of modulus at most one. If $M$ is finite, the family splits into $r$ nonempty sets, each with sum of norms at most $M$. The same partition works for every norm on the span, using that norm's value of $M$. We also determine exactly which finite lists of nonnegative numbers can be realized as the norms of a family of capacity one in some normed space of dimension at most $k$. We also obtain sharp rank-dependent bounds for products of the moduli of the entries on generalized diagonals and the permanent of the entrywise modulus, extending the known nonnegative-matrix bounds to real and complex matrices. The packing theorem also gives sharp support and entropy bounds for doubly stochastic matrices of bounded rank. \end{abstract} \noindent\textbf{Keywords.} Vector packing; matrix rank; majorization; stochastic matrix; permanent; entropy. \noindent\textbf{2020 Mathematics Subject Classification.} Primary 46B07; Secondary 15A15, 15A45, 15B51, 52A21. \section{Introduction and main theorem}\label{sec:introduction} \subsection{From a bound on the sum of norms to a partition}\label{sec:from-a-bound-on-the-sum-of-norms-to-a-partition} Let $\mathbb F\in\{\mathbb R,\mathbb C\}$, let $(v_j)_{j\in J}$ be a labeled family in a normed space over $\mathbb F$, and put $E=\operatorname{span}_{\mathbb F}\{v_j:j\in J\}.$ Repeated vectors may have different labels. A sum of nonnegative numbers over an arbitrary label set means the supremum of its finite subsums. All logarithms in this paper are natural. Define the \emph{coefficient-sum capacity} by \begin{equation}\label{eq:capacity} M=M((v_j),\|\cdot\|):= \sup_{\substack{H\subseteq J\text{ finite}\\|\alpha_j|\le1}} \left\|\sum_{j\in H}\alpha_jv_j\right\|. \end{equation} This is the supremum of the norms obtainable by choosing signs or complex phases for finitely many vectors. Indeed, on each finite set $H$, convexity in each coefficient permits restriction to $\alpha_j\in\{-1,1\}$ over $\mathbb R$, or to $|\alpha_j|=1$ over $\mathbb C$. If $E^*$ denotes the space of continuous linear functionals on $E$, with $\|\varphi\|=\sup_{\|v\|\le1}|\varphi(v)|$, duality gives \begin{equation}\label{eq:dual-capacity} M=\sup_{\substack{\varphi\in E^*\\\|\varphi\|\le1}} \sum_{j\in J}|\varphi(v_j)|. \end{equation} To see this, express the norm in \eqref{eq:capacity} as a supremum over $\varphi$, interchange the suprema, and align the signs or phases of the scalars $\varphi(v_j)$. The quantity $M$ is the weak $\ell_1$ norm of the family; we refer to it here as its capacity. For finite families, \eqref{eq:dual-capacity} is the quantity $\mu_1$ of \cite[Section~2]{ref6}. The equality of \eqref{eq:capacity} and \eqref{eq:dual-capacity}, and the restriction to signs or unit phases, are recorded in \cite[2.2]{ref6}. For nonnegative numbers $x_j$, the \emph{load} of a set $F$ is $\sum_{j\in F}x_j$. A packing with load bound $M$ is a partition of the labels into nonempty sets, each of load at most $M$. For a vector family, the load of a set $F$ is $\sum_{j\in F}\|v_j\|$. For a finite family with $M>0$, its \emph{normalized norm profile} is $(\|v_j\|/M)_{j=1}^n$. When $\dim E=r$, the classical dimension bound is $\sum_j\|v_j\|\le rM$; its relation to absolutely summing norms is recalled in Section~\ref{sec:dimension-bounds-signed-sums-and-coordinate-variations}. A bound on the total does not by itself say how the vectors can be partitioned. For example, three numbers equal to $3/5$ have total $9/5<2$, but cannot be placed in two sets of load at most one: every pair has load $6/5$. The result below shows that a family of vectors with capacity one whose span has dimension two cannot have this profile of norms. Our main theorem is the following. \subsection{One partition for every norm}\label{sec:one-partition-for-every-norm} \begin{theorem}[vector packing]\label{thm:packing} Let $(v_j)_{j\in J}$ be a family in a normed space over $\mathbb F\in\{\mathbb R,\mathbb C\}$, and put $E=\operatorname{span}_{\mathbb F}\{v_j:j\in J\}$. Suppose $1\le r=\dim_{\mathbb F}E<\infty$ and the capacity $M$ defined in \eqref{eq:capacity} is finite. Then $J$ has a partition into exactly $r$ nonempty sets $F_1,\ldots,F_r$ such that \begin{equation}\label{eq:packing} \sum_{j\in F_a}\|v_j\|\le M\qquad(1\le a\le r). \end{equation} Only countably many $v_j$ are nonzero, and their norms are summable. The partition can be chosen independently of the norm on $E$: \eqref{eq:packing} holds for every norm on $E$, with its own capacity \eqref{eq:capacity}. \end{theorem} For example, the columns of a nonzero matrix admit one partition for both $\|x\|_\infty=\max_i|x_i|$ and $\|x\|_1=\sum_i|x_i|$, computing the capacity separately for each norm. The bound concerns the sum of the individual norms in each set, rather than the norm of their sum. \subsection{Sharpness}\label{sec:sharpness} Both the number of sets and the load bound $M$ are sharp. Let $e_1,\ldots,e_r$ be the standard coordinate vectors in $\mathbb F^r$, with $e_a$ equal to one in coordinate $a$ and zero elsewhere. In the supremum norm, this family has capacity one, and each vector has norm one. No two can share a set of load at most one. The zero-span case has zero load; we exclude it from \mbox{Theorem~\ref{thm:packing}} because zero nonempty sets cannot partition a nonempty label set. \subsection{Consequences}\label{sec:consequences} The packing theorem has consequences for vector norms, matrix inequalities, and information bounds. A \emph{row-stochastic} matrix has nonnegative entries and every row sum equal to one. A \emph{column-stochastic} matrix is defined by the corresponding column condition; a matrix is \emph{doubly stochastic} if both conditions hold. \begin{itemize} \item \textbf{Small norms and signed sums.} It bounds the smallest norm in a finite family, gives large signed sums or sums with unit phases (\mbox{Corollary~\ref{cor:signed-sums}}), and refines the classical bound on coordinate variations (Section~\ref{sec:dimension-bounds-signed-sums-and-coordinate-variations}). \item \textbf{Rank and eigenvalue location.} Column maxima and relative diagonals give packing bounds on rank (\mbox{Corollary~\ref{cor:column-packing}} and \mbox{Theorem~\ref{thm:packing-rank}}), recover classical nonsingularity criteria, and locate eigenvalues according to their geometric multiplicity (\mbox{Corollary~\ref{cor:eigenvalue-localization}}). \item \textbf{Attainable profiles and norm inequalities.} It characterizes the normalized norm profiles attainable as the family and space vary, and the possible stochastic column maxima (\mbox{Theorem~\ref{thm:profiles}}). It also gives sharp majorization, symmetric-function, and weighted-product bounds (\mbox{Theorem~\ref{thm:majorization}}, \mbox{Corollary~\ref{cor:symmetric-functions}}, and \mbox{Theorem~\ref{thm:weighted-products}}). \item \textbf{Diagonal products and permanents.} It recovers the known sharp stochastic bounds, extends them to real and complex matrices (\mbox{Corollary~\ref{cor:diagonal-products}} and \mbox{Theorem~\ref{thm:permanent}}), and controls powers and partial sums of absolute diagonal products (\mbox{Corollary~\ref{cor:diagonal-majorization}}). \item \textbf{Prescribed diagonals.} It determines the minimum absolute entrywise mass for prescribed diagonal magnitudes (\mbox{Theorem~\ref{thm:minimum-mass}}) and characterizes the attainable diagonals of row-stochastic matrices under a rank bound (\mbox{Theorem~\ref{thm:stochastic-diagonals}}). \item \textbf{Doubly stochastic matrices.} It gives sharp bounds on entropy, support size, and entrywise power sums in the stated exponent ranges (\mbox{Theorem~\ref{thm:stochastic-bounds}}). \item \textbf{Mutual information.} It gives bounds depending on rank and the marginals, with sharpness when one marginal is prescribed and the other may vary (\mbox{Theorem~\ref{thm:information}}). \end{itemize} \subsection{Relation to earlier work}\label{sec:relation-to-earlier-work} In 2018, the author conjectured sharp rank-dependent maxima for diagonal products and permanents of stochastic matrices \cite{ref8}. The sharp maxima and equality cases were established in \cite{ref9} for diagonal products and in \cite{ref10} for the permanent. Here we derive these maxima from vector packing and extend the inequalities to real and complex matrices, with rank imposed on the original matrix. The equality classifications remain separate results; we do not classify complex equality cases. \mbox{Theorem~\ref{thm:packing}} refines the classical dimension estimate recalled in Section~\ref{sec:from-a-bound-on-the-sum-of-norms-to-a-partition} \cite[p.~33, item~(4)]{ref6}, \cite[(5)]{ref7} by controlling the whole family through a partition. For $n$ vectors in a real normed space, the small-norm bound in \mbox{Corollary~\ref{cor:signed-sums}} is equivalent to the signed-sum theorem of Ambrus and Grundbacher \cite[Theorems~2 and 7]{ref1}. This consequence already supplies the small-column step in the real-matrix proof of the permanent bound. The full partition theorem holds over both fields, includes infinite families of finite capacity, and chooses one partition valid for every norm. \subsection{Organization}\label{sec:organization} Section~\ref{sec:proof} proves \mbox{Theorem~\ref{thm:packing}}. Sections 3 and 4 develop the partition consequences and the majorization bounds; Sections 5 and 6 apply them to matrix inequalities and stochastic matrices. Further comparisons with earlier inequalities are made at their point of use. \section{Proof of \mbox{Theorem~\ref*{thm:packing}}}\label{sec:proof} The proof first constructs a partition and numerical weights using only linear algebra. For a finite family, we choose a partition and scalars of modulus one to maximize the absolute determinant of the resulting $r$ set sums. Changing one phase forces the assigned coordinate weight to be nonnegative; moving one vector to another set forces that weight to dominate its other coordinates. The weights sum to one in each set. A recovery identity then converts these coordinate bounds into norm bounds, for every norm at once. Absolute summability and compactness extend the construction to infinite families. \subsection{A partition maximizing the determinant}\label{sec:a-partition-maximizing-the-determinant} Start with a finite family $v_1,\ldots,v_n$ of nonzero vectors whose span has dimension $r$. Fix linear coordinates on $E$. For an assignment of the labels to $r$ indexed sets $F_1,\ldots,F_r$ (possibly empty) and a choice of scalars $\theta_j\in\mathbb F$ with $|\theta_j|=1$, put \begin{equation}\label{eq:set-sums} z_a=\sum_{j\in F_a}\theta_jv_j, \qquad D=\det[z_1\ \cdots\ z_r]. \end{equation} Over the reals, $|D|$ is the volume of the parallelepiped spanned by the set sums in the chosen coordinates. We seek an assignment whose volume cannot be increased by either of the two local changes described below. Over the complexes, the same determinant objective supplies the needed algebraic comparisons. There is an assignment with $D\ne0$. Choose linearly independent vectors $u_1,\ldots,u_r$ from the family, let $w$ be the sum of the remaining vectors, and define \[ D_0=\det[u_1\ u_2\ \cdots\ u_r], \qquad D_1=\det[w\ u_2\ \cdots\ u_r]. \] Assign $u_a$ to $F_a$ with phase one, and all remaining vectors to $F_1$ with a common sign $\varepsilon\in\{-1,1\}$. The resulting determinant is $D_0+\varepsilon D_1$. Since $D_0\ne0$, at least one of these two choices is nonzero. Allowing empty sets during the optimization, the assignments and unit phases form a compact space. Thus $|D|$ has a positive maximum. Fix a maximizing configuration. Its set sums form a basis, so its sets are in fact nonempty. Write $h_a:E\to\mathbb F$ for the coordinate functionals in this basis: $v=\sum_{a=1}^r h_a(v)z_a$. \subsection{Two local changes: changing a phase and moving a vector}\label{sec:two-local-changes-changing-a-phase-and-moving-a-vector} \begin{lemma}[coordinate weights]\label{lem:coordinate-weights} For the maximizing configuration chosen above, $D\ne0$, and its basis coordinates satisfy \begin{equation}\label{eq:coordinate-weights} d_j:=\theta_jh_a(v_j) =\max_{1\le b\le r}|h_b(v_j)|\in[0,1] \quad(j\in F_a), \qquad \sum_{j\in F_a}d_j=1. \end{equation} \end{lemma} \begin{proof} By Cramer's rule, \[ \det[z_1\ \cdots\ z_{a-1}\ v\ z_{a+1}\ \cdots\ z_r] =h_a(v)D\qquad(v\in E,\ 1\le a\le r). \] Fix $j\in F_a$ and write $d=\theta_jh_a(v_j).$ First change only its phase, from $\theta_j$ to $u\theta_j$ with $|u|=1$. Column $a$ in \eqref{eq:set-sums} becomes $z_a+(u-1)\theta_jv_j$. By multilinearity, the changed determinant $D'$ satisfies \begin{equation}\label{eq:phase-variation} \frac{D'}D=1+(u-1)\theta_jh_a(v_j)=1-d+ud. \end{equation} Over $\mathbb R$, the sign flip $u=-1$ and maximality give $|1-2d|\le1$, hence $d\in[0,1]$. Over $\mathbb C$, the largest modulus of \eqref{eq:phase-variation} over the unit circle is $|1-d|+|d|$, so this sum is at most one. Its reverse inequality follows from $(1-d)+d=1$. Equality in the triangle inequality forces $d$ to be real and in $[0,1]$, including the endpoints. Next move $j$ from $F_a$ to $F_b$, $b\ne a$, with a new unit phase $\eta$. Columns $a,b$ become $z_a-\theta_jv_j$ and $z_b+\eta v_j$. Expanding both columns, the term containing $v_j$ twice vanishes. The remaining terms give \begin{equation}\label{eq:move-variation} \frac{D'}D=1-\theta_jh_a(v_j)+\eta h_b(v_j) =1-d+\eta h_b(v_j). \end{equation} The move is allowed even if it empties $F_a$: the resulting determinant is zero, as \eqref{eq:move-variation} also predicts. This covers singleton sets. Since $1-d\ge0$, choose $\eta$ so that $\eta h_b(v_j)=|h_b(v_j)|$. Maximality gives $1-d+|h_b(v_j)|\le1$. Thus $|h_b(v_j)|\le d$ for $b\ne a$, while $|h_a(v_j)|=d$. Finally, $\sum_{j\in F_a}d_j=h_a(z_a)=1$. \end{proof} \begin{remark} A global maximum is sufficient but not necessary. A configuration with $D\ne0$ has the same coordinate properties if $|D|$ cannot be increased by changing one phase or moving one label with any new unit phase. The hypothesis $D\ne0$ is essential to this assertion. \end{remark} \subsection{From coordinate weights to bounds for every norm}\label{sec:from-coordinate-weights-to-bounds-for-every-norm} The purpose of the weights is to express each vector as a coefficient sum of the whole family, with all coefficients controlled by one number. \begin{lemma}[finite packing]\label{lem:finite-packing} For a finite family satisfying the hypotheses of \mbox{Theorem~\ref{thm:packing}}, one partition satisfies \eqref{eq:packing} for every norm on $E$, using that norm's own capacity. \end{lemma} \begin{proof} Remove the zero vectors, which does not change the capacity, and apply the preceding construction to the label set $J_+$ of the nonzero vectors. For $\ell\in J_+$, let $a(\ell)$ be its assigned set index. Expansion in the basis $z_b$ and substitution of the set sums give the recovery identity \begin{equation}\label{eq:recovery} v_j=\sum_bh_b(v_j)z_b =\sum_{\ell\in J_+}\theta_\ell h_{a(\ell)}(v_j)v_\ell. \end{equation} Every coefficient in the last sum has modulus at most $d_j$. Since $v_j\ne0$, \eqref{eq:coordinate-weights} gives $d_j>0$. Divide \eqref{eq:recovery} by $d_j$; the coefficients now have modulus at most one. Definition \eqref{eq:capacity} gives $\|v_j\|\le Md_j$. Summing over $F_a$ and using $\sum_{j\in F_a}d_j=1$ proves \eqref{eq:packing}. The assignment, phases, and weights depend only on the vectors and the fixed coordinates. The same identity therefore proves the inequality for every norm on $E$. Assign the zero labels to any of the $r$ nonempty sets, with weight zero. \end{proof} The recovery identity also gives a useful statement involving no norm: for every $\varphi\in E^*$, \begin{equation}\label{eq:functional-domination} |\varphi(v_j)|\le d_j\sum_\ell|\varphi(v_\ell)|. \end{equation} This follows by applying $\varphi$ to \eqref{eq:recovery} and using the triangle inequality. It explains why the weights can serve all norms at once. \begin{remark}[Lewis's variational method] In the real case this determinant maximization is an instance of Lewis's variational method \cite{ref11}; see also Pisier \cite[\mbox{Theorem~3.1}]{ref16} for the formulation using an arbitrary norm. For any norm $\alpha$ on the real $r\times r$ matrices, a maximizer $Z$ of $|\det U|$ over $\alpha(U)\le1$ is invertible and satisfies $\alpha(Z)=1$ and \[ |\operatorname{tr}(Z^{-1}U)|\le r\alpha(U) \qquad\text{for every }U, \] with equality at $U=Z$. This follows by differentiating the determinant along line segments in the unit ball, then using symmetry and homogeneity. For our family, let $V=[v_1\ \cdots\ v_n]$ in the fixed coordinates and give $r\times r$ matrices $U$ the quotient norm $\alpha(U)=\min_{VX=U}\max_j\|\operatorname{row}_jX\|_1$, where $X$ is $n\times r$. The determinant of $VX$ is affine in each row of $X$: terms involving that row twice have two proportional columns and vanish. A maximum of its absolute value on $\max_j\|\operatorname{row}_jX\|_1\le1$ therefore occurs with every row a signed coordinate vector. Those rows give precisely the signed partitions in \eqref{eq:set-sums}. The direct proof above also covers complex phases. \end{remark} \subsection{Infinite families}\label{sec:infinite-families} To repeat the determinant argument, we first need the set sums to converge uniformly over all assignments and phases. Finite dimension supplies this through absolute summability. \begin{lemma}[absolute summability]\label{lem:summability} Under the hypotheses of \mbox{Theorem~\ref{thm:packing}}, only countably many $v_j$ are nonzero and $\sum_j\|v_j\|<\infty$. \end{lemma} \begin{proof} Choose a basis $u_1,\ldots,u_r$ of $E$ and its coordinate functionals $g_1,\ldots,g_r$. These are continuous in finite dimension. For each $b$ and finite $H\subseteq J$, choose coefficients in \eqref{eq:capacity} aligning the scalars $g_b(v_j)$. It follows that \begin{equation}\label{eq:summability} \sum_{j\in H}|g_b(v_j)|\le M\|g_b\|, \qquad \sum_{j\in J}\|v_j\| \le M\sum_{b=1}^r\|u_b\|\|g_b\|<\infty. \end{equation} The second inequality uses $v_j=\sum_b g_b(v_j)u_b$ and the triangle inequality, then takes finite subsums. For each positive integer $N$, only finitely many vectors have norm at least $1/N$. The union of these finite sets contains every nonzero label. \end{proof} \begin{proof}[\normalfont\bfseries Proof of \mbox{Theorem~\ref*{thm:packing}}] \mbox{Lemma~\ref{lem:finite-packing}} proves the finite case. In general, $J_+=\{j:v_j\ne0\}$ is countable by \mbox{Lemma~\ref{lem:summability}}. Define $z_a,D$ by \eqref{eq:set-sums} for every assignment of $J_+$ to $r$ indexed sets and every choice of unit phases. The sums converge absolutely. After enumerating $J_+$, their tails are bounded uniformly over all assignments and phases by the tail of $\sum_j\|v_j\|$. Thus the set sums, and hence the determinant, are continuous on the compact product of the finite assignment spaces and the phase circles (sign choices over $\mathbb R$). The construction in Section~\ref{sec:a-partition-maximizing-the-determinant} applies with $w$ equal to the absolutely convergent sum of the remaining vectors. It again gives $D_0\pm D_1$ with $D_0\ne0$. Consequently $|D|$ has a positive maximum. At a maximizer, the one-label phase and move arguments give \eqref{eq:coordinate-weights}, including $\sum_{j\in F_a}d_j=1$; continuity of $h_a$ justifies applying it to the convergent set sum. The recovery identity \eqref{eq:recovery} converges absolutely. For fixed $j$, every finite partial sum on its right has norm at most $Md_j$ by \eqref{eq:capacity}. Passing to the limit yields $\|v_j\|\le Md_j$, and summing over each $F_a$ proves \eqref{eq:packing}. Zero labels can again be assigned arbitrarily with weight zero. The sets remain nonempty because $D\ne0$. For any other norm $\|\cdot\|'$ on $E,$ norm equivalence gives $\|x\|'\le C\|x\|$ for all $x\in E$ and some finite constant $C$. Its capacity satisfies $M'\le CM<\infty$, and the same sums converge in that norm. The partition and weights therefore give \eqref{eq:packing} with each norm's own capacity. Equation \eqref{eq:functional-domination} also extends by absolute convergence. \end{proof} \section{Classical inequalities and their partition refinements}\label{sec:classical-inequalities} \subsection{Dimension bounds, signed sums, and coordinate variations}\label{sec:dimension-bounds-signed-sums-and-coordinate-variations} Summing \eqref{eq:packing} gives $\sum_j\|v_j\|\le rM$. For a finite-dimensional normed space $E$, define \begin{equation}\label{eq:summing-norm} \pi_1(\mathrm{id}_E)= \sup_{\substack{\text{finite families }(v_j)\subset E\\M((v_j))>0}} \frac{\sum_j\|v_j\|}{M((v_j))}. \end{equation} This is the absolutely summing norm of the identity. Since the span of each family in \eqref{eq:summing-norm} has dimension at most $\dim E$, the preceding bound yields $\pi_1(\mathrm{id}_E)\le\dim E$. This estimate is classical: Kadets--Snobar \cite[(5)]{ref7} give an equivalent formulation over the reals, and Jameson \cite[p.~33, item~(4)]{ref6} gives the estimate over both fields. \mbox{Theorem~\ref{thm:packing}} adds a partition controlling the individual loads. \begin{corollary}[small norms and large signed sums]\label{cor:signed-sums} Let $v_1,\ldots,v_n$ be vectors in a normed space over $\mathbb F$, whose span has dimension $r\ge1$, and let $M$ be their capacity. Then \[ \min_{1\le j\le n}\|v_j\|\le\frac{M}{\lceil n/r\rceil}. \] In particular, for $n$ unit vectors, some signed sum of all $n$ vectors has norm at least $\lceil n/r\rceil$ over $\mathbb R$; over $\mathbb C$, the same conclusion holds with unit phases in place of signs. \end{corollary} \begin{proof} By \mbox{Theorem~\ref{thm:packing}}, one packing set contains at least $\lceil n/r\rceil$ labels and has load at most $M$. Its smallest norm is therefore at most $M/\lceil n/r\rceil$. For unit vectors this gives $M\ge\lceil n/r\rceil$, and the capacity of a finite family is attained by signs or unit phases. \end{proof} The real bound is the sharp bound of Ambrus and Grundbacher \cite[\mbox{Theorem~2}]{ref1}, applied to the unit ball in the real span of the vectors. Repeating each coordinate vector as evenly as possible in the supremum norm shows sharpness over both fields. For $n$ vectors in a real normed space, the small-norm bound in \mbox{Corollary~\ref{cor:signed-sums}} also follows by scaling from \cite[\mbox{Theorem~7}]{ref1}, applied in their span with the dual unit ball of the restricted norm. For a nonzero finite-dimensional subspace $L\subseteq\ell_1(J)$, where $\ell_1(J)$ consists of scalar families with finite sum of absolute values, define its \emph{coordinate variations} by \begin{equation}\label{eq:coordinate-variations} \kappa_j(L)=\sup_{\substack{x\in L\\x\ne0}} \frac{|x_j|}{\sum_\ell|x_\ell|}. \end{equation} For $L\subseteq\mathbb R^n$ or $L\subseteq\mathbb C^n$, Hoffman \cite[(1.1), (1.2), (4.1)]{ref5} obtained the sharp bound $\sum_j\kappa_j(L)\le\dim L$ from the Fan--Hoffman rank inequality. \mbox{Theorem~\ref{thm:packing}} refines this bound by partitioning the coordinate labels into $\dim L$ sets, each satisfying $\sum_{j\in F_a}\kappa_j(L)\le1$. This refinement holds over both fields and for arbitrary $J$. Indeed, regard the coordinate functionals $v_j(x)=x_j$ as vectors in the dual of $(L,\|\cdot\|_1)$. They span $L^*$, since their common annihilator in $L$ is zero. Their norms are $\kappa_j(L)$, and their capacity is one by phase alignment and the identity $\|x\|_1=\sum_j|x_j|$. \mbox{Theorem~\ref{thm:packing}} therefore partitions the coordinate labels into $\dim L$ nonempty sets, each satisfying \[ \sum_{j\in F_a}\kappa_j(L)\le1. \] \subsection{Absolute column maxima and rank from relative diagonals}\label{sec:absolute-column-maxima-and-rank-from-relative-diagonals} For a nonzero $m\times n$ matrix $A$ over $\mathbb F$, define its \emph{absolute column maxima} $p_j(A)$ and its largest absolute row sum $R(A)$ by \begin{equation}\label{eq:column-maxima} p_j(A)=\max_i|a_{ij}|, \qquad R(A)=\max_i\sum_j|a_{ij}|. \end{equation} Its columns $Ae_j$, in the supremum norm on $\mathbb F^m$, have norms $p_j(A)$, and their span has dimension $\operatorname{rank}_{\mathbb F}A$. Their capacity is $R(A)$: the triangle inequality gives the upper bound, and aligning the entries of a row attaining $R(A)$ gives equality. \begin{corollary}[absolute column maxima]\label{cor:column-packing} If $r=\operatorname{rank}A>0$, the column labels partition into $r$ nonempty sets with \begin{equation}\label{eq:column-packing} \sum_{j\in F_a}p_j(A)\le R(A)\qquad(1\le a\le r). \end{equation} Here $r$ is the rank of $A$ itself, even when the entrywise modulus matrix $|A|=(|a_{ij}|)$ has greater rank. \end{corollary} \begin{proof} Apply \mbox{Theorem~\ref{thm:packing}} to the columns of $A$ in the supremum norm. \end{proof} To state a rank consequence, define the \emph{packing number} $P(x)$ of $x\in[0,1]^n$ as the least number of sets into which its positive coordinates can be partitioned, each set having sum at most one. Set $P(0)=0$. Equivalently, $P(x)$ is the minimum number of bins of capacity one needed to pack items whose sizes are the positive coordinates of $x$, as in the classical bin packing problem. Zero coordinates can be adjoined to any existing set; for $k\ge1$, $P(x)\le k$ is equivalent to a partition of all $n$ labels into at most $k$ nonempty sets of load at most one. The convention at zero lets us include zero matrices in the following statement. For an $n\times n$ matrix $A=(a_{ij})$, a \emph{generalized diagonal} consists of the positions $(i,\sigma(i))$, where $\sigma$ is a permutation of $[n]=\{1,\ldots,n\}$. Its product is $\prod_i a_{i,\sigma(i)}$. Write $S_n$ for the set of all permutations of $[n]$. For a square matrix, write $\rho_i=\sum_j|a_{ij}|$ and $\gamma_j=\sum_i|a_{ij}|$ for its absolute row and column sums. For a permutation $\sigma$, define the two \emph{relative diagonals} by \begin{equation}\label{eq:relative-diagonals} t_i=\frac{|a_{i,\sigma(i)}|}{\rho_i}, \qquad t'_i=\frac{|a_{i,\sigma(i)}|}{\gamma_{\sigma(i)}}, \end{equation} with either ratio defined to be zero when its denominator is zero. \begin{theorem}[packing rank bound]\label{thm:packing-rank} For every real or complex $n\times n$ matrix $A$ and every permutation $\sigma$ of $\{1,\ldots,n\}$, the relative diagonals $t,t'$ defined in \eqref{eq:relative-diagonals} satisfy \begin{equation}\label{eq:packing-rank} \operatorname{rank}A\ge\max\{P(t),P(t')\}. \end{equation} \end{theorem} \begin{proof} The zero matrix is immediate. Otherwise divide each nonzero row by its positive absolute sum, leaving zero rows unchanged. This is invertible diagonal row scaling, so rank is preserved, and the resulting matrix has $R=1$. Its absolute column maxima dominate $t$, after relabeling column $\sigma(i)$ by $i$. \mbox{Corollary~\ref{cor:column-packing}} packs these maxima, hence also the relative diagonal, into $\operatorname{rank}A$ sets. Apply the same reasoning to the transpose, with permutation $\sigma^{-1}$, for $t'$. \end{proof} \subsection{Fan--Hoffman, L\'{e}vy--Desplanques, and Ostrowski}\label{sec:fan-hoffman-l-vy-desplanques-and-ostrowski} Since a partition into $r$ sets of load at most one has total load at most $r$, \eqref{eq:packing-rank} contains the Fan--Hoffman inequality \cite[\mbox{Theorem~1.3}]{ref4} \begin{equation}\label{eq:fan-hoffman} \operatorname{rank}A\ge \sum_{i:\rho_i>0}\frac{|a_{ii}|}{\rho_i}. \end{equation} The bound $\sum_jp_j(A)\le rR(A)$ on the sum of absolute column maxima follows already from this classical inequality. Choose a row attaining each absolute column maximum, and form an $n\times n$ matrix $B$ whose $j$th row is the row chosen for column $j$, allowing repetitions. Then $|b_{jj}|=p_j(A)$, $\operatorname{rank}B\le r$, and its absolute row sums $s_j\le R(A)$. Fan--Hoffman gives $\sum_{s_j>0}p_j(A)/s_j\le r$; a zero $s_j$ has $p_j(A)=0$. This proves the bound on the sum of absolute column maxima. Its stochastic form also appears, after transposition, in Riazanov and Vyalyi \cite[\mbox{Theorem~4.3}]{ref17}. For nonsingularity, assume $n\ge2$ and write $R_i=\sum_{j\ne i}|a_{ij}|$ for the off-diagonal row sum. If $|a_{ii}|>R_i$ for every $i$, then every relative diagonal entry is greater than $1/2$. No two can share a set of load at most one, so \eqref{eq:packing-rank} gives rank $n$. This is the L\'{e}vy--Desplanques strict diagonal-dominance criterion. Ostrowski's pairwise criterion \cite[Zusatz zu Satz~VI, p.~77]{ref14}, \cite[Satz~II with $\alpha=1$]{ref15} is recovered in the same way. When $\rho_i,\rho_j>0$, direct cross-multiplication gives \begin{equation}\label{eq:pairwise-criterion} t_i+t_j\le1 \quad\Longleftrightarrow\quad |a_{ii}|\,|a_{jj}|\le R_iR_j. \end{equation} Thus $|a_{ii}|\,|a_{jj}|>R_iR_j$ for every $i\ne j$ rules out every shared set and forces nonsingularity. The strict hypothesis itself rules out zero rows. For a row-stochastic matrix, $R_i=1-a_{ii}$, so Ostrowski's condition is precisely $a_{ii}+a_{jj}>1$ for all pairs. Every singular row-stochastic matrix therefore has two diagonal entries whose sum is at most one. Ostrowski's criterion implies that among any $r+1$ columns of a rank-$r$ row-stochastic matrix, two column maxima have sum at most one. Choose a row attaining the maximum for each. If two chosen rows coincide, the two maxima sum to at most one. Otherwise their square submatrix is singular. Its off-diagonal row sums are at most $1-p_j$, so the contrapositive of Ostrowski's criterion gives $p_i p_j\le(1-p_i)(1-p_j)$, hence $p_i+p_j\le1$, for some pair. \mbox{Corollary~\ref{cor:column-packing}} retains more information: it gives one partition of all column labels, with a load bound for every set. Write $c^{[m]}$ for $m$ repetitions of $c$. For an example of the additional information in the partition, take five relative diagonal entries all equal to $2/5$. Their sum is two, and every pair has sum at most one. A set can nevertheless hold at most two of them, so $P((2/5)^{[5]})=3$ and \eqref{eq:packing-rank} forces rank at least three. This bound is attained by the row-stochastic matrix \begin{equation}\label{eq:rank-three-example} \begin{pmatrix} 2/5&2/5&1/5&0&0\\ 2/5&2/5&1/5&0&0\\ 1/5&0&2/5&2/5&0\\ 1/5&0&2/5&2/5&0\\ 3/5&0&0&0&2/5 \end{pmatrix}. \end{equation} It has only three distinct rows, so its rank is at most three; the relative-diagonal packing bound gives the reverse inequality. \subsection{Eigenvalue location and geometric multiplicity}\label{sec:eigenvalue-location-and-geometric-multiplicity} For a complex $n\times n$ matrix $A=(a_{ij})$ and $z\in\mathbb C$, set \begin{equation}\label{eq:spectral-ratios} t_i(z)=\frac{|a_{ii}-z|}{|a_{ii}-z|+R_i}, \end{equation} with value zero when the denominator vanishes. The \emph{geometric multiplicity} of an eigenvalue $\lambda$ is $\mu=\dim\ker(A-\lambda I)$, where $I$ is the identity matrix. \begin{corollary}[eigenvalue localization]\label{cor:eigenvalue-localization} Let $A=(a_{ij})\in\mathbb C^{n\times n}$, and let $\lambda$ be an eigenvalue of $A$ with geometric multiplicity $\mu=\dim\ker(A-\lambda I)$. With $t(\lambda)$ defined by \eqref{eq:spectral-ratios}, we have \begin{equation}\label{eq:multiplicity-packing} P(t(\lambda))\le n-\mu. \end{equation} The same conclusion holds with off-diagonal column sums in place of $R_i$. If $\mu0$ whose span has dimension at most $k$ in some normed space over $\mathbb F$. \item $x$ is the vector of column maxima of an $n\times n$ row-stochastic matrix of rank at most $k$. \item $\sum_jx_j\ge1$ and $P(x)\le k$. \end{enumerate} The stochastic realization can be chosen of rank exactly $P(x)$. A vector realization exists in $\mathbb F^k$ with the supremum norm. \end{theorem} \begin{proof} For 1 implies 3, \mbox{Theorem~\ref{thm:packing}} gives $P(x)\le k$, while the triangle inequality gives $M\le\sum_j\|v_j\|$. For 2 implies 1, use the matrix columns in the supremum norm; their capacity is one. For 3 implies 2, take a packing into $r=P(x)$ nonempty sets $F_1,\ldots,F_r$, assigning zero labels to these sets as necessary. Here $r\ge1$ because $\sum_jx_j\ge1$. For each $a$, construct a probability row $w^{(a)}$ by setting $w^{(a)}_j=x_j$ on $F_a$ and distributing its remaining mass outside $F_a$, with $0\le w^{(a)}_j\le x_j$. This is possible because \begin{equation}\label{eq:outside-mass} \sum_{j\notin F_a}x_j\ge1-\sum_{j\in F_a}x_j. \end{equation} For completeness, the deficit can be assigned to the outside coordinates one at a time up to their upper bounds $x_j$; \eqref{eq:outside-mass} ensures that it is exhausted. Set row $i$ of $A$ equal to $w^{(a)}$ whenever $i\in F_a$. There are at most $r$ distinct rows, so $\operatorname{rank}A\le r$. Every entry in column $j$ is at most $x_j$, and the rows of its own set attain $x_j$. Thus the column maxima are exactly $x$. \mbox{Corollary~\ref{cor:column-packing}} gives the reverse rank bound $\operatorname{rank}A\ge P(x)=r$. Retaining one representative row per set realizes the same column norms and capacity in $\mathbb F^r$; append zero coordinates to embed in $\mathbb F^k$. \end{proof} \subsection{The balanced reciprocal profile}\label{sec:the-balanced-reciprocal-profile} Write $n=qk+s$, where $q\ge1$ and $0\le s0$. Apply the dual bound and let $\varepsilon\downarrow0$ to get $\sum_j1/x_j\ge N_{n,k}$ for positive $x$. If a coordinate is zero, the asserted harmonic-mean inequality holds by its stated convention. \end{proof} The product constant also has a direct explanation. Starting with the partition from \mbox{Theorem~\ref{thm:packing}}, split sets until there are exactly $k$ nonempty sets. This is possible because $k\le n$, and splitting preserves the load bound $M$. Within a set of size $n_a$, the arithmetic--geometric mean inequality gives a product at most $(M/n_a)^{n_a}$. Thus the total product is bounded by $M^n\prod_a n_a^{-n_a}$. Strict convexity of $t\log t$ shows that $\sum_a n_a\log n_a$ is minimized at balanced positive integer sizes: transferring one unit from $c$ to $a$ decreases it whenever $c\ge a+2$. This recovers $D_{n,k}$. For $n=3,k=2$, we have $b_{3,2}=(1,1/2,1/2)$, so \begin{equation}\label{eq:three-vector-example} \prod_jx_j\le\frac14<\left(\frac23\right)^3, \qquad e_2(x)\le\frac54<\frac43, \qquad \frac3{\sum_j1/x_j}\le\frac35. \end{equation} The sum bound $\sum_jx_j\le2$ alone gives only $8/27$ for the product and $4/3$ for $e_2$. More generally, when $k\nmid n$, the nonconstant balanced reciprocal profile strictly improves the Maclaurin bounds $\binom nm(k/n)^m$ based only on $\sum_jx_j\le k$, for $2\le m\le n$. \subsection{Weighted products and entropy of partitions}\label{sec:weighted-products-and-entropy-of-partitions} Equal weights lead to balanced cardinalities. For unequal weights, the sharp constant is instead a finite optimization over the masses of the partition sets. For a probability vector $w=(w_1,\ldots,w_n)$, define its \emph{Shannon entropy} by $H(w)=-\sum_jw_j\log w_j$, with $0\log0=0$. For strictly positive $w$ and $1\le k\le n$, put \begin{equation}\label{eq:partition-entropy} H_k^*(w)=\max_{\mathcal F}H(W_1,\ldots,W_k), \qquad W_a=\sum_{j\in F_a}w_j, \end{equation} where $\mathcal F=(F_1,\ldots,F_k)$ runs over partitions of $[n]$ into $k$ nonempty sets. Equivalently, if $X$ has distribution $w$, this is the maximum of $H(f(X))$ over deterministic functions $f$ taking exactly $k$ values on the support of $X$. This optimization was studied in \cite{ref3}. \begin{theorem}[weighted products]\label{thm:weighted-products} Let $n,k$ be integers with $1\le k\le n$, and let $v_1,\ldots,v_n$ be vectors in a real or complex normed space with $1\le\dim\operatorname{span}\{v_1,\ldots,v_n\}\le k$. Let $M$ be their coefficient-sum capacity, and let $w=(w_1,\ldots,w_n)$ satisfy $w_j>0$ and $\sum_jw_j=1$. Then \begin{equation}\label{eq:weighted-product} \prod_j\|v_j\|^{w_j} \le M\exp\big(H_k^*(w)-H(w)\big). \end{equation} The constant is attained among vector families of capacity $M$ whose span has dimension at most $k$. For every fixed permutation $\sigma$ of $[n]$, the exact maximum of $\prod_{i=1}^n a_{i,\sigma(i)}^{w_i}$ over row-stochastic $n\times n$ matrices $A$ with $\operatorname{rank}A\le k$ is $\exp\big(H_k^*(w)-H(w)\big)$. \end{theorem} \begin{proof} Put $x_j=\|v_j\|/M$. Apply \mbox{Theorem~\ref{thm:packing}} and split sets as necessary to obtain $k$ nonempty sets, each with load at most one. If some $x_j=0$, the product is zero. Otherwise, in a set $F_a$ of mass $W_a$, the weighted arithmetic--geometric mean inequality gives \begin{equation}\label{eq:weighted-am-gm} \sum_{j\in F_a}w_j\log\frac{x_j}{w_j/W_a} \le W_a\log\left(\sum_{j\in F_a}x_j\right)\le0. \end{equation} Summing yields $\sum_jw_j\log x_j\le H(W)-H(w)$, which proves \eqref{eq:weighted-product}, since $H(W)\le H_k^*(w)$. For an entropy-maximizing partition, take $v_j=M(w_j/W_a)e_a$ when $j\in F_a$ in the supremum norm. Each coordinate sum is $M$, so the capacity is exactly $M$, and equality holds. For a row-stochastic matrix $A$ of rank at most $k$, apply \eqref{eq:weighted-product} to the reordered columns $v_i=Ae_{\sigma(i)}$ in the supremum norm. Their capacity is one, their span has dimension at most $k$, and $a_{i,\sigma(i)}\le\|v_i\|_\infty$. Hence $\prod_{i=1}^{n}a_{i,\sigma(i)}^{w_i}\le\prod_{i=1}^{n}\|v_i\|_\infty^{w_i}\le\exp\!\bigl(H_k^*(w)-H(w)\bigr)$. For the matrix realization, give every row indexed by $F_a$ the probability row with entries $w_j/W_a$ on $F_a$ and zero elsewhere. The $k$ distinct rows have disjoint supports and are independent. The resulting matrix has rank $k$, and its diagonal entries attain equality in \eqref{eq:weighted-product}. A column permutation gives any prescribed generalized diagonal. \end{proof} For $w_j=1/n$, maximizing $H(W)$ is the same as minimizing $\sum_a n_a\log n_a$, so \eqref{eq:weighted-product} becomes the $n$th root of the product bound. With arbitrary weights, equal cardinalities need not be optimal. For $w=(3/5,1/10,1/10,1/10,1/10)$ and $k=2$, one set must have mass at least $3/5$. Entropy is maximized by putting the largest weight alone, giving masses $3/5,2/5$ and set sizes one and four. \section{Sharp matrix inequalities}\label{sec:matrix-inequalities} Throughout this section $A$ is a real or complex $n\times n$ matrix, $1\le k\le n$, and $\operatorname{rank}_{\mathbb F}A\le k$. The absolute row and column sums are $\rho_i$ and $\gamma_j$, as defined in Section~\ref{sec:absolute-column-maxima-and-rank-from-relative-diagonals}. The constants use $n=qk+s$, $0\le sk$ and set $h=\lceil n/k\rceil\ge2$. \mbox{Corollary~\ref{cor:signed-sums}}, applied to the columns in the supremum norm, gives a column $j_*$ whose absolute column maximum is at most $1/\lceil n/r\rceil\le1/h$, where $r=\operatorname{rank}A\le k$. Put $\beta_i=|a_{i,j_*}|$; every $\beta_i$ is at most $1/h$. Let $A_i$ be the submatrix obtained by deleting row $i$ and column $j_*$ from \emph{$A$ itself, not $|A|$}. The surviving row $\ell\ne i$ has absolute sum $1-\beta_\ell>0$. Dividing that row by $1-\beta_\ell$ gives a matrix $\widetilde A_i$ with absolute row sums one. Deletion cannot increase rank and invertible row scaling preserves rank, so $\operatorname{rank}\widetilde A_i\le k$. Since $n-1\ge k$, induction gives \begin{equation}\label{eq:minor-bound} \operatorname{per}|A_i| \le C_{n-1,k}\prod_{\ell\ne i}(1-\beta_\ell). \end{equation} No rank assumption has been applied to $|A_i|$. Expanding the nonnegative permanent $\operatorname{per}|A|$ along column $j_*$ and using \eqref{eq:minor-bound} yields \begin{equation}\label{eq:column-expansion} \operatorname{per}|A|\le C_{n-1,k}\Psi(\beta), \qquad \Psi(\beta)=\sum_i \beta_i\prod_{\ell\ne i}(1-\beta_\ell). \end{equation} The function $\Psi$ is affine in each coordinate separately. Replacing coordinates one at a time by endpoints without decreasing $\Psi$ shows that its maximum on $[0,1/h]^n$ occurs at a vertex. A vertex with $t\ge1$ nonzero coordinates has value $g_t=(t/h)(1-1/h)^{t-1}$; the all-zero vertex has value zero. For positive integers $t$, \begin{equation}\label{eq:vertex-ratio} \frac{g_{t+1}}{g_t}=\frac{t+1}{t}\frac{h-1}{h}. \end{equation} This ratio exceeds one for $th-1$. Since $2\le h\le n$, both maximizing values $t=h-1$ and $t=h$ are available. Hence \begin{equation}\label{eq:vertex-maximum} \Psi(\beta)\le g_{h-1}=g_h=(1-1/h)^{h-1}. \end{equation} Let $f(t)=t!/t^t$. The balanced composition of $n$ into $k$ positive integer parts has largest part $h$. Reducing one largest part by one gives the balanced composition of $n-1$. Therefore \begin{equation}\label{eq:constant-recurrence} \frac{C_{n,k}}{C_{n-1,k}} =\frac{f(h)}{f(h-1)} =\left(1-\frac1h\right)^{h-1}. \end{equation} Combining \eqref{eq:column-expansion}, \eqref{eq:vertex-maximum}, and \eqref{eq:constant-recurrence} gives \begin{equation}\label{eq:induction-step} \operatorname{per}|A| \le C_{n-1,k}(1-1/h)^{h-1}=C_{n,k}, \end{equation} which closes the induction. Undo the row scaling, then apply the same result to $A^{\mathsf T}$, whose permanent and rank are unchanged, to obtain both products in \eqref{eq:permanent-bound}. Each $J_t$ has rank one and permanent $t!/t^t$; their balanced direct sum has permanent $C_{n,k}$ and both products of row and column sums equal to one. \end{proof} This recovers the sharp stochastic permanent bound proved in \cite{ref10}, where its equality cases are classified. \mbox{Theorem~\ref{thm:permanent}} establishes the sharp bound for arbitrary real or complex matrices and does not classify their equality cases. Marcus and Minc \cite[\mbox{Corollary~3.2}]{ref12} proved $|\operatorname{per}A|^2\le\frac1n\sum_{i=1}^{n}\alpha_i^{2n}$, where $\alpha_1,\ldots,\alpha_n$ are the singular values of $A$. For doubly stochastic $A$, they obtained $\operatorname{per}A\le\sqrt{\operatorname{rank}A/n}$ \cite[\mbox{Corollary~3.3}]{ref12}. For rank at most $k$, the sharp bound in \eqref{eq:permanent-bound} is $C_{n,k}$. The improvement can be substantial: when $n=2k$ and $\operatorname{rank}A=k$, \eqref{eq:permanent-bound} gives $\operatorname{per}A\le2^{-k}$, compared with $1/\sqrt2$ from the Marcus--Minc rank bound. More generally, \eqref{eq:permanent-bound} bounds $\operatorname{per}|A|$ in terms of the absolute row and column sums, with the rank condition imposed on $A$. \subsection{Powers and sums of diagonal products}\label{sec:powers-and-sums-of-diagonal-products} The preceding two bounds jointly control the entire vector of absolute diagonal products. Write $D=D_{n,k}$, $C=C_{n,k}$, and \begin{equation}\label{eq:diagonal-vector-parameters} \begin{aligned} Q&=\min\left\{\prod_i\rho_i,\prod_j\gamma_j\right\}, \qquad z_\sigma=\prod_i|a_{i,\sigma(i)}|,\\ m_0&=C/D=(q!)^{k-s}((q+1)!)^s. \end{aligned} \end{equation} Thus $m_0$ is an integer. Set $z(A)=(z_\sigma)_{\sigma\in S_n}\in[0,\infty)^{n!}$. The vector $z(B_{n,k})$ has exactly $m_0$ nonzero coordinates, all equal to $D$: a permutation contributes if and only if it preserves every block. For $t\ge1$, let $|A|^{\circ t}$ denote the matrix obtained by taking the $t$th power of each entry of $|A|$. \begin{corollary}[majorization of absolute diagonal products]\label{cor:diagonal-majorization} Let $n,k$ be integers with $1\le k\le n$, and let $A$ be a real or complex $n\times n$ matrix with $\operatorname{rank}A\le k$. Then, for every coordinatewise nondecreasing Schur-convex function $\Phi$ on $[0,\infty)^{n!}$, \begin{equation}\label{eq:diagonal-vector-majorization} \Phi(z(A))\le\Phi\big(Qz(B_{n,k})\big). \end{equation} In particular, for $t\ge1$ and $1\le m\le n!$, \begin{equation}\label{eq:powers-and-partial-sums} \begin{aligned} \operatorname{per}(|A|^{\circ t}) &\le C D^{t-1}Q^t,\\ \sum_{j=1}^m z_j^\downarrow(A) &\le Q\min\{mD,C\}. \end{aligned} \end{equation} All bounds are attained by $A=B_{n,k}$, for which $Q=1$. \end{corollary} \begin{proof} If $Q=0$, all diagonal products vanish. Otherwise normalize $y=z(A)/Q$. \mbox{Corollary~\ref{cor:diagonal-products}} and \mbox{Theorem~\ref{thm:permanent}} give $0\le y_\sigma\le D$ and $\sum_\sigma y_\sigma\le C=m_0D$. Increase coordinates, without exceeding $D$, until the total is $C$. This is possible because $m_0\le n!$. The resulting vector is majorized by $(D^{[m_0]},0^{[n!-m_0]})$: each decreasing prefix is bounded both by its length times $D$ and by the total $C$. Monotonicity and Schur-convexity prove \eqref{eq:diagonal-vector-majorization}. Take $\Phi(z)=\sum z_\sigma^t$ or the sum of the $m$ largest coordinates to get \eqref{eq:powers-and-partial-sums}. \end{proof} No rank restriction on $|A|^{\circ t}$ is used. The range $t\ge1$ is essential to this conclusion: at $n=3,k=2,t=1/2$, $\operatorname{per}(J_3^{\circ1/2})=2/\sqrt3>1$, whereas $\operatorname{per}((J_1\oplus J_2)^{\circ1/2})=1$. \subsection{Prescribed diagonals and minimum entrywise mass}\label{sec:prescribed-diagonals-and-minimum-entrywise-mass} We next minimize the \emph{absolute entrywise mass} $\sum_{i,j}|a_{ij}|$ when the diagonal magnitudes are prescribed. The sharp answer is another partition optimization; in this case each set contributes the square of a sum of square roots. For prescribed diagonal magnitudes $\delta_i>0$ and rank at most $k$, the Fan--Hoffman inequality \eqref{eq:fan-hoffman}, together with Cauchy--Schwarz, gives \[ \sum_{i,j}|a_{ij}|\ge\frac1k\left(\sum_i\sqrt{\delta_i}\right)^2. \] For unit diagonal magnitudes, this is the bound $n^2/k$. The following theorem determines the exact minimum by retaining the partition constraint. \begin{theorem}[prescribed-diagonal mass]\label{thm:minimum-mass} For $\delta_1,\ldots,\delta_n>0$ and $1\le k\le n$, over either $\mathbb R$ or $\mathbb C$, \begin{equation}\label{eq:minimum-mass} \min_{\substack{\operatorname{rank}A\le k\\|a_{ii}|=\delta_i}} \sum_{i,j}|a_{ij}| =\min_{\mathcal F}\sum_{F\in\mathcal F} \left(\sum_{i\in F}\sqrt{\delta_i}\right)^2, \end{equation} where the right minimum is over partitions of $[n]$ into at most $k$ nonempty sets. It can equivalently be taken over exactly $k$ sets. \end{theorem} \begin{proof} The positive diagonal guarantees $\rho_i>0$. By \mbox{Theorem~\ref{thm:packing-rank}}, the relative diagonal $t_i=\delta_i/\rho_i$ has a packing $F_1,\ldots,F_r$ with $r\le k$. Cauchy--Schwarz within each set gives \begin{equation}\label{eq:mass-cauchy-schwarz} \left(\sum_{i\in F_a}\sqrt{\delta_i}\right)^2 =\left(\sum_{i\in F_a}\sqrt{\rho_i}\sqrt{t_i}\right)^2 \le\left(\sum_{i\in F_a}\rho_i\right) \left(\sum_{i\in F_a}t_i\right) \le\sum_{i\in F_a}\rho_i. \end{equation} Summing proves the lower bound by the right side of \eqref{eq:minimum-mass}. Conversely, for any partition $\mathcal F$, put on each $F\times F$ the block $u_Fu_F^{\mathsf T}$, where $u_F=(\sqrt{\delta_i})_{i\in F}$, and put zero outside the blocks. This nonnegative matrix has diagonal $\delta$, rank $|\mathcal F|$, and exactly the prescribed mass on the right side of \eqref{eq:minimum-mass}. Splitting a set with positive square-root sums $a,b$ replaces $(a+b)^2$ by $a^2+b^2$, decreasing the objective. Thus a minimum uses exactly $k$ sets. \end{proof} For $\delta_i=1$, the minimum is \begin{equation}\label{eq:integer-mass} \min_{n_1+\cdots+n_k=n}\sum_a n_a^2 =N_{n,k}=\frac{n^2}{k}+\frac{s(k-s)}k, \end{equation} where the sizes are positive integers. The minimum is attained by the direct sum of $k-s$ all-ones blocks of order $q$ and $s$ all-ones blocks of order $q+1$. For unit diagonal magnitudes, this refines the lower bound $\sum_{i,j}|a_{ij}|\ge n^2/k$ by the exact correction $s(k-s)/k$, which is positive precisely when $k\nmid n$. The analogous lower bound $\|A\|_F^2\ge N_{n,k}$ for the squared \emph{Frobenius norm} $\|A\|_F^2=\sum_{i,j}|a_{ij}|^2$ is false. For example, \begin{equation}\label{eq:frobenius-counterexample} A=\begin{pmatrix} 1&-1/2&-1/2\\-1/2&1&-1/2\\-1/2&-1/2&1 \end{pmatrix} \end{equation} has rank two (its eigenvalues are $0,3/2,3/2$), unit diagonal, and $\|A\|_F^2=9/2<5=N_{3,2}$. Its absolute entrywise mass is six, consistent with \eqref{eq:integer-mass}. \section{Stochastic and doubly stochastic matrices}\label{sec:stochastic-matrices} \subsection{Stochastic column maxima and attainable diagonals}\label{sec:stochastic-column-maxima-and-attainable-diagonals} For row-stochastic matrices the column family has capacity one in the supremum norm. We record the partition explicitly, since it is the input to every application in this section. \begin{corollary}[stochastic column maxima]\label{cor:stochastic-packing} If a row-stochastic $m\times n$ matrix has rank $r$ and column maxima $p_j=\max_i a_{ij}$, then its column labels partition into $r$ nonempty sets with \begin{equation}\label{eq:stochastic-packing} \sum_{j\in F_a}p_j\le1\qquad(1\le a\le r). \end{equation} The same partition controls any choice of one entry from each column: $\sum_{j\in F_a}a_{i_jj}\le1$ for arbitrary row indices $i_j$. Transposition gives the corresponding row-maximum partition for a column-stochastic matrix. \end{corollary} \begin{proof} This is \mbox{Corollary~\ref{cor:column-packing}} with $R(A)=1$. The chosen entries are bounded by their column maxima. \end{proof} \mbox{Corollary~\ref{cor:signed-sums}} gives $\min_jp_j\le1/\lceil n/r\rceil$. For square matrices this contains the diagonal-entry bound of \cite[\mbox{Theorem~3.1}]{ref10}. Conversely, that theorem yields the column-maximum bound, even for rectangular matrices, by the row selection used after \eqref{eq:fan-hoffman}. By transposition it extends \cite[\mbox{Corollary~3.3}]{ref10} from doubly stochastic to all square column-stochastic matrices: some row has every entry at most $1/\lceil n/r\rceil$. \mbox{Theorem~\ref{thm:profiles}} characterizes which column-maximum profiles are attainable. For prescribed diagonals, the condition $\sum_jx_j\ge1$ is unnecessary except at rank one. \begin{theorem}[attainable stochastic diagonals]\label{thm:stochastic-diagonals} Let $n\ge2$, $1\le k\le n$, and $d\in[0,1]^n$. If $k\ge2$, then $d$ is the diagonal of a row-stochastic $n\times n$ matrix of rank at most $k$ if and only if $P(d)\le k$. If $k=1$, the attainable diagonals are exactly the probability vectors, namely those with $\sum_i d_i=1$. The same statements hold for any fixed generalized diagonal. \end{theorem} \begin{proof} A diagonal is dominated, coordinate by coordinate, by the column maxima, so \eqref{eq:stochastic-packing} proves necessity for $k\ge2$. For sufficiency, take a packing of the labels into at most $k$ sets. If it has fewer than two sets, split it into two nonempty sets; when $d=0$, start with any such split. This is possible because $n,k\ge2$. For each resulting set $F_a$, form a probability row whose entries on $F_a$ are $d_j$, placing its deficit $1-\sum_{j\in F_a}d_j$ in one column belonging to another set, and zero elsewhere. Give this row to every row index in $F_a$. The matrix has at most $k$ distinct rows, hence rank at most $k$, and its diagonal is exactly $d$. The deficit cannot change a diagonal entry because it is placed outside $F_a$. A rank-one row-stochastic matrix has identical rows: its rows are proportional, and their sums are all one. Its diagonal therefore lists one probability row. Conversely, identical rows equal to $d$ realize every probability vector. Column permutation gives the last assertion. \end{proof} For square row- or column-stochastic matrices of rank at most $k$, \mbox{Corollary~\ref{cor:diagonal-products}} and \mbox{Theorem~\ref{thm:permanent}} give the sharp maxima $D_{n,k}$ and $C_{n,k}$ for a fixed diagonal product and the permanent. Their full stochastic equality classifications remain those of \cite{ref9,ref10}. The diagonal characterization above concerns row-stochastic matrices; it does not assert a characterization for doubly stochastic matrices. \subsection{Doubly stochastic entropy, support, and power sums}\label{sec:doubly-stochastic-entropy-support-and-power-sums} Column sums provide an additional constraint: each column now sums to one. This converts bounds on the column maxima into bounds on all entries. For $\alpha>0$, consider the entrywise power sum $\sum_{i,j}a_{ij}^{\alpha}$. Write \begin{equation}\label{eq:stochastic-constants} \begin{aligned} T_{n,k}(\alpha)&=(k-s)q^{2-\alpha}+s(q+1)^{2-\alpha},\\ L_{n,k}&=(k-s)q\log q+s(q+1)\log(q+1), \end{aligned} \end{equation} with $n=qk+s$, $0\le s0\}|&\ge N_{n,k},\\ \sum_{i,j}a_{ij}^\alpha&\ge T_{n,k}(\alpha) &&(0<\alpha<1),\\ -\sum_{i,j}a_{ij}\log a_{ij}&\ge L_{n,k},\\ \sum_{i,j}a_{ij}^\alpha&\le T_{n,k}(\alpha) &&(1<\alpha\le2). \end{aligned} \end{equation} Here $0\log0=0$. At $\alpha=1$, the power sum equals $n$. All bounds are attained by $B_{n,k}$. They also hold with $A=|Z|$ when $Z$ is real or complex, $\operatorname{rank}Z\le k$, and $|Z|$ is doubly stochastic, regardless of the rank of $|Z|.$ \end{theorem} The support and entropy bounds are limiting forms of the power-sum inequalities. As $\alpha$ decreases to zero, the power sum tends to the number of positive entries, while $T_{n,k}(\alpha)$ tends to $N_{n,k}$. At $\alpha=1$, both sides equal $n$. Subtracting $n$, dividing by $\alpha-1$, and taking the limit gives the entropy bound, since \[ \left.\frac{d}{d\alpha}\sum_{i,j}a_{ij}^{\alpha}\right|_{\alpha=1} =\sum_{i,j}a_{ij}\log a_{ij}, \qquad T_{n,k}'(1)=-L_{n,k}. \] \begin{proof} Let $p_j=\max_i a_{ij}$. \mbox{Corollary~\ref{cor:stochastic-packing}} gives $P(p)\le\operatorname{rank}A\le k$, and every $p_j$ is positive because its column sum is one. For $1<\alpha\le2$, \begin{equation}\label{eq:power-sum-proof} \sum_{i,j}a_{ij}^\alpha \le\sum_j p_j^{\alpha-1}\sum_i a_{ij} =\sum_jp_j^{\alpha-1} \le\sum_j(b_{n,k})_j^{\alpha-1}=T_{n,k}(\alpha). \end{equation} For $1<\alpha\le2$, the power $t^{\alpha-1}$ is increasing and concave, so $x\mapsto\sum_jx_j^{\alpha-1}$ is coordinatewise nondecreasing and Schur-concave. Here we use that a sum of the same concave function over the coordinates is Schur-concave. The final inequality in \eqref{eq:power-sum-proof} therefore follows from \mbox{Theorem~\ref{thm:majorization}}. For $0<\alpha<1$, the pointwise inequality reverses on positive entries. The power $t^{\alpha-1}$ is decreasing and convex, so the corresponding sum is coordinatewise nonincreasing and Schur-convex on the positive orthant. The dual part of \mbox{Theorem~\ref{thm:majorization}}, in its form for positive vectors, reverses the final inequality as well, giving the bound for $0<\alpha<1$ in \eqref{eq:stochastic-bounds}. Zero entries contribute zero to the power sum and are omitted in this pointwise comparison. For entropy, $a_{ij}\le p_j$ on positive entries gives \begin{equation}\label{eq:entropy-proof} -\sum_{i,j}a_{ij}\log a_{ij} \ge-\sum_j\log p_j \ge-\log D_{n,k}=L_{n,k}, \end{equation} using the column sums and \mbox{Corollary~\ref{cor:symmetric-functions}}. A column of total one and maximum $p_j$ needs at least $1/p_j$ positive entries. Summing and using the reciprocal bound in \mbox{Corollary~\ref{cor:symmetric-functions}} gives the support inequality. In $B_{n,k}$, a block of size $t$ has $t^2$ entries equal to $1/t$. Its contributions to a power sum, entropy, and support are respectively $t^{2-\alpha}$, $t\log t$, and $t^2$. These give equality throughout. For $A=|Z|$, \mbox{Corollary~\ref{cor:column-packing}} applied to $Z$ gives the same packing of the column maxima into sets of load at most one. The remainder of the proof is unchanged. \end{proof} At $\alpha=2$, \eqref{eq:stochastic-bounds} reads $\|A\|_F^2\le k$. This case also has a short proof using singular values, which applies to the modulus extension. Indeed, if $A=|Z|$ is doubly stochastic and $\operatorname{rank}Z\le k$, the unit absolute row and column sums of $Z$, together with Cauchy--Schwarz, imply that every singular value of $Z$ is at most one. Consequently, \[ \|A\|_F^2=\|Z\|_F^2\le\operatorname{rank}Z\le k. \] The entropy and support bounds retain the integer sizes that the coarser estimates $L_{n,k}\ge n\log(n/k)$ and $N_{n,k}\ge n^2/k$ discard. Let $A$ be a $5\times5$ doubly stochastic matrix of rank at most two, and let $H(A_{i\cdot})$ denote the entropy of row $i$, viewed as a probability vector. \mbox{Theorem~\ref{thm:stochastic-bounds}} gives the following bounds, with entropy expressed as an average over rows: \begin{equation}\label{eq:five-by-five-example} \frac15\sum_i H(A_{i\cdot}) \ge\frac{2\log2+3\log3}{5}, \qquad \sum_{i,j}a_{ij}^{3/2}\le\sqrt2+\sqrt3. \end{equation} Both inequalities are attained by $J_2\oplus J_3$, which has $13$ nonzero entries. The column-sum assumption is essential: identical rows concentrated in one column give a rank-one row-stochastic matrix with row entropy zero and only $n$ positive entries. \subsection{Information bounds with prescribed marginals}\label{sec:information-bounds-with-prescribed-marginals} Let $\Pi=(\pi_{ij})$ be the $m\times n$ joint probability matrix of finite random variables $X,Y$, with $m$ input labels and $n$ output labels. Delete labels of probability zero, so the marginals $\mu_i=\sum_j\pi_{ij}$ and $\nu_j=\sum_i\pi_{ij}$ are positive. The \emph{mutual information} of $X$ and $Y$ is \begin{equation}\label{eq:mutual-information} I(X;Y)=\sum_{i,j:\pi_{ij}>0} \pi_{ij}\log\frac{\pi_{ij}}{\mu_i\nu_j}. \end{equation} Riazanov and Vyalyi \cite[\mbox{Theorem~4.1}]{ref17} proved \[ I(X;Y)\le\log\operatorname{rank}\Pi. \] \mbox{Theorem~\ref{thm:information}} refines this bound by incorporating the marginals. The entropy optimization $H_k^*$ was defined in \eqref{eq:partition-entropy}. It measures the largest information that could be retained by recording only which set of a partition into $k$ sets contains the label. \begin{theorem}[marginal-sensitive information bound]\label{thm:information} If $\operatorname{rank}\Pi\le k\le\min\{m,n\}$, then \begin{equation}\label{eq:information-bound} I(X;Y)\le\min\{H_k^*(\mu),H_k^*(\nu)\}\le\log k. \end{equation} Each one-marginal bound is sharp when the other marginal and its alphabet may be chosen. With both marginals prescribed, \eqref{eq:information-bound} is a bound; attainment is not asserted in general. \end{theorem} \begin{proof} The row-stochastic matrix $A=(a_{ij})$, with $a_{ij}=\pi_{ij}/\mu_i$, records the conditional distribution of $Y$ given $X$. It is called the channel from $X$ to $Y$ and has the same rank as $\Pi$. Its column maxima $p_j$ are positive and pack into at most $k$ sets; split to exactly $k$ nonempty sets. Since $\nu_j=\sum_i\mu_i a_{ij}$, \eqref{eq:mutual-information} gives \begin{equation}\label{eq:information-proof} \begin{aligned} I(X;Y) &=H(\nu)+\sum_{i,j:a_{ij}>0}\mu_i a_{ij}\log a_{ij}\\ &\le H(\nu)+\sum_j\nu_j\log p_j\\ &\le H_k^*(\nu). \end{aligned} \end{equation} The last step is \eqref{eq:weighted-am-gm} with weights $\nu_j$, applied within the actual packing sets: their masses $W_a=\sum_{j\in F_a}\nu_j$ give $\sum_j\nu_j\log p_j\le H(W)-H(\nu)$. Apply the same argument to $\Pi^{\mathsf T}$ for the other marginal. The entropy of a probability vector with $k$ entries is at most $\log k$, by concavity of $-x\log x$. For sharpness with $\nu$ fixed, choose an entropy-maximizing partition and let $X$ be its set index, with probabilities $W_a$. Conditional on $X=a$, choose $Y=j\in F_a$ with probability $\nu_j/W_a$. The output marginal is $\nu$, the channel has rank $k$ because its rows have disjoint nonempty supports, and $X$ is determined by $Y$. Direct substitution into \eqref{eq:mutual-information} gives $I(X;Y)=H(W)=H_k^*(\nu)$. Transposition proves the analogous assertion for $\mu$. \end{proof} For uniform input on $m$ labels, balanced set sizes maximize \eqref{eq:partition-entropy}. Consequently, writing $m=qk+s$ with $0\le s