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.

Recommended Posts

Find the rank of a matrix in the XOR world (rank of a matrix on F2)
Find the eigenvalues of a real symmetric matrix in Python
Find the number of days in a month
[Python] Find the transposed matrix in a comprehension
A note on the default behavior of collate_fn in PyTorch
Find out the apparent width of a string in python
Get the number of readers of a treatise on Mendeley in Python
Find the intersection of a circle and a straight line (sympy matrix)
Get the caller of a function in Python
Make a copy of the list in Python
Find the divisor of the value entered in python
Find the solution of the nth-order equation in python
Output in the form of a python array
You walk in a spiral in a world where the walls of the cross rise (simulation)
[Example of Python improvement] I learned the basics of Python on a free site in 2 weeks.
Find the Hermitian matrix and its eigenvalues in Python
Find out the maximum number of characters in multi-line text stored in a data frame
Difference in results depending on the argument of multiprocess.Process
Write a log-scale histogram on the x-axis in python
I used Python to find out about the role choices of the 51 "Yachts" in the world.
Find a guideline for the number of processes / threads to set in the application server
A Study on Visualization of the Scope of Prediction Models
A reminder about the implementation of recommendations in Python
Create a shape on the trajectory of an object
[Python] Programming to find the number of a in a character string that repeats a specified number of times.
"A book to train programming skills to fight in the world" Python code answer example --1.8 "0" matrix
How to find the optimal number of clusters in k-means
Maya | Find out the number of polygons in the selected object
Display "Hello World" created in the local environment on the web
Survey on the use of machine learning in real services
Count the number of characters in the text on the clipboard on mac
Get the number of specific elements in a python list
Python --Find out number of groups in the regex expression
Find the index of the maximum value (minimum value) of a multidimensional array
How to find the scaling factor of a biorthogonal wavelet
Find the average / standard deviation of the brightness values in the image
Get the index of each element of the confusion matrix in Python
Find the difference in Python
"A book to train programming skills to fight in the world" Python code Solution example --1.7 Matrix rotation
Yield in a class that inherits unittest.TestCase didn't work with nose (depending on the version of nose?)
A memo that reproduces the slide show (gadget) of Windows 7 on Windows 10.
Verification of the spread of hoaxes in the "State of Emergency Declaration on April 1"
Process the contents of the file in order with a shell script
Examine the Lie-Trotter formula censoring error
Expressing "the most beautiful mathematical formula in the world" programmatically
LU decomposition in Python
Find the eigenvalues of a real symmetric matrix in Python
How to determine the existence of a selenium element in Python
Find the optimal value of a function with a genetic algorithm (Part 2)
Build a Selenium environment on Amazon Linux 2 in the shortest time
Why put a slice on the left side in the substitution formula
How to check the memory size of a variable in Python
On Linux, the time stamp of a file is a little past.
Find the point of contact of the common tangent of two circles (sympy matrix)
Read the standard output of a subprocess line by line in Python
How to check the memory size of a dictionary in Python
How to find the memory address of a Pandas dataframe value
[python] Get the rank of the values in List in ascending / descending order
How to get the vertex coordinates of a feature in ArcPy
A command to easily check the speed of the network on the console
Create a function to get the contents of the database in Go
I want to know the population of each country in the world.
[Python] A simple function to find the center coordinates of a circle
"A book to train programming skills to fight in the world" Python code answer example --1.9 Rotation of strings