To save content items to your account,
please confirm that you agree to abide by our usage policies.
If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account.
Find out more about saving content to .
To save content items to your Kindle, first ensure no-reply@cambridge.org
is added to your Approved Personal Document E-mail List under your Personal Document Settings
on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part
of your Kindle email address below.
Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations.
‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi.
‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Let $\mathbb {F}$ be either $\mathbb {R}$ or $\mathbb {C}$, and put $d_{\mathbb {F}}=\dim _{\mathbb {R}}\mathbb {F}$. Let $A_m\in \mathbb {F}^{N_m\times m}$ have independent standard Gaussian entries and assume $N_m/m\to \gamma>1$. We determine the exponential scale of the smallest least singular value among all square row submatrices:
With $c_\gamma =\gamma ^\gamma /(\gamma -1)^{\gamma -1}$, we prove $m^{-1}\log M_m^{\mathbb {F}}\xrightarrow {P}-d_{\mathbb {F}}^{-1}\log c_\gamma $ and, when $N_m=\gamma m+O(1)$, the convergence holds at rate $O(m^{-1})$. As an application, for real phase retrieval at the critical number $N=2m-1$ of measurements, the Balan–Wang stability parameter satisfies $\omega (A_m)=4^{-m+o_P(m)}$, so the sharp exponential base in the Gaussian Balan–Wang problem is $1/4$. The lower estimate extends to all bounded-density ensembles and continuity is necessary.
The circular $\beta $ ensemble for $\beta =1,2$ and 4 corresponds to circular orthogonal, unitary and symplectic ensemble respectively as introduced by Dyson. The statistical state of the eigenvalues is then a determinantal point process ($\beta = 2$) and Pfaffian point process ($\beta = 1,4$). The explicit functional forms of the correlation kernels then imply that the general n-point correlation functions exhibit an asymptotic expansion in $1/N^2$, which moreover can be lifted to an asymptotic expansion in $1/N^2$ for the spacing distributions and their generating function. We use $\sigma $-Painlevé characterisations to show that the functional form of the first correction is related to the leading term via a second derivative. In the case $\beta = 2$ this finding has immediate consequences in interpreting the empirical Riemann zeros spacing distribution at large height, and that of their thinning. Explicit functional forms are used to show that the spectral form factors for $\beta =1,2$ and 4 also admit an asymptotic expansion in $1/N^2$. Differential relations are identified expressing the first and second correction in terms of the limiting functional form, and evidence is presented that they hold for general $\beta $. For even $\beta $ it is proved that the two-point correlation function permits an asymptotic expansion in $1/N^2$, and moreover that the leading correction relates to the limiting functional form via a second derivative.
We consider random lower triangular matrices such that the entries on and below the diagonal are i.i.d. copies of some $\mathbb{Z}$-valued random variable. We prove that the Sylow $p$-subgroups of the cokernels of these matrices have the same constant order fluctuations as those of the matrix products studied by Nguyen and Van Peski. Unlike for matrix products, for triangular matrices, the law of the limiting fluctuations depends slightly on the distribution of the entries. As a special case, we can describe the limiting fluctuations of the rank of lower triangular matrices over $\mathbb{F}_p$ with i.i.d. random entries on and below the diagonal.
We consider the Brown measure of $a+\mathfrak {c}$, where a lies in a commutative tracial von Neumann algebra $\mathcal {B}$ and $\mathfrak {c}$ is a $\mathcal {B}$-valued circular element. Under certain regularity conditions on a and the covariance of $\mathfrak {c}$ this Brown measure has a density with respect to the Lebesgue measure on the complex plane which is real analytic apart from jump discontinuities at the boundary of its support. With the exception of finitely many singularities this one-dimensional spectral edge is real analytic. We provide a full description of all possible edge singularities as well as all points in the interior, where the density vanishes. The edge singularities are classified in terms of their local edge shape while internal zeros of the density are classified in terms of the shape of the density locally around these points. We also show that each of these countably infinitely many singularity types occurs for an appropriate choice of a when $\mathfrak {c}$ is a standard circular element. The Brown measure of $a+\mathfrak {c}$ arises as the empirical spectral distribution of a diagonally deformed non-Hermitian random matrix with independent entries when its dimension tends to infinity.
This paper is concerned with the study of random (Bernoulli and Markovian) products of matrices on a compact space of symbols. We establish the analyticity of the maximal Lyapunov exponent as a function of the transition probabilities, thus extending the results and methods of Y. Peres from a finite to an infinite (but compact) space of symbols. Our approach combines the spectral properties of the associated Markov operator with the theory of holomorphic functions in Banach spaces.
We investigate the limiting spectral distribution of a noncentral unified matrix model defined by $\boldsymbol{\Omega}(\mathbf{X}) = ({(\mathbf{X}\mathbf{P}_1+\mathbf{A})(\mathbf{X}\mathbf{P}_1+\mathbf{A})'}/{n_1}) ({\mathbf{X}\mathbf{P}_2\mathbf{X}'}/{n_2})^{-1}$, where $\mathbf{X}=(X_{ij})_{p\times n}$ is a random matrix with independent and identically distributed real entries having zero mean and finite second moment. $\mathbf{A}$ is a $p\times n$ nonrandom matrix. The matrices $\mathbf{P}_1$ and $\mathbf{P}_2$ are projection matrices satisfying $\mathrm{rank}(\mathbf{P}_1)=n_1$, $\mathrm{rank}(\mathbf{P}_2)=n_2$, and $\mathbf{P}_1\mathbf{P}_2=0$. When $\mathbf{P}_1$ and $\mathbf{P}_2$ are random, they are assumed to be independent of $\mathbf{X}$. When $p/n_1\to c_1\in(0,\infty)$ and $p/n_2\to c_2\in(0,1)$, we establish the almost sure convergence of the empirical spectral distribution of $\boldsymbol{\Omega}$ to a deterministic limiting distribution. Furthermore, we show that this limiting distribution coincides with that of the noncentral F-matrix, thus revealing a deep connection between the proposed model and classical multivariate analysis.
In recent works on the theory of machine learning, it has been observed that heavy tail properties of stochastic gradient descent (SGD) can be studied in the probabilistic framework of stochastic recursions. In particular, Gürbüzbalaban et al. (2021) considered a setup corresponding to linear regression for which iterations of SGD can be modelled by a multivariate affine stochastic recursion $X_n=A_nX_{n-1}+B_n$ for independent and identically distributed pairs $(A_n,B_n)$, where $A_n$ is a random symmetric matrix and $B_n$ is a random vector. However, their approach is not completely correct and, in the present paper, the problem is put into the right framework by applying the theory of irreducible-proximal matrices.
We consider a family $b_{s,\tau }$ of free multiplicative Brownian motions labeled by a real variance parameter s and a complex covariance parameter $\tau $. We then consider the element $xb_{s,\tau }$, where x is non-negative and freely independent of $b_{s,\tau }$. Our goal is to identify the support of the Brown measure of $xb_{s,\tau }$. In the case $\tau =s$, we identify a region $\Sigma _s$ such that the Brown measure is vanishing outside of $\overline {\Sigma }_s$ except possibly at the origin. For general values of $\tau $, we construct a map $f_{s-\tau }$ and define $D_{s,\tau }$ as the complement of $f_{s-\tau }(\overline {\Sigma }_s^c)$. Then, the Brown measure is zero outside $D_{s,\tau }$ except possibly at the origin. The proof of these results is based on a two-stage PDE analysis, using one PDE (following the work of Driver, Hall, and Kemp) for the case $\tau =s$ and a different PDE (following the work of Hall and Ho) to deform the $\tau =s$ case to general values of $\tau $.
For each of the four particle processes given by Dieker and Warren, we show the n-step transition kernels are given by the (dual) (weak) refined symmetric Grothendieck functions up to a simple overall factor. We do so by encoding the particle dynamics as the basis of free fermions first introduced by the first author, which we translate into deformed Schur operators acting on partitions. We provide a direct combinatorial proof of this relationship in each case, where the defining tableaux naturally describe the particle motions.
We provide a complete characterization of theories of tracial von Neumann algebras that admit quantifier elimination. We also show that the theory of a separable tracial von Neumann algebra $\mathcal {M}$ is never model complete if its direct integral decomposition contains $\mathrm {II}_1$ factors $\mathcal {N}$ such that $M_2(\mathcal {N})$ embeds into an ultrapower of $\mathcal {N}$. The proof in the case of $\mathrm {II}_1$ factors uses an explicit construction based on random matrices and quantum expanders.
We introduce a family of polynomials, which arise in three distinct ways: in the large N expansion of a matrix integral, as a weighted enumeration of factorizations of permutations, and via the topological recursion. More explicitly, we interpret the complex Grassmannian $\mathrm {Gr}(M,N)$ as the space of $N \times N$ idempotent Hermitian matrices of rank M and develop a Weingarten calculus to integrate products of matrix elements over it. In the regime of large N and fixed ratio $\frac {M}{N}$, such integrals have expansions whose coefficients count factorizations of permutations into monotone sequences of transpositions, with each sequence weighted by a monomial in $t = 1 - \frac {N}{M}$. This gives rise to the desired polynomials, which specialise to the monotone Hurwitz numbers when $t = 1$. These so-called deformed monotone Hurwitz numbers satisfy a cut-and-join recursion, a one-point recursion, and the topological recursion. Furthermore, we conjecture on the basis of overwhelming empirical evidence that the deformed monotone Hurwitz numbers are real-rooted polynomials whose roots satisfy remarkable interlacing phenomena. An outcome of our work is the viewpoint that the topological recursion can be used to “topologise” sequences of polynomials, and we claim that the resulting families of polynomials may possess interesting properties.
Given a word $w(x_{1},\ldots,x_{r})$, i.e. an element in the free group on r elements, and an integer $d\geq1$, we study the characteristic polynomial of the random matrix $w(X_{1},\ldots,X_{r})$, where $X_{i}$ are Haar-random independent $d\times d$ unitary matrices. If $c_{m}(X)$ denotes the mth coefficient of the characteristic polynomial of X, our main theorem implies that there is a positive constant $\epsilon(w)$, depending only on w, such that
for every d and every $1\leq m\leq d$. Our main computational tool is the Weingarten calculus, which allows us to express integrals on unitary groups such as the expectation above, as certain sums on symmetric groups. We exploit a hidden symmetry to find cancellations in the sum expressing $\mathbb{E}(c_{m}(w))$. These cancellations, coming from averaging a Weingarten function over cosets, follow from Schur’s orthogonality relations.
We compute the large size limit of the moment formula derived in [14] for the Hermitian Jacobi process at fixed time. Our computations rely on the polynomial division algorithm which allows to obtain cancellations similar to those obtained in [3, Lemma 3]. In particular, we identify the terms contributing to the limit and show they satisfy a double recurrence relation. We also determine explicitly some of them and revisit a special case relying on Carlitz summation identity for terminating $1$-balanced ${}_4F_3$ functions taken at unity.
We consider uniformly random lozenge tilings of simply connected polygons subject to a technical assumption on their limit shape. We show that the edge statistics around any point on the arctic boundary, that is not a cusp or tangency location, converge to the Airy line ensemble. Our proof proceeds by locally comparing these edge statistics with those for a random tiling of a hexagon, which are well understood. To realize this comparison, we require a nearly optimal concentration estimate for the tiling height function, which we establish by exhibiting a certain Markov chain on the set of all tilings that preserves such concentration estimates under its dynamics.
This paper considers the large N limit of Wilson loops for the two-dimensional Euclidean Yang–Mills measure on all orientable compact surfaces of genus larger or equal to $1$, with a structure group given by a classical compact matrix Lie group. Our main theorem shows the convergence of all Wilson loops in probability, given that it holds true on a restricted class of loops, obtained as a modification of geodesic paths. Combined with the result of [20], a corollary is the convergence of all Wilson loops on the torus. Unlike the sphere case, we show that the limiting object is remarkably expressed thanks to the master field on the plane defined in [3, 39], and we conjecture that this phenomenon is also valid for all surfaces of higher genus. We prove that this conjecture holds true whenever it does for the restricted class of loops of the main theorem. Our result on the torus justifies the introduction of an interpolation between free and classical convolution of probability measures, defined with the free unitary Brownian motion but differing from t-freeness of [5] that was defined in terms of the liberation process of Voiculescu [67]. In contrast to [20], our main tool is a fine use of Makeenko–Migdal equations, proving uniqueness of their solution under suitable assumptions, and generalising the arguments of [21, 33].
We establish a Central Limit Theorem for tensor product random variables $c_k:=a_k \otimes a_k$, where $(a_k)_{k \in \mathbb {N}}$ is a free family of variables. We show that if the variables $a_k$ are centered, the limiting law is the semi-circle. Otherwise, the limiting law depends on the mean and variance of the variables $a_k$ and corresponds to a free interpolation between the semi-circle law and the classical convolution of two semi-circle laws.
We introduce a modification of the generalized Pólya urn model containing two urns, and we study the number of balls $B_j(n)$ of a given color $j\in\{1,\ldots,J\}$ added to the urns after n draws, where $J\in\mathbb{N}$. We provide sufficient conditions under which the random variables $(B_j(n))_{n\in\mathbb{N}}$, properly normalized and centered, converge weakly to a limiting random variable. The result reveals a similar trichotomy as in the classical case with one urn, one of the main differences being that in the scaling we encounter 1-periodic continuous functions. Another difference in our results compared to the classical urn models is that the phase transition of the second-order behavior occurs at $\sqrt{\rho}$ and not at $\rho/2$, where $\rho$ is the dominant eigenvalue of the mean replacement matrix.
The walk matrix associated to an $n\times n$ integer matrix $\mathbf{X}$ and an integer vector $b$ is defined by ${\mathbf{W}} \,:\!=\, (b,{\mathbf{X}} b,\ldots, {\mathbf{X}}^{n-1}b)$. We study limiting laws for the cokernel of $\mathbf{W}$ in the scenario where $\mathbf{X}$ is a random matrix with independent entries and $b$ is deterministic. Our first main result provides a formula for the distribution of the $p^m$-torsion part of the cokernel, as a group, when $\mathbf{X}$ has independent entries from a specific distribution. The second main result relaxes the distributional assumption and concerns the ${\mathbb{Z}}[x]$-module structure.
The motivation for this work arises from an open problem in spectral graph theory, which asks to show that random graphs are often determined up to isomorphism by their (generalised) spectrum. Sufficient conditions for generalised spectral determinacy can, namely, be stated in terms of the cokernel of a walk matrix. Extensions of our results could potentially be used to determine how often those conditions are satisfied. Some remaining challenges for such extensions are outlined in the paper.
We consider the community detection problem in sparse random hypergraphs under the non-uniform hypergraph stochastic block model (HSBM), a general model of random networks with community structure and higher-order interactions. When the random hypergraph has bounded expected degrees, we provide a spectral algorithm that outputs a partition with at least a $\gamma$ fraction of the vertices classified correctly, where $\gamma \in (0.5,1)$ depends on the signal-to-noise ratio (SNR) of the model. When the SNR grows slowly as the number of vertices goes to infinity, our algorithm achieves weak consistency, which improves the previous results in Ghoshdastidar and Dukkipati ((2017) Ann. Stat.45(1) 289–315.) for non-uniform HSBMs.
Our spectral algorithm consists of three major steps: (1) Hyperedge selection: select hyperedges of certain sizes to provide the maximal signal-to-noise ratio for the induced sub-hypergraph; (2) Spectral partition: construct a regularised adjacency matrix and obtain an approximate partition based on singular vectors; (3) Correction and merging: incorporate the hyperedge information from adjacency tensors to upgrade the error rate guarantee. The theoretical analysis of our algorithm relies on the concentration and regularisation of the adjacency matrix for sparse non-uniform random hypergraphs, which can be of independent interest.
We derive a sufficient condition for a sparse random matrix with given numbers of non-zero entries in the rows and columns having full row rank. The result covers both matrices over finite fields with independent non-zero entries and $\{0,1\}$-matrices over the rationals. The sufficient condition is generally necessary as well.