Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  neuguy Dec 20 '12 at 0:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.