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!
采纳的回答
John D'Errico
2019-1-23
编辑：John D'Errico
2019-1-24
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.
更多回答（1 个）
Walter Roberson
2019-1-23
0 个投票
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 个评论
John D'Errico
2019-1-23
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
2019-1-23
See also binary inverse at https://www.mathworks.com/matlabcentral/answers/16192-inversion-of-a-boolean-matrix
类别
在 帮助中心 和 File Exchange 中查找有关 Operating on Diagonal Matrices 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
