As is well known, equilibrium analysis of evolutionary partnership games can be done by studying a so-called standard quadratic optimization problem, where a possibly indefinite quadratic form is maximized over the standard (probability) simplex. Despite the mathematical simplicity of this model, the nonconvex instances in this problem class allow for remarkably rich patterns of coexisting (strict) local solutions, which correspond to evolutionarily stable states (ESSs) in the game; seen from a dynamic perspective, ESSs form the asymptotically stable fixed points under the continuous-time replicator dynamics. In this study, we develop perturbation methods to enrich existing ESS patterns by a new technique, continuing the research strategy started by Chris Cannings and coworkers in the last quarter of the past century.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
1.1 Motivation
We consider the Standard Quadratic Optimization Problem (StQP) given by
where \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) (\({{{\mathcal {S}}}^n}\) denoting symmetric \(n \times n\)-matrices) and \(\Delta ^n\) is the standard-simplex
$$\begin{aligned} \Delta ^n=\left\{ \mathbf {x}\in {\mathbb {R}}^{n}:\sum _{i=1}^{n}x_{i}=1,\, x_{i}\ge 0\quad \hbox {for all }i \in N \right\} , \end{aligned}$$
where \(N=\left\{ 1,\dots ,n \right\} \), also denoted as \([{1}\! : \!{n}]\).
Despite its mathematical simplicity, above model serves in different domains of applied mathematics: apart from straightforward applications like in portfolio optimization [15], it can be used in mathematical biology [12, 13] as well as in Evolutionary Game Theory and Game Dynamics [1, 11, 17, 20]. For a more detailed account on the interrelation between these domains, we refer to [3, 4] and references therein. Here, we want to focus on perturbation approaches to generate richer ESSs patterns from existing ones, building upon the seminal work of Chris Cannings and coworkers [6‐9, 18, 19], as well as upon the more recent study [5].
Advertisement
1.2 Notation and Preliminaries
Given any set \(S\subseteq {\mathbb {R}}^n\), we denote by \(\hbox {conv }S\) the convex hull of S, and the linear hull is denoted by \(\text {span}\,S\), while closure and interior of S are denoted by \(\text {cl}\,S\) and \(S^\circ \), respectively. For a (convex) set C, the set of its extreme points is denoted by \(\text {Ext}\,C\). Later, we will use the relation \(\text {Ext}\,\hbox {conv }S \subseteq S\) holding for any set \(S\subseteq {\mathbb {R}}^n\). For matrices \(\left\{ {\mathsf {A}},{\mathsf {B}}\right\} \subset {{{\mathcal {S}}}^n}\) we write \({\mathsf {A}}\prec {\mathsf {B}}\) or \({\mathsf {B}}\succ {\mathsf {A}}\) if \({\mathsf {B}}-{\mathsf {A}}\) is positive-definite, and likewise \({\mathsf {A}}\preceq {\mathsf {B}}\) or \({\mathsf {B}}\succeq {\mathsf {A}}\) if \({\mathsf {B}}-{\mathsf {A}}\) is positive-semidefinite (in particular, if either of them coincides with the zero matrix denoted by \({\mathsf {O}}\) in this paper). Treating \(\left\{ {\mathsf {A}},{\mathsf {B}}\right\} \) as points in a Euclidean space, we consider the Frobenius inner product \({\mathsf {A}}\bullet {\mathsf {B}}:= \text {trace}({\mathsf {A}}{\mathsf {B}})\) and the norm \( \Vert {\mathsf {A}} \Vert = \sqrt{{\mathsf {A}}\bullet {\mathsf {A}}}\); as usual, we abbreviate \({\mathsf {A}}\perp {\mathsf {B}}\) for \({\mathsf {A}}\bullet {\mathsf {B}}=0\). Additional usual notation involving (sometimes also non-square or non-symmetric) matrices is \(\ker {\mathsf {A}}:=\left\{ {\mathbf {v}}: {\mathsf {A}}{\mathbf {v}}= \mathbf {o}\right\} \) and \(\text {colspace}({\mathsf {A}}):=\left\{ {\mathsf {A}}{\mathbf {v}}: {\mathbf {v}}\in {\mathbb {R}}^n\right\} \). Returning to \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\), by
we denote the set of all global solutions to (1). For \(n\ge 2\) and \({\mathsf {A}}=(\mathbf {a}_1,\ldots ,\mathbf {a}_n)\in {{{\mathcal {S}}}^n}\) define
where \({\mathsf {I}}_k\in {\mathcal {S}}^k\) is the identity matrix, and \(\mathbf {e}\) denotes the all ones vector of appropriate dimension. We note
Clearly we have \(\hbox {rank }{\mathsf {A}}\ge \hbox {rank }{\mathcal {B}}({\mathsf {A}})\). Furthermore, for \(\mathbf {x}\in \Delta ^n\), let
$$\begin{aligned} I(\mathbf {x})=\left\{ i \in N :x_i>0 \right\} \end{aligned}$$
be the support of \(\mathbf {x}\), and \(\Delta _I :=\left\{ \mathbf {x}\in \Delta ^n: I(\mathbf {x})\subseteq I\right\} \). The extended support with respect to \({\mathsf {A}}\) is given by
We will use some more convenient notation (again, we refer to [3] for background on the interplay of optimization and game equilibrium notions): given \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\), we denote by
$$\begin{aligned} \mathrm{ESS}({\mathsf {A}}) :=\left\{ \mathbf {x}\in \Delta ^n: \mathbf {x}\hbox { is an ESS for }{\mathsf {A}}\right\} \end{aligned}$$
the set of all strict local maximizers of (1), which is always finite but may be empty; by
$$\begin{aligned} \mathrm{NSS}({\mathsf {A}}) :=\left\{ \mathbf {x}\in \Delta ^n: \mathbf {x}\hbox { is an NSS for }{\mathsf {A}}\right\} \end{aligned}$$
$$\begin{aligned} \mathrm{NES}({\mathsf {A}}) :=\left\{ \mathbf {x}\in \Delta ^n: \mathbf {x}\hbox { is an NES for }{\mathsf {A}},\hbox { i.e., }{\mathsf {A}}\mathbf {x}\le (\mathbf {x}^\top {\mathsf {A}}\mathbf {x})\,\mathbf {e}\right\} \end{aligned}$$
the set of all KKT points of (1). The latter two sets are never empty; however, they may be infinite. Given \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) with finite \(\mathrm{NES}({\mathsf {A}})\), the procedures FINDEQ and CHECKSTAB discussed, e.g., in [2, 5], find all points in \(\mathrm{NES}({\mathsf {A}})\) and all members of \(\mathrm{ESS}({\mathsf {A}})\), respectively. Obviously,
with the equality \(\mathrm{SOL}({\mathsf {A}}) = \mathrm{NSS}({\mathsf {A}})= \mathrm{NES} ({\mathsf {A}})\) if \({\mathsf {A}}\) is negative-semidefinite. For indefinite \({\mathsf {A}}\) these sets may differ. We furthermore denote
Note that any \(\mathbf {p}\in \mathrm{NES}({\mathsf {A}})\) satisfies \(I(\mathbf {p})\subseteq J_{\mathsf {A}}(\mathbf {p})\), and quasistrictness of \(\mathbf {p}\) means that these two index sets coincide.
The significance of the latter two sets is the following: We try to find a perturbation \({\widetilde{{\mathsf {A}}}}\) of a matrix \({\mathsf {A}}\) such that \(\mathrm{ESS}({\widetilde{{\mathsf {A}}}})\) contains perturbations of some members of \({{\mathcal {E}}}({\mathsf {A}})\). These will be quasistrict ESSs of \({\widetilde{{\mathsf {A}}}}\), with supports not contained in pattern(\({\mathsf {A}}\)), and the enrichment of the pattern can be expressed as \(\text {qpattern}({\mathsf {A}})\) being a strict subset of \(\text {qpattern}({\widetilde{{\mathsf {A}}}})\).
For the readers’ convenience, we provide a short glossary of the sets used in our analysis, all refer to a fixed instance of (1) given by a symmetric matrix \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\):
all local solutions to (1) \(\equiv \) all neutrally stable states of evolutionary game based on \({\mathsf {A}}\);
ESS\(({\mathsf {A}})\)
all strict local solutions to (1) \(\equiv \) all evolutionarily stable states of evol. game based on \({\mathsf {A}}\);
NES\(({\mathsf {A}})\)
all KKT/first-order stationary points (1) \(\equiv \) all Nash equilibrium states of game based on \({\mathsf {A}}\);
\({{\mathcal {E}}}({\mathsf {A}})\)
all \(\mathbf {p}\in \mathrm{NES}({\mathsf {A}})\) which either are pure or have a strictly concave objective on their face \(\Delta _{I(\mathbf {p})}\);
\(\text {pattern}({\mathsf {A}})\)
ESS pattern = system of supports of all ESSs of evolutionary game based on \({\mathsf {A}}\);
\(\hbox {qpattern}({\mathsf {A}})\)
quasistrict ESS pattern = system of supports of all quasistrict ESSs of evol. game based on \({\mathsf {A}}\).
We collect some basic properties of the set \({{\mathcal {E}}}({\mathsf {A}})\) in the following
Advertisement
Proposition 1
(a)
\({{\mathcal {E}}}({\mathsf {A}})\) is nonempty and finite; to be more precise, we have
and all set inclusions above are strict in general.
(b)
Further we have \(\mathrm{ESS}({\mathsf {A}})\subseteq {{\mathcal {E}}}({\mathsf {A}})\subseteq \mathrm{NES}({\mathsf {A}})\), but in general \({{\mathcal {E}}}({\mathsf {A}})\) and \(\mathrm{NSS}({\mathsf {A}})\) are incomparable.
(c)
However, any \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\) with \(I(\mathbf {p})= J_{\mathsf {A}}(\mathbf {p})\) satisfies already \(\mathbf {p}\in \mathrm{ESS}({\mathsf {A}})\). In other words, any \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\setminus \mathrm{ESS}({\mathsf {A}})\) is a not quasistrict NES. Yet \(\mathbf {p}\) being a not quasistrict NES does not imply \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\).
(d)
In case that \({\mathsf {A}}=-{\mathsf {F}}{\mathsf {F}}^\top \) for some \({\mathsf {F}}\in {\mathbb {R}}^{n\times k}\) we have \({{\mathcal {E}}}({\mathsf {A}})=\text {Ext}(\mathrm{SOL}({\mathsf {A}}))\). Moreover, we have \({{\mathcal {E}}}({\mathsf {A}})=\text {Ext}(\Delta ^n\cap \ker {\mathsf {F}}^\top )\), provided the latter set is not empty, in which case we have \(J_{\mathsf {A}}(\mathbf {p})=[{1}\! : \!{n}]\) for any \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\).
(a) Implication (5) comes from \(f(\mathbf {x}) < f(\mathbf {p})\) for all \(\mathbf {x}\in \Delta _{I(\mathbf {p})}\setminus \left\{ \mathbf {p}\right\} \) due to (3) using \({\mathbf {v}}=\mathbf {x}-\mathbf {p}\perp \mathbf {e}\) and \({\mathbf {v}}^\top {\mathsf {A}}\mathbf {p}=0\). Further, the inequality \(0>f(\mathbf {x})-f(\mathbf {p}) = \frac{1}{2} (\mathbf {x}-\mathbf {p})^\top {\mathsf {A}}\mathbf {x}\) excludes the equilibrium condition \(({\mathsf {A}}\mathbf {x}) \le (\mathbf {x}^\top {\mathsf {A}}\mathbf {x})\mathbf {e}\) at \(\mathbf {x}\). Let us turn towards the set relations in (6); we deal with them from left to right;
(i)
SOL\(({\mathsf {A}})\) is nonempty and closed, so \(\hbox {conv }\mathrm{SOL}({\mathsf {A}})\ne \emptyset \) is compact, thus \(\text {Ext}\,\hbox {conv }\mathrm{SOL}({\mathsf {A}})\ne \emptyset \).
(ii)
Let \(\mathbf {p}\in \text {Ext}\,\hbox {conv }\mathrm{SOL}({\mathsf {A}})\). Then \(\mathbf {p}\in \mathrm{SOL}({\mathsf {A}})\subseteq \mathrm{NSS}({\mathsf {A}})\), and extremality in this set is obviously settled in case \(|I(\mathbf {p})|=1\). Turning to the case \(|I(\mathbf {p})|>1\), we note extremality of \(\mathbf {p}\) in \(\hbox {conv }\mathrm{SOL}({\mathsf {A}})\) implies
Hence we deduce \(\Delta _{I(\mathbf {p})}\cap \mathrm{SOL}({\mathsf {A}})=\{\mathbf {p}\}\). But this in turn even implies \(\Delta _{I(\mathbf {p})}\cap \mathrm{NES}({\mathsf {A}})=\{\mathbf {p}\}\) because \(f(\mathbf {x})<f(\mathbf {p})\) must hold for any \(\mathbf {x}\in \Delta _{I(\mathbf {p})}\setminus \{\mathbf {p}\}\), and therefore the directional derivative \((\mathbf {p}-\mathbf {x})^\top {\mathsf {A}}\mathbf {x}= \partial _{\mathbf {p}-\mathbf {x}}f(\mathbf {x})>0\), meaning \(\mathbf {x}\not \in \mathrm{NES}({\mathsf {A}})\). Obviously then also \(\Delta _{I(\mathbf {p})}\cap \text {Ext}\,\hbox {conv }\mathrm{NSS}({\mathsf {A}})=\{\mathbf {p}\}\) holds. If now \(\left\{ \mathbf {x},\mathbf {y}\right\} \subseteq \hbox {conv }\mathrm{NSS}({\mathsf {A}})\setminus \{\mathbf {p}\}\) and \(0<\lambda <1\) such that \(\mathbf {p}=\lambda \mathbf {x}+(1-\lambda )\mathbf {y}\), then \(\left\{ \mathbf {x},\mathbf {y}\right\} \subseteq \Delta _{I(\mathbf {p})}\), implying \(\mathbf {x}=\mathbf {y}=\mathbf {p}\), so \(\mathbf {p}\) is extremal in \(\hbox {conv }\mathrm{NSS}({\mathsf {A}})\). For \({\mathsf {A}}= \hbox {Diag }(1,2)\) we have \(\mathrm{SOL}({\mathsf {A}})=\left\{ \mathbf {e}_2\right\} \) but also \(\mathbf {e}_1\in \text {Ext}\,\hbox {conv }\mathrm{NSS}({\mathsf {A}})\).
(iii)
Let \(\mathbf {p}\in \text {Ext}\,\hbox {conv }\mathrm{NSS}({\mathsf {A}}) \subseteq \mathrm{NSS}({\mathsf {A}})\subseteq \mathrm{NES}({\mathsf {A}})\), so the case \(|I(\mathbf {p})|=1\) is settled. In case that \(|I(\mathbf {p})|>1\) we claim that \(f(\mathbf {x}) < f(\mathbf {p})\) for all \(\mathbf {x}\in \Delta _{I(\mathbf {p})}\setminus \{\mathbf {p}\}\). Otherwise, since f is quadratic, there would be a whole segment (the intersection of a straight line with \(\Delta _{I(\mathbf {p})}\)) of points along which f is constantly equalling \(f(\mathbf {p})\), because \(\partial _{\mathbf {x}-\mathbf {p}}f(\mathbf {p})=0\) for all \(\mathbf {x}\in \Delta _{I(\mathbf {p})}\). Due to extremality of \(\mathbf {p}\), this segment cannot contain two members of \(\mathrm{NSS}({\mathsf {A}})\) on either side of \(\mathbf {p}\). So there must be points \(\mathbf {p}_k\) on this segment arbitrarily close to \(\mathbf {p}\), say \(\Vert \mathbf {p}-\mathbf {p}_k\Vert <\tfrac{1}{k}\), that are not in \(\mathrm{NSS}({\mathsf {A}})\), thus there are points \(\mathbf {q}_k\in \Delta ^n\) with \(\Vert \mathbf {p}_k-\mathbf {q}_k\Vert <\tfrac{1}{k}\) and \(f(\mathbf {q}_k)>f(\mathbf {p}_k)=f(\mathbf {p})\). These points \(\mathbf {q}_k\) get arbitrarily close to \(\mathbf {p}\), meaning that \(\mathbf {p}\) is not in \(\mathrm{NSS}({\mathsf {A}})\), a contradiction. For \({\mathsf {A}}=\hbox {Diag }(0,1)\) we have \(\mathbf {e}_1 \in {{\mathcal {E}}}({\mathsf {A}})\setminus \mathrm{NSS}({\mathsf {A}})= {{\mathcal {E}}}({\mathsf {A}})\setminus \mathrm{ESS}({\mathsf {A}})\).
(iv)
Let \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\subseteq \mathrm{NES}({\mathsf {A}})\subseteq \hbox {conv }\mathrm{NES}({\mathsf {A}})\). Since \(\mathbf {e}_i\) are the extreme points of \(\Delta ^n\) we are done in case \(|I(\mathbf {p})|=1\). Moreover, if \(|I(\mathbf {p})|>1\), we have \(f(\mathbf {x}) < f(\mathbf {p})\) for all \(\mathbf {x}\in \Delta _{I(\mathbf {p})}\setminus \left\{ \mathbf {p}\right\} \) as observed when proving (5) above, and, arguing as in (ii), \(\Delta _{I(\mathbf {p})}\cap \hbox {conv }\mathrm{NES}({\mathsf {A}})=\{\mathbf {p}\}= \Delta _{I(\mathbf {p})}\cap \mathrm{NES}({\mathsf {A}})\). As \(\mathbf {p}=\lambda \mathbf {x}+(1-\lambda )\mathbf {y}\) with \(0<\lambda <1\) and \(\left\{ \mathbf {x},\mathbf {y}\right\} \subseteq \hbox {conv }\mathrm{NES}({\mathsf {A}})\) requires \(\left\{ \mathbf {x},\mathbf {y}\right\} \subseteq \Delta _{I(\mathbf {p})}\), we obtain \(\mathbf {x}=\mathbf {y}=\mathbf {p}\), i.e. extremality of \(\mathbf {p}\) in \(\hbox {conv }\mathrm{NES}({\mathsf {A}})\). For
we have \(\mathrm{NES}({\mathsf {A}}) = \{\mathbf {q}\}\cup \hbox {conv }\left\{ \mathbf {e}_1,\mathbf {p}\right\} \), but \(\mathbf {p}\notin {{\mathcal {E}}}({\mathsf {A}})\) and \(\mathbf {p}\) is not quasistrict.
(b) The leftmost inclusion follows similarly as in the proof of (5), while the rightmost is a consequence of (6) and of the generally valid relation \(\text {Ext}\,\hbox {conv }S \subseteq S\) which we used already in our proofs of (ai) and (aii). Examples of \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\setminus \mathrm{NSS}({\mathsf {A}})\) or \(\mathbf {q}\in \mathrm{NSS}({\mathsf {A}})\setminus {{\mathcal {E}}}({\mathsf {A}})\) are \(\mathbf {p}= \mathbf {e}_1\) for \({\mathsf {A}}=\hbox {Diag }(0,1)\) – see the proof of (aiii) — and \(\mathbf {q}=[\frac{1}{2},\frac{1}{2}]^\top \) for \({\mathsf {A}}={\mathsf {O}}\), respectively.
(c) If \(J_{\mathsf {A}}(\mathbf {p})=I(\mathbf {p})\) and \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\), then any \(\mathbf {x}\in \Delta ^n\) with \(\mathbf {x}^\top {\mathsf {A}}\mathbf {p}=\mathbf {p}^\top {\mathsf {A}}\mathbf {p}\) must lie in \(\Delta _{I(\mathbf {p})}\), therefore as in the proof of (aiv) we have \(\mathbf {p}^\top {\mathsf {A}}\mathbf {x}=\mathbf {x}^\top {\mathsf {A}}\mathbf {p}>\mathbf {x}^\top {\mathsf {A}}\mathbf {x}\) unless \(\mathbf {x}=\mathbf {p}\), which shows \(\mathbf {p}\in \mathrm{ESS}({\mathsf {A}})\). The example \(\mathbf {p}\) given in the proof of (aiv) proves the last assertion.
(d) is obvious from the fact that \(\mathrm{SOL}({\mathsf {A}})\) is convex itself, and that all critical points of a smooth concave maximization problem are global solutions, so \(\mathrm{SOL}({\mathsf {A}}) = \mathrm{NSS}({\mathsf {A}})= \mathrm{NES}({\mathsf {A}})\).\(\square \)
2 Main Results
Our aim is to increase the number of ESSs of a matrix \({\mathsf {A}}\) by perturbing it in a way such that members of \({{\mathcal {E}}}({\mathsf {A}}) \setminus \mathrm{ESS}({\mathsf {A}})\) get perturbed into (quasistrict) ESSs of the perturbed matrix. To this end, we consider perturbations of \({\mathsf {A}}\) of the form \({\widetilde{{\mathsf {A}}}} ={\mathsf {A}}+\varepsilon {\mathsf {B}}\), with \(\varepsilon \) small. We seek simple sufficient conditions on \({\mathsf {B}}\) that lead to successful perturbations in the sense that \(|\text {qpattern}({\widetilde{{\mathsf {A}}}})|> |\text {qpattern}({\mathsf {A}})|\). We further aim at results telling us that we have found a matrix with the largest number of quasistrict ESSs of prescribed support size.
The plan of this section is as follows: In Sect. 2.1 (Lemma 2), we keep both \({\mathsf {A}}\) and \(\mathbf {x}\in {{\mathcal {E}}}({\mathsf {A}})\) fixed and derive a sufficient condition on \({\mathsf {B}}\) guaranteeing \(I(\mathbf {x})\in \text {qpattern}({\widetilde{{\mathsf {A}}}})\) for \(\varepsilon >0\) small enough. This is accomplished by studying the first-order expansion in \(\varepsilon \) of the first-order optimality condition for the StQP with matrix \({\widetilde{{\mathsf {A}}}}\). In Sect. 2.2 (Lemma 3), we prove, loosely speaking, that if close to \({\mathsf {A}}\) there are sufficiently many matrices \({\overline{{\mathsf {A}}}}\) satisfying \(I(\mathbf {x}) \in \text {qpattern}({\overline{{\mathsf {A}}}})\), then there will be \({\mathsf {B}}\) satisfying the sufficient condition of Lemma 2, such that also \(I(\mathbf {x}) \in \text {qpattern}({\widetilde{{\mathsf {A}}}})\) for \(\varepsilon >0\) small enough. Further results (Theorems 8 and 9) explore ways to restrict \({\mathsf {A}}\) and \({\mathsf {B}}\) to smaller sets of matrices, varying either \({\mathsf {A}}\) or \({\mathsf {B}}\) while not losing any generality in \(\text {qpattern}({\widetilde{{\mathsf {A}}}})\). Negative-semidefinite matrices \({\mathsf {A}}\) are particularly interesting starting points for perturbation, as they have large sets \({{\mathcal {E}}}({\mathsf {A}})\). Proposition 6 and Corollary 10 deal with those. In Sect. 2.3, we introduce \(n\times n\) cyclically symmetric matrices, forming a vector space \({\mathcal {C}}^n\) of dimension \(\left\lceil \frac{n-1}{2}\right\rceil \). With those, a further simplification allows to restrict our perturbation procedure to a finite set of candidate matrices \({\mathsf {A}}\), with \({\mathsf {B}}\) ranging in a certain linear subspace of \({\mathcal {C}}^n\) depending on \({\mathsf {A}}\). In Sect. 2.4, the preceding results are applied to the setting of negative-semidefinite candidate matrices \({\mathsf {A}}\in {\mathcal {C}}^n\), where the task is to find a maximal subset \({{\mathcal {P}}}\subseteq {{\mathcal {E}}}({\mathsf {A}})\), such that there is \({\mathsf {B}}\in {\mathcal {C}}^n\) satisfying the sufficient condition of Lemma 2 for any \(\mathbf {x}\in {{\mathcal {P}}}\). Examples 12 and 13 for \(n\in \{6,7\}\) explicate the procedure. In Sect. 2.5, we report on our results for orders \(n\in [{4}\! : \!{23}]\). The subsections are interspersed with several examples illustrating our results, some also show limitations.
2.1 First-Order Conditions
The following lemma deals with perturbations of the form \({\mathsf {A}}+\varepsilon {\mathsf {B}}\) and fathoms what can be deduced from a first-order expansion of the resulting FINDEQ inequalities.
Lemma 2
Let \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\), \(\mathbf {x}\in \Delta ^n\), \(I:=I(\mathbf {x})\), and \(J:=J_{{\mathsf {A}}}(\mathbf {x})\ne I\). Assume \(({\mathsf {A}}\mathbf {x})_i=v\) for \(i\in J\) and \(({\mathsf {A}}\mathbf {x})_i<v\) for \(i\not \in J\), as well as \({\mathcal {B}}({\mathsf {A}}_{I\times I})\succ {\mathsf {O}}\), in case that \(|I|\ge 2\). Thus \(\mathbf {x}\in {{\mathcal {E}}}(A)\). Let \({\mathsf {A}}_1:={\mathsf {A}}_{I\times I}\), \({\mathsf {A}}_2:={\mathsf {A}}_{(J\setminus I)\times I}\), and similarly define submatrices \({\mathsf {B}}_1\) and \({\mathsf {B}}_2\) of \({\mathsf {B}}\in {{{\mathcal {S}}}^n}\). Further let \({\bar{{\mathsf {A}}}}_1:=\begin{pmatrix} {\mathsf {A}}_1 &{} \mathbf {e}\\ \mathbf {e}^\top &{} 0 \end{pmatrix} \) and \({\bar{{\mathsf {B}}}}_1:=\begin{pmatrix} {\mathsf {B}}_1 &{} \mathbf {o}\\ \mathbf {o}^\top &{} 0 \end{pmatrix} \), where \(\mathbf {e}\) is the all ones and \(\mathbf {o}\) the zero vector of suitable dimension. We abbreviate the relation \(\mathbf {b}-\mathbf {a}\in \mathrm{int}~{\mathbb {R}}^d_+\) by \(\mathbf {a}< \mathbf {b}\).
then for \(\varepsilon >0\) small enough, \({\mathsf {A}}+\varepsilon {\mathsf {B}}\) will have an ESS \(\mathbf {x}_\varepsilon \) such that \(I(\mathbf {x}_\varepsilon )=J_{{\mathsf {A}}+\varepsilon {\mathsf {B}}}(\mathbf {x}_\varepsilon )=I\), and hence we have \(I\in \text {qpattern}({\mathsf {A}}+\varepsilon {\mathsf {B}})\).
b) If \({\mathsf {B}}\) violates \(\left[ ({\mathsf {B}}_2~|~\mathbf {o})-({\mathsf {A}}_2~|~\mathbf {e}){\bar{{\mathsf {A}}}}_1^{-1}{\bar{{\mathsf {B}}}}_1\right] \begin{pmatrix} \mathbf {x}_I \\ -v \end{pmatrix}\le \mathbf {o}\), then for \(\varepsilon >0\) small enough, \({\mathsf {A}}+\varepsilon {\mathsf {B}}\) will not have an NES \(\mathbf {x}_\varepsilon \) such that \(I(\mathbf {x}_\varepsilon )=I\).
Proof
From \({\mathcal {B}}({\mathsf {A}}_1)\succ {\mathsf {O}}\) we deduce that \({\bar{{\mathsf {A}}}}_1\) is invertible,1 so we have \(\begin{pmatrix} \mathbf {x}_I \\ -v \end{pmatrix}={\bar{{\mathsf {A}}}}_1^{-1}\begin{pmatrix} \mathbf {o}\\ 1 \end{pmatrix}\). For \(\varepsilon >0\) small enough, \({\bar{{\mathsf {A}}}}_1+\varepsilon {\bar{{\mathsf {B}}}}_1\) will therefore be invertible as well, and \(\begin{pmatrix} (\mathbf {x}_\varepsilon )_I \\ -v_\varepsilon \end{pmatrix}:=({\bar{{\mathsf {A}}}}_1+\varepsilon {\bar{{\mathsf {B}}}}_1)^{-1}\begin{pmatrix} \mathbf {o}\\ 1 \end{pmatrix}\) with \((\mathbf {x}_\varepsilon )_{N\setminus I}:=\mathbf {o}\) gives rise to a candidate \(\mathbf {x}_\varepsilon \) for an ESS of \({\mathsf {A}}+\varepsilon {\mathsf {B}}\), satisfying \(I(\mathbf {x}_\varepsilon )=I\). By continuity, for \(\varepsilon >0\) small enough we will have \({\mathcal {B}}({\mathsf {A}}_1+\varepsilon {\mathsf {B}}_1)\succ {\mathsf {O}}\) and \(\big (({\mathsf {A}}+\varepsilon {\mathsf {B}})\mathbf {x}_\varepsilon \big )_i<v_\varepsilon \) for \(i\not \in J\). Showing \(\big (({\mathsf {A}}+\varepsilon {\mathsf {B}})\mathbf {x}_\varepsilon \big )_i<v_\varepsilon \) for \(i\in J\setminus I\) is the only remaining task in the proof of a). The latter inequality can be restated as \(\left[ ({\mathsf {A}}_2~|~\mathbf {e})+\varepsilon ({\mathsf {B}}_2~|~\mathbf {o})\right] \begin{pmatrix} (\mathbf {x}_\varepsilon )_I \\ -v_\varepsilon \end{pmatrix}<\mathbf {o}\). Using now \(({\bar{{\mathsf {A}}}}_1+\varepsilon {\bar{{\mathsf {B}}}}_1)^{-1}={\bar{{\mathsf {A}}}}_1^{-1}-\varepsilon {\bar{{\mathsf {A}}}}_1^{-1}{\bar{{\mathsf {B}}}}_1{\bar{{\mathsf {A}}}}_1^{-1}+{\mathcal {O}}(\varepsilon ^2)\) we obtain \(\begin{pmatrix} (\mathbf {x}_\varepsilon )_I \\ -v_\varepsilon \end{pmatrix}=\begin{pmatrix} \mathbf {x}_I \\ -v \end{pmatrix}-\varepsilon {\bar{{\mathsf {A}}}}_1^{-1}{\bar{{\mathsf {B}}}}_1\begin{pmatrix} \mathbf {x}_I \\ -v \end{pmatrix}+{\mathcal {O}}(\varepsilon ^2)\), so that indeed we have, using \(({\mathsf {A}}_2~|~\mathbf {e})\begin{pmatrix} \mathbf {x}_I \\ -v \end{pmatrix}=\mathbf {o}\),
for \(\varepsilon >0\) small enough, by our assumption (7). Turning to b), by the assumption made there, at least one component of the L.H.S. of (8) will become positive for \(\varepsilon >0\) small enough, showing \(\mathbf {x}_\varepsilon \not \in \mathrm{NES}({\mathsf {A}}+\varepsilon {\mathsf {B}})\). \(\square \)
Remark 1
For \({\mathsf {A}}\) and \(\mathbf {x}\) fixed, also I, J and v are fixed, so the matrices \({\mathsf {B}}\) satisfying (7) form the interior of a polyhedral cone, and thus a convex cone.
2.2 Perturbation
If there are (in a certain sense) enough arbitrarily small perturbations \({\bar{{\mathsf {A}}}}\) of \({\mathsf {A}}\) that transform \(\mathbf {x}\in {{\mathcal {E}}}({\mathsf {A}})\setminus \mathrm{ESS}({\mathsf {A}})\) into \({\bar{\mathbf {x}}}\in \mathrm{ESS}({\bar{{\mathsf {A}}}})\), with \(I(\mathbf {x})=I({\bar{\mathbf {x}}})=J_{{\bar{{\mathsf {A}}}}}({\bar{\mathbf {x}}})\), then there will be a matrix \({\mathsf {B}}\) that satisfies (7), as the following lemma claims.
Lemma 3
Let \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) and \({{\mathcal {P}}}\subseteq {{\mathcal {E}}}({\mathsf {A}})\setminus \mathrm{ESS}({\mathsf {A}})\). Fix \(k\ge 1\) and let V be a linear subspace of \({{{\mathcal {S}}}^n}\) of dimension \(k+1\), and for \(a>0\) define
Suppose that \(s:=\inf \limits _{a>0}\sigma ^k\left( \left\{ \frac{{\mathsf {B}}}{\Vert {\mathsf {B}}\Vert }:{\mathsf {B}}\in {\mathcal {V}}_{a,{\mathsf {A}},{{\mathcal {P}}}}\right\} \right) >0\), where \(\sigma ^k\) denotes spherical measure. Then there is \({\mathsf {B}}\in V\) such that
holds for all \((I,K)\in {\mathcal {I}}_{{\mathcal {P}}}:=\left\{ \Big (I(\mathbf {p}),J_{\mathsf {A}}(\mathbf {p})\setminus I(\mathbf {p})\Big ):\mathbf {p}\in {{\mathcal {P}}}\right\} \).
Proof
We have to show that the polyhedral cone \(C:=\{{\mathsf {B}}\in V:h_{I,K}({\mathsf {B}})\le \mathbf {o}, \forall (I,K)\in {\mathcal {I}}_{{\mathcal {P}}}\}\) has nonempty interior. By assumption, for every \(\ell \in {\mathbb {N}}\) there is \({\mathsf {B}}_\ell ^{(1)}\in {\mathcal {V}}_{\frac{1}{\ell },{\mathsf {A}},{{\mathcal {P}}}}\). Then the sequence \(\left( \frac{{\mathsf {B}}_\ell ^{(1)}}{\Vert {\mathsf {B}}_\ell ^{(1)}\Vert }\right) _{\ell \ge 1}\) of points on a k-sphere \(S^k\) of radius 1 has an accumulation point \({\mathsf {B}}^{(1)}\in V\). Now, by calculations similar to those that led to the L.H.S. of inequality (8), we have \(h_{I,K}({\mathsf {B}}_\ell ^{(1)})+{\mathcal {O}}\left( \Vert {\mathsf {B}}_\ell ^{(1)}\Vert ^2\right) <\mathbf {o}\) as \(\ell \rightarrow \infty \). This implies that \(h_{I,K}({\mathsf {B}}^{(1)})\le \mathbf {o}\) is satisfied for all \((I,K)\in {\mathcal {I}}_{{\mathcal {P}}}\), therefore \({\mathsf {B}}^{(1)}\in C\).
Next define \(N_1:=\{{\mathsf {B}}\in V\cap S^k:\det \Gamma ({\mathsf {B}}^{(1)},{\mathsf {B}})\le \delta _1\}\), where \(\Gamma (\cdot )\) denotes the Gram matrix of a set of vectors (or vectorized matrices), and \(\delta _1>0\) is chosen such that \(\sigma ^k(N_1)\le \frac{s}{2}\), and \(C_1:=\text {cone}(N_1)\). Further let \({\mathsf {B}}_\ell ^{(2)}\in {\mathcal {V}}_{\frac{1}{\ell },{\mathsf {A}},{{\mathcal {P}}}}\setminus C_1\ne \emptyset \) as \(\sigma ^k\left( \left\{ \frac{{\mathsf {B}}}{\Vert {\mathsf {B}}\Vert }:{\mathsf {B}}\in {\mathcal {V}}_{\frac{1}{\ell },{\mathsf {A}},{{\mathcal {P}}}}\setminus C_1 \right\} \right) >0\). Again, the sequence \(\left( \frac{{\mathsf {B}}_\ell ^{(2)}}{\Vert {\mathsf {B}}_\ell ^{(2)}\Vert }\right) _{\ell \ge 1}\) has an accumulation point \({\mathsf {B}}^{(2)}\in V\), that satisfies \({\mathsf {B}}^{(2)}\in C\). Moreover, \({\mathsf {B}}^{(1)}\) and \({\mathsf {B}}^{(2)}\) are linearly independent. Assume now that for \(r\le k\) we have found linearly independent elements \({\mathsf {B}}^{(1)},\ldots ,{\mathsf {B}}^{(r)}\in C\). Then define \(N_r:=\{{\mathsf {B}}\in V\cap S^k:\det \Gamma ({\mathsf {B}}^{(1)},\ldots ,{\mathsf {B}}^{(r)},{\mathsf {B}})\le \delta _r\}\), where \(\delta _r>0\) is chosen such that \(\sigma ^k(N_r)\le \frac{s}{2}\), and \(C_r:=\text {cone}(N_r)\). Further let \({\mathsf {B}}_\ell ^{(r+1)}\in {\mathcal {V}}_{\frac{1}{\ell },{\mathsf {A}},{{\mathcal {P}}}}\setminus C_r\). Such a sequence does indeed exist because of \(\inf \limits _{a>0}\sigma ^k\left( \left\{ \frac{{\mathsf {B}}}{\Vert {\mathsf {B}}\Vert }:{\mathsf {B}}\in {\mathcal {V}}_{a,{\mathsf {A}},{{\mathcal {P}}}}\setminus C_r\right\} \right) \ge \frac{s}{2}>0\), and the sequence \(\left( \frac{{\mathsf {B}}_\ell ^{(r+1)}}{\Vert {\mathsf {B}}_\ell ^{(r+1)}\Vert }\right) _{\ell \ge 1}\) has a limit point \({\mathsf {B}}^{(r+1)}\in C\). Summarizing, we have found \({\mathsf {B}}^{(1)},\ldots ,{\mathsf {B}}^{(k+1)}\in C\), spanning a subcone of C of full dimension \(k+1\). Therefore C has nonempty interior \(C^\circ \), and any \({\mathsf {B}}\in C^\circ \) satisfies (9) for all \((I,K)\in {\mathcal {I}}_{{\mathcal {P}}}\). \(\square \)
Does Lemma 3 also hold for \(k=0\), in which case we always have \(s\in \left\{ 0,1\right\} \) ? That is, if there is \({\mathsf {B}}\in {{{\mathcal {S}}}^n}\) and a sequence \((\varepsilon _m)\) of positive reals such that \(\varepsilon _m\rightarrow 0\) and \(\{I(\mathbf {p}):\mathbf {p}\in {{\mathcal {P}}}\}\subseteq \text {qpattern}({\mathsf {A}}+\varepsilon _m{\mathsf {B}})\) holds for all \(m\ge 1\), does that imply that (9) is satisfied for all \((I,K)\in {\mathcal {I}}_{{\mathcal {P}}}\)? The answer is no, as the following example shows.
Example 4
Let \({\mathsf {A}}:=\left( {\begin{matrix}-1 &{} 1 &{} 1\\ 1 &{} -1 &{} -1\\ 1 &{} -1 &{} -1 \end{matrix}}\right) \) and \({\mathsf {B}}:=\left( {\begin{matrix}1 &{} 0 &{} -1\\ 0 &{} 0 &{} 1\\ -1 &{} 1 &{} 0 \end{matrix}}\right) \). Then \({{\mathcal {E}}}({\mathsf {A}})=\{\tfrac{1}{2}(\mathbf {e}_1+\mathbf {e}_2),\tfrac{1}{2}(\mathbf {e}_1+\mathbf {e}_3)\}\) and \(\mathrm{ESS}({\mathsf {A}})=\emptyset \). We let \({{\mathcal {P}}}:=\{\mathbf {p}\}\), where \(\mathbf {p}=\tfrac{1}{2}(\mathbf {e}_1+\mathbf {e}_2)\), \(I=I(\mathbf {p})=\{1,2\}\), \(J_{\mathsf {A}}(\mathbf {p})=\{1,2,3\}\), \(K=\{3\}\). It is easily checked that \(h_{I,K}({\mathsf {B}})=\mathbf {o}\), i.e., (9) is violated. Next we compute \(\begin{pmatrix} (\mathbf {p}_\varepsilon )_I \\ -v_\varepsilon \end{pmatrix} =\left( {\begin{matrix}-1+\varepsilon &{} 1 &{} 1\\ 1 &{} -1 &{} 1\\ 1 &{} 1 &{} 0 \end{matrix}}\right) ^{-1} \begin{pmatrix} \mathbf {o}\\ 1 \end{pmatrix} =\frac{1}{4-\varepsilon }\left[ {\begin{matrix}2\\ 2-\varepsilon \\ -\varepsilon \end{matrix}}\right] \), with \(\mathbf {p}_\varepsilon \in \Delta ^3\) for \(0<\varepsilon \le 2\) and \(I(\mathbf {p}_\varepsilon )=\{1,2\}\) for \(0<\varepsilon <2\). Moreover, \(({\mathsf {A}}+\varepsilon {\mathsf {B}})_{K\times I}(\mathbf {p}_\varepsilon )_I=v_\varepsilon -\frac{\varepsilon ^2}{4-\varepsilon }<v_\varepsilon \) for \(0<\varepsilon <4\), meaning \(J_{{\mathsf {A}}+\varepsilon {\mathsf {B}}}(\mathbf {p}_\varepsilon )=\{1,2\}\), and \({\mathcal {B}}\big (({\mathsf {A}}+\varepsilon {\mathsf {B}})_{I\times I}\big )\succ {\mathsf {O}}\) for \(0<\varepsilon <4\). Therefore \(\mathbf {p}_\varepsilon \in \mathrm{ESS}({\mathsf {A}}+\varepsilon {\mathsf {B}})\) is quasistrict, and thus \(I\in \text {qpattern}({\mathsf {A}}+\varepsilon {\mathsf {B}})\) for all \(\varepsilon >0\) small enough.
Remark 2
If, in the setting of Lemma 3, we have \(s_a:=\sigma ^k\left( \left\{ \frac{{\mathsf {B}}}{\Vert {\mathsf {B}}\Vert }:{\mathsf {B}}\in {\mathcal {V}}_{a,{\mathsf {A}},{{\mathcal {P}}}}\right\} \right) >0\) for all \(a>0\), but \(\lim \limits _{a\searrow 0}s_a=0\) (this can happen, as the next example shows), then for each \({\mathsf {B}}\in \bigcap \limits _{a>0} \text {cl}\big ({\mathcal {V}}_{a,{\mathsf {A}},{{\mathcal {P}}}}\big )\) we have \(h_{I,K}({\mathsf {B}})\le \mathbf {o}\), but no such \({\mathsf {B}}\) will satisfy \(h_{I,K}({\mathsf {B}})<\mathbf {o}\).
Example 5
Let \(k=1\), \({\mathsf {A}}:=\left( {\begin{matrix}-1 &{} 1 &{} 1 &{} 2\\ 1 &{} -1 &{} -1 &{} -2\\ 1 &{} -1 &{} -1 &{} -2\\ 2 &{}-2 &{} -2 &{} -4 \end{matrix}}\right) \), \({\mathsf {B}}:=\left( {\begin{matrix}1 &{} 0 &{} -1 &{} -1\\ 0 &{} 0 &{} 1 &{} 1/2 \\ -1 &{} 1 &{} 0 &{} 0 \\ -1 &{} 1/2 &{} 0 &{} 0\end{matrix}}\right) \), \({\mathsf {C}}:=\left( {\begin{matrix}0 &{} 0 &{} 1 &{} 0\\ 0 &{} 0 &{} 0 &{} -1 \\ 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} -1 &{} 0 &{} 0\end{matrix}}\right) \), and \(V:=\text {span}\,({\mathsf {B}},{\mathsf {C}})\). We let \(\mathbf {p}=\tfrac{1}{2}(\mathbf {e}_1+\mathbf {e}_2)\in {{\mathcal {E}}}({\mathsf {A}})\setminus \mathrm{ESS}({\mathsf {A}})\), \(I:=I(\mathbf {p})=\{1,2\}\) and \(K=\{3,4\}\). We now look for \(\mathbf {p}_{\varepsilon ,\delta }\in \mathrm{ESS}({\mathsf {A}}+\varepsilon {\mathsf {B}}+\delta {\mathsf {C}})\), obtaining \(\mathbf {p}_{\varepsilon ,\delta }=\frac{1}{4-\varepsilon }[2,2-\varepsilon ,0,0]^\top \), with \(I(\mathbf {p}_{\varepsilon ,\delta })=\{1,2\}\) for \(0<\varepsilon <2\), and \(v_{\varepsilon ,\delta }=\frac{\varepsilon }{4-\varepsilon }\). Moreover, for \(0<\varepsilon <2\) fixed, \(({\mathsf {A}}+\varepsilon {\mathsf {B}}+\delta {\mathsf {C}})_{K\times I}(\mathbf {p}_{\varepsilon ,\delta })_I-v_{\varepsilon ,\delta }\mathbf {e}= \frac{1}{4-\varepsilon }\left[ {\begin{matrix}2\delta -\varepsilon ^2\\ \delta (\varepsilon -2)-\varepsilon ^2/2\end{matrix}}\right] <\mathbf {o}\) if and only if \(-\frac{1}{2}\frac{\varepsilon ^2}{2-\varepsilon }<\delta <\frac{\varepsilon ^2}{2}\). From this we conclude \(s_a:=\sigma ^1\left( \left\{ \frac{{\mathsf {B}}}{\Vert {\mathsf {B}}\Vert }:{\mathsf {B}}\in {\mathcal {V}}_{a,{\mathsf {A}},{{\mathcal {P}}}}\right\} \right) >0\) for \(a>0\), as well as \(s_a={\mathcal {O}}(a)\), as \(a\searrow 0\).
For \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) and \({{\mathcal {P}}}\subseteq {{\mathcal {E}}}({\mathsf {A}})\) we now define the following convex cone
which clearly satisfies \({\mathcal {C}}_{\mathsf {A}}({{\mathcal {P}}})=\bigcap \limits _{\mathbf {p}\in {{\mathcal {P}}}}{\mathcal {C}}_{\mathsf {A}}(\{\mathbf {p}\})\). Observe also that \({\mathsf {A}}+\lambda \mathbf {e}\mathbf {e}^\top \in {\mathcal {C}}_{\mathsf {A}}({{\mathcal {P}}})\) for all \(\lambda \in {\mathbb {R}}\) due to (2).
Further members of \({\mathcal {C}}_{\mathsf {A}}({{\mathcal {P}}})\), in case that \({\mathsf {A}}\) is negative-semidefinite, will be identified in the next result.
Proposition 6
Let \({\mathsf {A}}=-{\mathsf {F}}{\mathsf {F}}^\top \), where \({\mathsf {F}}\in {\mathbb {R}}^{n\times k}\) for some k and assume \(\Delta ^n\cap \ker {\mathsf {F}}^\top \ne \emptyset \). Then
(a)
for every \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\) we have \(|I(\mathbf {p})|\le \hbox {rank }\,{\mathsf {F}}+1\), and for every positive-definite \({\mathsf {L}}\in {\mathcal {S}}^k\) we have \({\mathsf {A}}':=-{\mathsf {F}}{\mathsf {L}}{\mathsf {F}}^\top \in {\mathcal {C}}_{\mathsf {A}}(\{\mathbf {p}\})\) with \(\hbox {rank }{\mathsf {A}}=\hbox {rank }{\mathsf {A}}'\).
If for some m the set \({{\mathcal {P}}}_m \ne \emptyset \), then there is a matrix \({\mathsf {A}}''=-{\mathsf {H}}{\mathsf {H}}^\top \in {{{\mathcal {S}}}^n}\) of rank \(m-1\), such that \(\text {colspace}({\mathsf {H}})\subseteq \text {colspace}({\mathsf {F}})\), satisfying \(\mathbf {p}^\top {\mathsf {A}}''\mathbf {p}=0\) for all \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\), and \({{\mathcal {P}}}_m\subseteq {{\mathcal {E}}}({\mathsf {A}}'')\).
Proof
(a) follows by Proposition 1(d); note that \({\mathsf {A}}'=-{\mathsf {F}}'({\mathsf {F}}')^\top \) with \({\mathsf {F}}' = {\mathsf {F}}\sqrt{\mathsf {L}}\) where \(\sqrt{\mathsf {L}}\) denotes the symmetric square root factorization of \({\mathsf {L}}\). (b) Assume that \({{\mathcal {P}}}_m\) is nonempty. Then from (a) we know that rank \({\mathsf {F}}\ge m-1\), and clearly \(k\ge \text {rank~}{\mathsf {F}}\). If rank \({\mathsf {F}}=m-1\) we can simply choose \({\mathsf {H}}={\mathsf {F}}\). So we assume rank \({\mathsf {F}}\ge m\), and consider \({\mathsf {H}}={\mathsf {F}}{\mathsf {B}}\), where \({\mathsf {B}}\in {\mathbb {R}}^{k\times (m-1)}\) satisfies rank \({\mathsf {F}}{\mathsf {B}}=m-1\). (Those \({\mathsf {B}}\) constitute an open dense subset of \({\mathbb {R}}^{k\times (m-1)}\).) Then rank \({\mathsf {A}}''=m-1\) and \(\text {colspace}({\mathsf {H}})\subseteq \text {colspace}({\mathsf {F}})\). Furthermore, Ext\((\Delta ^n\cap \ker {\mathsf {H}}^\top )\ne \emptyset \), and thus, by Proposition 1(d), we have \({{\mathcal {E}}}({\mathsf {A}}'')=\text {Ext}(\Delta ^n\cap \ker {\mathsf {H}}^\top )\). To show \({{\mathcal {P}}}_m\subseteq {{\mathcal {E}}}({\mathsf {A}}'')\) it is sufficient to have that \(\mathbf {p}\in {{\mathcal {P}}}_m\) and \(\mathbf {q}\in \Delta _{I(\mathbf {p})}\setminus \{\mathbf {p}\}\) together imply \(\mathbf {q}\not \in \ker {\mathsf {H}}^\top \). This would follow if the map from \(\Delta _{I(\mathbf {p})}\) to \({\mathbb {R}}^{m-1}\) taking \(\mathbf {x}\) to \({\mathsf {B}}^\top {\mathsf {F}}^\top \mathbf {x}\) is one-to-one, which again is satisfied by all \({\mathsf {B}}\) in an open dense subset of \({\mathbb {R}}^{k\times (m-1)}\). As \({{\mathcal {P}}}_m\) is a finite set, we find \({\mathsf {B}}\) as needed in a finite intersection of open dense subsets of \({\mathbb {R}}^{k\times (m-1)}\). \(\square \)
So when searching for negative-semidefinite matrices \({\mathsf {A}}\) of order n with many points of support size m in their sets \({{\mathcal {E}}}({\mathsf {A}})\), we may restrict our search to matrices of the minimal possible rank \(m-1\). However, not every element of \({\mathcal {C}}_{\mathsf {A}}(\{\mathbf {p}\})\) need have a representation as in Proposition 6(a):
Suppose now that (9) is satisfied for certain \({\mathsf {A}},{\mathsf {B}},I,K\). In which ways can we change either \({\mathsf {A}}\) or \({\mathsf {B}}\) while keeping (9) intact? We start considering variations \({\mathsf {B}}'\) of \({\mathsf {B}}\).
Theorem 8
Let \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) and \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\) such that \(|I(\mathbf {p})|<|J_{\mathsf {A}}(\mathbf {p})|\). Suppose that (9) holds for some \({\mathsf {B}}\in {{{\mathcal {S}}}^n}\), where \(I=I(\mathbf {p})\) and \(K=J_{\mathsf {A}}(\mathbf {p})\setminus I\). Then for any \({\bar{{\mathsf {B}}}}\in \text {span}\,{\mathcal {C}}_{\mathsf {A}}(\{\mathbf {p}\})\) and any \(\lambda \in {\mathbb {R}}\), the matrix \({\mathsf {B}}':={\mathsf {B}}+\lambda {\bar{{\mathsf {B}}}}\) will also satisfy (9).
Since \(h_{I,K}\) is linear, we conclude \(h_{I,K}({\mathsf {B}}')=h_{I,K}({\mathsf {B}})\), and this completes the proof. \(\square \)
Now we turn to variations \({\mathsf {A}}'\) of \({\mathsf {A}}\). Any matrix \({\mathsf {A}}'\in {\mathcal {C}}_{\mathsf {A}}({{\mathcal {P}}})\) is a candidate for some perturbation \({\mathsf {A}}'+\varepsilon {\mathsf {B}}\) to yield \(\{I(\mathbf {p}):\mathbf {p}\in {{\mathcal {P}}}\}\subseteq \text {qpattern}({\mathsf {A}}'+\varepsilon {\mathsf {B}})\); however, in general, not every \({\mathsf {A}}'\), if any, will achieve this goal. Anyway, the search for a suitable \({\mathsf {A}}'\) can be restricted to the set \({\mathcal {C}}'_{\mathsf {A}}({{\mathcal {P}}}):=\{{\mathsf {A}}'\in {\mathcal {C}}_{\mathsf {A}}({{\mathcal {P}}}):{\mathsf {A}}'\perp \mathbf {e}\mathbf {e}^\top \, ,\, \Vert {\mathsf {A}}'\Vert =1\}\).
Fixing now \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\) with \(|J_{\mathsf {A}}(\mathbf {p})|>|I(\mathbf {p})|\), and fixing \({\mathsf {B}}\) satisfying (9) with \(I=I(\mathbf {p}), K=J_{\mathsf {A}}(\mathbf {p})\setminus I\), we ask whether (9) will stay satisfied if we replace \({\mathsf {A}}\) with some \({\mathsf {A}}'\in {\mathcal {C}}_{\mathsf {A}}(\{\mathbf {p}\})\). The answer will clearly be yes, if \(J_{{\mathsf {A}}'}(\mathbf {p})=J_{\mathsf {A}}(\mathbf {p})=:J\) and \({\mathsf {A}}'_{J\times J}=\gamma {\mathsf {A}}_{J\times J}+\lambda \mathbf {e}\mathbf {e}^\top \) for some \(\gamma >0,\lambda \in {\mathbb {R}}\), but there are other cases as well, as the following theorem tells.
Theorem 9
Let \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) and \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\) such that \(|I|<|J|\), where \(I=I(\mathbf {p})\), \(J=J_{\mathsf {A}}(\mathbf {p})\), \(K=J\setminus I\), and also assume \(\mathbf {p}^\top {\mathsf {A}}\mathbf {p}=0\). Denote the L.H.S. of (9) by \(g({\mathsf {A}},{\mathsf {B}})\) [there it is denoted by \(h_{I,K}({\mathsf {B}})\) but we want to fix \({\mathsf {B}}\in {{{\mathcal {S}}}^n}\) now]. Then for any \({\mathsf {A}}'\in {\mathcal {C}}_{\mathsf {A}}(\{\mathbf {p}\})\) satisfying \(\mathbf {p}^\top {\mathsf {A}}'\mathbf {p}=0\) and \(\text {colspace}({\mathsf {A}}'_{J\times I})=\text {colspace}({\mathsf {A}}_{J\times I})\) we have \(g({\mathsf {A}},{\mathsf {B}})=g({\mathsf {A}}',{\mathsf {B}})\).
Proof
Our assumptions \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\) and \(\mathbf {p}^\top {\mathsf {A}}\mathbf {p}=0\) imply \({\mathsf {A}}_{J\times I}\mathbf {p}_I=\mathbf {o}\). Then also \({\mathsf {A}}_{I\times I}\mathbf {p}_I=\mathbf {o}\), and from \({\mathcal {B}}({\mathsf {A}}_{I\times I})\succ {\mathsf {O}}\) we deduce \(\text {rank}({\mathsf {A}}_{I\times I})=|I|-1\) and \({\mathsf {A}}_{I\times I}\preceq {\mathsf {O}}\). Moreover, every principal submatrix of order \(|I|-1\) of \({\mathsf {A}}_{I\times I}\) is negative definite.2 Next we show that there is a full rank matrix \({\mathsf {F}}\in {\mathbb {R}}^{|J|\times (|I|-1)}\) such that \((-{\mathsf {F}}{\mathsf {F}}^\top )_{[1:|J|]\times [1:|I|]}={\mathsf {A}}_{J\times I}\). In fact, denoting the upper left principal submatrix of order \(|I|-1\) of \({\mathsf {A}}_{I\times I}\) (corresponding to the index set \(I'\subseteq I\)) by \({\tilde{{\mathsf {A}}}}\), we have \(-{\tilde{{\mathsf {A}}}}={\mathsf {R}}{\mathsf {R}}^\top \succ {\mathsf {O}}\) for some invertible \({\mathsf {R}}\in {\mathcal {S}}^{|I|-1}\), and may choose \({\mathsf {F}}:={\mathsf {A}}_{J\times I'}({\mathsf {R}}^\top )^{-1}\). Indeed, it is easy to see \((-{\mathsf {F}}{\mathsf {F}}^\top )_{[1:|J|]\times [1:|I|-1]}={\mathsf {A}}_{J\times I'}\), and from \(\left[ ({\mathsf {A}}+{\mathsf {F}}{\mathsf {F}}^\top )\mathbf {p}\right] _{[1:|J|]}=\mathbf {o}\) we deduce exact match of the |I|th columns of both matrices. Clearly we have \(\text {colspace}({\mathsf {A}}_{J\times I})=\text {colspace}({\mathsf {F}})\). Now the same conclusions can be made about \({\mathsf {A}}'\), resulting in a full rank matrix \({\mathsf {F}}'\in {\mathbb {R}}^{|J|\times (|I|-1)}\) spanning the same column space as \({\mathsf {F}}\), so there has to be a positive-definite matrix \({\mathsf {Q}}\in {\mathcal {S}}^{|I|-1}\) such that \({\mathsf {A}}'_{J\times I}=(-{\mathsf {F}}{\mathsf {Q}}{\mathsf {F}}^\top )_{[1:|J|]\times [1:|I|]}\). We may and do assume that \({\mathsf {Q}}=\text {Diag}(\lambda _1,\ldots ,\lambda _{|I|-1})\succ {\mathsf {O}}\). It remains to show that the linear maps represented by \({\mathsf {M}}:=({\mathsf {A}}_{K\times I}~|~\mathbf {e})\begin{pmatrix} {\mathsf {A}}_{I\times I} &{} \mathbf {e}\\ \mathbf {e}^\top &{} 0 \end{pmatrix}^{-1}\) and \({\mathsf {M}}':=({\mathsf {A}}'_{K\times I}~|~\mathbf {e})\begin{pmatrix} {\mathsf {A}}'_{I\times I} &{} \mathbf {e}\\ \mathbf {e}^\top &{} 0 \end{pmatrix}^{-1}\) coincide on a set of vectors spanning \({\mathbb {R}}^{|I|+1}\).
We choose the set \(\{\left( {\begin{array}{c}\mathbf {o}\\ 1\end{array}}\right) ,\left( {\begin{array}{c}\mathbf {e}\\ 0\end{array}}\right) ,\left( {\begin{array}{c}\mathbf {f}_1\\ 0\end{array}}\right) ,\ldots ,\left( {\begin{array}{c}\mathbf {f}_{|I|-1}\\ 0\end{array}}\right) \}\), where \({\mathsf {F}}_{[1:|I|]\times [1:|I|-1]}=(\mathbf {f}_1,\ldots ,\mathbf {f}_{|I|-1})\). Linear independence of those vectors is established by noting that \(\left( {\begin{array}{c}\mathbf {f}_i\\ 0\end{array}}\right) _{i\in [1:|I|-1]}\) are linearly independent because \({\mathsf {F}}\) has full column rank, and by observing \({\mathsf {F}}^\top \mathbf {p}_I=\mathbf {o}\) (implying \(\mathbf {f}_i^\top \mathbf {p}_I=0\) for \(1\le i \le |I|-1\)) and \(\mathbf {e}^\top \mathbf {p}_I=1\). First of all note
Next fix \(i\in [1:|I|-1]\) and choose \({\mathbf {v}}_i\in {\mathbb {R}}^{|I|}\) such that (employing the Kronecker delta) \(\mathbf {f}_j^\top {\mathbf {v}}_i=\delta _{ij}\) for \(j\in [1:|I|-1]\) and \(\mathbf {e}^\top {\mathbf {v}}_i=0\). It can be easily checked that
where \({\mathsf {F}}_{[|I|+1:|J|]\times [1:|I|-1]}=(\mathbf {g}_1,\ldots ,\mathbf {g}_{|I|-1})\), which finishes the proof. \(\square \)
Corollary 10
Let \({\mathsf {A}}=-{\mathsf {F}}{\mathsf {F}}^\top \), where \({\mathsf {F}}\in {\mathbb {R}}^{n\times k}\), and assume \(\Delta ^n\cap \ker {\mathsf {F}}^\top \ne \emptyset \). Then for every fixed \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})=\text {Ext}(\Delta ^n\cap \ker {\mathsf {F}}^\top )\) and every fixed diagonal matrix \(\Lambda \succ {\mathsf {O}}\) we have \({\mathsf {A}}':=-{\mathsf {F}}\Lambda {\mathsf {F}}^\top \in {\mathcal {C}}_{\mathsf {A}}(\{\mathbf {p}\})\), and \(J_{{\mathsf {A}}'}(\mathbf {p})=J_{\mathsf {A}}(\mathbf {p})=[1:n]\). Moreover, \(\text {colspace}({\mathsf {A}}_{[1:n]\times I(\mathbf {p})})=\text {colspace}({\mathsf {A}}'_{[1:n]\times I(\mathbf {p})})\), therefore, by Theorem 9, for fixed \({\mathsf {B}}\in {{{\mathcal {S}}}^n}\), we have \(g({\mathsf {A}},{\mathsf {B}})=g({\mathsf {A}}',{\mathsf {B}})\).
That is, for every \({{\mathcal {P}}}\subseteq {{\mathcal {E}}}({\mathsf {A}})\) and for every \(\Lambda \succ {\mathsf {O}}\), if \(\{I(\mathbf {p}):\mathbf {p}\in {{\mathcal {P}}}\}\subseteq \text {qpattern}({\mathsf {A}}+\varepsilon {\mathsf {B}})\) for some \({\mathsf {B}}\in {{{\mathcal {S}}}^n}\) and for \(\varepsilon >0\) small enough, then also \(\{I(\mathbf {p}):\mathbf {p}\in {{\mathcal {P}}}\}\subseteq \text {qpattern}({\mathsf {A}}'+\varepsilon {\mathsf {B}})\) for that same \({\mathsf {B}}\in {{{\mathcal {S}}}^n}\) and for \(\varepsilon >0\) small enough.
2.3 Cyclic Symmetry
We call a subset \({{\mathcal {P}}}\subseteq {\mathbb {R}}^{n}\) closed under cyclic permutations, if \(\mathbf {p}\in {{\mathcal {P}}}\Rightarrow {\mathsf {P}}\mathbf {p}\in {{\mathcal {P}}}\), where \({\mathsf {P}}=(p_{ij})\) satisfies \(p_{ij}=1\) for \(j\equiv i+1 (\hbox { mod } n)\), and otherwise \(p_{ij}=0\). We call \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\)cyclically symmetric (or symmetric circulant), if it satisfies \({\mathsf {A}}={\mathsf {P}}^\top {\mathsf {A}}{\mathsf {P}}\), and employ the notation \({\mathsf {C}}(\mathbf {a})\) for a cyclically symmetric matrix whose first column is \(\mathbf {a}\). Note that for an \(n\times n\) cyclically symmetric matrix \({\mathsf {A}}\) the set \({{\mathcal {E}}}({\mathsf {A}})\) is closed under cyclic permutations. In case that \({\mathsf {A}}\) is cyclically symmetric, there are well-behaved subsets of \({{\mathcal {E}}}({\mathsf {A}})\), where the “transfer” can be achieved by cyclically symmetric perturbations, whenever it can be achieved by certain symmetric perturbations, as the following theorem tells.
Theorem 11
Let \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) be cyclically symmetric, let \({{\mathcal {P}}}\subseteq {{\mathcal {E}}}({\mathsf {A}})\) be closed under cyclic permutations, and let \({{\mathcal {P}}}':=\{\mathbf {p}\in {{\mathcal {P}}}:|I(\mathbf {p})|<|J_{\mathsf {A}}(\mathbf {p})|\}\), which is then also closed under cyclic permutations.
Suppose that there is \({\mathsf {B}}\in {{{\mathcal {S}}}^n}\) satisfying (9) for all \((I,K)\in {\mathcal {I}}_{{{\mathcal {P}}}'}\). Then the matrix \({\mathsf {C}}:=\sum _{i=1}^n({\mathsf {P}}^i)^\top {\mathsf {B}}{\mathsf {P}}^i\) is cyclically symmetric and satisfies
also for all \((I,K)\in {\mathcal {I}}_{{{\mathcal {P}}}'}\).
Thus, by Lemma 2, for \(\varepsilon >0\) small enough, we have \(\{I(\mathbf {p}):\mathbf {p}\in {{\mathcal {P}}}\}\subseteq \text {qpattern}({\mathsf {A}}+\varepsilon {\mathsf {C}})\).
Proof
From \({\mathsf {C}}={\mathsf {P}}^\top {\mathsf {C}}{\mathsf {P}}\) it is clear that \({\mathsf {C}}\) is cyclically symmetric. Next observe that \(({\mathsf {P}}^\top {\mathsf {B}}{\mathsf {P}})_{K\times I}={\mathsf {B}}_{K'\times I'}\), where \(I=I(\mathbf {p})\), \(I'=I({\mathsf {P}}\mathbf {p})\), \(K=J_{\mathsf {A}}(\mathbf {p})\setminus I\), and \(K'=J_{\mathsf {A}}({\mathsf {P}}\mathbf {p})\setminus I'\), as well as \(({\mathsf {P}}^\top {\mathsf {B}}{\mathsf {P}})_{I\times I}={\mathsf {B}}_{I'\times I'}\), for some \(\left\{ \mathbf {p},{\mathsf {P}}\mathbf {p}\right\} \subseteq {{\mathcal {P}}}\). Since \({\mathsf {A}}\) is cyclically symmetric, we have \({\mathsf {A}}_{K'\times I'}={\mathsf {A}}_{K\times I}\) and \({\mathsf {A}}_{I'\times I'}={\mathsf {A}}_{I\times I}\). Thus, if (9) is satisfied, it stays satisfied if we replace \({\mathsf {B}}\) by \(({\mathsf {P}}^i)^\top {\mathsf {B}}{\mathsf {P}}^i\). Summing over i then finishes the proof of (10). Finally, \(I(\mathbf {p})\in \text {qpattern}({\mathsf {A}}+\varepsilon {\mathsf {C}})\), for \(\varepsilon >0\) small enough, is true for \(\mathbf {p}\in {{\mathcal {P}}}'\) by Lemma 2, and true for \(\mathbf {p}\in {{\mathcal {P}}}\setminus {{\mathcal {P}}}'\) by a continuity argument (quasistrictness of NESs is preserved, as is negative-definiteness). \(\square \)
Remark 3
Note that cyclic symmetry of \({\mathsf {C}}\) has the following implication. If for some \(\mathbf {p}\in \Delta ^n\) the inequalities (10) are satisfied for \((I,K)\in {\mathcal {I}}_{\{\mathbf {p}\}}\), those inequalities will be satisfied for all \((I,K)\in {\mathcal {I}}_{{\mathcal {Z}}_\mathbf {p}}\), where \({\mathcal {Z}}_\mathbf {p}:=\{\mathbf {p},{\mathsf {P}}\mathbf {p},\ldots ,{\mathsf {P}}^{n-1}\mathbf {p},{\mathsf {R}}\mathbf {p},{\mathsf {P}}{\mathsf {R}}\mathbf {p},\ldots ,{\mathsf {P}}^{n-1}{\mathsf {R}}\mathbf {p}\}\), with \({\mathsf {R}}\mathbf {p}:=[p_n,p_{n-1},\ldots ,p_1]^\top \) denoting the vector with the coordinates of \(\mathbf {p}\) in reverse order.
Remark 4
Note that Proposition 6 is not valid if we require \({\mathsf {A}}\) and \({\mathsf {A}}''\) to be cyclically symmetric, as is demonstrated by the following example: For the cyclically symmetric matrix \({\mathsf {A}}:={\mathsf {C}}([-1,0,1,0,-1,0,1,0]^\top )\) of rank 2 we have \({{\mathcal {E}}}({\mathsf {A}})=\{\tfrac{1}{2}(\mathbf {e}_{i}+\mathbf {e}_{i+2}):i\in [{1}\! : \!{8}]\}\), with \(i+2\in [{1}\! : \!{8}]\) computed modulo 8, so all supports have size 2. Now there is no cyclically symmetric matrix \({\mathsf {A}}'\) of rank 1 satisfying \({{\mathcal {E}}}({\mathsf {A}})\subseteq {{\mathcal {E}}}({\mathsf {A}}')\), but we have \({{\mathcal {E}}}({\mathsf {A}})\subseteq {{\mathcal {E}}}({\mathsf {A}}'')\) for the rank 1 matrix \({\mathsf {A}}'':=-{\mathsf {H}}{\mathsf {H}}^\top \), where \({\mathsf {H}}^\top :=(1,1,-1,-1,1,1,-1,-1)\). Also observe that \({\mathsf {A}}_\varepsilon :={\mathsf {C}}([-1,0,1+\varepsilon ,0,-1-\varepsilon ,0,1+\varepsilon ,0]^\top )\) satisfies \(\mathrm{ESS}({\mathsf {A}}_\varepsilon )={{\mathcal {E}}}({\mathsf {A}})\) for arbitrarily small \(\varepsilon >0\), so in this example, perturbation of \({\mathsf {A}}\) yields a cyclically symmetric matrix as desired, whereas we can even get \({{\mathcal {E}}}({\mathsf {A}})\subseteq \mathrm{ESS}({\mathsf {A}}''_\varepsilon )\) with \(|\mathrm{ESS}({\mathsf {A}}''_\varepsilon )|=16\), where \({\mathsf {A}}''_\varepsilon :={\mathsf {A}}''+\varepsilon {\mathsf {I}}_8\), when not insisting on cyclic symmetry.
The vector space \({\mathcal {C}}^n:=\{{\mathsf {A}}\in {{{\mathcal {S}}}^n}: {\mathsf {A}}\text { is cyclically symmetric}\}\), on which we now concentrate, has dimension \(n'+1\), where \(n':=\lceil \frac{n-1}{2}\rceil \), a basis being \(\{{\mathsf {P}}^i+{\mathsf {P}}^{-i}:i\in [{0}\! : \!{n'}]\}\). As \({\mathcal {C}}^n\) is a subspace of the space of all circulant matrices (see [14]) of order n, all members of \({\mathcal {C}}^n\) are simultaneously diagonalizable, and because of their symmetry, a common orthogonal basis of real eigenvectors can be used for that purpose. Those are the nonzero vectors in the set \(\{\mathbf {c}_i,\mathbf {s}_i: i\in [{0}\! : \!{n'}]\}\), where
This leads to a basis for \({\mathcal {C}}^n\), consisting of low rank matrices \({\mathsf {V}}_i:=\mathbf {c}_i\mathbf {c}_i^\top +\mathbf {s}_i\mathbf {s}_i^\top \), with those ranks adding up to n, that will be more convenient. The set \(\{{\mathsf {V}}_i:i\in [{0}\! : \!{n'}]\}\) indeed constitutes such a basis. Just note that \({\mathsf {V}}_0=\mathbf {e}\mathbf {e}^\top \) has rank 1, \({\mathsf {V}}_{n'}= \mathbf {c}_{n'}\mathbf {c}_{n'}^\top \) in case of even n has rank 1 as well, and all remaining matrices \({\mathsf {V}}_i\) are seen to have rank 2 by orthogonality of \(\{\mathbf {c}_i,\mathbf {s}_i\}\) for each \(i\in [{1}\! : \!{n'}]\) (and also for \(i=n'\) if n is odd). Moreover, employing trigonometric identities, we obtain \(({\mathsf {V}}_i)_{k,\ell }=\cos \frac{2(k-\ell )i\pi }{n}\), which depends on \(k,\ell \) only via the residue class of \(|k-\ell |\mod n\), showing that \({\mathsf {V}}_i\in {\mathcal {C}}^n\) for all \(i\in [{0}\! : \!{n'}]\). Linear independence of the set \(\{{\mathsf {V}}_i:i\in [{0}\! : \!{n'}]\}\) follows from linear independence of corresponding column spaces, which follows from the observation that \(\{\mathbf {c}_i,\mathbf {s}_i:i\in [{0}\! : \!{n'}]\}\setminus \left\{ \mathbf {o}\right\} \) constitutes a basis of \({\mathbb {R}}^n\). Note that with respect to the Frobenius inner product, we have \({\mathsf {V}}_i\bullet {\mathsf {V}}_j=0\) if \(i\ne j\).
2.4 Construction
Now consider negative-semidefinite matrices \({\mathsf {A}}\in {\mathcal {C}}^n\) satisfying \({\mathsf {A}}\bullet {\mathsf {V}}_0=0\). That is, there is a representation \({\mathsf {A}}=-{\mathsf {F}}{\mathsf {F}}^\top =-\sum _{i\in L}\lambda _i{\mathsf {V}}_i\) for some \(L\subseteq [{1}\! : \!{n'}]\), \(\lambda _i>0\) for \(i\in L\), \({\mathsf {F}}\in {\mathbb {R}}^{n\times k}\), and the columns of \({\mathsf {F}}\) are nonzero multiples of vectors in the set \(\{\mathbf {c}_i,\mathbf {s}_i\ne \mathbf {o}:i\in L\}\). (Note that, if n is odd then \(k:=\hbox {rank }({\mathsf {A}})= 2|L|\) is even.) Also \(\tfrac{1}{n}\mathbf {e}\in \Delta ^n\cap \ker {\mathsf {F}}^\top \), therefore Corollary 10 applies. So when perturbing negative-semidefinite matrices \({\mathsf {A}}\in {\mathcal {C}}^n\setminus \{{\mathsf {O}}\}\) satisfying \({\mathsf {A}}\bullet {\mathsf {V}}_0=0\), we may restrict our attention to the finite set of candidate matrices\({\mathcal {A}}_n:=\{{\mathsf {A}}_L:\emptyset \ne L\subseteq [{1}\! : \!{n'}]\}\), where \({\mathsf {A}}_L:=-\sum _{i\in L}{\mathsf {V}}_i\). Moreover, by Theorem 8, we may restrict the matrix \({\mathsf {B}}\), used to perturb \({\mathsf {A}}_L\) via \({\mathsf {A}}_L+\varepsilon {\mathsf {B}}\), to \(\text {span}\,\{{\mathsf {V}}_j:j \in [{1}\! : \!{n'}]\setminus L\}\).
As we can restrict ourselves to matrices with zero diagonal, yet another basis will even better serve our needs: \(\{{\mathsf {W}}_i:i\in [{0}\! : \!{n'}]\}\), where \({\mathsf {W}}_0={\mathsf {V}}_0\) and \({\mathsf {W}}_i=\tfrac{1}{2}(\mathbf {e}\mathbf {e}^\top -{\mathsf {V}}_i)\) for \(i\in [{1}\! : \!{n'}]\), with \(({\mathsf {W}}_i)_{k,\ell }=\sin ^2\frac{(k-\ell )i\pi }{n}\). The last two sentences of the preceding paragraph remain true with \({\mathsf {A}}_L:=\sum _{i\in L}{\mathsf {W}}_i\) and \({\mathsf {B}}\in \text {span}\,\{{\mathsf {W}}_j:j \in [{1}\! : \!{n'}]\setminus L\}\).
We are only interested in the size of \(\text {qpattern}({\mathsf {A}})\), so we would not distinguish between \({\mathsf {A}}\in {\mathcal {C}}^n\) and \({\mathsf {A}}':={\bar{{\mathsf {P}}}}{\mathsf {A}}{\bar{{\mathsf {P}}}}^\top \), where \({\bar{{\mathsf {P}}}}\) is a permutation matrix. If \({\mathsf {A}}'={\bar{{\mathsf {P}}}}{\mathsf {A}}{\bar{{\mathsf {P}}}}^\top \in {\mathcal {C}}^n\), but \({\mathsf {A}}'\ne {\mathsf {A}}\), this allows for a further reduction of the set of candidate matrices. In particular, if for some permutation \(\tau \) of the set \([{1}\! : \!{n'}]\), we have \({\bar{{\mathsf {P}}}}{\mathsf {W}}_i{\bar{{\mathsf {P}}}}^\top ={\mathsf {W}}_{\tau (i)}\) for \(i\in [{1}\! : \!{n'}]\), then for sets \(L\subseteq [{1}\! : \!{n'}]\) and \(\tau L:=\{\tau (i):i\in L\}\) we have
where \({\mathsf {B}}'={\bar{{\mathsf {P}}}}{\mathsf {B}}{\bar{{\mathsf {P}}}}^\top \). That is, we can further restrict our set of candidate matrices to a subset \(\bar{\mathcal {A}_n}\subseteq {\mathcal {A}}_n\) by ensuring that for every \(L\subseteq [{1}\! : \!{n'}]\) exactly one matrix from the set \(\{{\mathsf {A}}_L,{\mathsf {A}}_{\tau L},{\mathsf {A}}_{\tau ^2 L},\ldots \}\) is contained in \(\bar{\mathcal {A}_n}\).
Example 12
For \(n=6\) we obtain
The only permutation \(\tau \) that can be introduced via a permutation matrix \({\bar{{\mathsf {P}}}}\) as above is the identity, so the set of candidate matrices will be \(\bar{\mathcal {A}_6}={\mathcal {A}}_6=\{{\mathsf {A}}_L:\emptyset \ne L\subseteq [{1}\! : \!{3}]\}\).
where \({\bar{{\mathsf {P}}}}=({\bar{p}}_{ij})\) satisfies \({\bar{p}}_{ij}=1\) for \(j\equiv 2i (\hbox { mod } n)\), and otherwise \({\bar{p}}_{ij}=0\). Then also \({\mathsf {W}}_1={\bar{{\mathsf {P}}}}{\mathsf {W}}_3{\bar{{\mathsf {P}}}}^\top \) holds. So \({\bar{{\mathsf {P}}}}\) induces a non-trivial permutation \(\tau \) on \([{1}\! : \!{3}]\), and the set of candidate matrices reduces to \(\bar{\mathcal {A}_7}:=\{{\mathsf {A}}_{\{1\}},{\mathsf {A}}_{\{1,2\}},{\mathsf {A}}_{\{1,2,3\}}\}\).
Note that for the candidate matrix \({\mathsf {A}}:={\mathsf {A}}_{[1:n']}\in \bar{\mathcal {A}_n}\) we have \({{\mathcal {E}}}({\mathsf {A}})=\mathrm{ESS}({\mathsf {A}})=\{\tfrac{1}{n}\mathbf {e}\}\), and the latter set will not change, if \({\mathsf {A}}\) is slightly perturbed. Therefore we exclude that candidate matrix from further considerations. For the remaining candidate matrices \({\mathsf {A}}_L\) we have \(L':=[{1}\! : \!{n'}]\setminus L\ne \emptyset \), and for \(\varvec{\alpha }\in {\mathbb {R}}^{L'}\) we define \({\mathsf {B}}_{\varvec{\alpha }}:=\sum _{i\in L'}\alpha _i{\mathsf {W}}_i\). For every \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}}_L)\), we denote by \({\mathcal {L}}_{L,\mathbf {p}}\) the solution set of inequality (9), where \(I=I(\mathbf {p})\) and \(K=J_{{\mathsf {A}}_L}(\mathbf {p})\setminus I\), and clearly that inequality is linear in \(\varvec{\alpha }\). Next, we denote by \({\mathcal {R}}_L\) a maximal subset of \({{\mathcal {E}}}({\mathsf {A}}_L)\) consisting only of \(\mathbf {p}\) of maximal support size, i.e., \(|I(\mathbf {p})|=\hbox {rank }({\mathsf {A}}_L)+1\), and satisfying \({\mathcal {Z}}_\mathbf {p}\cap {\mathcal {R}}_L=\{\mathbf {p}\}\) for every \(\mathbf {p}\in {\mathcal {R}}_L\), where \({\mathcal {Z}}_\mathbf {p}\) is introduced in Remark 3. Our aim is then to find a subset \(\bar{{\mathcal {R}}}_L\subseteq {\mathcal {R}}_L\) of largest \(\text {size}(\bar{{\mathcal {R}}}_L):=\sum _{\mathbf {p}\in \bar{{\mathcal {R}}}_L}|{\mathcal {Z}}_\mathbf {p}|\), such that
Any \(\varvec{\alpha }\) in that nonempty intersection will then lead to a matrix \({\mathsf {B}}_{\varvec{\alpha }}\), such that for \(\varepsilon >0\) small enough
A natural further reduction of the set of candidate matrices is via the definition \(\bar{\bar{\mathcal {A}_n}}:=\{{\mathsf {A}}_L\in \bar{\mathcal {A}_n}:{\mathcal {R}}_L\ne \emptyset \}\).
Example 13
(Continuation of Example 12) For \(n=6\) we have \({{\mathcal {E}}}({\mathsf {A}}_{\{1\}})={\mathcal {Z}}_{\mathbf {p}_1}\cup {\mathcal {Z}}_{\mathbf {p}_2}\), \({{\mathcal {E}}}({\mathsf {A}}_{\{2\}})={\mathcal {Z}}_{\mathbf {p}_1}\cup {\mathcal {Z}}_{\mathbf {p}_3}\), \({{\mathcal {E}}}({\mathsf {A}}_{\{3\}})={\mathcal {Z}}_{\mathbf {p}_2}\cup {\mathcal {Z}}_{\mathbf {p}_4}\), \({{\mathcal {E}}}({\mathsf {A}}_{\{1,2\}})={\mathcal {Z}}_{\mathbf {p}_1}\), \({{\mathcal {E}}}({\mathsf {A}}_{\{1,3\}})={\mathcal {Z}}_{\mathbf {p}_2}\), \({{\mathcal {E}}}({\mathsf {A}}_{\{2,3\}})={\mathcal {Z}}_{\mathbf {p}_5}\), where
Corresponding matrices with 9 ESSs of support size 2 (resp. 8 ESSs of support size 3, resp. 6 ESSs of support size 4) are given in Table 2. Also note that we have just derived \(\bar{\bar{\mathcal {A}_6}}=\{{\mathsf {A}}_{\{1\}},{\mathsf {A}}_{\{2\}},{\mathsf {A}}_{\{3\}},{\mathsf {A}}_{\{2,3\}}\}\).
Let us consider \(L=\{2\}\) in more detail: We have \({\mathsf {A}}_{\{2\}}={\mathsf {W}}_2\), \({\mathsf {B}}_{\varvec{\alpha }}=\alpha _1{\mathsf {W}}_1+\alpha _2{\mathsf {W}}_3\), and for \(I=I(\mathbf {p}_3)=\{1,2,3\}\), \(K=\{4,5,6\}\), inequality (9) reads
This results in \({\mathcal {L}}_{\{2\},\mathbf {p}_3}=\{\varvec{\alpha }\in {\mathbb {R}}^2:\alpha _1+\alpha _2<0,2\alpha _1-\alpha _2<0\}\) and \({\mathcal {L}}_{\{2\},\mathbf {p}_1}=\{\varvec{\alpha }\in {\mathbb {R}}^2:\alpha _2<0\}\). These two sets have nonempty intersection, containing \(\varvec{\alpha }=-[1,1]^\top \), which gives rise to \({\mathsf {B}}_{\varvec{\alpha }}\). Numerical experiments with varying \(\varepsilon \) yield that \(\varepsilon :=\tfrac{1}{4}\) is small enough for our purposes: With \({\mathsf {M}}:={\mathsf {A}}_{\{2\}}+\varepsilon {\mathsf {B}}_{\varvec{\alpha }}={\mathsf {C}}([0,\tfrac{7}{16},\tfrac{9}{16},-\tfrac{1}{2},\tfrac{9}{16},\tfrac{7}{16}]^\top )\) we have \(\mathrm{ESS}({\mathsf {M}})={\mathcal {Z}}_{{\bar{\mathbf {p}}}_3}\cup {\mathcal {Z}}_{\mathbf {p}_1}\), with \({\bar{\mathbf {p}}}_3=\tfrac{1}{19}[7,5,7,0,0,0]^\top \), and in particular \(|\mathrm{ESS}({\mathsf {M}})|=8\). Likewise, by choosing \(\varvec{\alpha }\in {\mathcal {L}}_{\{2\},\mathbf {p}_3}\setminus \text {cl}({\mathcal {L}}_{\{2\},\mathbf {p}_1})\), resp. \(\varvec{\alpha }\in {\mathcal {L}}_{\{2\},\mathbf {p}_1}\setminus \text {cl}({\mathcal {L}}_{\{2\},\mathbf {p}_3})\), we can construct matrices having 6 resp. 2 ESSs.
Figure 1 shows part of the search space for \(n=6\). Note that we may get rid of two of the four parameters, that matrices from \({\mathcal {C}}^6\) depend on, by assuming a zero diagonal and a fixed sum of entries. In the figure we have fixed the sum of entries of the first row to 2. The interior of the white triangle corresponds to matrices with one single ESS, namely \(\tfrac{1}{6}\mathbf {e}\). The boundary of the white triangle consists of negative-semidefinite matrices (up to an additive multiple of \(\mathbf {e}\mathbf {e}^\top \)), the three vertices corresponding to (positive multiples of) matrices \({\mathsf {W}}_1,{\mathsf {W}}_2\) and \({\mathsf {W}}_3\). The matrix \({\mathsf {M}}\) from above then belongs to the dark gray region. There is a circle attached to each shaded region containing information regarding the pattern of matrices in the interior of that region, e.g., \(8_3\) indicates that there are 8 ESSs, each of support size 3. Note that the figure clearly misses matrices where entries sum to 0 or a negative value, and indeed the pattern \(6_1\) attained at the matrix \({\mathsf {C}}([0,-1,-1,-1,-1,-1]^\top )\) does not show up in the figure; see, however, [5, Figure 1] for the whole search space.
Fig. 1
Part of the search space for \(n=6\) on the hyperplane characterized by \(a+b+c=1\), where points [a, b, c] depicted in barycentric coordinates correspond to positive multiples of matrices \({\mathsf {C}}([0,a,b,2c,b,a]^\top )\)
×
In terms of our perturbation approach, matrix \({\mathsf {A}}_{\{2,3\}}\) is our entry to region \(6_4\), matrix \({\mathsf {A}}_{\{3\}}\) to regions \(3_2\), \(6_2\) and \(9_2\), matrix \({\mathsf {A}}_{\{2\}}\) to regions \(2_3\), \(6_3\) and \(8_3\), and matrix \({\mathsf {A}}_{\{1\}}\) is our entry to the interior of \(\text {cl}(2_3\cup 2_33_2)\). Note that, in the latter case, \(\mathbf {p}_2\in {{\mathcal {E}}}({\mathsf {A}}_{\{1\}})\setminus {\mathcal {Z}}_{\mathbf {p}_1}\) has insufficient support size and thus does not enter the inequalities restricting \(\varvec{\alpha }\). Matrices found near \({\mathsf {A}}_{\{1\}}\) may lie on either side of, or straight on, the boundary \(2_3\)-\(2_33_2\).
We conclude this example by some further remarks concerning the regions in Fig. 1, and their boundaries. For matrices \({\mathsf {A}}\) from one of the regions, we always have \(\mathrm{ESS}({\mathsf {A}})={{\mathcal {E}}}({\mathsf {A}})\). Regarding boundaries, we have \(\mathrm{ESS}({\mathsf {A}})=\emptyset ,|\mathrm{NSS}({\mathsf {A}})|=\infty \) and \(\tfrac{1}{6}\mathbf {e}\in \mathrm{NSS}({\mathsf {A}})\) for every \({\mathsf {A}}\) on the boundary of the white triangle. There are 8 remaining boundary pieces in the complement of the closure of the white triangle, which are listed in Table 1. We observe two types of behavior. Either for a matrix \({\mathsf {A}}\) on a boundary, \(|\mathrm{ESS}({\mathsf {A}})|\) is the minimum of the numbers of ESSs found in the two regions separated by that boundary, while \(|{{\mathcal {E}}}({\mathsf {A}})|\) is the maximum of those, and \(\mathrm{NSS}({\mathsf {A}})=\mathrm{ESS}({\mathsf {A}}).\) Or \(\mathrm{ESS}({\mathsf {A}})=\emptyset \), while
is infinite. The relative interiors of the sides of the white triangle, that we added to the table, are also of the latter type, with the simplification, resulting from \(J_{\mathsf {A}}(\mathbf {p})= [{1}\! : \!{6}]\) in the second to last column, that \(\mathrm{NSS}({\mathsf {A}})=\hbox {conv }{{\mathcal {E}}}({\mathsf {A}})\). There may be further types of \(n'-2\)-dimensional boundaries for higher orders n.
Part of the search space for \(n=7\) on the hyperplane characterized by \(a+b+c=1\), where points [a, b, c] depicted in barycentric coordinates correspond to positive multiples of matrices \({\mathsf {C}}([0,a,b,c,c,b,a]^\top )\)
×
In general, we would desire a more detailed picture, such as given in Fig. 2, where pattern\(({\mathsf {A}})\) enters the definition of a “region” directly and not just via the sizes of the elements of pattern\(({\mathsf {A}})\). This would, however, not change Fig. 1. The question arises, if those newly defined “regions”, which in general have to be thought of as being confined to a hyperplane not containing the origin, are connected or even convex (the latter is not always the case, as can be seen in Fig. 1).
Table 2
Cyclically symmetric matrices of orders from 4 up to 19 with many ESSs of prescribed support size
The bold number in the lower left of each box indicates the order of matrices in that box, and the row \([14_3\,\vert \,1~5~8]\) in the box corresponding to order 7 tells us that the matrix \({\mathsf {C}}([0,1,5,8,8,5,1]^\top )\) has 14 ESSs of support size 3
Table 3
Cyclically symmetric matrices of orders 20 and 21 with many ESSs of prescribed support size
Table 4
Cyclically symmetric matrices of orders 22 and 23 with many ESSs of prescribed support size
2.5 Results
We used the construction outlined in the previous subsection to find cyclically symmetric matrices of orders \(n\in [{4}\! : \!{23}]\) with many ESSs of support size \(k\in [{2}\! : \!{n-2}]\), with k either 2 or odd, when n is odd. We wanted those matrices to have integer entries to facilitate the computation of the set of ESSs. While our main goal was to maximize the number of ESSs, we also made efforts to keep the integer entries small. Our results can be found in Tables 2, 3 and 4, containing a box for each order \(n\in [{4}\! : \!{23}]\), the order always being indicated by the bold number in the lower left of that box, with a row for each support size. The row \([8_52_4\,\vert \,1~5~4~2]\) in the box corresponding to order 8 tells us that the matrix \({\mathsf {C}}([0,1,5,4,2,4,5,1]^\top )\) has 8 ESSs of support size 5, but also 2 “spurious” ESSs of support size 4. It was not our aim to get a “pure” result \(8_5\) by introducing further inequalities on \(\varvec{\alpha }\). Indeed, cases of “spurious” ESSs of slightly smaller support sizes than aimed at appear also in other places of the tables, mainly for even orders. In some cases that information was suppressed due to lack of space, but we give it here; the corresponding vector \(\mathbf {a}\) can be found in row \([x | \mathbf {a}^\top ]\) in Tables 2, 3 and 4, where x is the first part of the regular-type faced entries in the five row vectors of the following four lines:
For instance, for \(24_72_63_4\) with order \(n={\mathbf{12}}\) we have \(\mathbf {a}^\top = [2,7,7,5,6,7]\) from Table 2. All calculations were done with Maple\(^{\mathrm{TM}}\) and the matrices listed in the tables were double-checked with Reinhard Ullrich’s program ref (rational equilibrium finder). For fixed n, the first task is to find the set \(\bar{\mathcal {A}_n}\) of candidate matrices. Containing at most one matrix indexed by any of the subsets L of \([{1}\! : \!{n'}]\), its size is bounded by \(2^{n'}\), but a further reduction in size to roughly \(\frac{2}{\varphi (n)}2^{n'}\), where \(\varphi \) denotes the Euler totient function, is possible, by keeping just one member of each orbit \(\{{\mathsf {A}}_L,{\mathsf {A}}_{\tau L},{\mathsf {A}}_{\tau ^2 L},\ldots \}\), where \(\tau \) is a permutation on \([{1}\! : \!{n'}]\) generating a cyclic group of order \(\frac{\phi (n)}{2}\). That resulted in, e.g., \(|\bar{\mathcal {A}_{22}}|=394\), which is much smaller then \(2^{11}\).
Next, we fixed \({\mathsf {A}}={\mathsf {A}}_L\in \bar{\mathcal {A}_n}\) of rank \(k-1\) and computed \({\mathcal {R}}_L\). Potential supports of members of \({\mathcal {R}}_L\) are all subsets of \([{1}\! : \!{n}]\) of size k. Among a certain subset and all its shifts and reflected shifts only one set has to be taken into account, which reduces the number of potential supports to roughly \(\frac{1}{2n}\left( {\begin{array}{c}n\\ k\end{array}}\right) \). For any such support I we then checked if there is \(\mathbf {p}\in {{\mathcal {E}}}({\mathsf {A}})\) with \(I(\mathbf {p})=I\), i.e., we numerically solved \({\mathsf {A}}_{I\times I}\mathbf {p}_I=\mathbf {o},\mathbf {e}^\top \mathbf {p}_I=1\). If the system appeared to lack a unique solution, we discarded that support. We also did that, if the solution was outside the simplex \(\Delta ^{k}\) or apparently on its boundary. Only if the solution \(\mathbf {p}\) was clearly in the interior of \(\Delta ^{k}\), and \({\mathcal {L}}_{L,\mathbf {p}}\ne \emptyset \) was fulfilled, did we include I in \({\mathcal {R}}_L\). E.g., for \(n=22\) and \(k=10\) we obtain 14938 (shift- and reflection-reduced) potential supports, of which not more than 280 belong to any set \({\mathcal {R}}_L\): There are 42 candidate matrices of rank 9 in \(\bar{\mathcal {A}_{22}}\). Corresponding sets \({\mathcal {R}}_L\) satisfy \(280 \ge |{\mathcal {R}}_L|\ge 1\) and \(11011 \ge \text {size}({\mathcal {R}}_L)\ge 22\) for L in a suitable 42-element set. For each such L we have to maximize \(\text {size}(\bar{{\mathcal {R}}}_L)\) under the constraints \(\bar{{\mathcal {R}}}_L\subseteq {\mathcal {R}}_L, \bigcap _{\mathbf {p}\in \bar{{\mathcal {R}}}_L}{\mathcal {L}}_{L,\mathbf {p}}\ne \emptyset \). We would work our way down starting with the most promising L corresponding to \(\text {size}({\mathcal {R}}_L)=11011\), thus finding the largest value 4422 of size\((\bar{{\mathcal {R}}}_{L})\) for \(L=\{1,2,3,4,11\}\), with size\(({{\mathcal {R}}}_{L})=6138\) being the 28th-largest among the corresponding 42 values.
We replaced the “\(<0\)”-inequalities originating in (9), that are present in the constraints of the maximization problem, by “\(\le -\delta \)”-inequalities for some fixed \(\delta >0\). The problem can be regarded as a Maximum Feasible Subsystem Problem, see [16]. For small n, we solved the problem by exhaustive search, for larger n we used a heuristic approach to generate good lower bounds for the optimal value (basically, we repeatedly started with a list built from a random permutation of the points in \({\mathcal {R}}_L\) and, starting at the beginning of the list, greedily included points \(\mathbf {p}\) while maintaining nonempty intersection of the corresponding sets \({\mathcal {L}}_{L,\mathbf {p}}\)). For n up to 19 we also computed upper bounds for the optimal values, derived from formulations as Min IIS (irreducible inconsistent subsystem) Cover problems [16], with those upper bounds matching the lower bounds. So we can be sure to have solved the maximization problems for \(n\in [{4}\! : \!{19}]\) to optimality, but we do not know whether some of our lower bounds for \(n\in [{20}\! : \!{23}]\) leading to entries in Tables 3 and 4 are actually the optimal objective values for the corresponding problems.
Having solved (or having found a good lower bound \({\underline{m}}\) for) the maximization problem means that we now know a matrix \({\mathsf {B}}_{\varvec{\alpha }}\) such that \({\mathsf {A}}+\varepsilon {\mathsf {B}}_{\varvec{\alpha }}\) will have many quasistrict ESSs. As we want integer entries for our matrices, we would rather consider matrices \(r_1{\mathsf {A}}+r_2{\mathsf {B}}_{\varvec{\alpha }}\) with \(r_1\) large and \(r_2\) of moderate size, and we would round the entries of that matrix to the nearest integers. Clearly \(r_2\) may not be too small, otherwise \({\mathsf {B}}_{\varvec{\alpha }}\)’s influence will get wiped out by the rounding. Also \(\frac{r_1}{r_2}=\frac{1}{\varepsilon }\) may not be too small, as we need \(\varepsilon \) small. So suitable \(r_1,r_2\) will lead to a matrix with \({\underline{m}}\) quasistrict ESSs of support size k, having typically very large integer entries. Computing a series of ever smaller multiples of that matrix and rounding again—which is what we did—can reduce the entries of the matrix to some extent. Trying to have integer entries close to the minimal values possible would require considering all \(\varvec{\alpha }\) in the nonempty intersection of the sets \({\mathcal {L}}_{L,\mathbf {p}}\) and all matrices \({\mathsf {A}}'\) as defined in Corollary 10, for all L for which \(\text {size}(\bar{{\mathcal {R}}}_L)={\underline{m}}\). We did not pursue that approach.
Summarizing, for orders \(n\in [{4}\! : \!{19}]\) and prescribed support sizes \(k\in [{2}\! : \!{n-2}]\), with k odd when n is odd, we have constructed matrices in \({\mathcal {C}}^n\) with a maximum number of quasistrict ESSs of support size k. Here maximality is meant among matrices in \({\mathcal {C}}^n\) occurring, in positive proportion, arbitrarily close to some negative-semidefinite matrix of rank \(k-1\). We do, however, not claim that the matrices we found are close to negative-semidefinite ones in the sense that there is a continuous path in \({\mathcal {C}}^n\) from one to the other along which the pattern does not change, as we do not know if there may be disconnected regions within \({\mathcal {C}}^n\) that share the same pattern, so that our rounding procedure could have led to a jump from one region to another. This holds in particular in some cases where \(n=n_1n_2\) is not a prime number. If the best result we found for some fixed k was not better than what we got by constructing a matrix from suitable matrices of orders \(n_1\) and \(n_2\) using construction techniques from [5], we would list the latter in our table, when it had entries of smaller size. Note that, in view of Lemma 3 and Example 4, our approach need not have worked for \(k=n-2\), but it did: It is known from [6, Thm. 5], that \(\max \limits _{{\mathsf {A}}\in {\mathcal {C}}^n}\left| \left\{ \mathbf {p}\in \mathrm{ESS}({\mathsf {A}}):|I(\mathbf {p})|=n-2\right\} \right| =n\), and our construction method produced matrices with integer entries achieving this maximal value for all \(n\in [{4}\! : \!{23}]\).
Remark 5
Special attention to cyclically symmetric matrices has been payed by [6], from which we can deduce that
and also if n is even and \(k=2\). The L.H.S. is, however, strictly smaller than the R.H.S. if \(n\ge 3\) and \(k=n-1\), and also if \(n\ge 3\) is odd and \(k=2\). (See also the next section for the case \(k=2\).) Furthermore, the best lower bound for the constant \(\gamma \) introduced in [6, Thm. 2], that is currently known, is \(15120^{\frac{1}{24}}\approx 1.4933\), and originates from a matrix \({\mathsf {A}}\in {\mathcal {C}}^{24}\) satisfying \(|\mathrm{ESS}({\mathsf {A}})|=15120\), see [5]. The main reason we concentrated on cyclically symmetric matrices is however that they are particularly well suited for our perturbation method. There are only finitely many column spaces associated with matrices in \({\mathcal {C}}^n\), which, by invoking Corollary 10, led to finite sets \(\bar{\mathcal {A}_n}\) of candidate matrices, something we cannot hope for if we replace \({\mathcal {C}}^n\) by (other interesting subsets of) \({{{\mathcal {S}}}^n}\).
3 Even Support Sizes of ESSs When the Order is Odd
The construction method described in Sect. 2 is not suited for finding cyclically symmetric matrices of odd order that have many ESSs of even support size, simply because \(\bar{\mathcal {A}_n}\) does not contain matrices of odd rank when n is odd. Remark 4 above addresses a related issue. Figure 2 nevertheless shows that for order \(n=7\) matrices with 7 ESSs of support size 4 can be found by perturbing the matrix \({\mathsf {A}}_{\{1\}}\in \bar{\mathcal {A}_7}\). Furthermore, it is seen in Fig. 2 that for some matrices of order 7, there are 7 ESSs of support size 2, but those matrices do not result from small perturbations of matrices in the set \(\bar{\mathcal {A}_7}\). In Fig. 2 regions of matrices sharing the same pattern are visualized by their shading, a particular support attached to some region always indicating just one member of a whole class of 7 cyclic shifts of that support. The (middle gray) \(7_3\) regions actually overlap, and their intersections, the dark gray triangle shaped regions, correspond to matrices with 14 ESSs of support size 3. The white triangle corresponds to matrices with 1 ESS of support size 7. The \(7_4\) regions are bounded by segments of the three ellipses \((b-c)^2=ab,(c-a)^2=bc\), and \((a-b)^2=ca\). Two sides of the dark gray triangle shaped regions are actually curved, and are segments of the three hyperbolae \(ac+3bc=ab+2c^2,ab+3ac=bc+2a^2\), and \(bc+3ab=ac+2b^2\), the third sides are the straight lines \(a=0,b=0,c=0\). The \(7_2\) regions are bounded by the lines \(a=0,2b=c\), resp. \(b=0,2c=a\), resp. \(c=0,2a=b\). The union of the three lines forming the boundary of the \(1_7\) region satisfies the equation
Figure 2 suggests that for given odd n, matrices in \({\mathcal {C}}^n\) with many ESSs of even support size k could be found by perturbing a negative-semidefinite cyclically symmetric matrix \({\mathsf {A}}\) of rank \(k-2\) in such a way that points \(\mathbf {p}\in \hbox {conv }\{\mathbf {p}_1,\mathbf {p}_2\}\), with \(\mathbf {p}_1,\mathbf {p}_2\in {{\mathcal {E}}}({\mathsf {A}}), |I(\mathbf {p}_1)|=|I(\mathbf {p}_2)|=|I(\mathbf {p}_1)\cap I(\mathbf {p}_2)|+1=k-1\), get perturbed into quasistrict ESSs of the perturbed matrix. (This should also be considered in the case of even n and k of any parity, as suggested by Fig. 1, where we can enter the \(6_3\) region by perturbing \({\mathsf {A}}_{\{3\}}\).) Since there is no straightforward way to adapt our construction method to that setting, we leave this approach to future research. We do however have results for \(k=2\), which are also given in Tables 2, 3 and 4.
3.1 Support Size 2
Fix \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) and consider the graph G with vertex set \(V(G)=[{1}\! : \!{n}]\) and an edge \(\{i,j\}\in E(G)\) iff \(\{i,j\}=I(\mathbf {p})\) for some \(\mathbf {p}\in \mathrm{ESS}({\mathsf {A}})\). Then we know from [19, Thm. 2 and Corollaries] that G is triangle-free. For a given triangle-free graph G let now \({\mathsf {A}}(G)=(a_{ij})\in {{{\mathcal {S}}}^n}\) be defined by \(a_{ii}=0\) for \(i\in [{1}\! : \!{n}]\), \(a_{ij}=1\Leftrightarrow \{i,j\}\in E(G)\), \(1\le i<j\le n\), and \(a_{ij}=-1\) otherwise. Then we know from [9, Thm. 1], that pattern\(({\mathsf {A}}(G))=E(G)\). So, as noted in [9, Thm. 5 and Corollaries], the maximum number of ESSs of support size 2 a matrix \({\mathsf {A}}\in {{{\mathcal {S}}}^n}\) can have is \(\left\lceil \frac{n^2-1}{4}\right\rceil \), corresponding to a complete bipartite graph with maximally balanced partition. For even n, the matrix \({\mathsf {A}}(G)\), obtained from the complete bipartite graph G with \([{1}\! : \!{n}]\) partitioned into odd and even numbers, turns out to belong to \({\mathcal {C}}^n\), therefore \(\frac{n^2}{4}=\max \limits _{{\mathsf {A}}\in {\mathcal {C}}^n}|\{\mathbf {p}\in \mathrm{ESS}({\mathsf {A}}):|I(\mathbf {p})|=2\}|\) is attained.
Not so for n odd. Note that \({\mathsf {A}}(G)\in {\mathcal {C}}^n\) means that G is a circulant graph on \(V(G)=[{1}\! : \!{n}]\), being determined by a subset \(S\subseteq [{1}\! : \!{n-1}]\) such that \(\{i,j\}\in E(G)\Leftrightarrow i-j\equiv s\mod n\) for some \(s\in S\). In order that G be triangle-free, S has to be a symmetric sum-free subset of \([{1}\! : \!{n-1}]\), i. e., \(s\in S\Rightarrow n-s\in S\), and \(s_1+s_2\equiv s\mod n\) has no solution with \(s_1,s_2,s\in S\). For small odd n, the maximal sizes \(m_n\) of such symmetric sum-free subsets of \([{1}\! : \!{n-1}]\) are easily found,
holds for that range. Note that we are interested in \(\frac{m_n}{2}\), because \(|E(G)|=\frac{|S|}{2}n\). The inequality \(\frac{n-3}{3}\le m_n\) holds for all odd n, as is seen by observing that
is a symmetric sum-free subset of \([{1}\! : \!{n-1}]\) of at least \(\frac{n-3}{3}\) elements. The inequality \(\frac{m_n}{2}\le \frac{n}{5}\), on the other hand, is not surprising in the light of [10, Prop. 1.3, Thm. 1.5], from which we can deduce that the maximal size possible for a sum-free subset of \([{1}\! : \!{n-1}]\) (without the requirement of being symmetric) is upper bounded by \(\frac{n}{5}\). Interestingly, this upper bound is attained infinitely often also by symmetric sum-free sets, i. e., the equality \(\frac{m_n}{2}=\frac{n}{5}\) holds for all \(n\in \{10k-5:k\ge 1\}\). This is seen by observing that \(\{1,4,6,9,11,14,\ldots ,10k-6\}\) (with differences of consecutive elements alternating between 3 and 2) is a symmetric sum-free subset of \([{1}\! : \!{10k-6}]\) of size \(4k-2\).
So we conclude, that \(M_n:=\max \limits _{{\mathsf {A}}\in {\mathcal {C}}^n}|\{\mathbf {p}\in \mathrm{ESS}({\mathsf {A}}):|I(\mathbf {p})|=2\}|\) satisfies
\(M_n\ge \frac{n(n-3)}{6}\) for any odd n, \(M_n=\frac{n^2}{5}\) for infinitely many odd n, and \(M_n>\frac{n^2}{5}\) for no odd n,
in particular, the maximum \(\frac{n^2-1}{4}\) for matrices constructed from bipartite graphs is never attained by \(M_n\) for odd \(n\ge 3\).
Acknowledgements
Open access funding provided by University of Vienna. We thank Reinhard Ullrich for helpful discussions.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Assume that \({\bar{{\mathsf {A}}}}_1\) is not invertible. Then there is a vector \(\mathbf {z}\) and a scalar u such that \({\bar{{\mathsf {A}}}}_1\begin{pmatrix} \mathbf {z}\\ u \end{pmatrix}=\begin{pmatrix} {\mathsf {A}}_1\mathbf {z}+ u\mathbf {e}\\ \mathbf {e}^\top \mathbf {z}\end{pmatrix}=\mathbf {o}\), while \(\begin{pmatrix} \mathbf {z}\\ u \end{pmatrix}\ne \mathbf {o}\). This implies \(\mathbf {z}\ne \mathbf {o}\), \(\mathbf {e}^\top \mathbf {z}=0\), and \(\mathbf {z}^\top {\mathsf {A}}_1\mathbf {z}=0\). Denote \(m:=|I|\) and \({\bar{\mathbf {z}}}:=\mathbf {z}_{[1:m-1]}\) and observe that \({\bar{\mathbf {z}}}\ne \mathbf {o}\). Furthermore, denoting columns and elements of \({\mathsf {A}}_1\) by \(\mathbf {a}_i\) resp. \(a_{ij}\), and using \({\mathcal {B}}({\mathsf {A}}_1)\succ {\mathsf {O}}\), we derive \(0<{\bar{\mathbf {z}}}^\top {\mathcal {B}}({\mathsf {A}}_1){\bar{\mathbf {z}}}=\mathbf {z}^\top (\mathbf {e}\,\mathbf {a}_m^\top +\mathbf {a}_m\,\mathbf {e}^\top -{\mathsf {A}}_1-a_{mm}\mathbf {e}\,\mathbf {e}^\top )\mathbf {z}=-\mathbf {z}^\top {\mathsf {A}}_1\mathbf {z}=0\), a contradiction.
Just note that \({\mathcal {B}}({\mathsf {A}}_{I\times I})\succ {\mathsf {O}}\) is equivalent to \(\mathbf {x}^\top {\mathsf {A}}_{I\times I}\mathbf {x}<0\) for all \(\mathbf {x}\in \mathbf {e}^\bot \setminus \{\mathbf {o}\}\), and then, because of \({\mathsf {A}}_{I\times I}\mathbf {p}_I=\mathbf {o}\), we have \((\lambda \mathbf {p}_I+\mathbf {x})^\top {\mathsf {A}}_{I\times I}(\lambda \mathbf {p}_I+\mathbf {x})\le 0\), for \(\lambda \in {\mathbb {R}}\) and \(\mathbf {x}\perp \mathbf {e}\), which means \({\mathsf {A}}_{I\times I}\preceq {\mathsf {O}}\). If for some \(I'\subset I\) with \(|I'|=|I|-1\) the matrix \({\mathsf {A}}_{I'\times I'}\) had not full rank, there would be \(\mathbf {q}\in \Delta ^{|I|}\) satisfying \(I(\mathbf {q})=I'\), such that \({\mathsf {A}}_{I\times I}\mathbf {q}=\mathbf {o}\). Thus the dimension of the kernel of \({\mathsf {A}}_{I\times I}\) would be at least 2, and the rank of \({\mathsf {A}}_{I\times I}\) would have to be less than \(|I|-1\), which is a contradiction.
The only permutation \(\tau \) that can be introduced via a permutation matrix \({\bar{{\mathsf {P}}}}\) as above is the identity, so the set of candidate matrices will be \(\bar{\mathcal {A}_6}={\mathcal {A}}_6=\{{\mathsf {A}}_L:\emptyset \ne L\subseteq [{1}\! : \!{3}]\}\).
