Which Exterior Powers are Balanced?

Abstract

A signed graph is a graph whose edges are given $\pm 1$ weights. In such a graph, the sign of a cycle is the product of the signs of its edges. A signed graph is called balanced if its adjacency matrix is similar to the adjacency matrix of an unsigned graph via conjugation by a diagonal $\pm 1$ matrix. For a signed graph $\Sigma$ on $n$ vertices, its exterior $k$th power, where $k=1,\ldots,n-1$, is a graph $\bigwedge^{k} \Sigma$ whose adjacency matrix is given by

\[ A(\mbox{$\bigwedge^{k} \Sigma$}) = P_{\wedge}^{\dagger} A(\Sigma^{\Box k}) P_{\wedge}, \]

where $P_{\wedge}$ is the projector onto the anti-symmetric subspace of the $k$-fold tensor product space $(\mathbb{C}^{n})^{\otimes k}$ and $\Sigma^{\Box k}$ is the $k$-fold Cartesian product of $\Sigma$ with itself. The exterior power creates a signed graph from any graph, even unsigned. We prove sufficient and necessary conditions so that $\bigwedge^{k} \Sigma$ is balanced. For $k=1,\ldots,n-2$, the condition is that either $\Sigma$ is a signed path or $\Sigma$ is a signed cycle that is balanced for odd $k$ or is unbalanced for even $k$; for $k=n-1$, the condition is that each even cycle in $\Sigma$ is positive and each odd cycle in $\Sigma$ is negative.