Solvability of linear systems over finite fields

If you have n equations in n unknowns over a finite field with q elements, how likely is it that the system of equations has a solution?

The number of possible n × n matrices with entries from a field of size q is q^n². The set of invertible n × n matrices over a field with q elements is GL_n(q) and the number of elements in this set is [1]

$|GL_n(q)| = q^{n(n-1)/2} \prod_{i=1}^n(q^i - 1)$

The probability that an n × n matrix is invertible is then

$\prod_{i=1}^n \left(1 - \frac{1}{q^i}\right)$

which is an increasing function of q and a decreasing function of n. More on this function in the next post.

Spaces and subspaces over finite fields
Finite projective planes
Finite field Diffie Hellman encryption

[1] Robert A. Wilson. The Finite Simple Groups. Springer 2009

Solvability of linear systems over finite fields

Related posts

Leave a Reply