Back to Search
Start Over
Which Exterior Powers are Balanced?
- Source :
- Scopus-Elsevier
- Publication Year :
- 2013
-
Abstract
- A signed graph is a graph whose edges are given (-1,+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 (-1,+1) matrix. For a signed graph $\Sigma$ on n vertices, its exterior k-th power, where k=1,..,n-1, is a graph $\bigwedge^{k} \Sigma$ whose adjacency matrix is given by \[ A({$\bigwedge^{k} {\Sigma}$}) = P^{\dagger} A(\Sigma^{\Box k}) P, \] where P 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,..,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.<br />Comment: 14 pages, 2 figures
- Subjects :
- Diagonal
0102 computer and information sciences
01 natural sciences
Quotient graph
Theoretical Computer Science
Combinatorics
symbols.namesake
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
Adjacency matrix
0101 mathematics
Signed graph
Mathematics
Discrete mathematics
Applied Mathematics
010102 general mathematics
Cartesian product
Graph
Tensor product
Computational Theory and Mathematics
010201 computation theory & mathematics
symbols
05C50, 05C75
Geometry and Topology
Combinatorics (math.CO)
Subspace topology
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Scopus-Elsevier
- Accession number :
- edsair.doi.dedup.....8ccd4b439a1f3faff3879a0732215d8c