All Questions
21 questions
31
votes
4
answers
2k
views
Probability of zero in a random matrix
Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, ...
- 37.7k
18
votes
3
answers
8k
views
Number of invertible {0,1} real matrices?
This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...
- 32.1k
10
votes
2
answers
635
views
Largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$?
What is known about the largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$? I am especially interested when $q=2$, and in the regime where $k$ is fixed an $n\to\infty$. Here are ...
- 455
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
463
views
Boundedness of total current in electrical network
Consider the following symmetric matrix (adjacency matrix):
$$A=(a_{ij})_{1\leq i,j\leq n}$$
such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...
- 1,495
6
votes
2
answers
283
views
Nonlinear boolean functions
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n_2\rightarrow \...
- 333
5
votes
1
answer
518
views
How many random matrices does it take to generate a matrix algebra?
Let $\mathbb{F}$ be a finite field.
Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra.
Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$
that one needs to take ...
- 3,104
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
939
views
Random projection and finite fields
Suppose we have, say, $n$ $2n$-dimensional linearly independent vectors over $\mathbb{F}_2$. We do a projection on a random $d$-dimensional subspace. We are interested in probability that images of ...
- 1,791
4
votes
0
answers
1k
views
Number of arrangements that contain at least 1 path from top to bottom of 2D matrix
I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white.
With that information, I can easily calculate the total number of black element arrangements that exist ...
- 47
3
votes
0
answers
116
views
Trace of Symmetric matrices in fixed rank
I am solving some problem related to symmetric matrices over a finite field $\mathbb{F}_q$ and I am stuck at the following problem:
For every $a\in\mathbb{F}_q $, let $S_a(t,m)$ be the set of all $m\...
- 179
3
votes
0
answers
142
views
Probability of hitting two vectors
Call an element of $ \{-m,\dots,0,\dots,m\}^{2^n}$ a vector. Assume $m = O(2^{2^n})$.
Let $u_1,u_2$ be vectors.
Let $\{v_1,\dots,v_{2^n}\}$ and $\{w_1,\dots,w_{2^n}\}$ be linearly independent ...
- 13.9k
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
2
answers
128
views
Spectral decomposition of a combinatorial matrix/Random walks on $s$-sets
$\newcommand{\Z}{\mathbb{Z}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\la}{\lambda}
\newcommand{\1}{\mathbf{1}}
\newcommand{\R}{\mathbb{R}}$
Take any $n\in[3;\infty]$. Here and in what follows, $[k;\...
- 128k
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
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
1
vote
0
answers
127
views
Delocalization of eigenvectors of graph Laplacians
Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...
- 41
1
vote
0
answers
131
views
Probabilistic lower bound on largest singular value of matrices
I have a distribution $\mathcal{D}$ that spits out vectors in $\{-1, 1\}^N$. Suppose I have a sample of $H$ of these vectors which I arrange into a matrix $M$ of the form $H \times N$.
Consider the ...
- 1,129
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