Almost commuting unitary matrices Suppose that $A_1,\dots, A_k$ are unitary matrices such that any two of them can be approximated by commuting unitary matrices. i.e. for any $i$ and $j$, there are unitary matrices $A_i'$ and $A_j'$ such that $\|A_i-A_i'\|<\varepsilon$, $\|A_j-A_j'\|<\varepsilon$ and $A_i'A_j'=A_j'A_i'$. Can we find unitary matrices $X_1,\dots,X_k$ such that any two of them commute and $\|X_i-A_i\|<O(\varepsilon)$ for all $i$?
What if any three (or small number) of them can be simultaneously approximated by commuting unitary matrices?
Here the matrix norm could be any unitary invariant norm. I'm specially interested in the operator norm and Hilbert-Schmidt norm.
 A: Edit Now this answers the first question for the operator norm and the normalized Hilbert-Schmidt norm.
The answer depends on the norm you are considering. The answer is no for the operator norm, but is yes for the normalized Hilbert-Schmidt norm (at least if you replace $O(\varepsilon)$ by $o(1)$, see the answers to this question). 
Here are some details on the counterexample for the operator norm.


*

*By a theorem of Lin (see here), for a pair of self-adjoint matrices of norm less than $1$, they approximately commute if and only if they can be approximated by commuting matrices.

*Voiculescu proved that the preceding does not hold for triples of  self-adjoint matrices of norm less than $1$ (see the link I gave here, or the references in the paper by Exel and Loring given in the comments).


1+2 imply that there is a sequence of triples $A_1^n,A_2^n,A_3^n$ of matrices of norm less than $1$ which are pairwise close to (self-adjoint) commuting matrices, but whose distance to the triples of commuting matrices is bounded below.


*By continuity of the functional calculus and the fact that $t \in [-2,2] \mapsto e^{it}$ is a homeomorphism on its image, this implies that the unitary matrices $(e^{i A_1^n}, e^{i A_1^n},e^{i A_1^n})$ are pairwise close
to pairs of commuting unitaries, but are at positive distance from triples of commuting unitaries. This is what you were looking for.

