Orthogonal complement in a finite field ${\mathbb Z}^{n}_{q}$

Question

When $V=\mathbb{Z}^n_q$ is a vector space, where $\mathbb Z_q$ is the set of integers modulo prime $q>2$, are the following statements true?

1. If $U ⊂ V$ is a $k$-dimensional subspace, then $$ U^⊥= \{ x∈V∣x^Tu=0 \ \mathrm {for\ all}\ u∈U \} $$ is of dimension $n-k$.

2. (If statement 1 is true) $U^⊥$ can be written by $n-k$ orthogonal vectors.

For an example of statement 1, if $V=\mathbb{Z}^3_3$, and $U=\{ a_1(1,2,1)^T+a_2(0,1,1)^T\ |\ \forall a_1,a_2\in\mathbb Z_3\} $ then $U^⊥$ can be expressed with basis $(1,2,1)^T$.

I'm not familiar with using linear algebra in finite fields, so I don't know how I should handle "orthogonal" vectors. I wrote down some examples and am pretty sure that statement 1 holds in finite fields, as it does in real case, but I'm not so certain of statement 2. Furthermore, I don't have a clue on how to prove these statements.

I'm not used to using English, so if there's anything wrong with my explanation, don't hesitate to ask. Thanks for your help!

Answer 1

1. You probably want to apply rank-nullity, so find a linear transformation which expresses $U^\perp$ as an image or kernel. For instance, consider the linear transformations $T_u \colon V \to \mathbb{Z}_q$ given by $x \mapsto x^T u$. Then $U^\perp = \cap_{u \in U} \ker T_u$. Fix a basis $u_1, \ldots, u_k$ of $U$; it's clear $U^\perp = \cap_{u_i} \ker T_{u_i}$. Glue the transformations together by considering $T \colon V \to \mathbb{Z}_q^k$ given by $x \mapsto (x^T u_i)_{i=1}^k$. Hence $U^\perp = \ker T$, so $\dim U^\perp = n - \dim {\rm im}(T)$. So, we just need to show $\dim {\rm im}(T) = k$. For that, notice that $T$ is given by right-multiplying $x^T$ by the matrix $(u_1, \ldots, u_k)$ ($u_i$ being column vectors here). By definition, this has column-span of dimension $k$, so it has row-span of dimension $k$, so $\dim {\rm im}(T) = k$. (For reference on this part, see here.)

2. Since it's possible for $u^T u = 0$ for $u \neq 0$, one can't interpret $u^T u$ as (square) "length" and divide by it. I can't think of anything else "orthonormal" would refer to. Edit: Ah, you actually mean "orthogonal", in the sense that you want a basis $\{u_i\}$ for $U^\perp$ where $u_i^T u_j = 0$ for all $i \neq j$. It's a little hard to find counterexamples, since the Gram-Schmidt process actually works with the usual inner product replaced by $u^T v$, at least whenever you don't divide by $0$, i.e. whenever none of your intermediate vectors satisfies $u^T u = 0$. A problem with Mike's subspace is that it's a subset of $Z = \{u \in \mathbb{Z}_q^n : u^T u = 0\}$. Interestingly, it seems $Z$ is itself a vector subspace if and only if $q=2$ (more generally, in characteristic $2$). Maybe this will help guide the construction of a counterexample/a proof that no counterexamples exist for $q>2$?

Answer 2

(2) is false. For example, if $U$ is the 1D subspace $\{(0,0,0), (1,1,1)\}$ of $\mathbb{Z}_2^3$, then $U^\bot$ is the 2D subspace $\{(0,0,0), (1,1,0), (1,0,1), (0,1,1)\}$ which has no orthogonal basis.

(1) is true. Here's a sketch without all the details.

Claim 1: Let $X$ be a vector space over a field $F$. Suppose $x_1,\ldots,x_k \in X$ are vectors, $\varphi_1,\ldots,\varphi_k \in X^*$ are functionals, and that $\varphi_i(x_j) = \delta_{ij}$, the Kronecker delta. Then, $x \mapsto \sum_{i=1}^k \varphi_i(x) x_i$ is a rank-$k$ projection with range $\operatorname{span}\{x_1,\ldots,x_k\}$ and kernel $\bigcap_{i=1}^k \ker(\varphi_i)$. In particular (e.g. by rank-nullity), $\dim(X) = k + \dim \left(\bigcap_{i=1}^k \ker(\varphi_i) \right)$.

Claim 2: Let $X$ be a vector space over a field $F$ and let $\varphi_1,\ldots, \varphi_k \in X^*$ be functionals. Then, $\varphi_1,\ldots,\varphi_k$ are linearly independent in $X^*$ if and only if there exist $x_1,\ldots,x_k \in X$ such that $\varphi_i(x_j) = \delta_{ij}$.

Claim 1 is quite direct. One of the implications of Claim 2 is easy, and the other implication comes from a Gramm-Schmidt type construction using Claim 1.

Now, in your situation, the standard inner-product on $\mathbb{Z}_q^n$ can be thought of as a choice of isomorphism $\mathbb{Z}_q^n \cong (\mathbb{Z}_q^n)^*$ so that $U$ can be thought of as a subpace of $(\mathbb{Z}_q^n)^*$. Choose a basis $\varphi_1,\ldots,\varphi_n$ for $U$, note $U^\bot = \bigcap_{i=1}^k \ker(\varphi_i)$ in this instance, and apply the equality from Claim 1.

Answer 3

You haven't said what your definition of $U^\perp$ is, so it's rather hard to check whether it's equal to something. You also don't say what goal or application you have in mind, so it's also hard to suggest how to get there.

But orthogonality over finite fields is a very strange concept, and certainly does not perfectly translate from the real case. For example, suppose that $n=q$, and $U=\langle u \rangle$, where $u=(1,1,\ldots,1)$. Then $u^T u = 1+1+\ldots+1 = q = 0$, so $u\in U^\perp$ if we use the above definition!

Also, you should keep in mind that, just like over $\mathbb{Q}$, you might have to extend the field to scale a basis to be orthonormal. For instance, take $(1,1)$ over $\mathbb{F}_3$. Then the normalized vector is $\frac{1}{\sqrt{2}} (1,1)$. But $2$ isn't a square in $\mathbb{F}_3$! We need to look in $\mathbb{F}_9^2$, the vector space over the field with 9 elements, to find the normalized vector.

With these caveats, much of the same theory works. For example, it seems to be true that $\dim{U} + \dim{U^\perp} = \dim V$, if we use your Statement #1 as a definition. But it's no longer true that $V=U+U^\perp$, since we may have $U\cap U^\perp \neq 0$.

As a general rule, things that you can prove using the basic algebra of matrices and determinants will still be true, while anything requiring the inner product might fail if it uses properties of $\mathbb{R}$.