0
votes
1answer
71 views

Probability and Rank of Symmetric Matrix

Let be a $n \times n$ Symmetric Matrix over Finite Field with $q$ elements, where the green color represents 0's and the black color non-zero entries. How I will be able to demonstrate that ...
0
votes
0answers
22 views

How large does $m$ have to be to get unique values with high probability? [duplicate]

We can suppose we are given two naturals, $r$ and $n$. We can then pick $n$ unique naturals: $\{x_0, x_1, \dots, x_n\}$. The following function is important: $$\prod_{k=1}^n{(x_k)^{y_k}} (\mod m)$$ ...
3
votes
1answer
65 views

probability of choosing $k$ linear independent elements from a finite field

Let $\mathbb{F}_q$ denote a finite field with $q$ elements. What is the probability of choosing $k$ linear independet elements from $\mathbb{F}_q^n$? I guess, it depends on how we choose from ...
2
votes
1answer
55 views

Query regarding a Lemma from a paper.

This is from a paper. Let me introduce the required definitions and post my query: Definition: A vector $\mathbf{x}$ is a $q$-dimensional vector of probabilities defined as $\mathbf{x}=(x_0,x_1,\dots ...
10
votes
1answer
378 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
68 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
86 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
62 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 ...