I Built an Online Calculator for Finite Fields and Linear Algebra

Matrixer multiplying matrices in F4
A demo of my new calculator multiplying matrices in F4

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 limited set of numbers and it is not possible to “break out” of this set of numbers by combining any numbers of that field.

A Little Example

The Field F5 has 5 elements: 0, 1, 2, 3 and 4.
In this field, e.g. 3+4 = 2 and 2*3 = 1 are valid expressions. Obviously in real numbers this would not make any sense, but in F5 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 ℝ. 7/5 = 1, Remainder: 2. Therefore 3+4 = 2 in F5.

Same for multiplication: 2*3 is 6 in ℝ. 6/5 = 1, Remainder: 1. Therefore 2*3 = 1 in F5.

If we do that for all elements of F5, we get following tables:

+01234
001234
112340
223401
334012
440123
*01234
000000
101234
202413
303142
404321

In General

For every other finite field whose number of elements is a prime number (F2, F3, F5, F7, …) 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 F3 there are the three elements 0, 1 and 2.
1+2 = 3 in ℝ. 3/3 = 1, Remainder: 0. Therefore 1+2 = 0 in F3.

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 F4, since F4 has 4 elements and 4 is not a prime number.

But why can’t I do that?
Well, the answer is, that F4 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 * 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 F4, 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:
2*0 = 0
2*1 = 2
2*2 = 0
2*3 = 2

As you can see, there is no element, so that 2*y = 1. Therefore, F4 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 F4 has the elements 0, 1, α and α+1. Yes, that’s right, α+1 is not a mathematical expression, but an element of F4.

I won’t explain in detail how to calculate with these elements, but here are the tables:

+01αα+1
001αα+1
110α+1α
ααα+101
α+1α+1α10
*01αα+1
00000
101αα+1
α0αα+11
α+10α+11α

This is already getting quite difficult and it is still the beginning. There are also fields like F8 with single elements like 1+β+β². 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:

Two matrices in F4

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:

Result of a multiplication of two matrices in Matrixer

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*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 F2, F3, F4, F5, F7, F8, F9, F11, F13, F17 and F19.

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:

An example 2x3 matrix

Vectors: Wrapped in square brackets, rows separated by comma.
For example [1, 2, 3] represents following vector:

An example vector with three rows

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)
  • b is β (beta)
  • bs is β²
  • j is ɩ (iota)

This means, that the calculation of 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. Feel free to leave a comment.

0 Comments
Inline Feedbacks
View all comments