Thursday, February 13, 2025

Solvability of linear systems over finite fields

Computer scienceSolvability 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 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]

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

\prod_i=1^n \left(1 - \frac1q^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





Check out our other content

Check out other tags:

Most Popular Articles