Solvability of linear systems over finite fields

The Endeavour 2024-07-23

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

The post Solvability of linear systems over finite fields first appeared on John D. Cook.

Solvability of linear systems over finite fields

The Endeavour 2024-07-23

Related posts