Skip to content
Preprint

The Maximum Diagonal Product of a Stochastic Matrix of Bounded Rank

Nov 2026 · 0 citations · 6 references
Mathematics

Abstract

Let $A=(a_{ij})$ be a nonnegative row-stochastic or column-stochastic $n\times n$ matrix of rank at most $k$, where $1\le k\le n$. Write $n=qk+s$, where $0\le s<k$. The author conjectured in 2018 that, for every permutation $\sigma$ of $\{1,\ldots,n\}$, $\prod_{i=1}^n a_{i,\sigma(i)}\le q^{-q(k-s)}(q+1)^{-(q+1)s}$. We prove this bound and classify all equality cases.

View source

Similar papers

Preprint Sep 2026

Exponent Profiles of Oscillatory Matrices under Matrix and Inverse Sparsity

We classify the simultaneous half-bandwidths $p,q$ of a symmetric oscillatory matrix $A$ and its inverse. At order $n\ge2$, the possible pairs are $(1,n-1)$, $(n-1,1)$, and all pairs with $2\le p,q\le n-1$. Let $e_k(A)$ be the least positive integer $m$ for which all minors of order $k$ of $A^m$ are positive, and let $...

Wei Xie · 0 citations
Preprint Oct 2026

An upper bound on the smallest singular value of dense signed random combinatorial matrices

Let $M_n$ be an $n\times n$ random matrix with entries in $\{-1, 0, 1\}$, where each row is independently and uniformly sampled from the set of all vectors in $\{-1, 0, 1\}^n$ containing exactly $d$ nonzero entries, with $d=pn$ for some fixed constant $p\in(0,1/2]$. A recent result by one of the authors gives a lower b...

Yu-Xiao Shi, Ze-Yan Song, Ke-Xin Yu et al. · 1 citation
Open access Oct 2026

The norm of the symmetric product of tensors and its applications to permanents

Let $A$ be an $np \times np$ positive semidefinite matrix partitioned into $p \times p$ blocks $A_{ij}$, and $P$ be the $n \times n$ matrix with $p_{ij} = {\rm per}(A_{ij})$. Marcus conjectures in 1965 that ${\rm per}(A) \geq {\rm per}(P)$, which remains open in general. In this paper, we prove a generalized Neuberger...

Evaristo José Das Mangas, Henrique F. da Cruz · 0 citations
Preprint Oct 2026

Rank and Invertibility of Dense Signed Random Regular Matrices

Let $A$ be the (non-symmetric) adjacency matrix of a uniformly random $d$-regular directed graph on $n$ vertices, and let $\Xi$ be independent of $A$ with i.i.d. Rademacher entries. Suppose that $\min(d,n-d)\ge\lambda n$ for some fixed $\lambda\in(0,1/2]$. We show that there exists $c>0$, depending only on $\lambda$, s...

Huai-Jin Liang, Yu-Xiao Shi, Ke-Xin Yu et al. · 1 citation
Preprint Oct 2026

The smallest singular value of products of random combinatorial and deterministic matrices

Let $p\in(0,1/2]$ be fixed, and let $d,n$ be positive integers satisfying $d=pn$. Let $Q_n$ be an $n\times n$ random combinatorial matrix whose rows are independent and uniformly distributed over the vectors in $\{0,1\}^n$ having exactly $d$ ones. For an arbitrary deterministic invertible $n\times n$ matrix $M$, we est...

Yu-Xiao Shi, Ke-Xin Yu, Ting-Zhou Yu · 0 citations
Preprint Sep 2026

Extremal numbers of acyclic matrices

For a zero-one matrix $P$, let $\operatorname{Ex}(n,P)$ denote the maximum number of ones in an $n\times n$ zero-one matrix avoiding $P$. We prove that $$\operatorname{Ex}(n,P) \leq n^{1+O_P(1/\log\log n)}$$ for every acyclic $P$, settling the weak form of the Pach-Tardos conjecture.

Lior Gishboliner, Xiang-Yu Li · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.