Some observations on Erdős matrices
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913610537631744 |
|---|---|
| author | Tripathi, Raghavendra |
| author_facet | Tripathi, Raghavendra |
| contents | In a seminal paper in 1959, Marcus and Ree proved that every $n\times n$ bistochastic matrix $A$ satisfies $\|A\|_{\operatorname{F}}^2\leq \max_{σ\in S_n}A_{i,σ(i)}$ where $S_n$ is the symmetric group on $\{1, \ldots, n\}$. Erdős asked to characterize the bistochastic matrices for which the equality holds in the Marcus--Ree inequality. We refer to such matrices as Erdős matrices. While this problem is trivial in dimension $n=2$, the case of dimension $n=3$ was only resolved recently in~\cite{bouthat2024question} in 2023. We prove that for every $n$, there are only finitely many $n\times n$ Erdős matrices. We also give a characterization of Erdős matrices that yields an algorithm to generate all Erdős matrices in any given dimension. We also prove that Erdős matrices can have only rational entries. This answers a question of~\cite{bouthat2024question}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06612 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Some observations on Erdős matrices Tripathi, Raghavendra Metric Geometry Probability 15A15, 15A45, 15B36, 15B51 In a seminal paper in 1959, Marcus and Ree proved that every $n\times n$ bistochastic matrix $A$ satisfies $\|A\|_{\operatorname{F}}^2\leq \max_{σ\in S_n}A_{i,σ(i)}$ where $S_n$ is the symmetric group on $\{1, \ldots, n\}$. Erdős asked to characterize the bistochastic matrices for which the equality holds in the Marcus--Ree inequality. We refer to such matrices as Erdős matrices. While this problem is trivial in dimension $n=2$, the case of dimension $n=3$ was only resolved recently in~\cite{bouthat2024question} in 2023. We prove that for every $n$, there are only finitely many $n\times n$ Erdős matrices. We also give a characterization of Erdős matrices that yields an algorithm to generate all Erdős matrices in any given dimension. We also prove that Erdős matrices can have only rational entries. This answers a question of~\cite{bouthat2024question}. |
| title | Some observations on Erdős matrices |
| topic | Metric Geometry Probability 15A15, 15A45, 15B36, 15B51 |
| url | https://arxiv.org/abs/2410.06612 |