Hostname: page-component-74656f9884-skzmx Total loading time: 0 Render date: 2026-11-06T11:03:18.829Z Has data issue: false hasContentIssue false
  • English
  • Français

A NONNEGATIVITY CRITERION FOR ERDŐS MATRICES

Part of: Special matrices Graph theory Basic linear algebra

Published online by Cambridge University Press:  02 October 2026

FRÉDÉRIC MORNEAU-GUÉRIN Open the ORCID record for FRÉDÉRIC MORNEAU-GUÉRIN [Opens in a new window]
FRÉDÉRIC MORNEAU-GUÉRIN*
Affiliation:
Département Éducation, Université TÉLUQ , Québec, Canada
*
e-mail: frederic.morneau-guerin@teluq.ca
Rights & Permissions [Opens in a new window]

Abstract

Let A be an $n\times n$ doubly stochastic matrix. The Marcus–Ree inequality asserts that $\|A\|_{\mathrm F}^2\leq \mathrm {maxtrace}(A)$. Matrices attaining equality are called Erdős matrices. Recent work of Karmakar et al. [‘Characterization of Erdős matrices by their zero entries’, Linear Algebra Appl. 739 (2026), 154–169] shows that every Erdős matrix is a restricted common diagonal sum matrix. By the structural theory of Brualdi and Dahl [‘Diagonal sums of doubly stochastic matrices’, Linear Multilinear Algebra 70 (2022), 4946–4972], a restricted common diagonal sum matrix with fully indecomposable skeleton $S=(s_{ij})$ admits additive potentials satisfying $a_{ij}=(u_i+v_j)s_{ij}$. Karmakar et al. observed that $\min _i u_i+\min _jv_j\geq 0$ is sufficient for Erdős-ness. We prove that it is also necessary. Thus, recognition reduces to solving one linear system per fully indecomposable block and checking signs, with no residual maxtrace computation.

Keywords

doubly stochastic matrixMarcus–Ree inequalityErdős matrixRCDS matrixassignment problem

MSC classification

Primary: 15B51: Stochastic matrices
Secondary: 15A15: Determinants, permanents, other special matrix functions 90C27: Combinatorial optimization 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

Information

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , First View , pp. 1 - 11
Check for updates
Copyright
© The Author(s), 2026. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

1 Introduction

Let $\Omega _n$ normal upper Omega Subscript n be the Birkhoff polytope of $n\times n$ n times n doubly stochastic matrices and set

$$ \begin{align*} \mathrm{maxtrace}(A)=\max_{\sigma\in S_n}\sum_{i=1}^n a_{i,\sigma(i)}. \end{align*} $$ StartLayout 1st Row maxtrace left parenthesis upper A right parenthesis equals max Underscript sigma element of upper S Subscript n Baseline Endscripts sigma summation Underscript i equals 1 Overscript n Endscripts a Subscript i comma sigma left parenthesis i right parenthesis Baseline period EndLayout

Equivalently, $\mathrm {maxtrace}(A)$ maxtrace left parenthesis upper A right parenthesis is the optimal value of the assignment problem with A as its cost matrix; we discuss this interpretation in more detail in Section 3.

Marcus and Ree [Reference Marcus and Ree8] proved that

(1.1) $$ \begin{align} \|A\|_{\mathrm F}^2\leq\mathrm{maxtrace}(A), \end{align} $$ StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline less than or equals maxtrace left parenthesis upper A right parenthesis comma

where

$$ \begin{align*} \|A\|_{\mathrm F} =\bigg(\sum_{i,j}a_{ij}^2\bigg)^{1/2} \end{align*} $$ StartMetric upper A EndMetric Subscript normal upper F Baseline equals left parenthesis sigma summation Underscript i comma j Endscripts a Subscript i j Superscript 2 Baseline right parenthesis Superscript 1 divided by 2

denotes the Frobenius norm. Upon learning of this result, Erdős asked for a characterisation of the matrices for which equality holds in (1.1) (see [Reference Bouthat, Mashreghi and Morneau-Guérin4, Reference Marcus and Ree8]). Thus, the problem is to determine all $A\in \Omega _n$ upper A element of normal upper Omega Subscript n satisfying

(1.2) $$ \begin{align} \mathrm{maxtrace}(A)=\|A\|_{\mathrm F}^2. \end{align} $$ maxtrace left parenthesis upper A right parenthesis equals StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline period

Following terminology introduced by Tripathi [Reference Tripathi10], we call the matrices satisfying (1.2) Erdős matrices.

The question has received renewed attention. The $3\times 3$ 3 times 3 case was classified by Bouthat et al. [Reference Bouthat, Mashreghi and Morneau-Guérin4]. Tripathi [Reference Tripathi10] subsequently proved that there are only finitely many Erdős matrices in each dimension, and that all of them are rational and have an algorithmic characterisation. The $4\times 4$ 4 times 4 case was later classified by Kushwaha and Tripathi [Reference Kushwaha and Tripathi7].

Most relevant here is the recent work of Karmakar et al. [Reference Karmakar, Krishna, Pal and Krishna Teja6]. They prove that every Erdős matrix belongs to the class of restricted common diagonal sum (RCDS) matrices studied by Brualdi and Dahl [Reference Brualdi and Dahl5]. Questions concerning prescribed diagonal sums of doubly stochastic matrices go back several decades. Wang [Reference Wang11] studied maximal and minimal diagonal sums, while constant diagonal sums were considered by Sinkhorn [Reference Sinkhorn9], Achilles [Reference Achilles1] and Balasubramanian [Reference Balasubramanian2, Reference Balasubramanian3]. The RCDS matrices of Brualdi and Dahl [Reference Brualdi and Dahl5] belong to this line of work. A permutation $\sigma $ sigma is inner for A if $a_{i,\sigma (i)}>0$ a Subscript i comma sigma left parenthesis i right parenthesis Baseline greater than 0 for every i, and outer otherwise; A is RCDS when all inner permutation diagonals have the same sum.

For a fully indecomposable skeleton $S=(s_{ij})$ upper S equals left parenthesis s Subscript i j Baseline right parenthesis , by which we mean the pattern of the matrix (see Section 2 for the precise definition), Brualdi and Dahl show that an RCDS matrix has the form

$$ \begin{align*} a_{ij}=(u_i+v_j)s_{ij} \end{align*} $$ a Subscript i j Baseline equals left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis s Subscript i j

for some real vectors $u=(u_1,\ldots ,u_n)$ u equals left parenthesis u 1 comma ellipsis comma u Subscript n Baseline right parenthesis and $v=(v_1,\ldots ,v_n)$ v equals left parenthesis v 1 comma ellipsis comma v Subscript n Baseline right parenthesis . We call u and v the additive potentials and the quantities $u_i+v_j$ u Subscript i Baseline plus v Subscript j the cross-sums. Although the potentials themselves are not unique, the cross-sums are uniquely determined. Karmakar et al. derive the criterion

$$ \begin{align*} \sum_{\substack{i\\s_{i,\sigma(i)}=0}}(u_i+v_{\sigma(i)})\geq0 \end{align*} $$ StartLayout 1st Row sigma summation Underscript StartLayout 1st Row i 2nd Row s Subscript i comma sigma left parenthesis i right parenthesis Baseline equals 0 EndLayout Endscripts left parenthesis u Subscript i Baseline plus v Subscript sigma left parenthesis i right parenthesis Baseline right parenthesis greater than or equals 0 EndLayout

for every outer permutation $\sigma $ sigma and, in particular, record

(1.3) $$ \begin{align} \min_i u_i+\min_j v_j\geq0 \end{align} $$ min Underscript i Endscripts u Subscript i Baseline plus min Underscript j Endscripts v Subscript j Baseline greater than or equals 0

as a sufficient condition for Erdős-ness [Reference Karmakar, Krishna, Pal and Krishna Teja6, Lemma 1.6].

Our main result is that, for a fully indecomposable RCDS matrix, (1.3) is also necessary:

$$ \begin{align*} A\text{ is Erdos}\iff u_i+v_j\geq0\quad \text{for all }i,j \iff \min_i u_i+\min_jv_j\geq 0. \end{align*} $$ upper A is Erdos long left right double arrow u Subscript i Baseline plus v Subscript j Baseline greater than or equals 0 for all i comma j long left right double arrow min Underscript i Endscripts u Subscript i Baseline plus min Underscript j Endscripts v Subscript j Baseline greater than or equals 0 period

The proof also yields a constructive interpretation: if $u_i+v_j<0$ u Subscript i Baseline plus v Subscript j Baseline less than 0 at a zero position, full indecomposability produces an outer permutation using that zero and no other one, whose diagonal sum exceeds $\|A\|_{\mathrm F}^2$ StartMetric upper A EndMetric Subscript normal upper F Superscript 2 . Thus, the aggregate inequalities of [Reference Karmakar, Krishna, Pal and Krishna Teja6] collapse to pointwise sign conditions. This gives a practical recognition procedure as well. After decomposing a doubly stochastic matrix into fully indecomposable blocks, one solves the linear system (2.3) on each block, verifies that the resulting cross-sums reproduce the block and checks the sign condition ${\min _i u_i+\min _jv_j\geq 0}$ min Underscript i Endscripts u Subscript i Baseline plus min Underscript j Endscripts v Subscript j Baseline greater than or equals 0 ; no maxtrace computation is required. Moreover, when the sign condition fails, Proposition 3.4 produces an explicit permutation certifying the failure of Erdős-ness. Finally, applying the criterion blockwise gives a characterisation of Erdős matrices in arbitrary dimension.

2 RCDS matrices and additive potentials

For a nonnegative matrix $A=(a_{ij})$ upper A equals left parenthesis a Subscript i j Baseline right parenthesis , write $\mathrm {skel}(A)=(s_{ij})$ skel left parenthesis upper A right parenthesis equals left parenthesis s Subscript i j Baseline right parenthesis , where $s_{ij}=1$ s Subscript i j Baseline equals 1 if $a_{ij}>0$ a Subscript i j Baseline greater than 0 and $s_{ij}=0$ s Subscript i j Baseline equals 0 otherwise. Every doubly stochastic matrix has total support: each positive position belongs to an inner permutation by the Birkhoff–von Neumann theorem.

Lemma 2.1. Suppose $A\in \Omega _n$ upper A element of normal upper Omega Subscript n and $ a_{ij}=(u_i+v_j)s_{ij}, $ a Subscript i j Baseline equals left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis s Subscript i j Baseline comma where $u=(u_1,\ldots ,u_n)$ u equals left parenthesis u 1 comma ellipsis comma u Subscript n Baseline right parenthesis and ${v=(v_1,\ldots ,v_n)}$ v equals left parenthesis v 1 comma ellipsis comma v Subscript n Baseline right parenthesis are real vectors and $S=\mathrm {skel}(A)$ upper S equals skel left parenthesis upper A right parenthesis . Then,

(2.1) $$ \begin{align} \|A\|_{\mathrm F}^2=\sum_i u_i+\sum_jv_j \end{align} $$ StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline equals sigma summation Underscript i Endscripts u Subscript i Baseline plus sigma summation Underscript j Endscripts v Subscript j

and, for every $\sigma \in S_n$ sigma element of upper S Subscript n ,

(2.2) $$ \begin{align} \sum_i a_{i,\sigma(i)}=\|A\|_{\mathrm F}^2- \sum_{\substack{i\\s_{i,\sigma(i)}=0}}(u_i+v_{\sigma(i)}). \end{align} $$ StartLayout 1st Row sigma summation Underscript i Endscripts a Subscript i comma sigma left parenthesis i right parenthesis Baseline equals StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline minus sigma summation Underscript StartLayout 1st Row i 2nd Row s Subscript i comma sigma left parenthesis i right parenthesis Baseline equals 0 EndLayout Endscripts left parenthesis u Subscript i Baseline plus v Subscript sigma left parenthesis i right parenthesis Baseline right parenthesis period EndLayout

In particular, A is RCDS.

Proof. Since $a_{ij}^2=(u_i+v_j)a_{ij}$ a Subscript i j Superscript 2 Baseline equals left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis a Subscript i j for all $i,j$ i comma j , the row and column sums give (2.1). In addition,

$$ \begin{align*} \sum_i a_{i,\sigma(i)}=\sum_i(u_i+v_{\sigma(i)})- \sum_{s_{i,\sigma(i)}=0}(u_i+v_{\sigma(i)}) \end{align*} $$ StartLayout 1st Row sigma summation Underscript i Endscripts a Subscript i comma sigma left parenthesis i right parenthesis Baseline equals sigma summation Underscript i Endscripts left parenthesis u Subscript i Baseline plus v Subscript sigma left parenthesis i right parenthesis Baseline right parenthesis minus sigma summation Underscript s Subscript i comma sigma left parenthesis i right parenthesis Baseline equals 0 Endscripts left parenthesis u Subscript i Baseline plus v Subscript sigma left parenthesis i right parenthesis Baseline right parenthesis EndLayout

and the first sum equals $\sum _i u_i+\sum _jv_j$ sigma summation Underscript i Endscripts u Subscript i plus sigma summation Underscript j Endscripts v Subscript j . This proves (2.2); for an inner permutation, the second sum is empty.

The following proposition is essentially the structural result of Brualdi and Dahl [Reference Brualdi and Dahl5, Theorem 2.6]; see also the formulation of Karmakar et al. [Reference Karmakar, Krishna, Pal and Krishna Teja6, Theorem 1.4].

Proposition 2.2. Let $S=(s_{ij})$ upper S equals left parenthesis s Subscript i j Baseline right parenthesis be fully indecomposable. Put $r_i=\sum _js_{ij}$ r Subscript i Baseline equals sigma summation Underscript j Endscripts s Subscript i j , $c_j=\sum _is_{ij}$ c Subscript j Baseline equals sigma summation Underscript i Endscripts s Subscript i j , $D_R=\mathrm {diag}(r_i)$ upper D Subscript upper R Baseline equals diag left parenthesis r Subscript i Baseline right parenthesis and $D_C=\mathrm {diag}(c_j)$ upper D Subscript upper C Baseline equals diag left parenthesis c Subscript j Baseline right parenthesis . The system

(2.3) $$ \begin{align} \begin{pmatrix}D_R&S\\S^\intercal&D_C\end{pmatrix}\binom{u}{v}=\binom{\mathbf1}{\mathbf1} \end{align} $$ Start 2 By 2 Matrix 1st Row 1st Column upper D Subscript upper R Baseline 2nd Column upper S 2nd Row 1st Column upper S Superscript intercalate Baseline 2nd Column upper D Subscript upper C Baseline EndMatrix StartBinomialOrMatrix u Choose v EndBinomialOrMatrix equals StartBinomialOrMatrix bold 1 Choose bold 1 EndBinomialOrMatrix

is solvable and any two solutions differ by $u\mapsto u+t\mathbf 1$ u right arrow from bar u plus t Baseline bold 1 , $v\mapsto v-t\mathbf 1$ v right arrow from bar v minus t Baseline bold 1 . Moreover, S is the skeleton of an RCDS doubly stochastic matrix if and only if

$$ \begin{align*} u_i+v_j>0\quad(s_{ij}=1), \end{align*} $$ u Subscript i Baseline plus v Subscript j Baseline greater than 0 left parenthesis s Subscript i j Baseline equals 1 right parenthesis comma

and then that matrix is uniquely determined by $a_{ij}=(u_i+v_j)s_{ij}$ a Subscript i j Baseline equals left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis s Subscript i j .

Proof. The coefficient matrix in (2.3) is the signless Laplacian of the bipartite graph with biadjacency matrix S.

This graph is connected. Indeed, if it were disconnected, its vertex set would split into two nonempty parts with no edges between them; let I be the set of rows and J the set of columns lying in one of the parts. Then, $S[I,J^{c}]=0$ upper S left bracket upper I comma upper J Superscript c Baseline right bracket equals 0 and $S[I^{c},J]=0$ upper S left bracket upper I Superscript c Baseline comma upper J right bracket equals 0 . The dimension sums of these two zero submatrices add up to $2n$ 2 n , so one of them is at least n; shrinking that submatrix if necessary yields an $r\times s$ r times s all-zero submatrix with $r+s=n$ r plus s equals n , which contradicts full indecomposability. Since the graph is connected and bipartite, the kernel of the coefficient matrix is spanned by $(\begin {smallmatrix}\mathbf {1}\\-\mathbf {1}\end {smallmatrix})$ StartBinomialOrMatrix bold 1 Choose negative bold 1 EndBinomialOrMatrix ; since the right-hand side of (2.3) is orthogonal to this vector, the system is solvable and its solutions have exactly the stated ambiguity. Equation (2.3) is equivalent to the row and column sums of $(u_i+v_j)s_{ij}$ left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis s Subscript i j being $1$ 1 . Positivity on the support therefore gives an RCDS matrix by Lemma 2.1, and the converse and uniqueness follow from the additive representation and invariance of the cross-sums.

Proposition 2.3 (Karmakar et al. [Reference Karmakar, Krishna, Pal and Krishna Teja6, Proposition 2.7]).

Every Erdős matrix is RCDS.

3 The potential criterion

3.1 Assignment duality

For a real $n\times n$ n times n matrix $C=(c_{ij})$ upper C equals left parenthesis c Subscript i j Baseline right parenthesis we write, as in Section 1,

$$ \begin{align*} \mathrm{maxtrace}(C)=\max_{\sigma\in S_n}\sum_{i=1}^n c_{i,\sigma(i)}. \end{align*} $$ StartLayout 1st Row maxtrace left parenthesis upper C right parenthesis equals max Underscript sigma element of upper S Subscript n Baseline Endscripts sigma summation Underscript i equals 1 Overscript n Endscripts c Subscript i comma sigma left parenthesis i right parenthesis Baseline period EndLayout

The maximum assignment problem for C is

(3.1) $$ \begin{align} \max\bigg\{ \sum_{i,j}c_{ij}x_{ij} : X=(x_{ij})\in\Omega_n \bigg\} \end{align} $$ max left brace sigma summation Underscript i comma j Endscripts c Subscript i j Baseline x Subscript i j Baseline colon upper X equals left parenthesis x Subscript i j Baseline right parenthesis element of normal upper Omega Subscript n Baseline right brace

and its dual is

(3.2) $$ \begin{align} \min\bigg\{ \sum_i\alpha_i+\sum_j\beta_j : \alpha_i+\beta_j\ge c_{ij}\ \text{for all }i,j \bigg\}. \end{align} $$ min left brace sigma summation Underscript i Endscripts alpha Subscript i Baseline plus sigma summation Underscript j Endscripts beta Subscript j Baseline colon alpha Subscript i Baseline plus beta Subscript j Baseline greater than or equals c Subscript i j Baseline for all i comma j right brace period

Since the extreme points of $\Omega _n$ normal upper Omega Subscript n are the permutation matrices, the optimum in (3.1) is $\mathrm {maxtrace}(C)$ maxtrace left parenthesis upper C right parenthesis .

For an RCDS matrix A, the potentials $u,v$ u comma v are dual feasible for the assignment problem restricted to the support of A: on the support, $ u_i+v_j=a_{ij}. $ u Subscript i Baseline plus v Subscript j Baseline equals a Subscript i j Baseline period

Passing to the unrestricted assignment problem adds the constraints

$$ \begin{align*} u_i+v_j\geq 0 \quad\text{whenever }s_{ij}=0. \end{align*} $$ u Subscript i Baseline plus v Subscript j Baseline greater than or equals 0 whenever s Subscript i j Baseline equals 0 period

This gives the following criterion.

Theorem 3.1. Let $A\in \Omega _n$ upper A element of normal upper Omega Subscript n be RCDS with fully indecomposable skeleton $S=(s_{ij})$ upper S equals left parenthesis s Subscript i j Baseline right parenthesis and let $u,v$ u comma v be its additive potentials, so that $ a_{ij}=(u_i+v_j)s_{ij}. $ a Subscript i j Baseline equals left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis s Subscript i j Baseline period The following conditions are equivalent:

  1. (i) A is an Erdős matrix;

  2. (ii) $(u,v)$ left parenthesis u comma v right parenthesis is feasible for the assignment dual (3.2) with $C=A$ upper C equals upper A ;

  3. (iii) $u_i+v_j\geq 0$ u Subscript i Baseline plus v Subscript j Baseline greater than or equals 0 whenever $s_{ij}=0$ s Subscript i j Baseline equals 0 ;

  4. (iv) $u_i+v_j\geq 0$ u Subscript i Baseline plus v Subscript j Baseline greater than or equals 0 for all $i,j$ i comma j ;

  5. (v) $\min _i u_i+\min _jv_j \geq 0$ min Underscript i Endscripts u Subscript i Baseline plus min Underscript j Endscripts v Subscript j Baseline greater than or equals 0 .

Proof. We first prove that conditions (ii)–(v) are equivalent. On the support of A,

$$ \begin{align*} u_i+v_j=a_{ij}>0, \end{align*} $$ u Subscript i Baseline plus v Subscript j Baseline equals a Subscript i j Baseline greater than 0 comma

so the dual constraints in (3.2) hold there with equality. At a zero position, they reduce to $u_i+v_j\geq 0$ u Subscript i Baseline plus v Subscript j Baseline greater than or equals 0 . Thus, conditions (ii) and (iii) are equivalent. Since the cross-sums are already positive on the support, condition (iii) is in turn equivalent to condition (iv). Finally,

$$ \begin{align*} \min_{i,j}(u_i+v_j) = \min_i u_i+\min_jv_j, \end{align*} $$ min Underscript i comma j Endscripts left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis equals min Underscript i Endscripts u Subscript i Baseline plus min Underscript j Endscripts v Subscript j Baseline comma

so conditions (iv) and (v) are equivalent.

Suppose now that condition (ii) holds. Weak duality for (3.1)–(3.2) with $C=A$ upper C equals upper A and Lemma 2.1 give

$$ \begin{align*} \mathrm{maxtrace}(A) \leq \sum_i u_i+\sum_jv_j = \|A\|_{\mathrm{F}}^{2}. \end{align*} $$ maxtrace left parenthesis upper A right parenthesis less than or equals sigma summation Underscript i Endscripts u Subscript i Baseline plus sigma summation Underscript j Endscripts v Subscript j Baseline equals StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline period

The reverse inequality is precisely the Marcus–Ree inequality (1.1). Hence,

$$ \begin{align*} \mathrm{maxtrace}(A)=\|A\|_{\mathrm{F}}^{2} \end{align*} $$ maxtrace left parenthesis upper A right parenthesis equals StartMetric upper A EndMetric Subscript normal upper F Superscript 2

and condition (i) follows.

Conversely, suppose that condition (i) holds and let $(\alpha ,\beta )$ left parenthesis alpha comma beta right parenthesis be an optimal solution of the assignment dual (3.2) with $C=A$ upper C equals upper A . Since A is doubly stochastic, every position $(i,j)$ left parenthesis i comma j right parenthesis with $s_{ij}=1$ s Subscript i j Baseline equals 1 belongs to an inner permutation (see Section 2). By Lemma 2.1, every such inner permutation has diagonal sum

$$ \begin{align*} \|A\|_{\mathrm{F}}^{2} =\mathrm{maxtrace}(A) \end{align*} $$ StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline equals maxtrace left parenthesis upper A right parenthesis

and is, therefore, optimal for the primal assignment problem. Complementary slackness then gives

(3.3) $$ \begin{align} \alpha_i+\beta_j = a_{ij} = u_i+v_j \quad\text{whenever }s_{ij}=1. \end{align} $$ alpha Subscript i Baseline plus beta Subscript j Baseline equals a Subscript i j Baseline equals u Subscript i Baseline plus v Subscript j Baseline whenever s Subscript i j Baseline equals 1 period

The bipartite graph associated with S is connected, as shown in the proof of Proposition 2.2. Rewriting (3.3) as

$$ \begin{align*} (\alpha_i-u_i)+(\beta_j-v_j)=0 \end{align*} $$ left parenthesis alpha Subscript i Baseline minus u Subscript i Baseline right parenthesis plus left parenthesis beta Subscript j Baseline minus v Subscript j Baseline right parenthesis equals 0

on every edge, connectedness implies that there exists $t\in \mathbb {R}$ t element of double struck upper R such that

$$ \begin{align*} \alpha_i-u_i=t \quad\text{for every }i \quad\text{and}\quad \beta_j-v_j=-t \quad\text{for every }j. \end{align*} $$ alpha Subscript i Baseline minus u Subscript i Baseline equals t for every i and beta Subscript j Baseline minus v Subscript j Baseline equals negative t for every j period

Consequently,

$$ \begin{align*} \alpha_i+\beta_j=u_i+v_j \quad\text{for all }i,j. \end{align*} $$ alpha Subscript i Baseline plus beta Subscript j Baseline equals u Subscript i Baseline plus v Subscript j Baseline for all i comma j period

At a zero position, dual feasibility therefore yields

$$ \begin{align*} u_i+v_j = \alpha_i+\beta_j \geq a_{ij} = 0. \end{align*} $$ u Subscript i Baseline plus v Subscript j Baseline equals alpha Subscript i Baseline plus beta Subscript j Baseline greater than or equals a Subscript i j Baseline equals 0 period

Thus, condition (iii) holds, which completes the proof.

Remark 3.2. Theorem 3.1 says that the potentials for the support-restricted assignment problem remain dual feasible for the unrestricted problem exactly when A is Erdős. It also sharpens [Reference Karmakar, Krishna, Pal and Krishna Teja6, Lemma 1.6]: for a fully indecomposable skeleton, the inequalities over the zero positions of outer permutations reduce to the pointwise conditions $u_i+v_j\geq 0$ u Subscript i Baseline plus v Subscript j Baseline greater than or equals 0 . The next proposition gives a constructive explanation.

3.2 A constructive cycle proof

The duality argument proves the criterion, but does not produce a permutation witnessing its failure. We now give such a construction.

Fix an inner permutation of A and permute the columns of A so that it becomes the identity, so that

$$ \begin{align*} s_{ii}=1\quad(1\leq i\leq n). \end{align*} $$ s Subscript i i Baseline equals 1 left parenthesis 1 less than or equals i less than or equals n right parenthesis period

This permutation of the columns permutes the entries of v and relabels the positions accordingly; it affects neither the hypotheses nor the conclusions below, so we may assume throughout this subsection that it has been carried out. Associate with S the directed graph $D_S$ upper D Subscript upper S on $\{1,\ldots ,n\}$ StartSet 1 comma ellipsis comma n EndSet , defined by

$$ \begin{align*} i\longrightarrow j \quad\Longleftrightarrow\quad s_{ij}=1. \end{align*} $$ i long right arrow j long left right double arrow s Subscript i j Baseline equals 1 period

Lemma 3.3. If S is fully indecomposable, then $D_S$ upper D Subscript upper S is strongly connected.

Proof. Suppose that $D_S$ upper D Subscript upper S is not strongly connected. Then, we may choose a vertex k from which not every vertex is reachable. Let I be the set of vertices reachable from k. Then, I is nonempty and proper, and no edge can leave I, since the endpoint of such an edge would also be reachable from k. Hence,

$$ \begin{align*} s_{ij}=0 \quad\text{whenever } i\in I \text{ and } j\notin I. \end{align*} $$ s Subscript i j Baseline equals 0 whenever i element of upper I and j not an element of upper I period

Thus, S contains an all-zero submatrix of size $|I|\times (n-|I|)$ StartAbsoluteValue upper I EndAbsoluteValue times left parenthesis n minus StartAbsoluteValue upper I EndAbsoluteValue right parenthesis , which contradicts full indecomposability.

The lemma allows us to isolate any single zero position.

Proposition 3.4. Under the hypotheses of Theorem 3.1, let $(i,j)$ left parenthesis i comma j right parenthesis be a zero position of S. Then, there exists a permutation $\sigma \in S_n$ sigma element of upper S Subscript n for which $(i,j)$ left parenthesis i comma j right parenthesis is the only zero position among

$$ \begin{align*} (k,\sigma(k)),\quad 1\leq k\leq n. \end{align*} $$ left parenthesis k comma sigma left parenthesis k right parenthesis right parenthesis comma 1 less than or equals k less than or equals n period

Consequently, if $u_i+v_j<0$ u Subscript i Baseline plus v Subscript j Baseline less than 0 , then

(3.4) $$ \begin{align} \sum_k a_{k,\sigma(k)} = \|A\|_{\mathrm{F}}^{2}-(u_i+v_j)> \|A\|_{\mathrm{F}}^{2}. \end{align} $$ sigma summation Underscript k Endscripts a Subscript k comma sigma left parenthesis k right parenthesis Baseline equals StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline minus left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis greater than StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline period

In particular, $\sigma $ sigma certifies that A is not Erdős.

Proof. Since $s_{ii}=1$ s Subscript i i Baseline equals 1 , we have $i\neq j$ i not equals j . By Lemma 3.3, there is a directed path from j to i. Choose a simple such path,

$$ \begin{align*} j=i_0\rightarrow i_1\rightarrow\cdots \rightarrow i_m=i. \end{align*} $$ j equals i 0 right arrow i 1 right arrow midline horizontal ellipsis right arrow i Subscript m Baseline equals i period

Define $\sigma $ sigma by

$$ \begin{align*} \sigma(i_\ell)=i_{\ell+1}\quad(0\leq\ell<m), \quad \sigma(i)=j, \end{align*} $$ StartLayout 1st Row sigma left parenthesis i Subscript script l Baseline right parenthesis equals i Subscript script l plus 1 Baseline left parenthesis 0 less than or equals script l less than m right parenthesis comma sigma left parenthesis i right parenthesis equals j comma EndLayout

and let $\sigma (k)=k$ sigma left parenthesis k right parenthesis equals k for all remaining indices.

Every position used by $\sigma $ sigma lies in the support of S, except for the closing position $(i,j)$ left parenthesis i comma j right parenthesis . Hence, $(i,j)$ left parenthesis i comma j right parenthesis is the unique zero position used by $\sigma $ sigma . The defect identity (2.2) therefore gives

$$ \begin{align*} \sum_k a_{k,\sigma(k)} = \|A\|_{\mathrm{F}}^{2}-(u_i+v_j). \end{align*} $$ sigma summation Underscript k Endscripts a Subscript k comma sigma left parenthesis k right parenthesis Baseline equals StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline minus left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis period

If $u_i+v_j<0$ u Subscript i Baseline plus v Subscript j Baseline less than 0 , the right-hand side is strictly larger than $\|A\|_{\mathrm {F}}^{2}$ StartMetric upper A EndMetric Subscript normal upper F Superscript 2 , as claimed.

Remark 3.5. Proposition 3.4 gives a constructive proof of (i) $\Rightarrow $ right double arrow (iii) in Theorem 3.1, independent of linear-programming duality.

4 Skeleton and blockwise characterisations

The potential criterion can be stated directly in terms of the skeleton.

Theorem 4.1. Let $S=(s_{ij})$ upper S equals left parenthesis s Subscript i j Baseline right parenthesis be a fully indecomposable zero–one matrix and let $u,v$ u comma v solve (2.3). Then, S is the skeleton of an Erdős matrix if and only if

(4.1) $$ \begin{align} u_i+v_j>0 &\quad (s_{ij}=1), \end{align} $$ StartLayout 1st Row 1st Column u Subscript i Baseline plus v Subscript j Baseline greater than 0 2nd Column left parenthesis s Subscript i j Baseline equals 1 right parenthesis comma EndLayout
(4.2) $$ \begin{align} u_i+v_j\geq0 &\quad (s_{ij}=0). \end{align} $$ StartLayout 1st Row 1st Column u Subscript i Baseline plus v Subscript j Baseline greater than or equals 0 2nd Column left parenthesis s Subscript i j Baseline equals 0 right parenthesis period EndLayout

Under (4.1), condition (4.2) is equivalent to $\min _i u_i+\min _jv_j\geq 0$ min Underscript i Endscripts u Subscript i Baseline plus min Underscript j Endscripts v Subscript j Baseline greater than or equals 0 . When these conditions hold, the unique Erdős matrix with skeleton S is

$$ \begin{align*} E(S)_{ij}=(u_i+v_j)s_{ij}. \end{align*} $$ upper E left parenthesis upper S right parenthesis Subscript i j Baseline equals left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis s Subscript i j Baseline period

Proof. Proposition 2.2 gives the RCDS matrix with skeleton S exactly under (4.1); Theorem 3.1 then gives Erdős-ness exactly under (4.2). Conversely, every Erdős matrix is RCDS by Proposition 2.3, so the same two results give the necessity and uniqueness. Finally, under (4.1), (4.2) is equivalent to nonnegativity of all cross-sums and

$$ \begin{align*} \begin{aligned} \min_{i,j}(u_i+v_j)=\min_i u_i+\min_jv_j. \end{aligned}\\[-35pt] \end{align*} $$ StartLayout 1st Row min Underscript i comma j Endscripts left parenthesis u Subscript i Baseline plus v Subscript j Baseline right parenthesis equals min Underscript i Endscripts u Subscript i Baseline plus min Underscript j Endscripts v Subscript j Baseline period EndLayout

Remark 4.2. The uniqueness assertion in Theorem 4.1 is also a special case of [Reference Karmakar, Krishna, Pal and Krishna Teja6, Theorem 1.8], which shows that a given skeleton carries at most one Erdős matrix; the present proof has the advantage of exhibiting $E(S)$ upper E left parenthesis upper S right parenthesis explicitly.

Every $A\in \Omega _n$ upper A element of normal upper Omega Subscript n has total support; hence, after row and column permutations,

$$ \begin{align*} PAQ=A_1\oplus\cdots\oplus A_m, \end{align*} $$ upper P upper A upper Q equals upper A 1 circled plus midline horizontal ellipsis circled plus upper A Subscript m Baseline comma

where the $A_k$ upper A Subscript k are fully indecomposable doubly stochastic blocks [Reference Brualdi and Dahl5].

Lemma 4.3. If $A=A_1\oplus \cdots \oplus A_m$ upper A equals upper A 1 circled plus midline horizontal ellipsis circled plus upper A Subscript m , then

$$ \begin{align*} \mathrm{maxtrace}(A)=\sum_k\mathrm{maxtrace}(A_k),\quad \|A\|_{\mathrm F}^2=\sum_k\|A_k\|_{\mathrm F}^2. \end{align*} $$ StartLayout 1st Row maxtrace left parenthesis upper A right parenthesis equals sigma summation Underscript k Endscripts maxtrace left parenthesis upper A Subscript k Baseline right parenthesis comma StartMetric upper A EndMetric Subscript normal upper F Superscript 2 Baseline equals sigma summation Underscript k Endscripts StartMetric upper A Subscript k Baseline EndMetric Subscript normal upper F Superscript 2 Baseline period EndLayout

Hence, A is Erdős if and only if every $A_k$ upper A Subscript k is Erdős.

Proof. The norm identity is immediate. Maximising separately in each block gives one inequality. Conversely, any permutation of A selects a partial matching in each block; extending it to a permutation of the full row and column index sets of that block cannot decrease its weight, since the entries are nonnegative. Thus, its contribution from $A_k$ upper A Subscript k is at most $\mathrm {maxtrace}(A_k)$ maxtrace left parenthesis upper A Subscript k Baseline right parenthesis . The last assertion follows from (1.1) applied blockwise.

Theorem 4.4. Let $PAQ{\kern-1pt}={\kern-1pt}A_1\oplus \cdots \oplus A_m$ upper P upper A upper Q equals upper A 1 circled plus midline horizontal ellipsis circled plus upper A Subscript m be the above decomposition and ${S_k{\kern-1pt}={\kern-1pt}\mathrm {skel}(A_k)}$ upper S Subscript k Baseline equals skel left parenthesis upper A Subscript k Baseline right parenthesis . For each k, let $u^{(k)},v^{(k)}$ u Superscript left parenthesis k right parenthesis Baseline comma v Superscript left parenthesis k right parenthesis solve (2.3) for $S_k$ upper S Subscript k . Then, A is Erdős if and only if, for every k,

$$ \begin{align*} (A_k)_{ij}=(u_i^{(k)}+v_j^{(k)})(S_k)_{ij}\quad\text{for all }i,j, \quad\text{and}\quad \min_i u_i^{(k)}+\min_jv_j^{(k)}\geq0. \end{align*} $$ left parenthesis upper A Subscript k Baseline right parenthesis Subscript i j Baseline equals left parenthesis u Subscript i Superscript left parenthesis k right parenthesis Baseline plus v Subscript j Superscript left parenthesis k right parenthesis Baseline right parenthesis left parenthesis upper S Subscript k Baseline right parenthesis Subscript i j Baseline for all i comma j comma and min Underscript i Endscripts u Subscript i Superscript left parenthesis k right parenthesis Baseline plus min Underscript j Endscripts v Subscript j Superscript left parenthesis k right parenthesis Baseline greater than or equals 0 period

Proof. If A is Erdős, Lemma 4.3 makes every $A_k$ upper A Subscript k Erdős and Proposition 2.3, together with Theorem 3.1, gives the stated conditions.

Conversely, the first condition gives the additive representation of each $A_k$ upper A Subscript k , so Lemma 2.1 shows that $A_k$ upper A Subscript k is RCDS. The second condition and Theorem 3.1 then make each $A_k$ upper A Subscript k Erdős, and Lemma 4.3 completes the proof.

5 Examples and consequences

Consider the matrix

$$ \begin{align*} E=\frac1{16} \begin{pmatrix} 0&11&5&0&0\\ 0&0&5&0&11\\ 10&0&6&0&0\\ 3&0&0&8&5\\ 3&5&0&8&0 \end{pmatrix}, \end{align*} $$ upper E equals one sixteenth Start 5 By 5 Matrix 1st Row 1st Column 0 2nd Column 11 3rd Column 5 4th Column 0 5th Column 0 2nd Row 1st Column 0 2nd Column 0 3rd Column 5 4th Column 0 5th Column 11 3rd Row 1st Column 10 2nd Column 0 3rd Column 6 4th Column 0 5th Column 0 4th Row 1st Column 3 2nd Column 0 3rd Column 0 4th Column 8 5th Column 5 5th Row 1st Column 3 2nd Column 5 3rd Column 0 4th Column 8 5th Column 0 EndMatrix comma

whose row and column sums are all equal to $1$ 1 , and whose skeleton is

$$ \begin{align*} S= \begin{pmatrix} 0&1&1&0&0\\ 0&0&1&0&1\\ 1&0&1&0&0\\ 1&0&0&1&1\\ 1&1&0&1&0 \end{pmatrix}. \end{align*} $$ upper S equals Start 5 By 5 Matrix 1st Row 1st Column 0 2nd Column 1 3rd Column 1 4th Column 0 5th Column 0 2nd Row 1st Column 0 2nd Column 0 3rd Column 1 4th Column 0 5th Column 1 3rd Row 1st Column 1 2nd Column 0 3rd Column 1 4th Column 0 5th Column 0 4th Row 1st Column 1 2nd Column 0 3rd Column 0 4th Column 1 5th Column 1 5th Row 1st Column 1 2nd Column 1 3rd Column 0 4th Column 1 5th Column 0 EndMatrix period

One checks directly that S has no all-zero submatrix of size $r\times s$ r times s with $r+s=5$ r plus s equals 5 , so S is fully indecomposable. A solution of the system (2.3) is given by

$$ \begin{align*} u=\bigg(0,\ 0,\ \frac1{16},\ -\frac38,\ -\frac38\bigg), \quad v=\bigg(\frac9{16},\ \frac{11}{16},\ \frac5{16},\ \frac78,\ \frac{11}{16}\bigg). \end{align*} $$ u equals left parenthesis 0 comma 0 comma one sixteenth comma minus three eighths comma minus three eighths right parenthesis comma v equals left parenthesis nine sixteenths comma StartFraction 11 Over 16 EndFraction comma five sixteenths comma seven eighths comma StartFraction 11 Over 16 EndFraction right parenthesis period

Every cross-sum at a support position is positive and reproduces the corresponding entry,

$$ \begin{align*} e_{ij}=u_i+v_j>0 \quad (s_{ij}=1), \end{align*} $$ e Subscript i j Baseline equals u Subscript i Baseline plus v Subscript j Baseline greater than 0 left parenthesis s Subscript i j Baseline equals 1 right parenthesis comma

so E is RCDS by Lemma 2.1. At two of the zero positions, however,

(5.1) $$ \begin{align} u_4+v_3=u_5+v_3=-\frac1{16}<0 \end{align} $$ u 4 plus v 3 equals u 5 plus v 3 equals negative one sixteenth less than 0

and Theorem 3.1 shows at once that E is not an Erdős matrix.

Proposition 3.4 converts either violation into an explicit permutation. Starting from the zero position $(4,3)$ left parenthesis 4 comma 3 right parenthesis and the inner permutation $(2,3,1,5,4)$ left parenthesis 2 comma 3 comma 1 comma 5 comma 4 right parenthesis , the construction returns

$$ \begin{align*} \sigma=(2,5,1,3,4) \end{align*} $$ sigma equals left parenthesis 2 comma 5 comma 1 comma 3 comma 4 right parenthesis

in one-line notation, which uses the position $(4,3)$ left parenthesis 4 comma 3 right parenthesis and no other zero position. Its diagonal sum is

$$ \begin{align*} \sum_i e_{i,\sigma(i)}=\frac{11+11+10+0+8}{16}=\frac{5}{2}, \end{align*} $$ sigma summation Underscript i Endscripts e Subscript i comma sigma left parenthesis i right parenthesis Baseline equals StartFraction 11 plus 11 plus 10 plus 0 plus 8 Over 16 EndFraction equals five halves comma

whereas

$$ \begin{align*} \|E\|_{\mathrm{F}}^{2}=\frac{39}{16}. \end{align*} $$ StartMetric upper E EndMetric Subscript normal upper F Superscript 2 Baseline equals StartFraction 39 Over 16 EndFraction period

The excess is

$$ \begin{align*} \sum_i e_{i,\sigma(i)}-\|E\|_{\mathrm{F}}^{2}=\frac1{16}=-(u_4+v_3), \end{align*} $$ sigma summation Underscript i Endscripts e Subscript i comma sigma left parenthesis i right parenthesis Baseline minus StartMetric upper E EndMetric Subscript normal upper F Superscript 2 Baseline equals one sixteenth equals minus left parenthesis u 4 plus v 3 right parenthesis comma

exactly as predicted by (3.4).

5.1 Adding one support entry can destroy the property

Call a zero–one matrix an Erdős skeleton if it is the skeleton of an Erdős matrix.

The class of Erdős skeletons is not upward closed.

Proposition 5.1. There are fully indecomposable zero–one matrices $S<S'$ upper S less than upper S prime such that $S'$ upper S prime is obtained from S by changing a single $0$ 0 into a $1$ 1 , S is an Erdős skeleton and $S'$ upper S prime is not.

Proof. Take

$$ \begin{align*} S=\begin{pmatrix} 0&1&1&1\\1&0&0&1\\1&0&1&0\\1&1&0&0 \end{pmatrix},\quad S'=\begin{pmatrix} 1&1&1&1\\1&0&0&1\\1&0&1&0\\1&1&0&0 \end{pmatrix}. \end{align*} $$ upper S equals Start 4 By 4 Matrix 1st Row 1st Column 0 2nd Column 1 3rd Column 1 4th Column 1 2nd Row 1st Column 1 2nd Column 0 3rd Column 0 4th Column 1 3rd Row 1st Column 1 2nd Column 0 3rd Column 1 4th Column 0 4th Row 1st Column 1 2nd Column 1 3rd Column 0 4th Column 0 EndMatrix comma upper S prime equals Start 4 By 4 Matrix 1st Row 1st Column 1 2nd Column 1 3rd Column 1 4th Column 1 2nd Row 1st Column 1 2nd Column 0 3rd Column 0 4th Column 1 3rd Row 1st Column 1 2nd Column 0 3rd Column 1 4th Column 0 4th Row 1st Column 1 2nd Column 1 3rd Column 0 4th Column 0 EndMatrix period

Both are fully indecomposable. For S, the potentials

$$ \begin{align*} u=\bigg(0,\frac13,\frac13,\frac13\bigg),\quad v=\bigg(0,\frac13,\frac13,\frac13\bigg) \end{align*} $$ u equals left parenthesis 0 comma one third comma one third comma one third right parenthesis comma v equals left parenthesis 0 comma one third comma one third comma one third right parenthesis

solve (2.3); they are positive on the support and all cross-sums are nonnegative, so S is an Erdős skeleton by Theorem 4.1. Passing from S to $S'$ upper S prime increases only the first row and column degrees. Since $u_1+v_1=0$ u 1 plus v 1 equals 0 , the same $u,v$ u comma v still solve (2.3) for $S'$ upper S prime . However, now $(1,1)$ left parenthesis 1 comma 1 right parenthesis belongs to the support and its cross-sum is $0$ 0 , violating the strict positivity required in Theorem 4.1. Thus, $S'$ upper S prime is not an Erdős skeleton.

6 Conclusion

The characterisation obtained above reduces Erdős-ness to a linear-algebraic sign test on the fully indecomposable blocks of the skeleton. In particular, it replaces the global maxtrace condition by the local requirement that all cross-sums $u_i+v_j$ u Subscript i Baseline plus v Subscript j are nonnegative, and a negative cross-sum yields an explicit permutation witnessing the failure of equality in the Marcus–Ree inequality.

Acknowledgements

The author is grateful to L. Bouthat, J. Mashreghi and S. Singh for previous collaborations.

References

Achilles, E., ‘Doubly stochastic matrices with some equal diagonal sums’, Linear Algebra Appl. 22 (1978), 293–296.10.1016/0024-3795(78)90079-4CrossRefGoogle Scholar
Balasubramanian, K., ‘On equality of some elements in matrices’, Linear Algebra Appl. 22 (1978), 135–138.10.1016/0024-3795(78)90064-2CrossRefGoogle Scholar
Balasubramanian, K., ‘Maximal diagonal sums’, Linear Multilinear Algebra 7 (1979), 249–251.10.1080/03081087908817282CrossRefGoogle Scholar
Bouthat, L., Mashreghi, J. and Morneau-Guérin, F., ‘On a question of Erdős on doubly stochastic matrices’, Linear Multilinear Algebra 72 (2024), 2823–2844.10.1080/03081087.2023.2300674CrossRefGoogle Scholar
Brualdi, R. A. and Dahl, G., ‘Diagonal sums of doubly stochastic matrices’, Linear Multilinear Algebra 70 (2022), 4946–4972.10.1080/03081087.2021.1901844CrossRefGoogle Scholar
Karmakar, P., Krishna, H., Pal, S. and Krishna Teja, G., ‘Characterization of Erdős matrices by their zero entries’, Linear Algebra Appl. 739 (2026), 154–169.10.1016/j.laa.2026.03.010CrossRefGoogle Scholar
Kushwaha, A. and Tripathi, R., ‘A note on Erdős matrices and Marcus–Ree inequality’, Linear Algebra Appl. 725 (2025), 223–247.10.1016/j.laa.2025.07.012CrossRefGoogle Scholar
Marcus, M. and Ree, R., ‘Diagonals of doubly stochastic matrices’, Q. J. Math. 10 (1959), 296–302.10.1093/qmath/10.1.296CrossRefGoogle Scholar
Sinkhorn, R., ‘Doubly stochastic matrices which have certain diagonals with constant sums’, Linear Algebra Appl. 16 (1977), 79–82.10.1016/0024-3795(77)90021-0CrossRefGoogle Scholar
Tripathi, R., ‘Some observations on Erdős matrices’, Linear Algebra Appl. 708 (2025), 236–251.10.1016/j.laa.2024.12.002CrossRefGoogle Scholar
Wang, E. T.-H., ‘Maximum and minimum diagonal sums of doubly stochastic matrices’, Linear Algebra Appl. 8 (1974), 483–505.10.1016/0024-3795(74)90083-4CrossRefGoogle Scholar