XOR世界で行列のrankを求める(F2上での行列のrank)

最初に

ご指導まっています

XORとは

詳しくは別サイトで調べてください.
かいつまんで話すと
1+1=0
1+0=1
0+1=1
0+0=0
と演算が定義されている世界だと思っていただければ(代数的に言うと$\mathbb{F_2}$上の和です.)

簡約化とは

行列のrankを保ちつつ都合がいい形に変形していく作業です.
rankが分かると嬉しいことが多いです(雑)
また簡約化する過程で存在すると逆行列を得ることができるので簡約化は結構大事なものです.

プログラム

まずは演算を定めます

def cal(a,b):
    if a==1 and b==1:
        return 0
    elif a==1 and b==0:
        return 1
    elif a==0 and b==1:
        return 1
    else:
        return 0

次に行列の行の足し算を定義しておきます(よく使うので)

def matcal(line1,line2):
    ans=[0]*(len(line1))
    for i in range(len(line1)):
        ans[i]+=cal(line1[i],line2[i])
    return ans

あとは簡約化(上三角までしかしないけど)をしてくれるやつを書くだけです

def simple(mat):
    ans=copy.copy(mat)
    rank=0
    for i in range(len(mat[0])):
        for j in range(rank,len(mat)):
            if ans[j][i]==1:
                for k in range(rank,len(mat)):
                    if ans[k][i]==1 and k!=j:
                        ans[k]=matcal(ans[k],ans[j])
                if j==rank:
                    pass
                else:
                    ans[j],ans[rank]=ans[rank],ans[j]
                rank+=1
                if rank==len(mat)-1:
                    return ans
                break
            else:
                pass
    return ans

流れを雑に説明すると
rank番目の列に1があるかを検索してあったら行を交換.そして自分より下の行の1を消す(足してあげる)
を繰り返す感じです.
きれいに簡約化しなくてもrankを求めるならこれで十分です.

動作

print(simple([[1,1,1],[1,1,0],[0,1,0]]))
>>>[[1, 1, 1], [0, 1, 0], [0, 0, 1]]

print(simple([[1,1,0],[1,1,0],[0,1,0]]))
>>>[[1, 1, 0], [0, 1, 0], [0, 0, 0]]

print(simple([[0,0,1],[0,1,0],[1,0,0]]))
>>>[[1, 0, 0], [0, 1, 0], [0, 0, 1]]

いい感じですね.

rankを返す

上のやつで簡約化もどきまで行えばrankを教えてくれる君です.

def rank(mat):
    l=len(mat[0])
    che=[0]*l
    cnt=0
    for i in range(len(mat)):
        if mat[i]!=che:
            cnt+=1
    return cnt

最後に

$\mathbb{F_2}$じゃなくても$Z/nZ$でやれるようにしたいですね.
ただ今回は１の逆元が1なので自分自身を足せばよかったですけど,$Z/nZ$だと逆元を探してくれるプログラムを準備しないといけないのでちょっと大変かも.