Given $m$ rows with $n$ variables where $m < n$, and given that there exists a combination of some of the rows that gives a zero vector.
Is it promised when computing the reduced-row echelon form, with Gaussian elimination to find a zero vector?
Update:
I clearly don't know, how to pick up the right words to ask my question. So let me give you the full context and please help me say it right, so the question will make sense.
I am solving step 3 in the quadratic sieve algorithm, here is a wiki description of it.
Suppose the composite number N is being factored. Bound $B$ is chosen, and the factor base is identified (which is called $P$), the set of all primes less than or equal to $B$. Next, positive integers $z$ are sought such that $z_2$ mod $N$ is B-smooth. Therefore it can be written, for suitable exponents $a_i$,
$${\displaystyle z^{2}{\text{ mod }}N=\prod _{p_{i}\in > P}p_{i}^{a_{i}}}$$ When enough of these relations have been generated (it is generally sufficient that the number of relations be a few more than the size of P), the methods of linear algebra can be used (for example, Gaussian elimination) to multiply together these various relations in such a way that the exponents of the primes on the right-hand side are all even:
$${\displaystyle {z_{1}^{2}z_{2}^{2}\cdots z_{k}^{2}\equiv \prod > _{p_{i}\in P}p_{i}^{a_{i,1}+a_{i,2}+\cdots +a_{i,k}}\ {\pmod {N}}\quad ({\text{where }}a_{i,1}+a_{i,2}+\cdots +a_{i,k}\equiv 0{\pmod > {2}})}}$$
Now, let's say I found $m$ relations and the number of primes in $P$ is $n$, such that $m<n$. It is given that there exists a combination of some of the $m$ relations that their product is a square number.
My question is: When I perform the Gaussian elimination over F2 to find a null space combination, is it promised that I will find one?
I successfully implemented the algorithm and the matrix part of my implementation works. But what I see is that if I found a null space(a combination of making a null space) and latter I add more relations(still $m < n$), I lose the null space solution and not able to solve the matrix again. Each time I add a new relation I start solving it from the beginning, I don't remember any previous state.
So what I want to know, could it be that there is a limitation with the Gaussian elimination algorithm, that it does not promise to find the null space if $m < n$?