1
$\begingroup$

Given arbitrary nonzero vectors $\vec{x}_1, \vec{y}_1, \vec{x}_2, \vec{y}_2 \in \mathbb{Z}^{n}_p$ ($p$ prime) with $\langle x_1, y_1 \rangle = \langle x_2, y_2 \rangle$, I am trying to show that: $(R_1 \vec{x}_1, (R_1^{-1})^{T} \vec{y}_1)$ is distributed identically to $(R_2 \vec{x}_2, (R_2^{-1})^{T} \vec{y}_2)$ where $R_1, R_2$ are random invertible matrices from $\mathbb{Z}_p^{n \times n}$.

Alternatively (and actually preferred), show that for any arbitrary nonzero vectors $\vec{x}_1, \vec{y}_1, \vec{x}_2, \vec{y}_2 \in \mathbb{Z}^{n}_p$ ($p$ prime) such that $\langle x_1, y_1 \rangle = \langle x_2, y_2 \rangle$, there exists an invertible matrix $R$ such that: $R \vec{x}_1 = \vec{x}_2$ and $(R^{-1})^{T} \vec{y}_1 = \vec{y}_2$.

$\endgroup$

1 Answer 1

2
$\begingroup$

Update: solution to the updated problem

Yes, there exists a matrix $R$. It is easy to treat the inner product as identifying $F^n$ with its dual space and phrase the claim as follows:

Fix a field $F$ and a finite-dimensional $F$-vectorspace $V$. Let $u,v\in V$ and let $\phi,\psi\in V^*$ with all four non-zero. Then there exists $R\in\mathrm{GL}(V)$ such that $Ru = v$ and $(R^{-1})^*\phi = \psi$ iff $\phi(u) = \psi(v)$.

Proof. The condition is clearly necessary. For sufficiency let $W = \ker(\phi)$ and let $Z = \ker(\psi)$, both spaces of codimension $1$ in $V$.

  1. Suppose $\phi(u)=\psi(v) \neq 0$. Then we have two direct sum decompositions $V = Fu\oplus W = Fv \oplus Z$. Let $R\in\mathrm{GL}(V)$ be any matrix such that $R.u = v$ and $R.W=Z$. Then $(R^{-1})^*\phi$ is a functional that vanishes on $Z$, hence is proportional to $\psi$. But $\left((R^{-1})^*\phi\right)(v) = \phi(R^{-1}v)=\phi(u)=\psi(v)$ so $(R^{-1})^*\phi = \psi$.

  2. Suppose $\phi(u)=\psi(v) = 0$. Then $u\in Z,\,v\in W$. Let $z,w \in V$ be vectors such that $\phi(z)=\psi(w)=1$. Now choose $R\in\mathrm{GL}(V)$ such that $R.Z=W$ and such that $Ru = v$ and $Rz = w$. The second choice is possible since an isomorphism of $Z,W$ can be chosen to map any specific non-zero vector to any specific non-zero vector, the second since $z,w$ are linearly independent of $Z,W$ respectively. By construction we have $Ru=v$ and $R.Z = W$, the latter forcing $(R^{-1})^*\phi$ to be proportional to $\psi$. Finally, $Rz = w$ ensures that $(R^{-1})^*\phi = \psi$ and we are done.

Solution to the original problem

The original statement concerned the distribution of the pair $\left(Rx,R^{-1}y\right)$ rather than $\left(Rx,(R^{-1})^Ty\right)$. The distribution is as follows:

Let $R$ be a uniform invertible matrix. The marginal on $\vec{z} = R \vec{x}$ is then a uniform non-zero vector. Conditioning on $\vec{z}$ we have two possibilities: either $\vec{z}$ is proportional to $\vec{y}$, at which point $R^{-1}\vec{y}$ is a fixed multiple of $\vec{x}$, or it is not, at which point $R^{-1}\vec{y}$ is uniformly distributed over all vectors not proportional to $\vec{x}$.

It follows that the pair $\left(R\vec{x},R^{-1}\vec{y}\right)$ is distributed over the union $$ \left\{ \left(\vec{z},\vec{w}\right) \mid \vec{z}\textrm{ indep of }\vec{y} \wedge \vec{w}\textrm{ indep of }\vec{x}\right\} \cup \left\{ \left(\alpha\vec{y},\alpha^{-1}\vec{x}\right) \mid \alpha\in\mathbb{F}_p^\times\right\} $$ where the distribution is uniform in each side, and the probability of ending on the right is $\frac{p-1}{p^n-1} = \frac{1}{1+p+\cdots+p^{n-1}}$.

Conclusion: in the original formulation

  1. The distribution depends on the pair $\left(\vec{x},\vec{y}\right)$.
  2. The pairing $\left\langle<\vec{x},\vec{y} \right\rangle$ does not play a role.
$\endgroup$
6
  • $\begingroup$ I think the value $\langle \vec{x}_i, \vec{y}_i \rangle$ does play a role, since $(R^{-1}_i \vec{y}_i)^{T} \cdot R_i \vec{x}_i = \langle \vec{x}_i, \vec{y}_i \rangle$. (So at least when you say $R_1^{-1}\vec{y}_1$ is uniformly distributed over all vectors not proportional to $\vec{x}_1$, this cannot be true -- it at least has to be uniformly distributed over all vectors not proportional to $\vec{x}_1$ such that its dot product with $\vec{z}_1$ equals $\langle \vec{x}_1, \vec{y}_1 \rangle$, no?) $\endgroup$
    – lkowalcz
    Commented Jun 22, 2018 at 15:47
  • $\begingroup$ I might be missing something but I think you're confusing the inverse and the transpose. $\endgroup$ Commented Jun 22, 2018 at 15:50
  • $\begingroup$ I don't think I am. I just wanted to point out that the dot product of the two new vectors: $R_i \vec{x}_i$ and $R^{-1}_i \vec{y}_i$, is equal to the dot product of the original vectors: $\vec{x}_i$ and $\vec{y}_i$. (this is true, no?). So, the value does seem to play a role -- you can't argue that the distribution of the new vectors is a pair of vectors that have a different dot product, for example. $\endgroup$
    – lkowalcz
    Commented Jun 22, 2018 at 15:53
  • 1
    $\begingroup$ You are confusing the inverse and the transpose. The identity you're thinking about is $\left\langle R\vec{x},\vec{y} \right\rangle = \left\langle \vec{x},R^T \vec{y} \right\rangle$. To see your claim is wrong let $R = \pmatrix{ 1 & 1\\ 0 & 1}$ and let $\vec{x} = \pmatrix{ x_1 \\ x_2}$, $\vec{y} = \pmatrix{ y_1 \\ y_2}$. Then $\left\langle R\vec{x},\vec{y} \right\rangle = x_1y_1 + x_2y_2 + x_2y_1$ whereas $\left\langle \vec{x},R^{-1}\vec{y} \right\rangle = x_1y_1 + x_2y_2 - x_1y_2$. $\endgroup$ Commented Jun 22, 2018 at 16:17
  • $\begingroup$ D'oh you're right! Sorry about that -- I've updated my question to be the one I actually had in mind. $\endgroup$
    – lkowalcz
    Commented Jun 22, 2018 at 17:01

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.