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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.
Improve this answer
$\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$
    – Lior Silberman
    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$
    – Lior Silberman
    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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .