Tagged Questions
10
votes
1answer
293 views
Probability of a random $n \times n$ matrix over $\mathbb F_2$ being nonsingular
Given a random square matrix of size $n\times n$ in the field $\mathbb F_2$, what is the probability that its determinant is $1$? (This is also the probability that the matrix is non-singular, since ...
1
vote
1answer
56 views
Variation over univariate Schwartz–Zippel lemma
Let $n\in\mathbb{N}$ and let $q\in[n,2n]$ be a prime number.
In addition, let $s,s':\mathbb{F}_q\to\mathbb{F}_q$ be polynomials of degree $\sqrt{n}$ such that $s\neq s'$.
From the ...
2
votes
1answer
83 views
Distinguishing vector distributions induced by polynomials
I am given two sequences of multivariate polynomials $\overline{p}=(p_1,p_2,\dots,p_k)$ and $\overline{q}=(q_1,q_2,\dots,q_k)$, all of them on the variables $x_1,\dots,x_n$ over some finite field ...
1
vote
1answer
61 views
Multiplying matrix by random vectors in $\mathbb{Z}_2$
Is it correct that for any uniformly, independently chosen vectors $r,s \in \mathbb{Z}_2^m$ and for any $0 \neq D \in \mathbb{Z}_2^{m \times m}$, we have that $Pr_{r,s}\left[r^T\cdot D \cdot s \neq 0 ...
