Questions tagged [random-matrices]

Statistics of spectral properties of matrix-valued random variables.

Filter by
Sorted by
Tagged with
39
votes
3answers
4k 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=...
20
votes
7answers
12k 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?
7
votes
1answer
599 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 ...
23
votes
1answer
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 $...
14
votes
1answer
6k 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 ...
5
votes
2answers
4k 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 ...
39
votes
1answer
4k 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 ...
40
votes
1answer
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....
16
votes
5answers
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 ...
6
votes
1answer
1k 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. ...
2
votes
1answer
514 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 ...
1
vote
1answer
584 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 ...
18
votes
5answers
2k 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 ...
15
votes
0answers
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 ...
19
votes
3answers
2k 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 ...
18
votes
1answer
898 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 ...
6
votes
0answers
927 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 ...
13
votes
2answers
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 ...
9
votes
1answer
369 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 ...
8
votes
2answers
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) ...
6
votes
0answers
223 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....
6
votes
1answer
256 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}}\,.$$ ...
6
votes
1answer
617 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$? ...
5
votes
2answers
288 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 ...
11
votes
1answer
2k 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,\...
10
votes
1answer
424 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 ...
8
votes
2answers
1k 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 ...
4
votes
0answers
824 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 ...
3
votes
1answer
146 views

Why is number of single cell clusters always greatest in a random matrix?

Consider a large $N\times N$ square lattice, where each cell has a probability $p$ of being "occupied" (let's call denote them as "black") and a probability $1-p$ of being empty (let's denote them as "...
2
votes
0answers
168 views

Why do larger random matrices maximize their number of clusters with lower densities?

Consider a matrix whose elements are independently assigned a value $1$ with probability $p$ and a value $0$ with probability $1-p$. Define a cluster of cells as a maximal connected component in the ...
2
votes
1answer
77 views

Generalization: (The "number" of) smaller sized clusters in large random binary matrices follow a descending order. Why?

This is a sequel to the question: Why is number of single cell clusters always greatest in a random matrix? In their answer, @Aaron Meyerowitz came up with a nice strategy to prove why the number of ...
2
votes
1answer
102 views

Independent decomposition of coordinate distribution

Let $\mathbf{x}$ be a random Gaussian vector in $\mathbb{R}^n$, i.e. $\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_n)$. Then for any fixed unit vector $\mathbf{u}$, one has $\mathbf{u}\mathbf{u}^\...
19
votes
1answer
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 ...
9
votes
1answer
603 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^{-...
9
votes
2answers
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 ...
7
votes
2answers
470 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 ...
6
votes
1answer
225 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^{-...
4
votes
1answer
543 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 ...
4
votes
1answer
456 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 ...
3
votes
0answers
197 views

Difficult Gaussian-sum inequality for large random Bernoulli-Toeplitz matrices

I have come across the following problem in an attempt to prove an entropy bound for large random Bernoulli-Toeplitz matrices (Conjecture 1 on p. 16 of this preprint by Clifford et al. 2015), which is ...
3
votes
1answer
501 views

Upper bounds on the condition number of the eigenvector matrix

Let $A$ be an $n\times n$ real matrix with entries in a fixed interval $[a_\min,a_\max]$, with $a_\min$, $a_\max>0$. Question: Are there any upper bounds on the condition number of the ...
3
votes
0answers
73 views

Eigenvalues of Hadamard product of two Wishart-type matrices

Given two independent Gaussian matrices with i.i.d. entries: $A\in\mathbb{R}^{n\times p}$ and $B\in\mathbb{R}^{n\times q}$, where and $A_{i,j},B_{i,j}\sim\mathcal{N}(0,1)$. Assume that $\max(p,q)<n....
2
votes
1answer
267 views

Distribution of the Gram matrix

Let $\mathbf{X}$ be an $m\times k$ random matrix ($m>k$) of rank $k$, having the density function $f_\mathbf{X}(X)$. What is the distribution of $\mathbf{Y}=\mathbf{XX}^T$? Basically my question is ...
2
votes
3answers
693 views

Sum of Square of the Eigenvalues of Wishart Matrix

Let $A\in\mathbb{R}^{m\times d}$ matrix with iid standard normal entries, and $m\geqslant d$, and define $S=A^T A$. I want to have a tight upper bound for $\sum_{k=1}^d \lambda_k^2$, where $\...
2
votes
1answer
281 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)^{ - ...
1
vote
1answer
124 views

Ordinary least square and random projection

Let $X$ be a given $d \times T$ matrix, and let $M$ be an $n \times d$ random matrix (say i.i.d. centered coefficients). Define $Y=MX$ in $\mathbb{R}^n$ and $H=Y'(YY')^{-1}Y$, where $'$ denotes the ...
5
votes
1answer
210 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 ...
4
votes
1answer
213 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$ ...
3
votes
1answer
268 views

Modularity in a graph - definition of the random component

This question concerns the definition of modularity in a graph. Consider a simple, undirected, unweighted graph $G$ with vertices in set $V$ and edges in set $E$ . Between any two vertices there is ...
3
votes
2answers
220 views

Random matrices: why to distingusish bulk and edge cases?

I have been recently reading some papers on universality of spectral statistics of random matrices written by Terry Tao, Van Vu, L. Erdos, H.T. Yau and others, and I am puzzled by such a dichotomy, ...