Permutation rigidity conjecture for a diagonal stationarity condition

Counterexample in every tested rectangular dimension, complete corrected rigidity theorem, and unconditional repair of the trace maximum.

Centorrino–Bullo–Russo, arXiv:2506.06134, Appendix D, Conjecture 3, asks whether diagonality of

$$K(U)=U^{\mathsf T}\Lambda_1^{\mathsf T} \bigl(\Lambda_1U\Lambda_2U^{\mathsf T}\Lambda_1^{\mathsf T}\bigr)^{-1/3} \Lambda_1U$$

forces $U\in O(n)$ to be a permutation, where

$$\Lambda_1=[D\ \ 0]\in\mathbb R^{m\times n}, \qquad \Lambda_2>0$$

are diagonal and $\Lambda_2$ has distinct entries. The paper was subsequently published in Neural Computation 38 (2026), 725–764, doi:10.1162/NECO.a.1509; the precise conjecture and numbering here refer to the accessible arXiv version.

A fully rational counterexample is

$$\Lambda_1= \begin{pmatrix}2&0&0&0\\0&1&0&0\end{pmatrix}, \qquad \Lambda_2=\operatorname{diag}(2,1,1/2,1/3),$$ $$U= \begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&3/5&-4/5\\ 0&0&4/5&3/5 \end{pmatrix}.$$

Here $U$ is orthogonal but not a permutation,

$$\Lambda_1U\Lambda_2U^{\mathsf T}\Lambda_1^{\mathsf T} =\operatorname{diag}(8,1),$$

and nevertheless

$$\boxed{K(U)=\operatorname{diag}(2,1,0,0).}$$

More generally, for every $n\ge m+2$, take

$$D=\operatorname{diag}(m,m-1,\ldots,1),$$ $$\Lambda_2= \operatorname{diag}\left(m,m-1,\ldots,1, \frac12,\frac13,\ldots,\frac1{n-m+1}\right),$$

and any nonpermutation $Q\in O(n-m)$. With

$$U=I_m\oplus Q$$

one has

$$\boxed{K(U)=\operatorname{diag}(m,m-1,\ldots,1,0,\ldots,0).}$$

Thus there is a continuous family of counterexamples even though both the active diagonal entries and the eigenvalues of $\Lambda_2$ are pairwise distinct. In particular, the conjecture fails in all five dimension pairs actually tested in the source:

$$(5,10),\ (10,20),\ (10,50),\ (50,100),\ (50,500).$$

The complete correction is as follows. Put

$$Y=\Lambda_1U,\qquad C=Y\Lambda_2Y^{\mathsf T}.$$

If $K=Y^{\mathsf T}C^{-1/3}Y$ is diagonal, its nonzero columns are mutually orthogonal in the positive definite $C^{-1/3}$-inner product. Since $\operatorname{rank}Y=m$, exactly $m$ columns are nonzero. After an active-column permutation $\Pi$, orthogonality forces

$$U\Pi=V\oplus Q,\qquad V\in O(m),\quad Q\in O(n-m).$$

Writing

$$H=V\Lambda_JV^{\mathsf T},\qquad C=DHD$$

for the selected active eigenvalues, diagonality of the active block is equivalent to

$$[DC^{-1/3}D,H]=0 \iff [D^2,C^{2/3}]=0 \iff [D^2,H]=0.$$

Therefore

$$\boxed{ K(U)\text{ diagonal} \iff U\Pi=V\oplus Q \ \text{and}\ [D^2,V\Lambda_JV^{\mathsf T}]=0.}$$

When the entries of $D^2$ are distinct, $V$ is a signed permutation, but the inactive orthogonal block $Q$ remains completely unrestricted.

The false auxiliary conjecture is not needed for the source’s intended trace maximum. Assume $d_1\ge\cdots\ge d_m>0$ and $\lambda_1\ge\cdots\ge\lambda_n>0$, and set

$$Z=[D\ \ 0]U\Lambda_2^{1/2}.$$

For $1\le j\le m$, the exterior-power singular-value inequality gives

$$\prod_{i=1}^{j}s_i(Z) = \|\wedge^j Z\| \le \prod_{i=1}^{j}d_i\sqrt{\lambda_i}.$$

Applying the increasing convex function $x\mapsto e^{2px}$ to the resulting logarithmic weak majorization yields, for every $p>0$,

$$\operatorname{tr} \bigl(\Lambda_1U\Lambda_2U^{\mathsf T}\Lambda_1^{\mathsf T}\bigr)^p \le \sum_{i=1}^{m}d_i^{2p}\lambda_i^p.$$

Equality holds at $U=I_n$. Hence

$$\boxed{ \max_{U\in O(n)} \operatorname{tr} \bigl(\Lambda_1U\Lambda_2U^{\mathsf T}\Lambda_1^{\mathsf T}\bigr)^p = \sum_{i=1}^{m}d_i^{2p}\lambda_i^p \qquad(p>0).}$$

In particular, the source’s $p=2/3$ trace-maximization lemma remains valid unconditionally despite the failure of its proposed permutation-rigidity premise.