ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 19 Mar 2018 03:56:04 +0100solving matrix over GF(2)https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/ 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$?
Fri, 16 Mar 2018 02:06:28 +0100https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/Comment by dan_fulea for <pre><code>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])
</code></pre>
<p>If the matrix $A$ is unkown, we have $Ax+b = y$.</p>
<p>How can we solve the matrix $A$?</p>
https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?comment=41576#post-id-41576We 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?Fri, 16 Mar 2018 02:31:17 +0100https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?comment=41576#post-id-41576Comment by omgggggg for <pre><code>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])
</code></pre>
<p>If the matrix $A$ is unkown, we have $Ax+b = y$.</p>
<p>How can we solve the matrix $A$?</p>
https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?comment=41578#post-id-41578Yes, 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$.Fri, 16 Mar 2018 02:59:15 +0100https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?comment=41578#post-id-41578Answer by tmonteil for <pre><code>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])
</code></pre>
<p>If the matrix $A$ is unkown, we have $Ax+b = y$.</p>
<p>How can we solve the matrix $A$?</p>
https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?answer=41577#post-id-41577A 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.Fri, 16 Mar 2018 02:31:33 +0100https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?answer=41577#post-id-41577Comment by omgggggg for <p>A few hints:</p>
<ul>
<li>$Ax+b=y$ can be rewritten as $Ax=y-b$ </li>
<li>$x$ is the first vector of the canonical basis</li>
<li>the image by $A$ of the ith vector of the canonical basis is the ith column of $A$</li>
<li>hence any matrix whose first column is the vector $y-b = y+b = (0,1,1,0,,0,0,0,0)$ does the job</li>
</ul>
<p><strong>EDIT</strong> Let me fix the question in comments:</p>
<ul>
<li>if $x$ is any (nonzero) vector, you can easily find an invertible matrix $B$ such that $x=Be0$ (where $e0 = (1,0,0,0,...)$) </li>
<li>then any matrix $A$ such that $ABe0=y-b$ is a solution to your problem.</li>
<li>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).</li>
<li>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.</li>
</ul>
<p>If you have problems in turning those hints into Sage code, do not hesitate to tell where you are locked.</p>
https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?comment=41579#post-id-41579There 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.Fri, 16 Mar 2018 10:12:11 +0100https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?comment=41579#post-id-41579Comment by omgggggg for <p>A few hints:</p>
<ul>
<li>$Ax+b=y$ can be rewritten as $Ax=y-b$ </li>
<li>$x$ is the first vector of the canonical basis</li>
<li>the image by $A$ of the ith vector of the canonical basis is the ith column of $A$</li>
<li>hence any matrix whose first column is the vector $y-b = y+b = (0,1,1,0,,0,0,0,0)$ does the job</li>
</ul>
<p><strong>EDIT</strong> Let me fix the question in comments:</p>
<ul>
<li>if $x$ is any (nonzero) vector, you can easily find an invertible matrix $B$ such that $x=Be0$ (where $e0 = (1,0,0,0,...)$) </li>
<li>then any matrix $A$ such that $ABe0=y-b$ is a solution to your problem.</li>
<li>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).</li>
<li>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.</li>
</ul>
<p>If you have problems in turning those hints into Sage code, do not hesitate to tell where you are locked.</p>
https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?comment=41617#post-id-41617As 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.Mon, 19 Mar 2018 03:56:04 +0100https://ask.sagemath.org/question/41575/solving-matrix-over-gf2/?comment=41617#post-id-41617