Example of Linear System of Polynomials over finite field

126 Views Asked by At

I'm trying to find any system of polynomial over finite field (solvable in $K[x]_{m(x)}$) with characteristic two. I want please any example of $a_{ij}$ and $b_k$

$$a_{11}(x)*p+a_{12}(x)*q+a_{13}(x)*r = b_1(x)$$ $$a_{21}(x)*p+a_{22}(x)*q+a_{23}(x)*r = b_2(x)$$ $$a_{31}(x)*p+a_{32}(x)*q+a_{33}(x)*r = b_3(x)$$

where $p,q$ and $r$ are the variables and the coefficients of every polynomial $a_{ij}$ are in $K[x]_{m(x)}$ with $K=\mathbb{F}_2$

1

There are 1 best solutions below

0
On BEST ANSWER

I give an example over $\Bbb{F}_8=K[x]/\langle x^3+x+1\rangle$. First let me shamelessly copy the following relevant table from this answer. Here $\alpha=x+\langle x^3+x+1\rangle$ is trivially a zero of the polynomial $m(x)=x^3+x+1$ that is irreducible in $K[x]$. See the latter half of that other answer for more details. $$ \eqalign{ \alpha^0&=&&=1,\\ \alpha^1&=&&=\alpha,\\ \alpha^2&=&&=\alpha^2,\\ \alpha^3&=&&=1+\alpha,\\ \alpha^4&=&\alpha\cdot\alpha^3=\alpha(1+\alpha)&=\alpha+\alpha^2,\\ \alpha^5&=&\alpha\cdot\alpha^4=\alpha(\alpha+\alpha^2)=\alpha^2+\alpha^3=\alpha^2+(1+\alpha)&=1+\alpha+\alpha^2,\\ \alpha^6&=&\alpha\cdot\alpha^5=\alpha(1+\alpha+\alpha^2)=\alpha+\alpha^2+\alpha^3= \alpha+\alpha^2+(1+\alpha)&=1+\alpha^2,\\ \alpha^7&=&\alpha\cdot\alpha^6=\alpha(1+\alpha^2)=\alpha+\alpha^3=\alpha+(1+\alpha)&=1. }$$ The above table show all the non-zero elements of $\Bbb{F}_8$, and you see that the multiplicative group is cyclic of order seven (as promised by the general theory). I very much prefer to use $\alpha$ here in place of $x$. This is becaus once we go to the quotient field of $K[x]$, $x$ stops being a free variable.

Let's "randomly" pick the 3x3 system $$ \left\{ \begin{array}{rcrcrcl} \alpha x_1&+&&&\alpha^2x_3&=&1,\\ x_1&+&x_2&+&\alpha x_3&=&0,\\ (1+\alpha)x_1&+&\alpha x_2&&&=&\alpha. \end{array}\right. $$ The matrix of coefficients is $$ A=\left(\begin{array}{ccc} \alpha&0&\alpha^2\\ 1&1&\alpha\\ 1+\alpha&\alpha&0 \end{array}\right). $$ We see that $$ \det A=\alpha^3+\alpha^3+\alpha^2(\alpha+1)=0+\alpha^3+\alpha^2=1+\alpha+\alpha^2\neq0, $$ so $A$ is non-singular, and we know that the system has a unique solution. We find this with the usual method of finding the reduced row echelon form of the augmented matrix (thereby making the calculation of the determinant unnecessary). First I permute the rows to get a $1$ to the upper left $$ \left(\begin{array}{cccc} 1&1&\alpha&0\\ \alpha&0&\alpha^2&1\\ 1+\alpha&\alpha&0&\alpha \end{array}\right). $$ Adding (we are in characteristic two, so addition and subtraction are the same operation) the indicated multiples of the first row to the other two gives $$ \left(\begin{array}{cccc} 1&1&\alpha&0\\ 0&\alpha&\alpha^2+\alpha^2&1\\ 0&\alpha+(1+\alpha)&\alpha(1+\alpha)&\alpha \end{array}\right) =\left(\begin{array}{cccc} 1&1&\alpha&0\\ 0&\alpha&0&1\\ 0&1&\alpha+\alpha^2&\alpha \end{array}\right). $$ To get a $1$ at position $(2,2)$ I divide the second row by $\alpha$. From the table we see that $1/\alpha=\alpha^7/\alpha=\alpha^6=1+\alpha^2$, so I multiply it with $1+\alpha^2$, and get $$ \left(\begin{array}{cccc} 1&1&\alpha&0\\ 0&1&0&1+\alpha^2\\ 0&1&\alpha+\alpha^2&\alpha \end{array}\right). $$ Pivoting the second column amounts to adding the second row to the other two, so we get $$ \left(\begin{array}{cccc} 1&1+1&\alpha&1+\alpha^2\\ 0&1&0&1+\alpha^2\\ 0&1+1&\alpha+\alpha^2&\alpha+(1+\alpha^2) \end{array}\right)= \left(\begin{array}{cccc} 1&0&\alpha&1+\alpha^2\\ 0&1&0&1+\alpha^2\\ 0&0&\alpha+\alpha^2&1+\alpha+\alpha^2 \end{array}\right). $$ From the table we see that the $(3,3)$ entry $\alpha^2+\alpha=\alpha^4$. Therefore its inverse is $1/\alpha^4=\alpha^7/\alpha^4=\alpha^3=1+\alpha$, so I multiply the last row with $1+\alpha$. To do that I need to calculate the product. Again I use the table heavily: $$ (1+\alpha)(1+\alpha+\alpha^2)=\alpha^3\cdot\alpha^5=\alpha^8=\alpha\cdot\alpha^7=\alpha, $$ and get $$ \left(\begin{array}{cccc} 1&0&\alpha&1+\alpha^2\\ 0&1&0&1+\alpha^2\\ 0&0&1&\alpha \end{array}\right). $$ Pivoting the last column then gives $$ \left(\begin{array}{cccc} 1&0&0&1+\alpha^2+\alpha^2\\ 0&1&0&1+\alpha^2\\ 0&0&1&\alpha \end{array}\right)= \left(\begin{array}{cccc} 1&0&0&1\\ 0&1&0&1+\alpha^2\\ 0&0&1&\alpha \end{array}\right). $$ From this we can read the solution $$ x_1=1,\quad x_2=1+\alpha^2,\quad x_3=\alpha.$$

I leave it as an exercise to check (by plugging them in) that this is, indeed, a solution. I did it, so you have to do it, too!

The key to the arithmetic is to use the table in both directions. Multiplication/division is easier, if you first convert everything to powers of $\alpha$. Addition is easier, if you first convert everything to low degree polynomials of $\alpha$ (here at most quadratic).