2

Let be $S$ a system of N linear equations, with K unknowns; and K > N, where the equations are linear and over $\mathbb{F}_2$, how many solutions are in this finite field linear system?

juaninf
  • 1,264

1 Answers1

4

As in all fields, if the matrix of the system and the augmented matrix have the same rank $r\quad (r\le N)$, the set of solutions is an affine subspace of $\mathbf F_2^K$ of codimension r, hence there are $2^{N-r}$ points in this subspace. If the rank of the augmented matrix is greater than the rank of the matrix of the system, there is no solution.

Bernard
  • 175,478
  • and if $K\leq N$?. please can you give a reference to read about that – juaninf Apr 18 '17 at 22:57
  • 2
    Same answer. The rank $r$ is $\le \min(K,N)$ anyway. I have no special reference, but it's obvious writing the matrices in reduced row echelon form by Gauß' pivot method. – Bernard Apr 18 '17 at 23:09
  • @juaninf: The theory of linear systems described in any freshman linear algebra works over any field (only when "Euclidean metric" concepts such as lengths and angles make an appearance - then you need to stick to real numbers). – Jyrki Lahtonen Apr 19 '17 at 05:01