4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Other examples: (1) $f$ is an entrywise odd function and $U=\operatorname{diag}(1,-1)$, (2) $f$ is any function and $U=I$. $\endgroup$
    – user1551
    Commented Sep 1, 2020 at 15:53
  • $\begingroup$ 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. $\endgroup$ Commented Sep 12, 2020 at 3:06
  • $\begingroup$ $U$ is an unitary matrix or arbitrary unitary matrix? Is $U$ fixed? $\endgroup$
    – C.F.G
    Commented Sep 12, 2020 at 18:36
  • 1
    $\begingroup$ 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... $\endgroup$
    – Undead
    Commented Sep 13, 2020 at 14:27
  • $\begingroup$ Much better! The answer below is brilliant. $\endgroup$ Commented Sep 14, 2020 at 10:31

1 Answer 1

5
+50
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .