# Sign patterns of principal minors of real symmetric matrices

This page contains the source code and explanations related to the results in the paper:
Tobias Boege, Jesse Selover and Maksym Zubkov: Sign patterns of principal minors of real symmetric matrices

ABSTRACT: We analyze a combinatorial rule satisfied by the signs of principal minors of a real symmetric matrix. The sign patterns satisfying this rule are equivalent to uniform oriented Lagrangian matroids. We first discuss their structure and symmetries and then study their asymptotics, proving that almost all of them are not representable by real symmetric matrices. We offer several conjectures and experimental results concerning representable sign patterns and the topology of their representation spaces.

## Installation of software

We require a recent Perl, Mathematica and sagemath installation which are fairly standard. In addition, we need the SAT solver tools from the CInet project. You can also follow the instructions on the SelfadhesiveGaussianCI page.

## Enumeration and symmetry reduction of admissible sign patterns

The Perl script signs.pl enumerates admissible sign patterns using a SAT solver and then reduces them to canonical representatives modulo the hyperoctahedral group.

$perl signs.pl 3 >signs3.log 38 compatible sign vectors Performing symmetry reduction ..... 5 representatives  It prints some progress information while it is working, including an estimate (obtained via the probabilistic model counter GANAK) for the number of sign vectors to be processed. Its output is a list of records, one per line, with a sign pattern and its orbit size: $ cat signs3.log
++++++++: 8
+++++++-: 8
++++++--: 12
+++++---: 8
++++----: 2


The orbit sizes add up to the number 38 reported earlier by the program.

The encoding of sign patterns is briefly mentioned in the paper: we use strings of + and - characters for the principal minors in “grouped-lexicographic” order, i.e., the subsets of $$N$$ are first grouped by cardinality and within each group arranged lexicographically based on a fixed ordering of $$N$$.

The canonical representative of an orbit is that sign pattern which has the largest number of leading + signs in this encoding. This is the representative chosen by signs.pl.

This procedure works decently also for $$n = 4$$ and $$n = 5$$:

$perl signs.pl 4 >signs4.log 990 compatible sign vectors Performing symmetry reduction ........................ 24 representatives$ perl signs.pl 5 >signs5.log
395094 compatible sign vectors
Performing symmetry reduction ........................ [...]
434 representatives


The script understands a few options: --count-only to stop after obtaining the estimate of the number of solutions to the boolean formula, and --positive-singletons which adds axioms to orient all singletons positively. Combining both, we get the reported upper bound on the number of hyperoctahedral orbits for $$n = 6$$:

$perl signs.pl --count-only --positive-singletons 6 7109686748 compatible sign vectors  ## The space $$\mathrm{PR}_3$$ With the list of 5 canonical representatives of admissible sign patterns, the analysis of their representation spaces is swiftly done using computational real algebraic geometry tools in $$\verb|Mathematica|$$. We use cylindrical algebraic decomposition to count their connected components and produce the figures from the paper. The whole notebook with all code and computations is available for download (compressed): ## Representability for $$n \le 5$$ To find representations for admissible sign patterns, we implemented a simple sampling methodology in $$\verb|sagemath|$$ which generates a random rational matrix and computes its sign pattern. This has a chance of working well because if a sign pattern is representable, then its space of representations has a positive Lebesgue measure in the space of all symmetric matrices with normalized diagonal. The sampling script sample.sage has two modes. In the first mode, it is given options -n NUMER -d DENOM -t TRIES which give bounds on the numerators and denominators of matrix entries (by default both bounds are $$35$$ which appears good enough) and the number of random matrices to generate. The matrices always have their diagonal elements fixed to $$1$$ which is justified in the paper. It then outputs a list of records containing the witnessed sign patterns, how often they were encountered and a simple representation. In the second mode, a sign pattern is explicitly given using the -p PATTERN option. In this case, a little more information is used during the sampling of matrices to target the representation space of the given pattern. Namely, the diagonals are fixed to $$\pm 1$$ depending on the $$1 \times 1$$ minor signs and each off-diagonal entry is ensured to be strictly smaller or larger than $$1$$ in absolute value, depending on the $$2 \times 2$$ minor signs. The switch -b can be used to stop sampling after the first representation was found. This second mode works well for $$n = 3$$ and $$n = 4$$: $ cut -f1 -d: signs4.log | while read S
> do sage sample.sage -t 10000 -p "$S" 4 > done >sample4.log  This loops through all hyperoctahedral representatives obtained in the previous sections and samples 10,000 rational matrices for each of them. In our test run, this is sufficient to find representations for all orbits. The case $$n = 5$$ is tougher. We first generate 4,000,000 random matrices and collect their sign patterns. Since we do not target a specific pattern with the -p option in this case, the script also reports representable sign patterns which are not canonical. The reduce.pl script acts on matrices via the symmetric group trying to produce a representation for their canonical hyperoctahedral representative. In our test run, this leaves only 18 of the sign patterns without a representation. $ sage sample.sage -t 4000000 5 >sample5.log
$perl reduce.pl 5 sample5.log >reduce5.log$ cut -f1 -d: signs5.log | while read S
> do grep -Gq "$S" reduce5.log || echo "$S"
> done | tee leftover.log
++++++++++++++++++++++++++-----+
++++++++++++++++++++++---------+
+++++++++++++++++++++-++-------+
+++++++++++++++++++----------+++
++++++++++++++++++-+--+--------+
+++++++++++++++++-----------++++
+++++++++++++++++--------------+
++++++++++++++++----------++++++
++++++++++++++++----------++++-+
++++++++++++++++----------+++--+
++++++++++++++++----------++---+
++++++++++++++++----------+----+
++++++++++++++++---------------+
+++++++++++++++-----------++++++
+++++++++++++++-----------++++-+
+++++++++++++++-----------+++--+
+++++++++++++++-----------+-++++
+++++++++-+-+--+----------+++--+


On these “leftover” sign patterns, we can run the targeted sampling procedure as shown before for $$n = 4$$. With enough iterations, representations of all sign patterns except the elusive $$s_*$$ are generated with the default bounds on numerator and denominator.

The representations are accumulated into the following files:

The correctness can be independently verified using verify.pl:

$prove verify.pl :: 4 sample4.log verify.pl .. ok All tests successful. Files=1, Tests=24, 0 wallclock secs ( 0.01 usr 0.00 sys + 0.42 cusr 0.01 csys = 0.44 CPU) Result: PASS$ prove verify.pl :: 5 sample5.log
verify.pl .. ok
All tests successful.
Files=1, Tests=433, 15 wallclock secs ( 0.07 usr  0.00 sys + 15.52 cusr  0.00 csys = 15.59 CPU)
Result: PASS


Notice that sample5.log contains 433 representations as it is missing $$s_*$$. The canonical representative of $$s_*$$ is +++++++++-+-+--+----------+++--+ and $$s_*$$ as given in the paper arises from it by duality. We are unable to decide whether it is representable or not.

The file last5.pip encodes a trivial polynomial optimization problem over the representation space of $$s_*$$ intersected with a large bounding box for the solver SCIP. Only the $$3 \times 3$$ minors and the whole determinant are used in the formulation (the script writepip5.pl ignores principal minors marked with * in the input pattern). During the solving, it appears that certain matrices become too close to singular and eventually SCIP aborts.

$perl writepip5.pl -- +--+++**********--+++-+-++*****+ >last5.pip$ scip
SCIP> optimize
[...]
LU pivot element is almost zero (< 1e-10) - Basis is numerically singular
LU pivot element is almost zero (< 1e-10) - Basis is numerically singular
54.9s|  6300 |  4457 |  3616k| 574.1 |    83M | 125 | 102 |  23 | 583 | 165k|  4 |   3 |   0 | 1.000000e+00 |      --      |    Inf |   3.20%
55.5s|  6400 |  4511 |  3665k| 572.8 |    83M | 125 | 102 |  23 |   0 | 167k|  0 |   3 |   0 | 1.000000e+00 |      --      |    Inf |   3.22%
56.6s|  6500 |  4587 |  3734k| 574.7 |    85M | 125 | 102 |  23 | 196 | 171k|  3 |   3 |   0 | 1.000000e+00 |      --      |    Inf |   3.22%
58.3s|  6600 |  4635 |  3831k| 580.5 |    87M | 125 | 102 |  23 | 202 | 175k|  4 |   3 |   0 | 1.000000e+00 |      --      |    Inf |   3.24%
59.5s|  6700 |  4695 |  3911k| 583.9 |    89M | 125 | 102 |  23 | 229 | 178k|  7 |   3 |   0 | 1.000000e+00 |      --      |    Inf |   3.26%
63.4s|  6800 |  4751 |  4163k| 612.4 |    91M | 125 | 102 |  23 | 595 | 185k|  4 |   3 |   0 | 1.000000e+00 |      --      |    Inf |   3.27%
64.1s|  6900 |  4817 |  4194k| 608.0 |    92M | 125 | 102 |  23 | 291 | 187k|  6 |   3 |   0 | 1.000000e+00 |      --      |    Inf |   3.29%
scip: /usr/src/debug/scip/scip-804/src/scip/lp.c:12131: lpSolve: Assertion !set->lp_checkstability || SCIPsetIsRelGE(set, lp->lpobjval, lp->lpiobjlim)' failed.
Aborted (core dumped)


Finally, we also provide a $$\verb|Mathematica|$$ notebook which contains the setup for testing representability of $$s_*$$ via cylindrical algebraic decomposition. We also determine certain symmetries of the polynomial system which allow us to fix the signs or even an ordering of some entries. However, the CAD computation still runs out of memory eventually.

## A lower bound for $$\mathrm{PR}_4$$

We show that if a sign pattern $$s$$ is representable, then all its minors are representable and that the number of connected components of the representation space of $$s$$ is at least as high as that of any of its minors. Using that all sign patterns on $$n = 4$$ are representable and we have the exact numbers of connected components of all sign patterns on $$n = 3$$, we can obtain a lower bound on the number of connected components of $$\mathrm{PR}_4$$ by summing over the lower bounds for the 24 canonical representatives times their orbit sizes. The script dimh0-pr4.pl does this using a hardcoded table generated by dimh0-pr3.pl:

\$ perl dimh0-pr4.pl
+++++++++------+: at least 4 x 96 = 384
+++++++--++----+: at least 2 x 12 = 24
+++++++++-------: at least 16 x 64 = 1024
+++++++-+-------: at least 4 x 16 = 64
++++++++++++++--: at least 4 x 64 = 256
++++++++++++++++: at least 1 x 16 = 16
+++++++++++++++-: at least 4 x 16 = 64
+++++++--+-----+: at least 4 x 48 = 192
+++++----------+: at least 16 x 2 = 32
++++++---------+: at least 16 x 16 = 256
++++++++++-----+: at least 4 x 48 = 192
++++++++++------: at least 16 x 48 = 768
+++++++++++-----: at least 16 x 16 = 256
+++++++--------+: at least 16 x 48 = 768
+++++++++++----+: at least 4 x 8 = 32
++++++++-------+: at least 16 x 64 = 1024
++++++----+----+: at least 4 x 8 = 32
++++++++--------: at least 16 x 16 = 256
+++++++-+--+----: at least 4 x 16 = 64
+++++++++--+----: at least 4 x 64 = 256
++++++++++-++---: at least 2 x 48 = 96
+++++++++++++---: at least 4 x 96 = 384
++++++++++-+----: at least 4 x 96 = 384
++++++++++++----: at least 16 x 64 = 1024
Total = 7848
`

## Colophon

Project page created: 22/07/2024

Project contributors: Tobias Boege, Jesse Selover and Maksym Zubkov

Software used: Perl (v5.38.0), GANAK (v1.0.1), nbc_minisat_all (v1.0.2.b), CInet::ManySAT (v1.1.1), CInet::Base (v0.10.2), SageMath (v10.4), Mathematica (v13.3) and SCIP (v8.0.4).

System setup used: All computations were performed on a customary Thinkpad T14 with 32 GiB of RAM.