# Matrix multiplication using Galois field

$$\begin{bmatrix}1 &1 &6\\4& 3& 2\\5 &2& 2\\5& 3& 4\\4& 2& 4\end{bmatrix}\begin{bmatrix}4\\5\\6\end{bmatrix} = \begin{bmatrix}3\\5\\4\\3\\2\end{bmatrix}.$$ I am not getting that how come this result is possible ?

[Editor's comment #1: The question makes sense, but the asker forgot to explain their notation - possibly because they have not been exposed to any alternatives (happens regrettably often when programmers and/or telecommunication majors are introduced to finite fields). Below please find an elaboration of my educated guess, JL.]

Here the notation is using a common way of writing polynomials with binary coefficients as integers. We are working over the field $GF(2^3)$ aka $\Bbb{F}_8$ defined as $\Bbb{F}_2[\alpha]$, where $\alpha$ is a zero of an irreducible cubic. We then compactly represent an arbitrary element $$z=a_0+a_1\alpha+a_2\alpha^2\in GF(8), \ a_0,a_1,a_2\in GF(2),$$ as the sequence of bits $$z=a_2a_1a_0$$ that is then (internally to the computer program) stored as the integer $$i(z)=(a_2a_1a_0)_2$$ in base two.

For example, the element $\alpha^2+\alpha$ is converted to $6$, because $$\alpha^2+\alpha=1\cdot\alpha^2+1\cdot\alpha^1+0\cdot\alpha^0=110_2=6.$$

[Editor's comment #2: A popular choice is that $\alpha$ is a zero of the polynomial $x^3+x+1$. In other words, we have the equation $$\alpha^3+\alpha+1=0.$$ Unless I made a mistake, the first component of the matrix product above matches with this minimal polynomial in the sense that the calculation $$1\cdot4+1\cdot5+6\cdot6=1\cdot\alpha^2+1\cdot(1+\alpha^2)+(\alpha+\alpha^2)^2=\alpha+1=3,$$ is true when $\alpha^3+\alpha+1=0$, JL.]

• Welcome to MSE! Did you include all of the information in the problem statement (like which field)? MSE likes to see that you have tried and what issues you are having or where you are stuck. – Moo Nov 11 '16 at 5:06
• It will also help if you format your matrices correctly. $\begin{bmatrix} 1&1&6\\4&3&2\\5&2&2\end{bmatrix}$ for example outputs $\begin{bmatrix} 1&1&6\\4&3&2\\5&2&2\end{bmatrix}$ – JMoravitz Nov 11 '16 at 5:16
• well.. i want to state that I am working on GF(2^3). And I have two matrixes i.e. $$A = \begin{bmatrix} 1&1&6 \\ 4&3&2 \\ 5&2&2 \\ 5&3&4 \\ 4&2&4 \end{bmatrix}$$ and $$B = \begin{bmatrix} 4 \\ 5 \\ 6\end{bmatrix}.$$ Now the result that I am getting after the multiplication of $$AB = \begin{bmatrix} 3 \\ 5 \\ 4 \\ 3 \\ 2\end{bmatrix}.$$ I had tried this on matlab by using the gfconv function but the result that I obtained was not the same as mentioned above. – Harvaneet Kaur Nov 11 '16 at 9:41
• Harvaneet Kaur, I edited the question because it was abundantly clear to me that you use a notation the answer wanna-bes are not familiar with (or, even if familiar, expect you to explain it for them because it is NOT standard math notation). No wonder, they thought the question is unclear! Anyway, I don't remember Matlab conventions for finite fields, and it may well be that either A) Matlab uses a different primitive element, or B) a different notation (IIRC it writes a polynomial as a sequence of coefficients, but may be not). Let's wait and see whether voters think the question is ok now! – Jyrki Lahtonen Nov 11 '16 at 13:13

Posting the details of the calculations for the first couple of matrix entries. I use the assumption that $\alpha$ is a zero of the primitive polynomial $x^3+x+1$, and hence $\alpha$ is generator of the multiplicative group of $GF(8)$. Below we have a table of base-$\alpha$ discrete logarithms of non-zero elements of $GF(8)$ \eqalign{ \alpha^0&=1&&=\color{red}1,\\ \alpha^1&=\alpha&&=\color{red}2,\\ \alpha^2&=\alpha^2&&=\color{red}4,\\ \alpha^3&=1+\alpha&&=\color{red}3,\\ \alpha^4&=\alpha+\alpha^2&&=\color{red}6,\\ \alpha^5&=1+\alpha+\alpha^2&&=\color{red}7,\\ \alpha^6&=1+\alpha^2&&=\color{red}5,\\ \alpha^7&=1. } where I use $\color{red}{\mathrm{red}}$ to list how an element of $GF(8)$ is stored as a bitfield interpreted as an integer (see my comments in the OP).

I refer you to my on-site table of discrete logarithms for the derivation of this table as well as first examples of its use. A reader can view this answer as another example in the use of discrete log tables for carrying out arithmetic in a binary field.

For the first entry we have \begin{aligned} \color{red}{1\cdot4+1\cdot5+6\cdot6}&=1\cdot\alpha^2+1\cdot(\alpha^2+1)+(\alpha^2+\alpha)\cdot(\alpha^2+\alpha)\\ &=\alpha^2+(\alpha^2+1)+\alpha^4\cdot\alpha^4\\ &=1+\alpha^8\\ &=1+\alpha=\color{red}{3}. \end{aligned} For the second entry it goes like \begin{aligned} \color{red}{4\cdot4+3\cdot5+2\cdot6}&=\alpha^2\cdot\alpha^2+(\alpha+1)\cdot(\alpha^2+1)+\alpha\cdot(\alpha^2+\alpha)\\ &=\alpha^4+\alpha^3\cdot\alpha^6+\alpha\cdot\alpha^4\\ &=\alpha^4+\alpha^9+\alpha^5\\ &=\alpha^4+\alpha^2+\alpha^5\\ &=(\alpha+\alpha^2)+\alpha^2+(1+\alpha+\alpha^2)\\ &=1+\alpha^2=\color{red}{5}. \end{aligned}

For the third entry \begin{aligned} \color{red}{5\cdot4+2\cdot5+2\cdot6}&=(1+\alpha^2)\cdot\alpha^2+\alpha\cdot(\alpha^2+1)+\alpha\cdot(\alpha^2+\alpha)\\ &=\alpha^6\cdot\alpha^2+\alpha\cdot\alpha^6+\alpha\cdot\alpha^4\\ &=\alpha^8+\alpha^7+\alpha^5\\ &=\alpha+1+\alpha^5\\ &=\alpha+1+(1+\alpha+\alpha^2)\\ &=\alpha^2=\color{red}{4}. \end{aligned}

Leaving the last two as exercises. Ask, if you have problems.

• I'm afraid I cannot help you with coercing Matlab to oblige. – Jyrki Lahtonen Nov 20 '16 at 12:21
• Thank you so much Jyrki.. :) – Harvaneet Kaur Nov 21 '16 at 14:44
• well , this part is clear to me now.. but now comes my major problem. Actually have to write a program that do all these mathematics on galois field .. starting from matrix multiplication , inverse of a matrix, to a system of linear equation defined over some field.. can you suggest me somthing that can help me with my work. :/ – Harvaneet Kaur Nov 21 '16 at 14:48