# Does full rank matrix A in $F_2$ still determine a unique solution in the linear system $Ax=b$?

Matrix $$A$$ is a $$n\times n$$ binary matrix.

Vector $$b$$ is a $$n\times 1$$ binary vector.

The unknown $$x$$ is a $$n\times 1$$ binary vector.

When will the system $$Ax=b$$ have a unique solution?

Here the normal multiplication is BIT-AND and the addition is BIT-XOR. Matrix $$A$$ is full rank iff none of the rows can be represented as a linear combination of other rows.

Further question: How do we prove that $$A$$ is full rank? (Besides Gaussian Elimination, $$det(A)\neq 0$$ etc)

• There isn't much in introductory linear algebra that cares about which field you're working over. Most of it translates between fields entirely unchanged. Commented Nov 23, 2022 at 7:59
• @Arthur, would changing the addition from BIT-XOR to BIT-OR be any different as well? Commented Nov 23, 2022 at 8:14
• Is $F_2$ still a field if you do that? If yes, then very little changes. If no, then you have to be more careful. Commented Nov 23, 2022 at 9:00

• An answer to your final additional question is for instance: check that $$\det(A)\ne0.$$
The proof for these two answers is the same for $$\Bbb F_2$$ (or any field) as for $$\Bbb R.$$
• Thanks! I tried the $det(A)\neq 0$ approach before. I am excluding this as well. I am looking for approaches that cannot apply to the general matrices. Commented Nov 23, 2022 at 8:17
• What I can think of is plugging in different $x$ values and then checking the distribution of $b$. Since this is a 1-to-1 mapping the distribution should be even. Is there some way that I can verify this fact fast enough? Commented Nov 23, 2022 at 8:25