3
$\begingroup$

I was helping someone work on a computing problem with bit vectors that reduced to finding a basis knowing a spanning set, and realized quickly that the Gram-Schmidt process does not work as expected in characteristic-2. Since orthogonality was not a requirement anyway I came up with an alternate approach, but it left me wondering: Is there a way to salvage Gram-Schmidt in this setting (a vector space over $\mathbb{F}_2 = \mathbb{Z}/2\mathbb{Z}$) to get a meaningful concept of orthogonal basis? (Orthonormal seems out of the question since I don't see a way to define a meaningful norm.)

$\endgroup$
  • $\begingroup$ Is the Gröbner Basis what are you looking for? $\endgroup$ – Vlad May 18 '15 at 3:59
  • 1
    $\begingroup$ To simply extract a basis from a set of generators, Gauß elimination into row echelon form should suffice. $\endgroup$ – Hagen von Eitzen May 18 '15 at 4:37
  • $\begingroup$ "Inner products" (=the sum of products of components) are not a reliable tool for detecting linear (in)dependece in characteristic two. It may happen that an entire subspace is orthogonal to itself. For example many interesting error-correcting codes (= linear subspaces of $\Bbb{F}_2^n$) have this property. $\endgroup$ – Jyrki Lahtonen May 18 '15 at 5:19
  • $\begingroup$ @HagenvonEitzen: Yes that's essentially what I did. $\endgroup$ – R.. GitHub STOP HELPING ICE May 18 '15 at 5:48
  • $\begingroup$ @JyrkiLahtonen: Could you expand on that to make an answer? Is there any other definition that can replace inner-product orthogonality to recover useful properties, or is orthogonality just largely meaningless in characteristic 2? $\endgroup$ – R.. GitHub STOP HELPING ICE May 18 '15 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.