# Unitary matrix commute with function

I'm wondering in which cases the following identity is satisfied : $$f\left(UXU^T\right) = Uf\left(X\right)U^T$$ where $$X \in \mathbb{R}^{n\times n}$$ is a square matrix, $$U$$ is any permutation matrix and $$f:\mathbb{R}^{n\times n} \rightarrow \mathbb{R}^{n\times n}$$

I already know of two cases :

1. $$f$$ can be expressed as a matrix Taylor series (in this case $$U$$ could be any unitary matrix)
2. $$f$$ is an element-wise function

Are these the general cases?

Bonus :

Is there an extension of the preceding identity to tensors $$T \in \mathbb{R}^{n^m}$$ and $$f:\mathbb{R}^{n^m} \rightarrow \mathbb{R}^{n^m}$$. I am not sure what form the product and the operator $$U$$ would take in that case.

• Other examples: (1) $f$ is an entrywise odd function and $U=\operatorname{diag}(1,-1)$, (2) $f$ is any function and $U=I$. Commented Sep 1, 2020 at 15:53
• Since this question has not received much attention, you might want to change this to the context of your/others' research and ask if in that situation, with $U,f$ having certain properties does this result hold : because even if $f$ is somewhat irregular, then for special $X,U$ this could work. Commented Sep 12, 2020 at 3:06
• $U$ is an unitary matrix or arbitrary unitary matrix? Is $U$ fixed? Commented Sep 12, 2020 at 18:36
• I made the question a bit more precise : $U$ is any permutation matrix and $X$ is any square matrix. Both are fixed. I'll ask a different version of the question if it does not find an answer... Commented Sep 13, 2020 at 14:27
• Much better! The answer below is brilliant. Commented Sep 14, 2020 at 10:31

## 1 Answer

Here's a bit of relevant literature:

• Deep Sets (NIPS 2017) classifies all linear functions $$\mathbb R^{n\times k} \to \mathbb R^{n\times l}$$ that are permutation invariant / equivariant across the first axis.

• On Universal Equivariant Set Networks (ICLR 2020) deals with the case of finding all homogeneous polynomial functions $$\mathbb R^{n\times k} \to \mathbb R^{n\times l}$$ that are permutation equivariant across the first axis.

• Invariant and Equivariant Graph Networks (ICLR 2019) deals with the case of finding linear functions $$\mathbb R^{n^k} \to \mathbb R^{n^k}$$ that are permutation invariant / equivariant across all $$k$$ axes

Especially, the 3rd paper gives as an example the case of linear function $$\mathbb R^{n^2}\to\mathbb R^{n^2}$$ that are permutation equivariant across each axis, i.e. $$f(P^T X P)=P^T f(X) P$$, which is precisely your problem. They show that the space of such linear functions is $$15$$-dimensional, independent of $$n$$ (!).

One can combine papers 2 and 3 to find all homogeneous polynomial functions $$\mathbb R^{n^k}\to\mathbb R^{n^k}$$ that are permutation equivariant across all $$k$$ axes.