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 qn². The set of invertible n × n matrices over a field with q elements is GLn(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.

Related posts

[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.

Previous Post
Next Post