Determining the minimum rank of the signed adjacency matrices of a graph over all signings

For a finite simple graph $G$ and a signing $\sigma:E(G)\to\{-1,1\}$ of its edges, let $A(G^{\sigma})$ be the signed adjacency matrix obtained by replacing each 1-entry of the adjacency matrix by the corresponding sign. Akbari, Ghafari, Kazemian, and Nahvi (Discrete Mathematics, 2020) proved that $\max_{\sigma}\operatorname{rank}(A(G^{\sigma}))=\operatorname{perrank}(G)$, the order of the largest subgraph that is a disjoint union of edges and cycles, and posed two problems: determine $\min_{\sigma}\operatorname{rank}(A(G^{\sigma}))$, and find an efficient algorithm constructing the full-rank signing whose existence they proved nonconstructively. The algorithmic problem is resolved by the work of Carlson, Chandrasekaran, Chang, Kakimura, and Kolla (MFCS 2019; Discrete Optimization 2020), which gives a polynomial-time algorithm finding an invertible symmetric signing whenever one exists. The minimum-rank problem remains open: no combinatorial characterization, exact formula, or complexity classification is known for general graphs, and even deciding whether some signing of an adjacency matrix is singular is unresolved for non-bipartite graphs.

Background

A signed graph is a graph in which every edge carries a sign, $+1$ or $-1$; for a finite simple graph $G$ (no loops or parallel edges) a signing is a map $\sigma:E(G)\to\{-1,1\}$, and the signed adjacency matrix $A(G^{\sigma})$ is obtained from the ordinary 0/1 adjacency matrix $A(G)$ by replacing the entry 1 of each edge $e$ by $\sigma(e)$. A natural measure of a signing is the rank of $A(G^{\sigma})$ (equivalently its nullity, $|V(G)|-\operatorname{rank}$). Switching — flipping the signs of all edges incident to a chosen subset of vertices — conjugates $A(G^{\sigma})$ by a diagonal $\pm 1$ matrix, so it preserves the rank and the whole spectrum; on graphs without cycles (forests) all signings are switching-equivalent to the all-positive signing, so the rank is signing-independent there and equals twice the matching number (the maximum number of pairwise vertex-disjoint edges), a classical fact.

Akbari, Ghafari, Kazemian, and Nahvi studied which graphs admit a signing of full rank. Their key parameter is the perrank of $G$: the largest number of vertices of a subgraph of $G$ that is a disjoint union of copies of $K_2$ and cycles; $G$ has full perrank exactly when such a spanning structure exists, i.e., when $G$ has a $\{1,2\}$-factor — a spanning subgraph in which every vertex has degree 1 or 2 (also called a perfect 2-matching). Expanding $\det(A(G^{\sigma}))$ over transversals (selections of one nonzero entry per row and column; each nonzero transversal of an adjacency matrix corresponds to a $\{1,2\}$-factor) and applying the Combinatorial Nullstellensatz — a theorem of Alon guaranteeing a nonzero evaluation of a multivariate polynomial over small sets when a maximal-degree monomial has nonzero coefficient — they proved that a graph has a signing of full rank iff it has full perrank, and more generally that

$\max_{\sigma}\operatorname{rank}\bigl(A(G^{\sigma})\bigr)=\operatorname{perrank}(G).$

The proof is nonconstructive: it does not exhibit the good signing. They therefore posed two problems: determine $\min_{\sigma}\operatorname{rank}(A(G^{\sigma}))$, and find an efficient algorithm producing the full-rank signing guaranteed by the theorem.

The algorithmic problem was resolved by work of Carlson, Chandrasekaran, Chang, Kakimura, and Kolla on symmetric matrix signings (a symmetric signing of a real symmetric matrix $M$ is the entrywise product of $M$ with a symmetric $\pm 1$ matrix; for $A(G)$ this is exactly a signing of the edges). They independently proved the same existence characterization — an invertible symmetric signing exists iff the support graph of $M$ contains a perfect 2-matching — in an arXiv preprint first posted in November 2016 by Carlson, Chandrasekaran, Chang, and Kolla (Kakimura joined for the peer-reviewed versions), and they note that the Akbari et al. proof coincides with the nonconstructive proof in that early version. Their peer-reviewed versions (MFCS 2019 and Discrete Optimization, 2020) go further: Theorems 2 and 8 give a polynomial-time algorithm, based on cycle-cover expansions in auxiliary bipartite graphs, that constructs an invertible symmetric signing whenever one exists. This resolves the source paper's Problem 2. On the minimization side the same work shows a sharp contrast: deciding whether a real symmetric matrix has a singular signing is NP-complete in general, but the hard instances have non-zero diagonal entries; for adjacency matrices of bipartite graphs the problem is polynomial; for adjacency matrices of general graphs its complexity is left open. This decision problem is precisely the core of the surviving Problem 1, since $\min_{\sigma}\operatorname{rank}(A(G^{\sigma}))<|V(G)|$ iff some signing of $A(G)$ is singular.

For the value of the minimum, the neighboring theory is as follows. Over the two-element field $\mathbb{F}_2$ one has $-1\equiv 1$, so $A(G^{\sigma})\equiv A(G)\pmod 2$ for every signing and the parity of the determinant is signing-invariant; consequently, if $A(G)$ is nonsingular over $\mathbb{F}_2$ then every signing is nonsingular and the minimum equals $|V(G)|$ (for complete graphs of even order this is the classical fact that Seidel matrices — symmetric matrices with zero diagonal and $\pm 1$ off-diagonal entries, i.e., signed adjacency matrices of complete graphs — are nonsingular). For a fixed signing, He, Hao, and Lai proved $|V|-2m(G)-c(G)\le\eta(G,\sigma)\le|V|-2m(G)+2c(G)$, where $m(G)$ is the matching number and $c(G)$ the cyclomatic number (the dimension of the cycle space, $|E|-|V|+$ number of components); in rank terms every signing satisfies $2m(G)-2c(G)\le\operatorname{rank}(A(G^{\sigma}))\le 2m(G)+c(G)$. For complete graphs, Bašić, Fowler, Pisanski, and Sciriha determined exactly the orders $n\equiv 1\pmod 4$ admitting a signing with nullity 1 (a signed nut graph: a signing whose adjacency matrix has one-dimensional kernel spanned by a vector with no zero entry). None of these results determines the minimum rank over signings for a general graph. The problem is also distinct from other minimum-rank problems in which the magnitudes of the entries are free reals constrained only by sign or support: the classical minimum rank problem (arbitrary non-zero real edge weights), the sign-pattern minimum rank problem, and the minimum semidefinite rank of signed graphs.

Problem Statement

Let $G$ be a finite simple graph on $n$ vertices with adjacency matrix $A(G)$, and for a signing $\sigma:E(G)\to\{-1,1\}$ let $A(G^{\sigma})$ be the signed adjacency matrix. As posed by Akbari, Ghafari, Kazemian, and Nahvi following their result $\max_{\sigma}\operatorname{rank}(A(G^{\sigma}))=\operatorname{perrank}(G)$:

$\text{Determine } \min_{\sigma:E(G)\to\{-1,1\}} \operatorname{rank}\bigl(A(G^{\sigma})\bigr) \text{ for an arbitrary graph } G.$

Determining the value means establishing it for all finite simple graphs — for instance by a formula or characterization in terms of invariants of $G$, or by an efficient (polynomial-time) algorithm computing the value — that is, exhibiting a signing that attains it and showing that no signing of $G$ attains a strictly smaller rank. The determination subsumes the decision question whether $\min_{\sigma}\operatorname{rank}(A(G^{\sigma}))<n$, equivalently whether some signing of $A(G)$ is singular, whose computational complexity for general graphs is currently unknown (it is polynomial for bipartite graphs and NP-complete for general symmetric matrices with non-zero diagonal, by Carlson et al.); that complexity question is a separate open problem in the Carlson et al. line of work, and settling it on its own does not determine $\min_{\sigma}\operatorname{rank}(A(G^{\sigma}))$, so it is not an answer to the problem as stated. Results restricted to particular graph classes, to balanced (switching-equivalent to all-positive) signings, or to matrices other than simple-graph adjacency matrices do not resolve the problem as stated.

References

1. S. Akbari, A. Ghafari, K. Kazemian, M. Nahvi, Some criteria for a signed graph to have full rank, Discrete Mathematics 343(8) (2020) 111910. DOI: 10.1016/j.disc.2020.111910; arXiv:1708.07118. https://doi.org/10.1016/j.disc.2020.111910
2. C. Carlson, K. Chandrasekaran, H.-C. Chang, N. Kakimura, A. Kolla, Spectral aspects of symmetric matrix signings, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Leibniz International Proceedings in Informatics (LIPIcs) 138 (2019), Article 81, 81:1-81:13. DOI: 10.4230/LIPIcs.MFCS.2019.81. https://doi.org/10.4230/LIPIcs.MFCS.2019.81
3. C. Carlson, K. Chandrasekaran, H.-C. Chang, N. Kakimura, A. Kolla, Spectral aspects of symmetric matrix signings, Discrete Optimization 37 (2020) 100582. DOI: 10.1016/j.disopt.2020.100582. https://doi.org/10.1016/j.disopt.2020.100582
4. C. Carlson, K. Chandrasekaran, H.-C. Chang, A. Kolla, Invertibility and largest eigenvalue of symmetric matrix signings, arXiv:1611.03624 (v1 November 2016, v2 July 2017; the arXiv versions list four authors, and N. Kakimura joined for the peer-reviewed versions). https://arxiv.org/abs/1611.03624
5. M. Zurel, L. Z. Cohen, R. Raussendorf, Simulation of quantum computation with magic states via Jordan-Wigner transformations, Physical Review A 112(4) (2025) 042602. DOI: 10.1103/ng4l-96kd; arXiv:2307.16034. https://doi.org/10.1103/ng4l-96kd
6. S. He, R.-X. Hao, H.-J. Lai, Bounds for the matching number and cyclomatic number of a signed graph in terms of rank, Linear Algebra and its Applications 572 (2019) 273-291. DOI: 10.1016/j.laa.2019.03.012. https://doi.org/10.1016/j.laa.2019.03.012
7. Y. Lu, J. Wu, No signed graph with the nullity eta(G,sigma)=|V(G)|-2m(G)+2c(G)-1, arXiv:2006.00002 (2020). https://arxiv.org/abs/2006.00002
8. F. Belardo, S. M. Cioaba, J. Koolen, J. Wang, Open problems in the spectral theory of signed graphs, The Art of Discrete and Applied Mathematics 1(2) (2019) #P2.10. DOI: 10.26493/2590-9770.1286.D7B; arXiv:1907.04349. https://doi.org/10.26493/2590-9770.1286.D7B
9. N. Bašić, P. W. Fowler, T. Pisanski, I. Sciriha, On singular signed graphs with nullspace spanned by a full vector: signed nut graphs, Discussiones Mathematicae Graph Theory 42(4) (2022) 1351–1382. DOI: 10.7151/dmgt.2436; arXiv:2009.09018. https://doi.org/10.7151/dmgt.2436
10. N. Matar, L. H. Mitchell, S. K. Narayan, On the minimum semidefinite rank of signed graphs, Linear Algebra and its Applications 642 (2022) 73–85. DOI: 10.1016/j.laa.2022.02.004. https://doi.org/10.1016/j.laa.2022.02.004