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.
