Questions tagged [random-matrices]

Statistics of spectral properties of matrix-valued random variables.

Filter by
Sorted by
Tagged with
42 votes
3 answers
5k views

The probability for a symmetric matrix to be positive definite

Let me give a reasonable model for the question in the title. In ${\rm Sym}_n({\mathbb R})$, the positive definite matrices form a convex cone $S_n^+$. The probability I have in mind is the ratio $p_n=...
Denis Serre's user avatar
  • 51.5k
23 votes
7 answers
15k views

Expected determinant of a random NxN matrix

What is the expected value of the determinant over the uniform distribution of all possible 1-0 NxN matrices? What does this expected value tend to as the matrix size N approaches infinity?
Jason Knight's user avatar
7 votes
1 answer
833 views

Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s

Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
Tony's user avatar
  • 272
24 votes
1 answer
3k views

What kind of random matrices have rapidly decaying singular values?

I've been told that in machine learning it's common to compute the singular value decomposition of matrices in order to throw out all information in the matrix except that corresponding to, say, the $...
Qiaochu Yuan's user avatar
7 votes
2 answers
5k views

Distribution of dot product of two unit random vectors

Consider $\mathbf{u}, \mathbf{v}\in \mathcal{C}^M$ to be two independent unit norm random vectors on the $M-1$ dimensional complex sphere $\mathcal{S}^{M-1}$. In addition, $\mathbf{u}$ follows an ...
Allen's user avatar
  • 141
4 votes
1 answer
610 views

How to get the lower bound of the following $\tau$?

Let $A=\{a_{ij}\}_{1\le i,j\le n}$ be an $n$ by $n$ normalized Gaussian random matrix with $E[a_{ij}]=0$ and $E[a_{ij}^2]=1/n$. Ordering its eigenvalues by $\lambda_1\le \lambda_2\le \cdots \lambda_n$ ...
Hermi's user avatar
  • 274
44 votes
1 answer
5k views

Anti-concentration bound for permanents of Gaussian matrices?

In a recent paper with Alex Arkhipov on "The Computational Complexity of Linear Optics," we needed to assume a reasonable-sounding probabilistic conjecture: namely, that the permanent of a matrix of i....
Scott Aaronson's user avatar
39 votes
1 answer
5k views

When should we expect Tracy-Widom?

The Tracy-Widom law describes, among other things, the fluctuations of maximal eigenvalues of many random large matrix models. Because of its universal character, it obtained his position on the ...
Adrien Hardy's user avatar
  • 2,085
23 votes
2 answers
831 views

Moments of Plücker coordinates on complex Grassmannian

Consider the Grassmannian $Gr(k,N)\simeq U(N)/(U(k)\times U(N-k))$ which parametrizes $k$-dimensional subspaces of $\mathbb{C}^N$. Let us put on it the $U(N)$-invariant probability measure. Let $\...
Abdelmalek Abdesselam's user avatar
20 votes
3 answers
3k views

Jensen Polynomials for the Riemann Zeta Function

In the paper by Griffin, Ono, Rolen and Zagier which appeared on the arXiv today, (Update: published now in PNAS) the abstract includes In the case of the Riemann zeta function, this proves the ...
Stopple's user avatar
  • 10.8k
16 votes
5 answers
2k views

Expected value of determinant of simple infinite random matrix

Suppose we have a matrix $A \in \mathbb{R}^{n\times n}$ where $$A_{ij} = \begin{cases} 1 & \text{with probability} \quad p\\ 0 &\text{with probability} \quad1-p\end{cases}$$ I would like to ...
Hipstpaka's user avatar
  • 355
16 votes
1 answer
8k views

Intuitive understanding of the Stieltjes transform

I have been using random matrix theory in signal processing and have some trouble understanding what the Stieltjes transform does. The gist of my work is that I have an $N\times N$ true covariance ...
user avatar
7 votes
1 answer
2k views

Determinant of real Wishart matrix

Suppose $A$ is a real $N \times P$ matrix, $P \geq N$, with entries drawn independently according to $A_{ij} \sim \mathcal{N}(0,1)$. Then $W = A \, A^\top$ is a member of the real Wishart ensemble. ...
Latrace's user avatar
  • 73
4 votes
1 answer
396 views

Expected norms of Wishart matrices

Suppose $x_i \stackrel{\text{i.i.d}}{\sim} \mathcal{N}(\mu,\Sigma)$. What can we say about dependence on $b$ of Frobenius/spectral norm quantities below? $$f(b)=\left\|\frac{1}{b}\sum_{i=1}^b x_i x_i^...
Yaroslav Bulatov's user avatar
3 votes
2 answers
923 views

Expectation of the trace of inverse of a Gaussian random matrix

Given a $N×M$ random complex gaussian matrix $X$ and $N×K$ random complex gaussian matrix $Y$ I'm interested in approximating the expectation expressed as: \begin{align} E[trace({(aX{X^H} + I)^{ - ...
hichem hb's user avatar
  • 367
3 votes
1 answer
2k views

Singular value decomposition of random rectangular matrices

Let $A$ be a $m\times n$ real matrix, whose entries are independent, identically distributed random variables, following standard normal distributions (mean zero and unit variance). What is the ...
valle's user avatar
  • 864
1 vote
1 answer
937 views

Expected size of determinant of $AA^T$ for non-square random $A$

If $A$ is chosen uniformly at random over all possible $m \times n$ (0,1)-matrices, what is the expected size of the absolute value of the determinant of $AA^T$. We can assume $m < n$ and all ...
Simd's user avatar
  • 3,195
19 votes
1 answer
2k views

Smallest eigenvalue of a tricky random matrix

While experimenting with positive-definite functions, I was led to the following: Let $n$ be a positive integer, and let $x_1,\ldots,x_n$ be sampled from a zero-mean, unit variance gaussian. Consider ...
Suvrit's user avatar
  • 28.4k
18 votes
5 answers
3k views

Moments of the trace of orthogonal matrices

Let $O_n$ be the (real) orthogonal group of $n$ by $n$ matrices. I am interested in the following sequence which showed up in a calculation I was doing $$a_k = \int_{O_n} (\text{Tr } X)^k dX$$ where ...
J. E. Pascoe's user avatar
  • 1,429
18 votes
1 answer
1k views

How fast can extreme eigenvalues of the average of random matrices converge to their expectation?

Suppose that $X_1,X_2,\ldots,X_m$ are independent $d\times d$ random matrices and let $\overline{X} := \frac{1}{m}\sum_{i=1}^m X_i$. One of the questions studied under the theory of random matrices is ...
sbahmani's user avatar
  • 181
15 votes
0 answers
2k views

PT Symmetry and the Riemann Hypothesis

Recently there have been articles in Quanta, in Science Alert, and at phys.org among others, on possible recent progress toward the Hilbert-Polya conjecture, which implies the Riemann Hypothesis. The ...
Stopple's user avatar
  • 10.8k
14 votes
2 answers
2k views

What do we actually know about logarithmic energy ?

In potential theory, the $\textit{logarithmic energy}$ of a Radon measure $\mu$ acting on $\mathbb{C}$ is defined by $$I(\mu)=\iint\log\frac{1}{|x-y|}\mu(dx)\mu(dy).$$ Of course it is not well ...
Adrien Hardy's user avatar
  • 2,085
11 votes
1 answer
3k views

Matrix inversion lemma with pseudoinverses

The utility of the Matrix Inversion Lemma has been well-exploited for several questions on MO. Thus, with some positive hope, I'd like to field a question of my own. Suppose we pick $n$ values $x_1,\...
Suvrit's user avatar
  • 28.4k
11 votes
1 answer
615 views

A simple proof for a theorem of Szekeres and Turán

Szekeres and Turán found in 1937 a formula for the sum of the squares and the sum of the fourth powers of determinants of all $n$ by $n$ matrices with $\pm 1$ entries. (The sum of squares case follows ...
Gil Kalai's user avatar
  • 24.2k
10 votes
2 answers
1k views

Probability of random (0,1) Toeplitz matrix being invertible

A Toeplitz matrix or diagonal-constant matrix is a matrix in which each descending diagonal from left to right is constant. What is the probability that a random $n \times n$ binary Toeplitz ...
user avatar
10 votes
1 answer
436 views

Probability that a random distance function is metric

Take a random $n \times n$ nonnegative symmetric matrix $D$ with zero diagonal. What is the probability that it is an abstract distance matrix, i.e. satisfies $D_{xy}+D_{yz} \geq D_{xz}$ for all index ...
Felix Goldberg's user avatar
10 votes
1 answer
423 views

Complexity of the union of randomly rotated unit cubes

It is a remarkable fact that the union of congrent cubes has only at most near-quadratic combinatorial complexity, $O^*(n^2)$ for $n$ cubes, known to be almost tight. This contrasts with the union of ...
Joseph O'Rourke's user avatar
9 votes
2 answers
3k views

Eigenvalue densities of sample covariance matrices when the population covariance matrix is a perturbed identity matrix

TLDR: I'm looking for a random matrix theory reference for the eigenvalue densities of sample covariance matrices (both dimensions approaching infinity at the same rate) when the true (population) ...
user avatar
9 votes
1 answer
649 views

Scaling in Mehta's integral

The following expression is known as Mehta's integral and deeply connected to random matrix theory: $$\frac{1}{(2\pi)^{n/2}}\int_{-\infty}^{\infty} \cdots \int_{-\infty}^{\infty} \prod_{i=1}^n e^{-...
Pritam Bemis's user avatar
8 votes
0 answers
229 views

Decay of orthogonal contributions in a random set of vectors

Suppose we sample $k$ vectors $v$ from normal distribution centered at zero and diagonal covariance with diagonal entries $1,\frac{1}{2},\ldots,\frac{1}{d}$ and normalize $v$: $$\frac{v_1}{\|v_1\|},\...
Yaroslav Bulatov's user avatar
8 votes
2 answers
2k views

Expectation of trace of nth power of unitary matrices

I am trying to find the answer of $$\int dU \ |Tr(U^m)|^2$$ where $m\in\mathbb{N}$ and $U$'s are unitary matrices in $\textit{U}(n)$ and $dU$ is a normalized Haar measure. In the case $m=1$, the ...
Atnap's user avatar
  • 127
7 votes
1 answer
774 views

Trace of inverse of random positive-definite matrix in high dimension?

Consider a random matrix $A \in \mathbb{R}^{n\times n}$ with i.i.d. entries, with symmetric law and finite variance. I am curious about the behavior of $$\mathrm{Tr}( (A^T A + \lambda \mathrm{Id})^{-1}...
Goulifet's user avatar
  • 2,174
7 votes
2 answers
560 views

Generating function of $SO(N)$ random matrix

I am interested in the generating function of $SO(N)$ random matrix, that is, I want to compute $$ Z_N[J]=\int dM e^{{\rm Tr} (J^T M)}, $$ where $dM$ is the $SO(N)$ Haar measure, and $J$ is an ...
Adam's user avatar
  • 345
7 votes
4 answers
454 views

What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?

Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by $...
dohmatob's user avatar
  • 6,706
6 votes
1 answer
241 views

Upper bound for a Selberg-type integral over a rectangular region

(Cross-posted from math-SE). I am trying to estimate the values of the following integral for large $n$, $$\frac{1}{n!}\intop_{\Omega}\prod_{1\leq i<j\leq n}(x_{j}-x_{i})^{2}\,\prod_{j=1}^{n}e^{-...
level1807's user avatar
  • 467
6 votes
0 answers
206 views

Reference request: maximal determinant of matrices with pairwise orthogonal rows and entries in $\{1, 0, -1\}$

We know that "Hadamard maximal determinant problem" concerns the largest determinant of a matrix of oder $n$ with entries in $\{-1,1\}$ or $\{0, 1\}$. For $n=4k$, it is the Hadamard ...
Arun 's user avatar
  • 725
6 votes
0 answers
1k views

Relationship between R-transform and free convolution of random matrices?

I've been using the R-transform to calculate the free convolution of the eigenvalue spectra of two random matrices and I am trying to understand how it works, and in particular how it relates to ...
Jiahao Chen's user avatar
  • 1,870
6 votes
0 answers
243 views

Dimension-free sample complexity for estimating Gaussian covariance

(also asked on math.se, with no answers) Suppose I have $m$ samples drawn from a Gaussian in $\mathbb{R}^n$, and need sample covariance $\Sigma_m$ to be $\epsilon$-close to true covariance $\Sigma$: $$...
Yaroslav Bulatov's user avatar
6 votes
1 answer
827 views

Average minimum number of random k-sparse vectors in GF(2) to span the whole space?

What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...
mhsnk's user avatar
  • 197
6 votes
1 answer
293 views

Phase transition in matrix

Playing around with Matlab I noticed something very peculiar: Take the symmetric matrix $A \in \mathbb R^{n \times n}$ defined by $$A_{ij}= i \delta_{ij} - \frac{\varepsilon}{\sqrt{i}\sqrt{j}}\,.$$ ...
Sascha's user avatar
  • 506
5 votes
1 answer
276 views

Reference request: results on the asymptotic distribution of singular values related to a random orthogonal matrix

Let $Q$ be a random variable taking as its values the set of $n \times k$ real matrices with orthogonal columns, and whose distribution is the Haar measure on the Stiefel manifold $O(n)/O(n-k)$. This ...
Christopher A. Wong's user avatar
5 votes
2 answers
361 views

What is $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T Z \sigma]$ for a random Gaussian matrix $Z$?

Given an $n \times n$ random matrix $\mathbf{Z}$ with each entry i.i.d. $\mathcal{N} (0,1)$, what is $\mathbb{E} [\max_{\sigma \in \{ \pm 1\}^n} \sigma^T Z \sigma]$ as $n \to \infty$? If this is too ...
Television's user avatar
5 votes
0 answers
233 views

Riemann theta function inequality for a class of large random matrices

The following is essentially the same question as in this previous post, but since I have completely re-formulated it (hopefully for the better ;-), I decided to post a new question instead of an edit....
Dierk Bormann's user avatar
4 votes
1 answer
300 views

Distribution of Submatrix of Orthogonal Matrix

Let $O$ be a matrix sampled from the Haar measure on $O(n)$. Let $X$ be the upperleft $k\times k$ submatrix of $O$. In a physics research project I am interested in the distribution of $X$, say $\rho(...
Junkai Dong's user avatar
4 votes
1 answer
224 views

Spectral density of symmetrized Haar matrix

Let $O$ be a random orthogonal matrix (according to Haar measure) of size $n$. I found by simulations that the spectral density of $O+O^\top$ is the arcsin law rescaled to the interval $[-2,2]$. I can'...
Pluviophile's user avatar
  • 1,404
4 votes
1 answer
224 views

Is the inequality of the random matrices correct?

I am not familiar with random matrices but I need to confirm the correctness of the inequality below. Let $\xi_i\in\{\pm 1\}$ be independent random signs, and let $A_1,\ldots, A_n$ be $m\times m$ ...
Nate's user avatar
  • 131
4 votes
1 answer
301 views

Haar integral of rational function of unitaries

I'm trying to compute the following Haar integral over the unitary group: $$ \int\limits_{\mathbb{U}(d)}\dfrac{1}{\sum_{k,l=1}^d u_{ik}\overline{u_{il}}c_{kl}}dU. $$ Is there anything known about the ...
TheBluegrassMathematician's user avatar
4 votes
0 answers
939 views

Expected operator norm of inverse Wishart matrix

Let $ W\sim W_p(n,I)$ be a white $p\times p$ Wishart matrix, and assume $n>p+1$, which ensures that $W$ is invertible almost surely. Let $\|W^{-1}\|_{\text{op}}$ be the operator norm (maximum ...
mlopes's user avatar
  • 41
4 votes
1 answer
730 views

Determinant of a random row stochastic matrix

Does anyone know anything about the determinant of a random $n\times n$ row stochastic matrix? What I have in mind is that the rows are independently selected from the uniform distribution on the unit ...
Anthony Quas's user avatar
  • 22.4k
4 votes
1 answer
595 views

Characterizations of the GOE/GUE family of distributions

This question is somewhat related to this one. Loosely speaking, when should I expect a GOE/GUE distribution? The angle of my approach to this is not through statements such as "there is a natural ...
Alex R.'s user avatar
  • 4,902