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

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.

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