All Questions
31 questions
22
votes
2
answers
1k
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, $...
- 24.7k
21
votes
0
answers
2k
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 ...
- 24.7k
16
votes
4
answers
597
views
The lattice 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 ...
- 24.7k
15
votes
1
answer
1k
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 ...
- 4,922
11
votes
1
answer
636
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 ...
- 24.7k
11
votes
1
answer
919
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 ...
- 3,626
8
votes
1
answer
227
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 ...
- 2,479
7
votes
2
answers
347
views
Matrices over $\mathbb{F}_p$ that have nonzero determinant under any element permutation
$\DeclareMathOperator\GL{GL}$A few months ago, the following discussion took place on AoPS, concerning matrices that have nonzero determinant under any permutation of their entries: https://...
- 541
7
votes
1
answer
880
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 ...
- 272
6
votes
1
answer
837
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$? ...
- 307
5
votes
3
answers
1k
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$ ...
- 3,377
5
votes
0
answers
235
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....
- 686
4
votes
1
answer
207
views
Upper bound on the number of binary matrices with small rank
I'm looking for the tightest upper bound on the number of different binary matrices $A \in {\{-1,1\}^{m \times n}}$ for which $\mathrm{rank}(A)\leq r$. I'm interested in the regime $1 \ll r \ll m \...
- 968
4
votes
0
answers
187
views
Dyadic distribution of $0/1$ permanents
Fix reals $a,b\in(1,2)$ satisfying $1<b<a<ab<2$.
What fraction of $0/1$ matrices of dimensions $n\times n$ have permanents
in $[b2^m,a2^m]$ at some $m\in\{0,1,2,\dots,\lfloor\log_2n!\...
- 13.9k
4
votes
0
answers
355
views
Distribution of min/max row sum of matrix with i.i.d. uniform random variables
Given a $n\times n$ symmetric random matrix such that
all diagonal elements are all fixed as $1$.
all elements in upper triangle (excluding the diagonal) are i.i.d. uniform random variables ...
- 272
3
votes
1
answer
184
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 "...
user125648
3
votes
0
answers
202
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 ...
- 686
2
votes
4
answers
512
views
Statistical computation in matrix. Rows before columns? riddle..
First I'll phrase the question as a riddle, and than as a general math problem.
We have 12 lettered vases $(A,B,...,L)$, in each vase there are 30 numbered balls (1-30). In each ball there is some ...
- 23
2
votes
1
answer
299
views
Can this particular random matrix model be converted/related to any existing graph theory model?
Context:
This a sequel to the question: Is the Erdős–Rényi giant component result applicable here?
Consider a matrix whose elements are independently assigned a value
$1$ with probability $p$ ...
user123818
2
votes
1
answer
132
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}^\...
- 515
2
votes
1
answer
90
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 ...
user125648
2
votes
0
answers
59
views
Min/max row-sum distribution of a symmetric matrix 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 such that
all diagonal elements are all fixed as $0$.
randomly select $k$ distinct cells in the upper triangle (excluding the diagonal), and then ...
- 272
2
votes
0
answers
227
views
Average minimum number of random k-sparse vectors in $\mathbb{F}_2^n$ to span a specific base vector?
A while back I posted a question in MO about the average minimum number of independent random k-sparse (having at most $k$ non-zero elements) vectors belonging to $\mathbb{F}_2^n$ to span the whole ...
- 307
1
vote
2
answers
305
views
Joint moments like $\tau(XYXYXY)$ in terms of individual moments of free variables $X,Y$
Terry Tao RMT book has the following formula for joint moment of freely independent random variables $X,Y$ in Section 2.5
$$\tau(XYXY)=\tau(X)^2\tau(Y^2)+\tau(X^2)\tau(Y)^2-\tau(X)^2\tau(Y)^2$$
...
- 2,442
1
vote
1
answer
519
views
How typical are integer isometries on a hypercube? Littlewood-Offord problem for Bernoulli Gram matrices
Let $m\geq 3$ be fixed and $n\to\infty$. Consider $v=(v_j)_{j\leq m}$ with $v_1,\ldots,v_m\in \{-1,+1\}^n$. Let:
$N_I(v)$ be the number of sequences $u_1,\ldots,u_m\in \{-1,+1\}^n$ isometric to $v$ ...
- 175
1
vote
1
answer
195
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 6,853
1
vote
1
answer
684
views
Probability that random Bernoulli matrix is full rank
This is probably known already, but I could not find a quick argument.
Let $M$ be an $n\times m$ binary matrix with iid Bernoulli$(1/2)$ entries, and $n>m$. Tikhomirov recently settled that the ...
- 1,096
1
vote
1
answer
394
views
On rank of random $0/1$ matrices
It is known that a $0/1$ matrix picked from uniform distribution from $\{0,1\}^{n\times n}$ is non-singular with probability $1-o(1)$.
Fix an integer $t$.
Consider a random matrix formed the ...
user94040
1
vote
1
answer
121
views
Probability for high mutual coherence on all subsets of a Gaussian vector set
We examine as set of independent normal vectors:
$$ \forall i \in [N]\triangleq \{1,\dots,N\}:\,\mathbf{x}_{i}\sim\mathcal{N}\left(0,\mathbf{I}_{d}\right)$$
For any $\epsilon>0$ and $K\leq N$, we ...
- 968
1
vote
1
answer
220
views
Probabilistic statement on matrix ranks
Given $A\in\{0,1\}^{n\times n}$ with $\operatorname{rank}(A)=r=2^{O((\log_2n)^{\frac{1}{c+1}})}$.
Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.
Does
$$\lim_{n\rightarrow\infty}\mathsf{P_{A\...
- 13.9k
0
votes
0
answers
45
views
On full rank submatrices of a construction
Take two matrices $T_1$ and $T_2$ in $\mathbb Z^{n\times n}$ with entries uniformly in $[-b,b]\cap\mathbb Z$ at some $b>0$. The matrices will be of rank $n$ each with probability at least $1-\frac1{...
- 1,826