[PYTHON] Find the rank of a matrix in the XOR world (rank of a matrix on F2)

At first

I am a university student in the Faculty of Agriculture who is studying mathematics as a hobby. I still have a lot of math and programming skills, so I'd be happy if you could teach me> <

What is XOR

Please check another site for details. When you talk 1+1=0 1+0=1 0+1=1 0+0=0 If you think of it as a world where operations are defined (algebraically speaking, it is the sum on $ \ mathbb {F_2} $.)

What is simplification?

It is a work to transform into a convenient shape while maintaining the rank of the matrix. It is often nice to know the rank (miscellaneous) Also, if it exists in the process of simplification, the inverse matrix can be obtained, so simplification is quite important.

program

First, determine the operation

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

Next, define the addition of the rows of the matrix (because it is often used).

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

All you have to do is write the one that simplifies (but only up to the upper triangle)

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

To explain the flow roughly Swap rows if you're searching for a 1 in the rankth column, and delete (add) 1s in the rows below you It feels like repeating. This is enough if you want the rank without a clean simplification.

motion

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]]

it is a good feeling.

Returns rank

You can tell the rank if you go to the simplification with the above one.

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

Finally

I want to be able to do it with $ Z / nZ $ instead of $ \ mathbb {F_2} $. However, this time the inverse element of 1 is 1, so I should have added myself, but if it is $ Z / nZ $, it may be a little difficult because I have to prepare a program that searches for the inverse element.