I Built an Online Calculator for Finite Fields and Linear Algebra
TL;DR: Here it is: matrixer.davidaugustat.com
Everyone is familiar with the so-called real numbers, meaning numbers that we use in our daily life, like 3, -4, 0.5 or \(\pi\). As a computer science student I attend a math class at university where we not only use real numbers, but also other algebraic fields, the so-called finite fields.
As opposed to the real numbers, finite fields only have a finite set of numbers. When performing the mathematical operations \(+, -, \cdot\) or \(/\) on elements from this limited set of numbers, it is not possible to “break out” of it, i.e. the result is an element of the same set.
A Little Example
The Field \(\mathbb{F}_5\) has 5 elements: \(0, 1, 2, 3\) and \(4\).
In this field, e.g. \(3+4 = 2\) and \(2\cdot 3 = 1\) are valid expressions. Obviously in real numbers this would not make any sense, but in \(\mathbb{F}_5\) it does.
But how did I calculate these numbers?
This is actually not that hard for single calculations. All you have to do is calculating as you would with real numbers, but then divide the result by \(5\) and take the remainder.
For example \(3+4\) is \(7\) in \(\mathbb{R}\). \(7/5 = 1\), Remainder: \(2\). Therefore \(3+4 = 2\) in \(\mathbb{F}_5\).
Same for multiplication: \(2\cdot 3\) is \(6\) in \(\mathbb{R}\). \(6/5 = 1\), Remainder: \(1\). Therefore \(2\cdot 3 = 1\) in \(\mathbb{F}_5\).
If we do that for all elements of \(\mathbb{F}_5\), we get following tables for addition and multiplication:
\[\begin{array}{c|ccccc} + & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 0 & 1 & 2 & 3 & 4 \\ 1 & 1 & 2 & 3 & 4 & 0 \\ 2 & 2 & 3 & 4 & 0 & 1 \\ 3 & 3 & 4 & 0 & 1 & 2 \\ 4 & 4 & 0 & 1 & 2 & 3 \end{array}\] \[\begin{array}{c|ccccc} \cdot & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 \\ 2 & 0 & 2 & 4 & 1 & 3 \\ 3 & 0 & 3 & 1 & 4 & 2 \\ 4 & 0 & 4 & 3 & 2 & 1 \end{array}\]In General
For every other finite field whose number of elements is a prime number (\(\mathbb{F}_2, \mathbb{F}_3, \mathbb{F}_5, \mathbb{F}_7, \dots\)) it works exactly the same. The only difference is, that you don’t divide by \(5\) but by the according number of elements in the field.
E.g. in \(\mathbb{F}_3\) there are the three elements \(0, 1\) and \(2\).
\(1+2 = 3\) in \(\mathbb{R}\). \(3/3 = 1\), Remainder: \(0\). Therefore \(1+2 = 0\) in \(\mathbb{F}_3\).
As I said, these rules only apply for finite fields, that have a number elements that is a prime number. This means, you cannot calculate like that in \(\mathbb{F}_4\), since \(\mathbb{F}_4\) has 4 elements and \(4\) is not a prime number.
But why can’t I do that?
The answer is, that \(\mathbb{F}_4\) wouldn’t be a field anymore, if you calculated like this. In an algebraic field every element (except \(0\)) must have a multiplicative inverse element by definition. A multiplicative inverse element \(y\) of an element \(x\) is defined as \(x \cdot y = 1\).
In other words: For every element in the field, there must exist an element, so that the element multiplied by the other element is \(1\).
If we look at \(\mathbb{F}_4\), we can quickly find out, that it doesn’t match that criteria if calculated like a prime number field. Let’s take the element \(2\) as a counterexample:
\[\begin{align*} 2\cdot 0 = 0 \\ 2\cdot 1 = 2 \\ 2\cdot 2 = 0 \\ 2\cdot 3 = 2 \end{align*}\]As you can see, there is no element, so that \(2\cdot y = 1\). Therefore, \(\mathbb{F}_4\) is not a field if we define it like that.
However, if the number of elements in a field is a prime number, there exists a multiplicative inverse element for every element. The proof for this would be too complex for this article, so I won’t include it.
That’s where extended fields come into play
It is possible nonetheless, to define a field with 4 elements. Such a field is called an extended field, and it is a lot harder to calculate with these, since their elements and rules are somewhat unusual.
The actual field \(\mathbb{F}_4\) has the elements \(0, 1, \alpha\) and \(\alpha + 1\). Yes, that’s right, \(\alpha + 1\) is not a mathematical expression, but an element of \(\mathbb{F}_4\).
I won’t explain in detail how to calculate with these elements, but here are the tables:
\[\begin{array}{c|ccccc} + & 0 & 1 & \alpha & \alpha+1\\ \hline 0 & 0 & 1 & \alpha & \alpha+1 \\ 1 & 1 & 0 & \alpha+1 & \alpha \\ \alpha & \alpha & \alpha+1 & 0 & 1 \\ \alpha+1 & \alpha+1 & \alpha & 1 & 0 \end{array}\] \[\begin{array}{c|ccccc} \cdot & 0 & 1 & \alpha & \alpha+1\\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & \alpha & \alpha+1 \\ \alpha & 0 & \alpha & \alpha+1 & 1 \\ \alpha+1 & 0 & \alpha+1 & 1 & \alpha \end{array}\]This is already getting quite difficult and it is still the beginning. There are also fields like \(\mathbb{F}_8\) with single elements like \(1+\beta+\beta^2\). Calculating with these gives you a headache and takes a lot of time.
Now, at university we use these finite fields quite a lot and we also do linear algebra using finite fields. I wish you good luck multiplying these matrices without getting anything wrong:
Matrixer
As you will likely have noticed, calculating with finite fields is not that easy to do by hand. However, since I like programming a lot, I decided to just write a calculator that can do these calculations for me.
Still remember the matrices from above? My calculator called “Matrixer” can do it in less than 20 milliseconds:
Don’t believe me? Here is a link to this exact calculation.
Matrixer can not only multiply matrices, but also does following things:
- Basic calculations with numbers (addition, subtraction, multiplication, division and exponentiation)
- Calculate the multiplicative inverse element (\(x\cdot y = 1\))
- Calculate the additive inverse element (\(x+y = 0\))
- Add and subtract matrices
- Transpose matrices (swap rows and columns)
- Multiply a matrix by a vector
- Add, multiply and subtract vectors
- Solve a homogeneous equation system
- Convert a matrix to reduced row echelon form
All of these calculations can be done with real numbers, but also on the finite fields \(\mathbb{F}_2, \mathbb{F}_3, \mathbb{F}_4, \mathbb{F}_5, \mathbb{F}_7, \mathbb{F}_8, \mathbb{F}_9, \mathbb{F}_{11}, \mathbb{F}_{13}, \mathbb{F}_{17}\) and \(\mathbb{F}_{19}\).
The Interface
I tried to make it as easy as possible to enter mathematical expressions. Therefore I developed a tiny language that can be used to input expressions:
Usual math expressions: Just like on any calculator:
For example 5*3*(0.5-2^3)+(2/3) is a valid input.
Matrices: Wrapped in curly brackets, rows separated by semicolon and columns separated by comma.
For example {1, 2, 3; 4, 5, 6} represents following matrix:
Vectors: Wrapped in square brackets, rows separated by comma.
For example [1, 2, 3] represents following vector:
Numbers of extended fields: Using replacement letters.
Since we don’t have Greek letters on our keyboards, I chose phonetically similar Latin letters as replacements:
- a is \(\alpha\) (alpha)
- b is \(\beta\) (beta)
- bs is \(\beta^2\)
- j is \(\iota\) (iota)
This means, that the calculation from above looks like this when you enter it:
{1, a, a+1; 0, a+1, 1; a, 0, a+1} * {1, 1; a+1, a; 0, a+1}
You can find a lot more detailed instructions for entering expressions on the website itself.
About the Code
The entire calculator is written in JavaScript running on the front end in the user’s browser. This means that the website is highly scalable since no code is executed on the server, but only static files are sent to the user.
One disadvantage of this is however, that Matrixer doesn’t work in all browsers. Until now I discovered that that the website doesn’t work in Internet Explorer 11. Nothing happens when I click the “Calculate” button. Nonetheless, in every other browser I had at hands (Chrome, Firefox, Edge), the calculator worked flawlessly.
As of today, the complete source code is about 7000 lines (including comments and empty lines). This includes JavaScript, HTML and CSS files.
I decided to make the entire project open source and you can find the complete source code in this GitHub repository. It is released under a GNU GPL V3.0 License, meaning that you can re-purpose this code for your own projects as long as you credit me and publish your code under the same license.
And that’s it!
Check out my calculator here if you haven’t yet, and also have a look at the code if you like. If anything doesn’t work or seems wrong, just contact me and I will try to fix the problem.