Row reduction using modular arithmetic
45 views (last 30 days)
Show older comments
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!
0 Comments
Accepted Answer
John D'Errico
on 23 Jan 2019
Edited: John D'Errico
on 24 Jan 2019
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.
More Answers (1)
Walter Roberson
on 23 Jan 2019
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.
2 Comments
John D'Errico
on 23 Jan 2019
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
on 23 Jan 2019
See also binary inverse at https://www.mathworks.com/matlabcentral/answers/16192-inversion-of-a-boolean-matrix
See Also
Categories
Find more on Linear Algebra in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!