Conditions of P for existence of orthogonal matrix Q and permutation matrix U satisfying QP = PU

Question

Question: Let $P\in \mathbb{R}^{d\times n}$ be a $d$-rank real matrix and $PP^T = c I_d$ with a certain constant $c > 0$. Under what additional conditions of $P$ does there exist an orthogonal matrix $Q\in O(d), Q\ne I_d$ and a permutation matrix $U\in S_n, U\ne I_n$ such that the equation $QP=PU$ holds?

Here, $O(d)$ denotes the set of $d\times d$ orthogonal matrices, and $S_n$ denotes the set of $n\times n$ permutation matrices.

Thoughts: This question arises when I am studying group theory and affine geometry, where I am interested in the mathematical formalization of "self-symmetric" structures for $n$ vectors in $d$-dimensional Euclidean space.

For $P$ to satisfy the equation $QP = PU$, it is necessary for $P$ to have at least two columns with identical norms. This allows the set of vectors forming the columns of $P$ to be invariant to certain rotations/reflections, i.e., applying a certain rotation/reflection $Q$ to each of the vectors in this set again gives the original set. For example, consider $$ P = \begin{pmatrix} 1 & -1 & 0 & 0\\ 0 & 0 & 1 & -1 \end{pmatrix}. $$ A solution could be $$ Q = \begin{pmatrix} 0 & -1 \\ -1 & 0 \end{pmatrix} \quad \text{and} \quad U=\begin{pmatrix} 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{pmatrix}. $$ This example involves four 2-dimensional unit vectors aligned with the axes. After rotations of $90^{\circ},180^{\circ}$ or $270^{\circ}$, possibly followed by reflections, the transformed vectors by $Q$ remain as the columns of $P$. Similarly, $$ P = \begin{pmatrix} 1 & -1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & -1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & -1 \end{pmatrix}, $$ is also a desired $P$ with one of the solutions

$$ Q = \begin{pmatrix} 0 & 0 & -1 \\ 0 & -1 & 0 \\ -1 & 0 & 0 \end{pmatrix} \quad \text{and} \quad U=\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}. $$

In addition, I can trivially obtain $QP = PU \implies Q =\frac{1}{c} PUP^T \implies I_d = \frac{1}{c^2}PUP^T P U^T P^T$, but I do not have additional information for $P^T P$ except it has $d$ repeated eigenvalues with the other $n-d$ eigenvalues zero.

Further insights, relevant references, or avenues for additional study are much appreciated.

Answer 1

If $QP=PU$ then the matrix $PU$ has this in common with $P$: $$ (PU)^TPU=(QP)^TQP=P^TQ^TQP=P^TP. $$ That is, when the columns of $P$ are permuted according to the permutation $U$, their pairwise inner products are unchanged. (So this is stronger than the statement that two of them have the same norm.)

This necessary condition is also sufficient. If two $n$-tuples $v_1,\dots ,v_n$ and $w_1,\dots ,w_n$ of vectors in $\mathbb R^d$ are such that $v_i\cdot v_j=w_i\cdot w_j$ for all $i$ and $j$ then there is a linear isometry $Q$ such that for all $i$ $Qv_i=w_i$. Applying this with $v_i$ the $i$th column of $P$ and $w_i$ the $i$th column of $PU$, we see that if $(PU)^T(PU)=P^TP$ then there exists $Q$ such that $QP=PU$.