Consider the function

$$f(x_1, x_2, \ldots, x_k) = S_1^{x_1} S_2^{x_2} \cdots S_k^{x_k}.$$

Each $x_1, x_2, \ldots, x_k \in \{0, 1\}$ and each $S_i \in \mathbb{Z}_q^{n \times n}$ is a randomly chosen $n \times n$ matrix over the field $\mathbb{F}_q$.

For a particular choice of these matrices, I am trying to find the expected number of collisions (number of inputs that map to the same output) for $f$ (and also the variance of the number of collisions for $f$.)

Since a random matrix is almost a full rank matrix, I expect the number of collisions to be very low, but I could not prove it.

Consider the function

$$f(x_1, x_2, \ldots, x_k) = S_1^{x_1} S_2^{x_2} \cdots S_k^{x_k}.$$

Each $x_1, x_2, \ldots, x_k \in \{0, 1\}$ and each $S_i \in \mathbb{F}_q^{n \times n}$ is a randomly chosen $n \times n$ matrix over the field $\mathbb{F}_q$. $q$ is assumed to be a prime.

For a particular choice of these matrices, I am trying to find the expected number of collisions (number of inputs that map to the same output) for $f$ (and also the variance of the number of collisions for $f$.)

The number of collisions of $f$ is defined as

$$ \big|\{A : |f^{-1}(\{A\})| > 1\}\big|. $$

Since a random matrix is almost a full rank matrix, I expect the number of collisions to be very low, but I could not prove it.

Consider the function

$$f(x_1, x_2, \ldots, x_k) = S_1^{x_1} S_2^{x_2} \cdots S_k^{x_k}.$$

Each $x_1, x_2, \ldots, x_k \in \{0, 1\}$ and each $S_i \in \mathbb{Z}_q^{n \times n}$ is a randomly chosen $n \times n$ matrix over the field $\mathbb{F}_q$.

For a particular choice of these matrices, I am trying to find the expected number of collisions (number of inputs that map to the same output) for $f$ (and also the variance of the number of collisions for $f$.)

Since a random matrix is almost a full rank matrix, I expect the number of collisions to be very high, but I could not prove it.

Consider the function

$$f(x_1, x_2, \ldots, x_k) = S_1^{x_1} S_2^{x_2} \cdots S_k^{x_k}.$$

Each $x_1, x_2, \ldots, x_k \in \{0, 1\}$ and each $S_i \in \mathbb{Z}_q^{n \times n}$ is a randomly chosen $n \times n$ matrix over the field $\mathbb{F}_q$.

For a particular choice of these matrices, I am trying to find the expected number of collisions (number of inputs that map to the same output) for $f$ (and also the variance of the number of collisions for $f$.)

Since a random matrix is almost a full rank matrix, I expect the number of collisions to be very low, but I could not prove it.