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

$\endgroup$
5
  • 2
    $\begingroup$ Looks good to me. $\endgroup$
    – Daniel S
    Jun 2, 2023 at 7:51
  • $\begingroup$ Thank's Daniel! $\endgroup$
    – P_Gate
    Jun 2, 2023 at 8:14
  • $\begingroup$ it is correct you can close the question $\endgroup$
    – Don Freecs
    Jun 3, 2023 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, 2023 at 21:07
  • $\begingroup$ Didn't you post this question on Math SE? $\endgroup$ Jun 6, 2023 at 6:51

1 Answer 1

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

$\endgroup$

Your Answer

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

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