This is an extension of a previously asked question: Inner Product Spaces over Finite Fields.
Inner product spaces in the typical undergraduate linear algebra course are stressed to be over $\mathbb{C}$ or $\mathbb{R}$. Answers to the previous question say that while we might not get inner products over finite fields, we can get pretty close and get a bilinear symmetric form. Such a bilinear form would share most of the properties of the inner product, with one difference being that nonzero vectors may be self-orthogonal. Today I asked a professor about inner product spaces over finite fields, and he elaborated a little bit.
An interesting thing he mentioned was that we arrive at these bilinear symmetric forms via polynomials. As a motivating example, it is easy to define inner product spaces over $\mathbb{R}$. But when we study eigenvalues of linear operators we find that characteristic polynomial does not always split. So we "mod out" (the parentheses indicate my own understanding) the field with the polynomial equation $x^2+1=0$, and from then on whenever we see an equation like that we say $x^2=-1$. This gives us the complex numbers, and while our original inner product on $\mathbb{R}$ no longer works as an inner product, there is another inner product obtained by conjugation.
He then said bilinear symmetric forms for vector spaces over finite fields are obtained in a similar way, by finding a polynomial equation of this sort that works for the field in question. This is a nontrivial problem and usually (for a given order $n$ for the field) very difficult.
Now, finally, my question: I would like someone to elaborate on this "polynomial equation" business via some simple example. That is, I would like someone to construct a vector space over a finite field with a bilinear symmetric form and explain to me where the polynomial part comes in.
Also, please correct any mistakes in my thoughts, this was explained to me informally and this is my first time hearing about this so I wouldn't be surprised if I'm getting something mixed up.
Best Answer
The main idea is that although you can't set up an inner product space over $\mathbb{F}_q$ because you can't put an order on a finite field, but there's no reason you can't make bilinear maps.
I suppose you haven't taken field theory yet; that is where you learn about modding out by polynomials. Basically, you take a polynomial $p(x)$ of degree $n$ which is irreducible over a finite field $\mathbb{F}_q$ (which means that it can't be factored into two smaller polynomials over $\mathbb{F}_q$) and you tack on solutions to the polynomial to $\mathbb{F}_q$ to make a bigger field $\mathbb{F}_{q^n}$. Elements in the bigger field look like polynomials over $\mathbb{F}_q$, with their multiplication defined by division modulo $p(x)$. If you just take the coefficients of the polynomials that comprise the elements in the big field, you can view the elements of $\mathbb{F}_{q^n}$ as vectors over $\mathbb{F}_q$. If you would like a rigorous description of this process, you can read about it in any abstract algebra book, and all over the web.
For a practical application of this, as it turns out, you can write any polynomial of degree $\leq n$ over $\mathbb{F}_q$ in the form $\sum_{k=0}^{n-1}a_k x^{q^k}$. So, we can view a vector space of dimension $n$ over $\mathbb{F}_q$ as vectors in the basis $(1,x^q,x^{q^2},\ldots,x^{q^n})$. Thus you can set up symmetric bilinear forms by making matrices $A$ in this basis and defining transformations $B(x,y)=x^\intercal A y$. This is the technique behind the Kipnis-Shamir attack on the HFE cryptosystem.