0

Is it possible to have $m$ rows with $n$ variables over F2, where $m < n$
that will have some combination of rows that can form a zero vector, but there will be no zero vectors in reduced-row echelon form?

Please provide an example of such a setup if this is indeed possible.

Ilya Gazman
  • 1,440

1 Answers1

1

Having $m$ rows and $n$ columns is obviously possible for matrices over $\Bbb F_2$, no matter the $m$ and $n$.

Gaussian elimination is an algorithm that works for matrices over any field and it is generally formulated in a way that may be applied verbatim in that generality (even when it is presented only for the case $A\in\Bbb R^{m\times n}$). I don't quite understand your objection, but I presume it revolves around a confusion between the action of $\Bbb Z$ over $V$, according to which you may write $x+x+x+x=4x$, and the action of $\Bbb F_2$, which is the one of interest and which only has $\overline 0\cdot x$ and $\overline 1\cdot x$.

  • I am using the Gaussian elimination to solve the matrix in the last step of the Quadratic Sieve algorithm. My goal is to find a combination of rows that when XORed together will result in a Zero vector. The question is: Assuming such a combination is possible, is it promised to find it when computing the reduced-row echelon form, given that $m < n$? – Ilya Gazman Aug 08 '20 at 19:25
  • If I understand correctly, then no: at best you can find a basis of the space of relations, just like you do with $\Bbb R$. –  Aug 08 '20 at 19:37
  • No, I am saying that it is given that there is at least one combination of $m$ rows that will create a null space vector. The question is, is it promised that Gaussian elimination will find it? – Ilya Gazman Aug 08 '20 at 20:20
  • 1
    @IlyaGazman I don't understand, and I won't inspect any further because we are repeating ourselves. The Gaussian elimination agorithm does the same thing for matrices over $\Bbb F_2$ that it does for matrices over $\Bbb R$. If if it does for $\Bbb R$, it does for $\Bbb F_2$. If it doesn't for $\Bbb R$, then probably it doesn't for $\Bbb F_2$. –  Aug 08 '20 at 20:31
  • If the matrix is of less than full rank, Gaussian elimination will produce a row of all zeroes, just like it would over $\mathbb{R}$. – saulspatz Aug 08 '20 at 20:39
  • @Gae.S. sorry for confusing you with $\Bbb F_2$ it is truly irrelevant to what I am asking. I try making another question about it – Ilya Gazman Aug 08 '20 at 20:46