# “Orthogonal complement” in $\mathbb{Z}_q^n$

Let $W$ be the finite $\mathbb{Z}$-module obtained from $\mathbb{Z}_q^n$ with addition componentwise where $\mathbb{Z}_q$ is the integers mod $q$. Let $V$ be a submodule of $W$. Let $V^{\perp} = \{w \in W : \forall v \in V \quad w \cdot v = 0 \}$ where $w\cdot v = w_1v_1 + \ldots + w_nv_n$. Is it true that ${(V^{\perp})}^{\perp} = V$ for all $q \geq 2$?

According to Wikipedia, this holds for finite dimensional inner product space, but I wish to know whether it holds in $\mathbb{Z}_q^n$ where $\cdot$ isn't an inner product.

-
Yes, this is true and quite elementary (in general this is true over an arbitrary field), so off-topic for this site. –  Qiaochu Yuan Nov 26 '11 at 6:04
I'm sorry if it appears elementary to you, but I've never seen this in any textbook. I need this for my research, but I'm a computer scientist, not a mathematician. –  Stephen Nov 26 '11 at 6:11
By the way, I'm considering any $q$, so not only fields. –  Stephen Nov 26 '11 at 6:12

Yeah, it's true. Since $\mathbb{Z}/q$ is a principal ideal ring, there is an extension of the Euclidean algorithm to matrices that puts any matrix in Smith normal form. It means that after an automorphism of $(\mathbb{Z}/q)^n$, any submodule $V$ can be put into a standard form in which it is generated by vectors of the form $d_k e_k$, where $e_k$ is a standard basis vector, $d_k$ is a divisor of $q$, and each $k$ only appears at most once. In that case you can check directly that $(V^\perp)^\perp$ is no larger than $V$.
(I'm taking the question in the more interesting case in which $q$ might not be prime.)
Let me add some detail which may be useful for Stephen, depending on his background. Greg is saying there is a basis $w_1,\dots,w_n$ of $({\mathbf Z}/q)^n$ and integers $d_1,\dots,d_m$ (where $m \leq n$) dividing $q$ such that $d_1w_1,\dots,d_mw_m$ is a basis of $V$. The matrix $A$ having columns $w_1,\dots,w_n$ is in $GL_n({\mathbf Z}/q)$ and $A(U) = V$ where $U$ has basis $d_1e_1,\dots,d_me_m$. Then $A((U^\perp)^\perp) = (V^\perp)^\perp$, so $(V^\perp)^\perp = V$ iff $(U^\perp)^\perp = U$. By direct calculation, $U^\perp$ has basis $(q/d_1)e_1,\dots,(q/d_m)e_m,e_{m+1},\dots,e_n$ [contd.] –  KConrad Nov 26 '11 at 16:14
and $(U^\perp)^\perp$ has basis $d_1e_1,\dots,d_me_m$, so $(U^\perp)^\perp = U$. (Note, by the way, that $V^\perp$ is not $A(U^\perp)$ but rather $(A^{-1})^\top(U^\perp)$.) –  KConrad Nov 26 '11 at 16:18
By the way, how do you get $A((U^{\perp})^{\perp}) = (V^{\perp})^{\perp}$? –  Stephen Nov 27 '11 at 22:21