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.

In answer to the question here:

Lights out game on hexagonal grid

The following argument is given:

"Thus if v is in the null space of A, then d is orthogonal to v and as a consequence, d is in the row space of A."

Here everything is over $\mathbb{F}_2$, and the "inner product" is the standard dot product $x\cdot y=\sum_{i=1}^nx_iy_i$.

However, this is not an inner product at all! It may very well be the case that $x\cdot x=0$ but $x\ne 0$.

I'm sure that a certain amount of linear algebra can still be preserved here. In particular, if I can prove that $$\dim W + \dim W^\perp = \dim V$$ it will suffice. So my main question here is how can I prove the above equality in this setting.

share|improve this question
    
Dear Gadi: The equality $\dim W + \dim W^\perp = \dim V$ holds whenever the bilinear form is non-degenerate. The proof is the obvious one. (I assume $\dim V < \infty$.) –  Pierre-Yves Gaillard Jan 24 '12 at 15:53

2 Answers 2

Let $f$ be a non-degenerate bilinear form on a finite dimensional vector space $V$, let $W$ be a subspace, and let $X$ be the right orthogonal of $W$. Then we have $$ \dim W+\dim X=\dim V. $$ Proof. The map $g:V\to V^*$ defined by $g(v)(v'):=f(v',v)$ is bijective.

The restriction map $V^*\to W^*$ is surjective and its kernel is $g(X)$.

share|improve this answer

The usual definition of inner product makes essential use of the properties of $\mathbb{R}$ and $\mathbb{C}$ and so is not really available for vector spaces over fields which are not subfields of $\mathbb{C}$. However, once we drop the positive-definiteness condition what we are left with is the notion of a non-degenerate symmetric bilinear form. Explicitly,

Definition. Let $V$ be a vector space over the field $k$. A non-degenerate symmetric bilinear form is a function $f : V \times V \to k$ with the following properties:

  1. $f(v, w) = f(w, v)$
  2. $f(\lambda v, w) = \lambda f(v, w)$
  3. $f(u + v, w) = f(u, w) + f(v, w)$
  4. If $f(v, w) = 0$ for all $w$, then $v = 0$.

Now, let $V$ be equipped be a non-degenerate symmetric bilinear form $(v, w) \mapsto \langle v, w \rangle$. This is good enough to make sense of various other notions in linear algebra, at least in the finite-dimensional case. (In the infinite-dimensional case things are better if we introduce some analytic/topological considerations.) From here on all vector spaces are assumed to be finite-dimensional and equipped with a non-degenerate symmetric bilinear form.

  1. The linear map $V \to V^*$ defined by $v \mapsto \langle v, - \rangle$ is an isomorphism of vector spaces.

  2. This implies that for any linear map $T : V \to W$, there is a unique linear map $T^* : W \to V$ such that $$\langle T^* v, w \rangle = \langle v, T w \rangle$$

  3. For any subspace $U$, let $U^\perp$ be the subspace defined below: $$U^\perp = \{ w \in V : \forall u \in U . \, \langle u, w \rangle = 0 \}$$ It is precisely the kernel of the linear map $V \to U^*$ defined by $v \mapsto (w \mapsto \langle v, w \rangle)$. By (1) $V \to V^*$ is surjective, and the restriction map $V^* \to U^*$ is surjective (by choosing a basis of $U$ and extending to a basis of $V$), so by the rank-nullity theorem $$\dim U^\perp + \dim U^* = \dim U^\perp + \dim U = \dim V$$ as required.

    Unfortunately, as Henning points out in the comments, it may happen that $U \cap U^\perp \ne \{ 0 \}$. A counterexample can be constructed in every even dimension. Let $n$ be a positive integer, and let $V = k^{2n}$ with standard basis vectors $e_1, \ldots, e_{2n}$. Suppose $\operatorname{char} k = 2$, i.e. $1 + 1 = 0$. Let $$\langle e_i, e_j \rangle = \begin{cases} 1 & \text{if } i + n = j \text{ or } j + n = i \\ 0 & \text{otherwise} \end{cases}$$ and extend to bilinearly to $V \times V$. This is easily checked to be a non-degenerate symmetric bilinear form, but by construction $\langle e_i, e_i \rangle = 0$ for each $e_i$! (But, for $\operatorname{char} k \ne 2$, there exist some vector $v$ so that $\langle v, v \rangle = 0$.)

share|improve this answer
    
How about $V=(\mathbb F_2)^2$ and define $\langle v,w\rangle=1$ iff $v$ and $w$ are different nonzero vectors? In that case $U^\bot=U$ for a one-dimensional subspace $\{0,v\}$, so $U\cap U^\bot=\{0\}$ seems to fail. Or did I miss some condition on "nondegenerate symmetric bilinear form" that this example doesn't satisfy? (I think this is basically a case of the usual equivalence between "symmetric bilinear" and "quadratic" forms breaking down in characteristic 2). –  Henning Makholm Jan 24 '12 at 17:18
    
@Henning: That seems to be the only part of the theorem that breaks – everything else is still true, though we have to weaken "equals" to "is isomorphic to" in $V \cong U \oplus U^\perp$. –  Zhen Lin Jan 24 '12 at 18:12
    
Not only is it true that it might happen that $U \cap U^\perp \ne \{ 0 \}$, but it might also be that $U = U^\perp$. Over $(\mathbb F_2)^2$ equipped with the usual inner product, if $U$ is the one-dimensional subspace $U = \{[0,0], [1,1]\}$, then $U^\perp = U$. There is some literature in coding theory on the topic of self-dual codes, subspaces $U$ of dimension $n$ of the $2n$-dimensional space $(\mathbb F_2)^{2n}$ for which $U^\perp = U$. –  Dilip Sarwate Jan 24 '12 at 19:46

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.