Finding all rows of 2 variables using Gaussian Elimination Suppose I have a system of linear equations. Using Gaussian elimination, I can determine whether a solution exists, and even find a valid solution.

During the elimination, I can combine rows together, to produce new rows with different number of variables. Is there a method to find all possible rows that contain exactly 2 variables? For example, I may want to find all equalities between variables. This is equivalent to finding all rows that contain exactly 2 variables. Is it possible to do this without trying all (exponentially many) combinations of rows? 

For example if I have:

Row 1: A xor B xor C = 1

Row 2: A xor B xor D = 1

I can combine row 1 and row 2 to say that C xor D = 0 

If I have a large amount of rows, and they require large combinations of large rows to produce smaller rows, is it trivial or hard to find all rows of size 2? Can I do better than adding random pairs to the system and checking it still has a solution?
If I understand you correctly, you have a matrix $M$ over $GF(2)$ (the field with two elements), and want to find all linear combinations of rows which have weight exactly $2$.

Using Gaussian elimination, you can bring your matrix into echelon form. This makes it easy to determine, for any particular row, whether it is in the span of the rows of $M$. Since there are only $\binom{n}{2}$ many rows of weight $2$, the entire algorithm will run in polynomial time. (It is likely that this can be optimized further.)