Questions tagged [random-matrices]
Statistics of spectral properties of matrix-valued random variables.
89
questions
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=...
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?
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 ...
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 $...
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 ...
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$ ...
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....
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 ...
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 $\...
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 ...
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 ...
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 ...
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. ...
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^...
3
votes
2
answers
922
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)^{ - ...
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 ...
1
vote
1
answer
936
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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,\...
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 ...
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 ...
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 ...
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 ...
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^{-...
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) ...
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\|},\...
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 ...
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 ...
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}...
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
$...
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 ...
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 ...
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$? ...
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}}\,.$$
...
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$:
$$...
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^{-...
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 ...
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 ...
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....
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$ ...
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 ...
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(...
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 ...
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 ...
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 ...
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'...