Row reduction using modular arithmetic

I'm looking to row reduce an augmented matrix mod 2.

Is there any way to do this using the rref function? Say I have a matrix A, I've tried the operation,

A = mod(rref(A),2)

but with no success. Is there any way to ammend this, or possibly work around this with a different function?

Thank you!

Answer 1

[John D'Errico]

I must have been bored this morning. So I hacked rref to produce rrefgf. It will work for any integer ring as induced by a given modulus.

A = magic(3)
A =
     8     1     6
     3     5     7
     4     9     2
>> [Ar,jb] = rrefgf(A,11)
Ar =
     1     0     0
     0     1     0
     0     0     1
jb =
     1     2     3
>> Ar = rrefgf([A,eye(size(A))],11)
Ar =
     1     0     0     8    10     7
     0     1     0     0     1     2
     0     0     1     6     3     5
>> mod(A*Ar(:,4:6),11)
ans =
     1     0     0
     0     1     0
     0     0     1

So A has an inverse in the ring of integers modulo 11. It is singular modulo 2 though.

[Ar,jb] = rrefgf(A,2)
Ar =
     1     0     1
     0     1     0
     0     0     0
jb =
     1     2

Working in modulo 2, see that A may be any integer class, including logical.

A = rand(10,10) < 0.5
A =
  10×10 logical array
   1   0   1   0   0   0   1   1   1   0
   0   0   1   1   0   0   0   1   0   1
   0   1   1   0   0   0   1   1   1   1
   0   0   0   0   0   0   0   1   1   0
   0   1   0   0   0   0   0   1   1   1
   0   1   0   0   1   0   1   1   0   1
   1   1   0   1   0   0   0   0   0   1
   1   0   0   0   1   1   1   1   1   1
   1   1   0   1   0   1   1   0   1   0
   0   1   0   1   0   0   1   0   0   0
>> [Ar,jb] = rrefgf(A,2)
Ar =
  10×10 logical array
   1   0   0   0   0   0   0   0   0   0
   0   1   0   0   0   0   0   0   0   0
   0   0   1   0   0   0   0   0   0   0
   0   0   0   1   0   0   0   0   0   0
   0   0   0   0   1   0   0   0   0   0
   0   0   0   0   0   1   0   0   0   0
   0   0   0   0   0   0   1   0   0   0
   0   0   0   0   0   0   0   1   0   0
   0   0   0   0   0   0   0   0   1   0
   0   0   0   0   0   0   0   0   0   1
jb =
     1     2     3     4     5     6     7     8     9    10

So we see this randomly generated A was full rank.

As a test, rrfgf will even survive a non-prime modulus, although it will quite often be true that if the modulus is not prime, the matrix will be singular in the induced group of integers. A prime modulus can still result in a singular matrix, but less often. And of course, a highly composite modulus will very often fail in this respect.

A = [4     3     5     1
   2     1     1     0
   0     4     4     3
   2     1     1     4];
[Ar,jb] = rrefgf([A,eye(size(A))],9)
Ar =
     1     0     0     0     0     8     1     6
     0     1     0     0     4     2     6     8
     0     0     1     0     5     1     1     7
     0     0     0     1     0     2     0     7
jb =
     1     2     3     4

jb was 1:4, so A was non-singular, modulo 9.

mod(A*Ar(:,5:8),9)
ans =
     1     0     0     0
     0     1     0     0
     0     0     1     0
     0     0     0     1
     

rrfgf is attached. I should probably post it on the FEX.

[Dipie11]

Unreal, thank you very much for your help. Much appreciated!

Answer 2

[Walter Roberson]

No, it cannot be done using rref().

However rref.m is fairly straight foward code, and you could potentially copy it to a new function and edit that for your purposes.

[John D'Errico]

With the minor caveat that you need to use a modular inverse, because you will be dividing by a pivot element. In mod 2, that is not an issue, since your pivot element will never be 0, and in mod 2 arithmetic, the only other choice is 1. And 1 is its own inverse in mod 2 arithmetic. Things get terribly easy in mod 2.

[Walter Roberson]

See also binary inverse at https://www.mathworks.com/matlabcentral/answers/16192-inversion-of-a-boolean-matrix