Statistics of spectral properties of matrix-valued random variables.

learn more… | top users | synonyms

30
votes
1answer
3k 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 ...
27
votes
2answers
1k 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 ...
21
votes
1answer
2k 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 ...
21
votes
0answers
980 views

Correspondence between eigenvalue distributions of random unitary and random orthogonal matrices

In the course of a physics problem (arXiv:1206.6687), I stumbled on a curious correspondence between the eigenvalue distributions of the matrix product $U\bar{U}$, with $U$ a random unitary matrix and ...
18
votes
1answer
1k views

Unexpected $\sqrt{3}$

A somewhat lengthy calculation, involving integrals, reveals that the probability an $n\times n$ Hermitian matrix, drawn from the Gaussian unitary ensemble, is positive definite, decays as ...
16
votes
0answers
467 views

Random Distance Matrices

My question is motivated by the following recent paper: http://arxiv.org/abs/1110.6333 Assume you have a metric space $(X,d)$ equipped with a Borel probability measure $\mu$. We can further assume ...
15
votes
1answer
1k 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 ...
15
votes
4answers
486 views

The latice spanned by $m$ random 0-1 vectors of length $n$

Consider $m$ random 0-1 vectors of length $n$. Let $L$ be the lattice spanned by them. What is the value of $m$ (as a function of $n$) for which it is true with positive probability that $L=Z^n$? More ...
15
votes
0answers
279 views

Quasi-classical limit of representation theory

I am looking for a good reference on a general phenomenon of quasi-classical limit in representation theory, which relates "large" representations to measures on (co-adjoint orbits of) the associated ...
15
votes
0answers
772 views

The Fourier Transform of taking Eigenvalues

The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
14
votes
4answers
775 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 ...
14
votes
2answers
384 views

Repeated random two-steps in $\mathbb{R}^3$: unbounded?

I created a random isometry $T$ of $\mathbb{R}^3$ by generating a random orthogonal matrix $M$, uniformly distributed among all such, and a random displacement $v$, whose coordinates are drawn from a ...
14
votes
2answers
593 views

Laws of Iterated Logarithm for Random Matrices and Random Permutation

The law of iterated logarithm asserts that if $x_1,x_2,\dots$ are i.i.d $\cal N(0,1)$ random variables and $S_n=x_1+x_2+\cdots+x_n$, then $$\limsup_{n \to \infty} S_n/\sqrt {n \log \log n} = \sqrt 2, ...
13
votes
2answers
1k 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 ...
12
votes
7answers
4k 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?
12
votes
4answers
982 views

An experiment on random matrices

A bit unsure if my use/mention of proprietary software might be inappropriate or even frowned upon here. If this is the case, or if this kind of experimental question is not welcome, please let me ...
12
votes
1answer
771 views

A Question on Random Matrices

Consider the following $n\times n$ random matrix $V_{n}$ where the $(p,q)$ entry is given by $$ V_{n}(p,q):= \frac{1}{\sqrt{n}}\exp(2\pi i(p-1) x_{q}) $$ where $x_{1},x_{2},\ldots,x_{n}$ are iid ...
11
votes
4answers
863 views

Why only three classical matrix ensembles in RMT? (Newbie question)

I am just starting out on understanding random matrix theory from a background in applied mathematics. I have a very basic question about the Gaussian ensembles: why are there only three classical ...
11
votes
2answers
919 views

Evaluation of a combinatorial sum (that comes from random matrices)

I'm looking for an elementary combinatorial/generating function/etc proof of the following result: For nonnegative integers $r$, $$\frac{1}{r!} = \sum_{p_0+p_1+\cdots = r} ...
11
votes
0answers
250 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 ...
11
votes
0answers
493 views

Probability a random Toeplitz matrix is singular

Consider Toeplitz matrices where the entries in the first row and column (which define the whole matrix) are independently chosen to be either $1$ or $0$ with probability $1/2$. Define $p_n$ to be the ...
11
votes
0answers
315 views

Lower Bound on the Volume of Certain Polytopes

Given a partition $\rho\in\mathcal{P}(n)$ with $k$ blocks $$ \rho=\{B_1,B_2,\ldots,B_{k}\} $$ we can define the set of equations $$ E_{i}:\sum_{j \in B_{i}}{x_{j-1}}=\sum_{j \in ...
10
votes
1answer
370 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
1answer
641 views

Non-probabilistic proof of the Johnson–Lindenstrauss lemma

The Johnson–Lindenstrauss lemma states that a small set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are ...
10
votes
3answers
986 views

Random Walks and Lyapunov exponents

Given a sequence $Y_1, Y_2, \dots$ of i.i.d. matrices in $GL_n(\mathbb R)$, there is a theorem of Furstenberg and Kesten which says that if $\mathbb E(\log||Y_1||)$ is finite, there exists a constant ...
10
votes
1answer
359 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
0answers
168 views

What are the difficulties in proving almost-everywhere stability of Gaussian elimination?

It is well known that Gaussian elimination without pivoting is numerically unstable, and in practice Gaussian elimination is done with row pivoting (partial pivoting). A theorem of Wilkinson states ...
9
votes
1answer
259 views

What is known about the distribution of eigenvectors of random matrices?

Let $A$ be a real asymmetric $n \times n$ matrix with i.i.d. random, zero-mean elements. What results, if any, are there for the eigenvectors of $A$? In particular: How are individual eigenvectors ...
9
votes
2answers
627 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 ...
9
votes
2answers
195 views

Iterating Random Matrix Operations

Consider the following probability measure on the integers concentrated around $0$: the probability of drawing $0$ is $\frac{1}{2}$, of drawing ($1$ or $-1$) is $\frac{1}{4}$ split evenly among the ...
9
votes
1answer
562 views

Average over Random Permutations

Consider $S_{n}$ the symmetric group and for each $\sigma\in S_{n}$ let $U_{\sigma}$ be its $n\times n$ permutation matrix. Let $A$ be an Hermitian $n\times n$ matrix. I'm interested in computing the ...
9
votes
2answers
873 views

Expected values of traces of products of random matrices

Suppose I want to compute a quantity of the type: $\mathbb{E}\mathrm{tr}(AUBU^{\ast})$ where averaging is over Haar measure on the unitary group $\mathcal{U}(n)$ (one can of course consider higher ...
9
votes
1answer
657 views

U(3) Sato-Tate measure.

An undergraduate is performing some computations, related to a Sato-Tate conjecture of $U(3)$ type (a curve over $Q$, for which the roots of local L-functions look like eigenvalues of a random matrix ...
8
votes
2answers
743 views

Intuition behind the spectral density of random matrices

Hi, I have read that the spectral density of an NxN random matrix consisting of iid random variables with zero mean and unit variance converges as N goes to infinity to the uniform distribution on ...
8
votes
3answers
829 views

Singularity of sparse random matrices

The following topic came up in conversation with my office-mate Lionel: Let $p$ be a fixed prime, $c$ a fixed positive real parameter and $n$ a large number. Consider a random $(0,1)$ matrix with ...
8
votes
1answer
112 views

GOE Version of Longest Increasing Subsequence

Let $S_n$ be the symmetric group equipped with uniform measure. For any $\pi\in S_n$, let $L_n=L_n(\pi)$ denote the longest increasing subsequence. A celebrated result of Baik, Deift and Johansson ...
8
votes
1answer
862 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 ...
8
votes
1answer
273 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
1answer
666 views

Matrix integral identity

1) How to prove that $N\times N$ matrix integral over complex matrices $Z$ $$ \int d Z d Z^\dagger e^{-Tr Z Z^\dagger} \frac{x_1\det e^Z -x_2 \det ...
8
votes
0answers
419 views

Framework for primes vs random matrices

This is inspired by What results would follow from or imply "randomness" of the primes? , but I think it is sufficiently different to ask separately. We can formalise probability in ...
8
votes
0answers
345 views

Has the technique of “sprinkling” been used in studying random matrices?

In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
8
votes
0answers
285 views

A formula for moments of the limit distribution of singular values in the proof of the circular law

One of the steps in the proof of the circular law in random matrix theory is obtaining the limiting spectral distribution for the matrix $(\frac{1}{\sqrt{n}} X_n - zI)(\frac{1}{\sqrt{n}} X_n - ...
7
votes
3answers
477 views

Relationship between free probability and deterministic graphs?

Consider the $N\times N$ matrix $$ M = \left(\begin{array} \\ 0 & 1 & & 0 \\ 1 & \ddots & \ddots & \\ & \ddots & \ddots & 1 \\ 0 & & 1 & 0 \\ ...
7
votes
2answers
455 views

Maximum Singular Value of a random +1/-1 matrix

Hi, Define a matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ such that each element is independently and randomly chosen with probability 0.5 to be either +1, or -1. Do you know any result in the ...
7
votes
1answer
194 views

Concentration of sum of powers of normals

Let $Z_1,Z_2,\ldots,Z_n$ be i.i.d. copies of a random variable $Z$ distributed as $\frac{1}{\sqrt{2}}X+i\frac{1}{\sqrt{2}}Y$ with $X$ and $Y$ independent standard Normal random variables ...
7
votes
1answer
522 views

Expected norm of sum of random orthogonal matrices

Somehow I got wondering about the following question today: Suppose $Q_1,\ldots,Q_n$ are random (uniformly sampled) $d \times d$ orthogonal matrices. What is the expected value of the quantity ...
7
votes
1answer
143 views

Distribution of entries of a doubly-sorted random matrix

Take an $n \times n$ random matrix whose entries are i.i.d. with uniform distribution in $[0,1]$. Look at the sums of the elements of each row and then permute the rows so that these sums form an ...
7
votes
3answers
704 views

A conjecture about the entropy of matrix vector products

Consider a random $m$ by $n$ partial circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$ and let $m < n$. Now consider a random $n$ dimensional vector $v$ ...
7
votes
0answers
229 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 $m$ 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 ...
6
votes
5answers
783 views

L-functions and random matrices

I am curious about the connection between properties of L-functions and random matrices, and about (if existent) function field versions of that. Do you know a survey or an other article where one ...