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

Solution 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$?

Solution 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.