Gaussian Elimination on Modulo 2 Matrices

Revision en2, by -synx-, 2017-05-30 17:27:35

e-maxx
This link mentions that we can speed up conventional Gaussian elimination by using bitset
to achieve O(n3 / 32) using bitwise operations.
I have 3 questions:
1. Do they mean mod 2 inverses wrt following under modulo 2 1 + 1 = 0, 0 + 0 = 0, 0 + 1 = 1 + 0 = 1?
2. For mod 2 inverse to exist, does this imply det(A) mod 2 ≠ 0?
3. Can someone please help correct the following implementation?

vector<bitset<N>>gaussModTwo(vector<bitset<N>>a,vector<bitset<N>>b){
	int n=a.size(), i, j;
	for(i=0;i<n;++i){
		for(j=i;j<n;++j) if(a[j][i]){
			swap(a[j],a[i]);
			swap(b[j],b[i]);
			break;
		}
		for(j=0;j<n;++j) if(j!=i) {
			a[j]^=a[i];
			b[j]^=b[i];
		}
	}
	return b;
}
Tags gaussian elimination, matrices

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English -synx- 2017-05-30 19:53:35 31
en2 English -synx- 2017-05-30 17:27:35 25 Tiny change: 'erses wrt boolean $1+1=0, 0' -> 'erses wrt following under modulo 2 $1+1=0, 0'
en1 English -synx- 2017-05-30 17:24:55 829 Initial revision (published)