# solving matrix over GF(2)

A = matrix(GF(2), 8, 8, [])
b = vector(GF(2), [0, 1, 1, 0, 1, 0, 1, 1])
y = vector(GF(2), [0, 0, 0, 0, 1, 0, 1, 1])
x = vector(GF(2), [1, 0, 0, 0, 0, 0, 0, 0])


If the matrix $A$ is unkown, we have $Ax+b = y$.

How can we solve the matrix $A$?

edit retag close merge delete

We can write simpler $Ax=b'$ with an obvious $b'$. This is a linear system in the $8^2=64$ entries of $A$, considered as unknowns, if i get the message right, but we have only $8$ equations, corresponding to the components of the constant given known vector $b'=y-b$. We need now all solutions?

( 2018-03-15 20:31:17 -0600 )edit

Yes, we need all possible solutions of $A$, since we have many equations like $Ax+b=y$, we will solve each equation and take the intersection to get the final $A$.

( 2018-03-15 20:59:15 -0600 )edit

Sort by » oldest newest most voted

A few hints:

• $Ax+b=y$ can be rewritten as $Ax=y-b$
• $x$ is the first vector of the canonical basis
• the image by $A$ of the ith vector of the canonical basis is the ith column of $A$
• hence any matrix whose first column is the vector $y-b = y+b = (0,1,1,0,,0,0,0,0)$ does the job

EDIT Let me fix the question in comments:

• if $x$ is any (nonzero) vector, you can easily find an invertible matrix $B$ such that $x=Be0$ (where $e0 = (1,0,0,0,...)$)
• then any matrix $A$ such that $ABe0=y-b$ is a solution to your problem.
• by the previous part of the answer, the set of matrices $M$ such that $Me0=y-b$ is the $d(d-1)$ linear set $S$ of matrices whose first column is $y-b$ (and the other are the $d(d-1)$ free variables).
• then, the set of solutions of your original problem is the set $\{MB^{-1} \mid M \in S\}$, which you can write in terms of the $d(d-1)$ free variables.

If you have problems in turning those hints into Sage code, do not hesitate to tell where you are locked.

more

There exist other cases such as y = vector(GF(2), [1, 0, 1, 0, 1, 0, 0, 0]) and x = vector(GF(2), [0, 1, 1, 1, 1, 1, 0, 0]). The values of x and y are variable.

( 2018-03-16 04:12:11 -0600 )edit

As you said, we can get the $M\in S$ whose first column is $y-b$, but i don't know how to generate the set $S$ by Sage code.

( 2018-03-18 21:56:04 -0600 )edit