solving matrix over GF(2)

asked 2018-03-16 02:06:28 +0200

omgggggg
35 ●2 ●3 ●8

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$?

Comments

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?

dan_fulea ( 2018-03-16 02:31:17 +0200 )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$.

omgggggg ( 2018-03-16 02:59:15 +0200 )edit

add a comment

answered 2018-03-16 02:31:33 +0200

tmonteil
27333 ●31 ●203 ●514 http://wiki.sagemath.o...

updated 2018-03-16 11:47:52 +0200

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.

edit flag offensive delete link

Comments

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.

omgggggg ( 2018-03-16 10:12:11 +0200 )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.

omgggggg ( 2018-03-19 03:56:04 +0200 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

solving matrix over GF(2)

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

solving matrix over GF(2) edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

solving matrix over GF(2)