Let $q_i$ for $i=1,\dots,m$ be the columns of the matrix $Q \in \mathbb{R}^{n \times m}$, where $n \geq 2m$, which are pairwise orthonormal, i.e.,
$$q_i^\top q_j = \begin{cases} 1 & \text{if}\quad i=j \\ 0 & \text{otherwise} \end{cases}$$
Further, let $ P\in \{0, 1\}^{n \times n}$ be a permutation matrix and
$$M = Q^\top P^\top Q$$
How does the permutation $P$ has to be designed, so that the maximum singular value
$$\sigma_{\text{max}}(M)<1\text{ ?}$$
Background
$\sigma_{\text{max}}(M)=\cos(\theta_{\text{min}})$, where $\theta_{\text{min}}$ is the minimal principal angle between the spaces spanned by the columns of $Q$ and $P^\top Q$. So, if $P$ is the identity matrix the columns of $Q$ and $P^\top Q$ span the same space, so that $\theta_{\text{min}}=0$ and $\sigma_{\text{max}}(M)=1$. Of course, there are other permutation which lead to $\sigma_{\text{max}}(M)<1$. So I could also ask: How to choose $P$, so that the minimal angle between $\mathcal{R}(Q)$ and $\mathcal{R}(P^\top Q)$ is $\theta_{\text{min}}>0$ ? ($\mathcal{R}=$ range)
It is a curious question. If you want that the readers work about it, give its context.
I assume that the essential condition $n\geq 2m$ is fulfilled and I use the following notation $M=Q^TP_{\sigma}Q$ where $\sigma$ is a permutation of $\{1,\cdots,n\}$; if $\sigma=\sigma_1\circ\cdots\circ\sigma_p$ is the decomposition of $\sigma$ in disjoint cycles, then let $f(\sigma)=p+\text{number of fixed points of } \sigma$.
The result is, a priori, astonishing; numerical experimentations seem to show that
(for every $Q$ satisfying $Q^TQ=I_m$, $\sigma_{max}(Q^TP_{\sigma}Q)=1$) iff $f(\sigma)>n-m$.
EDIT. Answer to Rob. You did not read my post.
Your "background" is well-known. The question is why to use permutation matrices.
My conjecture is an equivalence. If $f(\sigma) >n-m$ then, for any $Q$, $\sigma_{max}=1$. You say that you have a proof. When you post such a question, the least you can do is: to present such a proof; the second part of my conjecture is: if $f(\sigma) \leq n-m$, then there is $Q$ s.t. $\sigma_{max}<1$. You write that the previous result is false; give a counter-example.