Ask Your Question

solving matrix over GF(2)

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

omgggggg gravatar image
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 flag offensive 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?

dan_fulea gravatar imagedan_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 gravatar imageomgggggg ( 2018-03-16 02:59:15 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

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

tmonteil gravatar image

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

omgggggg gravatar imageomgggggg ( 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 gravatar imageomgggggg ( 2018-03-19 03:56:04 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower


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

Seen: 1,416 times

Last updated: Mar 16 '18