4
$\begingroup$

In this question we are dealing with "$q$-ary" lattices. I will give the definition available to me and I'm interested in proving the lemma. As a reference see the PDF on page 2 from Peikert's lectures.

Definition. Let $\mathbb{Z}_q := \{ 0, 1, \dots, q-1\}$. We define $ \Lambda^{\perp}(\mathbf{A}) := \left\{ \mathbf{z} \in \mathbb{Z^m} : \mathbf{Az = 0} \right\} $, where $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$

Lemma. Let $\mathbf{H} \in \mathbb{Z}_{q}^{n \times n}$ be invertible. Then $\Lambda^{\perp}(\mathbf{HA}) = \Lambda^{\perp}(\mathbf{A}) $.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Looks good to me. $\endgroup$
    – Daniel S
    Jun 2 at 7:51
  • $\begingroup$ Thank's Daniel! $\endgroup$
    – P_Gate
    Jun 2 at 8:14
  • $\begingroup$ it is correct you can close the question $\endgroup$
    – Don Freecs
    Jun 3 at 23:33
  • 1
    $\begingroup$ Really the OP should factor out their proof from the question, and answer their own question with that answer. $\endgroup$
    – Mark
    Jun 5 at 21:07
  • $\begingroup$ Didn't you post this question on Math SE? $\endgroup$
    – Rodrigo de Azevedo
    Jun 6 at 6:51

1 Answer 1

Reset to default
1
$\begingroup$

Thanks for the comments confirming that my proof is correct. As suggested in the comments, I'm happy to answer the question myself.

Proof:

$\Lambda^{\perp}(\mathbf{HA}) \subset \Lambda^{\perp}(\mathbf{A}) $, let $\mathbf{z} \in \Lambda^{\perp}(\mathbf{HA})$ then $\mathbf{HAz = 0}$ and $H$ is invertible implies $\mathbf{H^{-1}HAz = 0}$ and this implies $\mathbf{z} \in \Lambda^{\perp}(\mathbf{A})$.

$\Lambda^{\perp}(\mathbf{A}) \subset \Lambda^{\perp}(\mathbf{HA}) $, let $\mathbf{z} \in \Lambda^{\perp}(\mathbf{A})$ then $\mathbf{Az = 0}$ and multiply by $\mathbf{H}$ implies $\mathbf{HAz = 0}$ and this implies $\mathbf{z} \in \Lambda^{\perp}(\mathbf{HA})$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.