When is a relation representable as matrix commutation? Given a relation $R$ on a set $S$, when is there an injection $f:S\hookrightarrow \text{End}(V)$ for some vector space $V$ such that for all $x$ and $y$ in $S$, we have $x\,R\,y$ iff $[f(x),f(y)]=0$? The case where $V$ is a Hilbert space and we demand that the image of $f$ be hermitian matrices is of particular interest.
Since $[M,M]=0$ and $[M,N]=-[N,M]$, we need at the very least that $R$ is reflexive and symmetric. However, I believe these are not sufficient. Indeed, if we consider the set $S=\{a,b,c,d\}$, and the relation which is the reflexive/symmetric completion of:
$$\{(a,b),(b,c),(c,d),(d,a)\},$$
then I believe that to not be representable as commutation (not for good reasons, I just couldn't find an example after trying obvious things).
I tried solving this problem by restricting to the hermitian case and saying that matrices commute when their eigenspaces are compatible, but I couldn't extract a simple condition on $R$ from this.
Motivation: In quantum mechanics, observables are simultaneously measurable if they commute. I am interested in the restrictions this places on the "simultaneously measurable" relation. Symmetric and reflexive are very natural properties for this relation to have on physical grounds, but I am wondering if there are other restrictions. 
 A: Any symmetric and reflexive relation may be represented this way.
For simplicity, let us say a relation is representable if such a map exists.
Lemma. Let $R_1$ and $R_2$ be representable relations on a set $S$, with representations $f_1: S \to  End(V_1)$ and $f_2: S \to End(V_2)$.
Then the intersection of the relations $R_1 \cap R_2$ is representable.
Proof. Consider the map $g: S \to End(V_1 \times V_2)$ which maps $s$ to the block diagonal matrix
$$
g(s) = \left( \begin{array}{cc} f_1(s) & 0 \\ 0 & f_2(s) \end{array}\right).
$$
This is a representation since $g$ is injective if $f_1$ or $f_2$ is.
Then $g(s_1)$ and $g(s_2)$ commute if and only if $f_i(s_1)$ and $f_i(s_2)$ commute for both $i = 1,2$, that is, if $s_1$ and $s_2$ are related in both $R_1$ and $R_2$.
Hence, it suffices to show that a family of relations which generate all symmetric and reflexive relations under intersection is all representable.
Such a family is exactly the relations on $S$ where everything is related except for two chosen elements $a$ and $b$.
But this relation may be represented by mapping $a$ and $b$ to any pair of non-commuting matrices, while mapping all other elements of $S$ to multiples of the identity.
Note that all our matrices may be chosen to be Hermitian as well, since a block diagonal Hermitian matrix is also Hermitian.
