Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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
3  
By the way, I'm considering any $q$, so not only fields. –  Stephen Nov 26 '11 at 6:12
add comment

1 Answer

up vote 12 down vote accepted

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

share|improve this answer
2  
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
2  
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
    
Thanks to both of you. Do you know any reference with such a result? –  Stephen Nov 27 '11 at 21:25
    
By the way, how do you get $A((U^{\perp})^{\perp}) = (V^{\perp})^{\perp}$? –  Stephen Nov 27 '11 at 22:21
    
I'm also interested in a reference, do you know any? –  Carl Jan 17 '12 at 0:52
add comment

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.