Fork me on GitHub
Math for the people, by the people.

User login

Number of independent variables of f over GF(2)

Primary tabs

Number of independent variables of f over GF(2)

Hello,
I have a degenerate quadratic form f in n indeterminates over GF(2).
I need an algorithm to:
1) Count the number m(<n) of independent variables of f.
2) Convert the quadratic form to a canonical form in m indeterminates.
Any help is appreciated.
I searched on the internet without any results.


Something didn't sit right, now I see what I should have said.

It is not that XQX^t has that form, but rather that q is given by
the matrix in that form with respect to the basis which makes b in the form of hyperbolic pairs. That is, XBX^t has the form

0 1 0....
1 0 0 ....
0 0 0 1 ....
. . 1 0 ....
. . . . 0
. . . . . 0

and you decompose XBX^t= L + L^t where L is upper triangular with 0's on the diagonal. It is not generally true that XQX^t=L, but it could happen. Nonetheless, q is no expressible as q(u)=u(D+L)u^t where
D is the diagonal matrix with entries q(y_i), where y_i form the new basis.

Sorry for any earlier confusion.

Thank you for this very informative answer, Algeboy. It is really helpful.

Yes, I think this is Artin's fault. He wrote "the book" (Geometric Algebra) on bilinear forms and quadratic forms and purposefully left out characteristic 2. He argued that it simplified the reading. Since many authors to follow, followed him, they too have had little to say.

However, you can see these algorithms in a number of places: Bourbaki vol. 24 (which has some mistakes surprisingly!), Chevalley "The algebraic theory of spinors", and/or Taylor "The geometry of classical groups".

You wont find them listed as algorithms but instead you will find the algorithms as proofs that every geometry (with respect to the given quadratic form) has a "standard basis". The proofs are inductive. To start with, note that if you polarize the quadratic form you get an alternating bilinear map (alternating because char=2). Therefore, a you have the usual hyperbolic basis plus a possible radical. The algorithm to write a bilinear form in standard bases is well-known and the same one that works in odd char. works in char 2 as well.
Once you have those coordinates, use that basis to write your quadratic form. All that you have different is the diagonal. That is, if q:V\to K is your quadratic form, and x_1...x_n is any basis, then you can describe q completely by the structure constants:

q(a_1 x_1+...+ a_n x_n) = \sum_{i=1}^n a_i^2 q(x_i)
+ \sum_{1<= i<j<=n} a_i a_j b(x_i,x_j)

where b is the associated bilinear map for q. So q is represented by the matrix Q, so q(u) := uQu^t, which can be taken to be upper triangular with diagonal entries the q(x_i) and the Q_{ij} entries for 1<=i<j<=n are b(x_i,x_j). Similarly, b can be represented by the matrix B where b(u,v)= uBv^t and B_{ij}=b(x_i,x_j), 1<= i,j<= n. Notice this shows that:

B = Q + Q^t

Now changing the basis for V affects B by XBX^t and Q by XQX^t also.
So write B in standard hyperbolic basis + radical, so B looks like

ex:

0 1 0....
1 0 0 ....
0 0 0 1 ....
. . 1 0 ....
. . . . 0
. . . . 0

Let X be the change of basis matrix. So now conjugating Q gives
XQX^t in the form (as argued from the above formula for q)

q1 1 0....
0 q2 0 ....
. . q3 1 ....
. . 0 q4 ...
. . . . q5
. . . . q6

where qi = q(x_i).

You can read off the data you are after easily from that canonical description. You have a bunch of hyperbolic lines followed by a sum of totally isotropic 1-spaces -- those span the bilinear radical.
Those 1-spaces which are non-singular are therefore anisotropic. Note that if the fields is finite and q is nonsingular, then the dimension of the anisotropic component is 1 if the dim is odd, and either 0 or 2 if the dimension is even.

Subscribe to Comments for "Number of independent variables of f over GF(2)"