# Questions about a vector space over a finite field with a bilinear symmetric form.

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.

-
You want a nondegenerate symmetric bilinear form, not simply a bilinear form. One example of an $n$-dimensional vector space over a finite field ${\mathbf F}_q$ is the field ${\mathbf F}_{q^n}$ of order $q^n$. One nondegenerate symmetric bilinear form ${\mathbf F}_{q^n} \times {\mathbf F}_{q^n} \rightarrow {\mathbf F}_q$ is the trace-pairing $\langle a,b\rangle = {\rm Tr}_{{\mathbf F}_{q^n}/{\mathbf F}_q}(ab)$, and on finite fields the trace function can be written down as a polynomial (this is not possible for infinite fields). –  KCd Dec 19 '12 at 23:11

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.

-
I wouldn't call $\sum_{k=0}^{m-1} a_kx^{q^k}$ a polynomial of degree $\leq n$. Also, these are additive polynomials, so certainly not close to "any" polynomial even without a restriction on the degree. –  KCd Dec 19 '12 at 23:07
@KCd I'm sorry, I misspoke: what I meant was that you can write any polynomial element of $\mathbb{F}_{q^n}$ (that is, any polynomial modulo $p(x)$) in that form. –  Alexander Gruber Dec 19 '12 at 23:08
@AlexanderGruber You're right, I haven't taken field theory yet, actually I only have a very brief intro to group theory under my belt. But your answer clears up what I was trying to get my head around. Field theory sounds interesting - I'll be sure to give it a go. Since this question won't really have a definite single answer, I'll mark this one as the answer. –  Gyu Eun Lee Dec 20 '12 at 0:04

Bilinear forms (nondegenerate) on a vector space over a finite field arise from nonsingular matrices; the important ones are the "reflexive" ones for which $B(x,y) = B(y,x)$ for all $x$ and $y$. These come from nonsingular symmetric or alternating matrices (and give rise to symmetric or symplectic bilinear forms, respectively).

The symmetric forms can also be obtained from what is called a Quadratic form; this is a quadratic homogeneous degree 2 polynomial in the coordinates of the vector space (for example, if we are working over $\mathbb{F}_{q}^{3}$, a quadratic form can be defined by $Q((X_0,X_1,X_2)) = X_0^2 + X_1X_2$. A Bilinear form is described by $B(u,v) = Q(u+v)-Q(u)-Q(v)$ (or (1/2) this value if the characteristic is not $2$).

Not sure of the difficulty as an open problem; nondegenerate bilinear forms over finite fields are completely classified. We have the symplectic form, and then the symmetric forms are classified by their Quadratic form into three types (elliptic, hyperbolic, and parabolic). Usually modding out the polynomial ring by a chosen irreducible polynomial is used to extend fields, in much the same way as creating the complexes from the reals, but this is usually considered a field theory problem (and is well studied), where bilinear forms more fall into geometric type problems.

-
After looking at the previous question, just thought I'd mention that if we allow conjugation maps on the finite fields, then we obtain "sesquilinear maps" instead of bilinear (linear along with a field automorphism), and then we obtain a couple extra types of nondegenerate forms. –  Morgan Rodgers Jul 6 at 13:26