# The bifurcation lemma for strong properties in the inverse eigenvalue
problem of a graph

Shaun M. Fallat Department of Mathematics and Statistics, University of
Regina, Regina, SK, S4S 0A2, Canada (shaun.fallat@uregina.ca). H. Tracy Hall
Hall Labs, LLC<EMAIL_ADDRESS>Jephian C.-H. Lin Department of Applied
Mathematics, National Sun Yat-sen University, Kaohsiung 80424, Taiwan
<EMAIL_ADDRESS>Bryan L. Shader Department of Mathematics, University
of Wyoming, Laramie, WY 82071, USA<EMAIL_ADDRESS>
###### Abstract

The inverse eigenvalue problem of a graph studies the real symmetric matrices
whose off-diagonal pattern is prescribed by the adjacencies of the graph. The
strong spectral property (SSP) is an important tool for this problem. This
note establishes the bifurcation lemma, which states that if a spectrum can be
realized by a matrix with the SSP for some graph, then all the nearby spectra
can also be realized by matrices with the SSP for the same graph. The idea of
the bifurcation lemma also works for other strong properties and for not
necessarily symmetric matrices. This is used to develop new techniques for
verifying a spectrally arbitrary pattern or inertially arbitrary pattern. The
bifurcation lemma provides a unified theoretical foundation for several known
results, such as the stable northeast lemma and the nilpotent-centralizer
method.

Keywords: Inverse eigenvalue problem, strong properties, implicit function
theorem, inverse function theorem, bifurcation lemma, graphs.

AMS subject classifications: 05C50, 15A18, 15B35, 15B57, 58C15.

##  1 Introduction

Let $G$ be a graph on $n$ vertices. Define $\mathcal{S}(G)$ as the set of all
$n\times n$ real symmetric matrices whose $(i,j)$-entry, for $i\neq j$, is
nonzero if and only if $\\{i,j\\}$ is an edge. Note that the diagonal entries
can be any real number. The inverse eigenvalue problem of a graph $G$
(IEP-$G$) asks what spectra can be realized over all matrices in
$\mathcal{S}(G)$?

The IEP-$G$ has become a central study for researchers interested in general
aspects of the spectra of graphs or certain branches of combinatorial matrix
theory. From the early beginnings of Parter and Weiner (see [16, 18]),
studying the behavior of eigenvalue multiplicities in trees and particular
induced subgraphs, with mild extensions to include cycles, this subject has
continued to expand, although a complete resolution seems rather distant.
However, over the past few years, motivated in part by seminal work of Colin
de Veredière [8] incorporating a particular aspect of genericity (called the
strong Arnol’d property), other similar properties have been developed with
significant impact on recent advances to the IEP-$G$. These matrix properties,
known as the strong spectral and strong multiplicity properties (see [3, 4]),
are defined below and have been used with considerable success on specific
aspects of the IEP-$G$. These “strong” properties allow one to preserve some
spectral information under certain matrix perturbations, which ability has
allowed new sorts of analysis on the IEP-$G$ by considering forbidden minor
characterizations and some extremal problems involving related parameters
including: the minimum rank, maximum multiplicity, and the minimum number of
distinct eigenvalues of a graph. See, e.g., [3, 4] and the references therein.

A natural question is the following. Let $G$ be a graph on $n$ vertices.
Suppose $A\in\mathcal{S}(G)$ has $\operatorname{spec}(A)=\Lambda$. For a
sequence $\Lambda^{\prime}$ of $n$ real numbers such that
$\|\Lambda-\Lambda^{\prime}\|$ (treated as vectors) is small enough, is there
a matrix $A^{\prime}\in\mathcal{S}(G)$ such that
$\operatorname{spec}(A^{\prime})=\Lambda^{\prime}$?

The purpose of this note is to provide a positive answer to the above question
by proving the so-called bifurcation lemma, utilizing the inverse function
theorem. The organization of the paper is as follows: In Section 2, we develop
a version of the inverse function theorem for the purpose of proving the
bifurcation lemma. The statement of the bifurcation lemma and its proof will
be given in Section 3, which leads to an immediate consequence known in [1] as
the stable northeast lemma. Applications of the bifurcation lemma on the
number of minimum distinct eigenvalues and on the ordered multiplicity lists
of a cycle will be given in Section 4. Finally, a version of the bifurcation
lemma for non-symmetric matrices is given in Section 5 and, as a consequence,
a more flexible version of the nilpotent-centralizer method [12] is presented
and new methods for finding spectrally arbitrary and inertially arbitrary
patterns are developed.

In the remainder of this section, we set up some basic notation of matrices
and review the definition and some propositions of the strong properties. Let
$A$ be a symmetric matrix and
$\operatorname{spec}(A)=\\{\lambda_{1}^{(m_{1})},\ldots,\lambda_{q}^{(m_{q})}\\}$
with $\lambda_{1}<\cdots<\lambda_{q}$. The _ordered multiplicity list_ of $A$
is the sequence ${\bf m}(A)=(m_{1},\ldots,m_{q})$. The number of distinct
eigenvalues of $A$ is denoted as $q(A)=q$. Let $n_{+}(A)$, $n_{-}(A)$, and
$n_{0}(A)$ be the number of positive, negative, and zero eigenvalues of $A$,
respectively. Then the _partial inertia_ of $A$ is the pair
$\operatorname{pin}(A)=(n_{+}(A),n_{-}(A))$. When $A$ is an $n\times n$
matrix, the partial inertia is enough to determine the inertia
$(n_{+}(A),n_{-}(A),n_{0}(A))$ since $n_{+}(A)+n_{-}(A)+n_{0}(A)=n$. The
matrix norm used in this paper is the Frobenius norm
$\|A\|^{2}=\operatorname{tr}(A^{\top}\\!A)$.

###  1.1 Strong properties

Let $\operatorname{Mat}_{n}(\mathbb{R})$ be the family of $n\times n$ real
matrices. Let $\mathcal{B}_{n}$ be the set of matrices in
$\operatorname{Mat}_{n}(\mathbb{R})$ with $\|A\|<0.5$, noting that for all
$L\in\mathcal{B}_{n}$ the matrix $I+L$ is invertible. Let
$\operatorname{Sym}_{n}(\mathbb{R})$ and $\operatorname{Skew}_{n}(\mathbb{R})$
be the families of real symmetric and real skew-symmetric matrices of order
$n$, respectively. Throughout the paper, we will view them as vector spaces
equipped with the inner product

$\left\langle A,B\right\rangle=\operatorname{tr}(B^{\top}\\!A).$

Finally, for a given graph $G$, let $\mathcal{S}^{\rm cl}(G)$ be the
topological closure of $\mathcal{S}(G)$. That is,

$\mathcal{S}^{\rm
cl}(G)=\\{A=\begin{bmatrix}a_{ij}\end{bmatrix}\in\operatorname{Sym}_{n}(\mathbb{R}):a_{ij}=0\text{
if }ij\in E(\overline{G})\\},$

which is a subspace of $\operatorname{Sym}_{n}(\mathbb{R})$.

Let $A\in\operatorname{Sym}_{n}(\mathbb{R})$ be a matrix and $q$ the number of
distinct eigenvalues of $A$. Then $A$ has the _strong spectral property_ (or
the SSP) if $X=O$ is the only symmetric matrix satisfying

$A\circ X=O,\quad I\circ X=O,\quad\text{and }[A,X]=O.$

Here $[A,X]=AX-XA$. The matrix $A$ has the _strong multiplicity property_ (or
the SMP) if $X=O$ is the only symmetric matrix satisfying

$A\circ X=O,\quad I\circ X=O,\quad[A,X]=O,$ $\text{and
}\operatorname{tr}(A^{k}X)=0\text{ for }k=0,\ldots,q-1.$

Finally, $A$ has the _strong Arnol’d property_ (or the SAP) if $X=O$ is the
only symmetric matrix satisfying

$A\circ X=O,\quad I\circ X=O,\quad\text{and }AX=O.$

The SAP was used in [7] (English translation [8]) to define the Colin de
Verdière parameter $\mu(G)$. The SSP and the SMP were introduced in [4] for
the study of the IEP-$G$.

Let $U$ and $W$ be vector subspaces of $\operatorname{Sym}_{n}(\mathbb{R})$.
Then $U\cap W=\\{{\bf 0}\\}$ if and only if
$U^{\perp}+W^{\perp}=\operatorname{Sym}_{n}(\mathbb{R})$. We will use this
fact to produce an equivalent condition of the strong properties mentioned
above.

Suppose $A$ is a matrix in $\mathcal{S}(G)$ with $q$ distinct eigenvalues. We
may calculate the orthogonal complements for the following subspaces. Let

$U=\\{X\in\operatorname{Sym}_{n}(\mathbb{R}):A\circ X=O,\ I\circ X=O\\}.$

Then $U^{\perp}=\mathcal{S}^{\rm cl}(G)$. Additionally, for

$\displaystyle W_{S}$
$\displaystyle=\\{X\in\operatorname{Sym}_{n}(\mathbb{R}):[A,X]=O\\},$
$\displaystyle W_{M}$
$\displaystyle=\\{X\in\operatorname{Sym}_{n}(\mathbb{R}):[A,X]=O\text{ and
}\operatorname{tr}(A^{k}X)=0\text{ for }k=0,\ldots,q-1\\},$ $\displaystyle
W_{A}$ $\displaystyle=\\{X\in\operatorname{Sym}_{n}(\mathbb{R}):AX=O\\},$

we have

$\displaystyle W_{S}^{\perp}$
$\displaystyle=\\{K^{\top}\\!A+AK:K\in\operatorname{Skew}_{n}(\mathbb{R})\\},$
$\displaystyle W_{M}^{\perp}$
$\displaystyle=\\{K^{\top}\\!A+AK:K\in\operatorname{Skew}_{n}(\mathbb{R})\\}+\operatorname{span}\\{A^{k}:k=0,\ldots,q-1\\},$
$\displaystyle W_{A}^{\perp}$
$\displaystyle=\\{L^{\top}\\!A+AL:L\in\operatorname{Mat}_{n}(\mathbb{R})\\}.$

The calculation of these orthogonal complements can be found in, e.g., [4,
Theorem 27]. (In fact, these are the tangent and normal spaces of certain
manifolds, but in this note we demonstrate the result using elementary
language.) Thus, we have the following proposition.

######  Proposition 1.1.

Let $G$ be a graph and $A\in\mathcal{S}(G)$ a matrix with $q$ distinct
eigenvalues. Then

  1. (a)

The matrix $A$ has the SSP if and only if

$\mathcal{S}^{\rm
cl}(G)+\\{K^{\top}\\!A+AK:K\in\operatorname{Skew}_{n}(\mathbb{R})\\}=\operatorname{Sym}_{n}(\mathbb{R}).$

  2. (b)

The matrix $A$ has the SMP if and only if

$\mathcal{S}^{\rm
cl}(G)+\\{K^{\top}\\!A+AK:K\in\operatorname{Skew}_{n}(\mathbb{R})\\}+\operatorname{span}\\{A^{k}:k=0,\ldots,q-1\\}=\operatorname{Sym}_{n}(\mathbb{R}).$

  3. (c)

The matrix $A$ has the SAP if and only if

$\mathcal{S}^{\rm
cl}(G)+\\{L^{\top}\\!A+AL:L\in\operatorname{Mat}_{n}(\mathbb{R})\\}=\operatorname{Sym}_{n}(\mathbb{R}).$

##  2 Inverse function theorem

In this section, we revisit the classical inverse function theorem and
construct a version that is suitable for our purpose.

Let $F({\bf u})$ be a function from an open subset of a vector space $U$ to
another vector space $W$. Recall that a function is _smooth_ if it is
infinitely differentiable throughout its domain. Let ${\bf u}_{0}$ be a point
in the domain $F({\bf u}_{0})={\bf w}_{0}$. Note that the tangent space around
${\bf u}_{0}$ in $U$ and the tangent space around ${\bf w}_{0}$ in $W$ are $U$
and $W$, respectively. The _derivative_ of $F$ at ${\bf u}_{0}$, denoted as
$\dot{F}\Big{|}_{{\bf u}={\bf u}_{0}}$, is a linear operator

${\bf d}\mapsto\lim_{t\rightarrow 0}\frac{F({\bf u}_{0}+t{\bf d})-F({\bf
u}_{0})}{t}$

from the tangent space of $U$ to the tangent space of $W$ that takes a
direction ${\bf d}$ and outputs the directional derivative. When both $U$ and
$W$ are finite-dimensional, it is easy to check if $\dot{F}\Big{|}_{{\bf
u}={\bf u}_{0}}$ is injective, surjective, or invertible since it is linear.
In particular, when $\dim U=\dim W<\infty$, we know one of the three
properties is enough to imply the other two.

######  Example 2.1.

Let $U=\operatorname{Skew}_{n}(\mathbb{R})$ and
$W=\operatorname{Mat}_{n}(\mathbb{R})$. Then the function $F(K)=e^{K}$ from an
open subset of $U$ to $W$ has

$\dot{F}\Big{|}_{K=O}=K,$

since

$\displaystyle\lim_{t\rightarrow 0}\frac{e^{O+Kt}-e^{O}}{t}$
$\displaystyle=\lim_{t\rightarrow
0}\frac{1}{t}\left[\frac{(Kt)^{0}}{0!}+\frac{(Kt)^{1}}{1!}+\frac{(Kt)^{2}}{2!}+\frac{(Kt)^{3}}{3!}+\cdots-I\right]$
$\displaystyle=\lim_{t\rightarrow
0}\left[\frac{K^{1}}{1!}+\frac{K^{2}t^{1}}{2!}+\frac{K^{3}t^{2}}{3!}+\cdots\right]=K.$

######  Example 2.2.

Let $U=\mathcal{B}_{n}$ and $W=\operatorname{Mat}_{n}(\mathbb{R})$. Let
$F:U\rightarrow W$ be a function defined by $F(L)=(I+L)^{-1}$. Then

$\dot{F}\Big{|}_{L=O}=-L$

since

$\displaystyle\lim_{t\rightarrow 0}\frac{(I+Lt)^{-1}-I}{t}$
$\displaystyle=\lim_{t\rightarrow
0}\frac{1}{t}\left[I-Lt+(Lt)^{2}-(Lt)^{3}+\cdots-I\right]$
$\displaystyle=\lim_{t\rightarrow
0}\left[-L+(Lt)^{1}-(Lt)^{2}+\cdots\right]=-L.$

Theorem 2.3 is one of the common statements of the inverse function theorem,
which can be found in, e.g., [11, Theorem 1.12].

######  Theorem 2.3 (Inverse function theorem).

Let $U$ and $W$ be finite-dimensional vector spaces over $\mathbb{R}$ with
$\dim U=\dim W$. Let $F$ be a smooth function from an open subset of $U$ to
$W$ with $F({\bf u}_{0})={\bf w}_{0}$. If $\dot{F}\Big{|}_{{\bf u}={\bf
u}_{0}}$ is invertible, then there are an open subset $W^{\prime}\subseteq W$
containing ${\bf w}_{0}$ and a smooth function $T:W^{\prime}\rightarrow U$
such that $T({\bf w}_{0})={\bf u}_{0}$ and $F\circ T$ is the identity map on
$W^{\prime}$.

The condition $\dim U=\dim W$ is necessary so that the derivative can possibly
be invertible. However, the inverse function theorem still works when $U$ and
$W$ have different dimensions and the derivative is surjective. Here we state
another version of the inverse function theorem and include the proof for
completeness.

######  Theorem 2.4.

Let $U$ and $W$ be finite-dimensional vector spaces over $\mathbb{R}$. Let $F$
be a smooth function from an open subset of $U$ to $W$ with $F({\bf
u}_{0})={\bf w}_{0}$. If $\dot{F}\Big{|}_{{\bf u}={\bf u}_{0}}$ is surjective,
then there are an open subset $W^{\prime}\subseteq W$ containing ${\bf w}_{0}$
and a smooth function $T:W^{\prime}\rightarrow U$ such that $T({\bf
w}_{0})={\bf u}_{0}$ and $F\circ T$ is the identity map on $W^{\prime}$.

###### Proof.

Let $\dot{F}=\dot{F}\Big{|}_{{\bf u}={\bf u}_{0}}$. Let $U^{\prime}$ be the
orthogonal complement of the kernel $\ker(\dot{F})$. Since $\dot{F}$ is
surjective, the restriction of $\dot{F}$ on $U^{\prime}$ is an invertible
operator. Let ${\bf u}_{0}+U^{\prime}$ be the affine subspace

$\\{{\bf u}_{0}+{\bf u}:{\bf u}\in U^{\prime}\\}.$

Let $\tilde{F}$ be the restriction of $F$ on the intersection of $U^{\prime}$
and the domain of $F$. Thus, $\tilde{F}$ is a function whose domain and
codomain are vector spaces of the same dimension, and
$\dot{\tilde{F}}\Big{|}_{{\bf u}={\bf u}_{0}}$ equals the restriction of
$\dot{F}$ on $U^{\prime}$, which is invertible. By Theorem 2.3, there is an
open subset $W^{\prime}\subseteq W$ containing ${\bf w}_{0}$ and a smooth
function $T:W^{\prime}\rightarrow{\bf u}_{0}+U^{\prime}\subseteq U$ such that
$T({\bf w}_{0})={\bf u}_{0}$ and $\tilde{F}\circ T$ is the identity map on
$W^{\prime}$. Since $\tilde{F}$ is a restriction of $F$, naturally $F\circ T$
is also the identity map on $W^{\prime}$. ∎

##  3 Bifurcation lemma

We establish the so-called bifurcation lemma in this section. Before this
verification, we observe that Proposition 3.1 demonstrates that each strong
property is equivalent to the derivative of a certain perturbation function
being surjective.

######  Proposition 3.1.

Let $G$ be a graph on $n$ vertices and $A\in\mathcal{S}(G)$ with $q$ distinct
eigenvalues.

  1. (a)

For the function $F:\mathcal{S}^{\rm
cl}(G)\times\operatorname{Skew}_{n}(\mathbb{R})\rightarrow\operatorname{Sym}_{n}(\mathbb{R})$
defined by

$F(B,K)=e^{-K}(A+B)e^{K},$

the derivative $\dot{F}\Big{|}_{\begin{subarray}{c}B=O\\\ K=O\end{subarray}}$
is surjective if and only if $A$ has the SSP.

  2. (b)

For the function $F:\mathcal{S}^{\rm
cl}(G)\times\operatorname{Skew}_{n}(\mathbb{R})\times\mathbb{R}^{q}\rightarrow\operatorname{Sym}_{n}(\mathbb{R})$
defined by

$F(B,K,{\bf c})=e^{-K}p(A+B)e^{K},$ $\text{where }{\bf
c}=(c_{0},\ldots,c_{q-1})\text{ and }p(x)=x+\sum_{k=0}^{q-1}c_{k}x^{k},$

the derivative $\dot{F}\Big{|}_{\begin{subarray}{c}B=O\\\ K=O\\\ {\bf c}={\bf
0}\\\ \end{subarray}}$ is surjective if and only if $A$ has the SMP.

  3. (c)

For the function $F:\mathcal{S}^{\rm
cl}(G)\times\mathcal{B}_{n}\rightarrow\operatorname{Sym}_{n}(\mathbb{R})$
defined by

$F(B,L)=(I+L)^{\top}(A+B)(I+L),$

the derivative $\dot{F}\Big{|}_{\begin{subarray}{c}B=O\\\ L=O\\\
\end{subarray}}$ is surjective if and only if $A$ has the SAP.

###### Proof.

We show that the partial derivatives of each function correspond to the spaces
related to each of the strong properties.

Case (a). Let $\dot{F}=\dot{F}\Big{|}_{\begin{subarray}{c}B=O\\\
K=O\end{subarray}}$. Let $F_{B}=\frac{\partial F}{\partial
B}\Big{|}_{\begin{subarray}{c}B=O\\\ K=O\end{subarray}}$ and
$F_{K}=\frac{\partial F}{\partial K}\Big{|}_{\begin{subarray}{c}B=O\\\
K=O\end{subarray}}$ be the corresponding partial derivatives. Thus,

$\operatorname{range}(\dot{F})=\operatorname{range}(F_{B})+\operatorname{range}(F_{K})$

and $\dot{F}$ is surjective if and only if
$\operatorname{range}(F_{B})+\operatorname{range}(F_{K})=\operatorname{Sym}_{n}(\mathbb{R})$.
Observe that $\operatorname{range}(F_{B})=\mathcal{S}^{\rm cl}(G)$ and

$\operatorname{range}(F_{K})=\\{K^{\top}\\!A+AK:K\in\operatorname{Skew}_{n}(\mathbb{R})\\}.$

Thus,
$\operatorname{range}(F_{B})+\operatorname{range}(F_{K})=\operatorname{Sym}_{n}(\mathbb{R})$
if and only if $A$ has the SSP by Proposition 1.1.

Case (b). Similarly, let $\dot{F}=\dot{F}\Big{|}_{\begin{subarray}{c}B=O\\\
K=O\\\ {\bf c}={\bf 0}\end{subarray}}$ and let $F_{B}$, $F_{K}$, and $F_{{\bf
c}}$ be the corresponding partial derivatives at $B=O$, $K=O$, and ${\bf
c}={\bf 0}$. By direct computation, we have
$\operatorname{range}(F_{B})=\mathcal{S}^{\rm cl}(G)$,

$\operatorname{range}(F_{K})=\\{K^{\top}\\!A+AK:K\in\operatorname{Skew}_{n}(\mathbb{R})\\},$

and

$\operatorname{range}(K_{{\bf
c}})=\operatorname{span}\\{A^{k}:k=0,\ldots,q-1\\}.$

By Proposition 1.1, $\dot{F}$ is surjective if and only if $A$ has the SMP.

Case (c). Following the same workflow and with $F_{B}$ and $F_{L}$ being the
corresponding partial derivatives at $B=O$ and $L=O$, we arrive at the
conclusion by observing $\operatorname{range}(F_{B})=\mathcal{S}^{\rm cl}(G)$
and

$\operatorname{range}(F_{L})=\\{L^{\top}\\!A+AL:L\in\operatorname{Mat}_{n}(\mathbb{R})\\}.$

∎

Note that the functions in Proposition 3.1 are all compositions of
perturbations. The function $B\mapsto A+B$ is a perturbation of $A$ that does
not change the pattern (when $B$ is small enough). The function $K\mapsto
e^{-K}Me^{K}$ does not change the spectrum of $M$, the function $(K,{\bf
c})\mapsto e^{-K}p(M)e^{K}$ does not change the ordered multiplicity list, and
the function $L\mapsto(I+L)^{\top}M(I+L)$ preserves the inertia (and rank) of
$L$.

######  Theorem 3.2 (Bifurcation lemma).

Let $G$ be a graph and $A\in\mathcal{S}(G)$. If $A$ has the

  1. (a)

SSP,

  2. (b)

SMP, or

  3. (c)

SAP,

respectively, then there is $\epsilon>0$ such that for any $M$ with
$\|M-A\|<\epsilon$, a matrix $A^{\prime}\in\mathcal{S}(G)$ exists such that

  1. (a)

$\operatorname{spec}(A^{\prime})=\operatorname{spec}(M)$ and $A^{\prime}$ has
the SSP,

  2. (b)

${\bf m}(A^{\prime})={\bf m}(M)$ and $A^{\prime}$ has the SMP, or

  3. (c)

$\operatorname{pin}(A^{\prime})=\operatorname{pin}(M)$ and $A^{\prime}$ has
the SAP,

respectively.

###### Proof.

We prove the case for the SSP only, since the other cases are similar. Let $F$
be the function in Proposition 3.1(a) and $\dot{F}$ its derivative at zero.
Since $A$ has the SSP, $\dot{F}$ is surjective. By the inverse function
theorem (Theorem 2.4), there are an open subset
$W^{\prime}\subseteq\operatorname{Sym}_{n}(\mathbb{R})$ containing $A$ and a
smooth function $T$ such that $T(A)=(O,O)$ and $F\circ T$ is the identity map
on $W^{\prime}$. Thus, for any $M\in W^{\prime}$, we may let
$(B^{\prime},K^{\prime})=T(M)$. Then

$F(B^{\prime},K^{\prime})=e^{-K^{\prime}}(A+B^{\prime})e^{K^{\prime}}=F(T(M))=M,$

which implies $A+B^{\prime}$ and $M$ have the same spectrum since
$e^{K^{\prime}}$ is an orthogonal matrix and $e^{-K^{\prime}}$ is its inverse.
Therefore, when $\|M-A\|$ is sufficiently small, $A^{\prime}=A+B^{\prime}$ is
a matrix in $\mathcal{S}(G)$ and
$\operatorname{spec}(A^{\prime})=\operatorname{spec}(M)$. Moreover, the
derivative of $F$ at $B=B^{\prime}$ and $K=K^{\prime}$ remains surjective when
the perturbation is small enough, so $A^{\prime}$ has the SSP as well. The
other cases can be obtained by choosing an appropriate function in Proposition
3.1. ∎

Let $A$ be a real symmetric matrix and suppose $QDQ^{\top}$ is its
diagonalization with $Q$ an orthogonal matrix. Since the Frobenius norm is
unitarily invariant,

$\|QD^{\prime}Q^{\top}-QDQ^{\top}\|^{2}=\|D^{\prime}-D\|^{2}.$

Thus, $M$ can be chosen as $QD^{\prime}Q$ for any $D^{\prime}$ with
$\|D^{\prime}-D\|<\epsilon$. By applying the bifurcation lemma to a matrix $M$
with the nearby spectrum, ordered multiplicity list, or inertia, the following
corollaries are immediate.

######  Corollary 3.3.

Let $G$ be a graph and $A\in\mathcal{S}(G)$ a matrix with the SSP and
$\operatorname{spec}(A)=\\{\lambda_{1},\ldots,\lambda_{n}\\}$. Then there is
$\epsilon>0$ such that for any $\mu_{1},\ldots,\mu_{n}$ with
$|\mu_{i}-\lambda_{i}|<\epsilon$ for all $i=1,\ldots,n$, a matrix
$A^{\prime}\in\mathcal{S}(G)$ exists with the SSP and
$\operatorname{spec}(A^{\prime})=\\{\mu_{1},\ldots,\mu_{n}\\}$.

######  Corollary 3.4.

Let $G$ be a graph and $A\in\mathcal{S}(G)$ a matrix with the SMP and ${\bf
m}(A)={\bf m}$. Then for any refinement ${\bf m}^{\prime}$ of ${\bf m}$, there
is a matrix $A^{\prime}\in\mathcal{S}(G)$ with the SMP and ${\bf
m}(A^{\prime})={\bf m}^{\prime}$.

Corollary 3.5 is known as the stable northeast lemma for graphs, which was
developed in [1, Corollary 2]. It is also an immediate consequence of the
bifurcation lemma.

######  Corollary 3.5.

Let $G$ be a graph on $n$ vertices and $A\in\mathcal{S}(G)$ a matrix with the
SAP such that $\operatorname{pin}(A)=(a,b)$ with $a+b<n$. Then each of the
partial inertia $(a+1,b)$ and $(a,b+1)$ can be achieved by a matrix
$A^{\prime}\in\mathcal{S}(G)$ with the SAP.

Note that Corollary 3.5 remains true if the assumption of SAP is dropped, but
the resulting matrix $A^{\prime}$ is not guaranteed to also have the SAP. See
[5, Lemma 1.1].

######  Corollary 3.6.

Let $G$ be a graph on $n$ vertices and $A\in\mathcal{S}(G)$ a matrix with the
SAP and $\operatorname{rank}(A)=r$. Then for any $r^{\prime}$ with $r\leq
r^{\prime}\leq n$ there is a matrix $A^{\prime}\in\mathcal{S}(G)$ with the SAP
and $\operatorname{rank}(A^{\prime})=r^{\prime}$.

Similar to the comments after Corollary 3.5, the SAP in Corollary 3.6 can be
removed. That is, if $A\in\mathcal{S}(G)$ has rank $r$, then for any
$r^{\prime}$ with $r\leq r^{\prime}\leq n$ there is a matrix $A^{\prime}$ with
$\operatorname{rank}(A^{\prime})=r^{\prime}$. This is well-known by the
following argument: Pick an invertible matrix $B\in\mathcal{S}(G)$; then since
$B$ can be obtained from $A$ by a sequence of rank-$1$ perturbations without
leaving $\mathcal{S}(G)$, the ranks of matrices on the way from $A$ to $B$
include at least all the integers between $r$ to $n$. The matrices resulting
from this process are not, however, guaranteed to have the SAP.

##  4 Applications

In this section we provide several consequences of the bifurcation lemma.

###  4.1 Minimum number of distinct eigenvalues

Recall that $q(A)$ is the number of distinct eigenvalues of $A$. With the
bifurcation lemma, each eigenvalue of high multiplicity can be divided into a
pair of eigenvalues each with smaller multiplicity. Therefore, one may
increase the number of distinct eigenvalues by one without changing the
pattern of the matrix.

######  Theorem 4.1.

Let $G$ be a graph on $n$ vertices and $A\in\mathcal{S}(G)$ a matrix with the
SSP or the SMP, respectively. Then for any $q^{\prime}$ with $q(A)\leq
q^{\prime}\leq n$, there is a matrix $A^{\prime}\in\mathcal{S}(G)$ with the
SSP or the SMP, respectively, such that $q(A^{\prime})=q^{\prime}$.

It remains an open question whether the assumption of the SSP or the SMP in
Theorem 4.1 can be dropped.

###  4.2 Cycles

Let $C_{n}$ be the cycle on $n$ vertices. It is known [10] that a set of real
numbers $\lambda_{1}\leq\cdots\leq\lambda_{n}$ is the spectrum of a matrix in
$\mathcal{S}(C_{n})$ if and only if

$\lambda_{1}\leq\lambda_{2}<\lambda_{3}\leq\lambda_{4}<\lambda_{5}<\cdots$

or

$\lambda_{1}<\lambda_{2}\leq\lambda_{3}<\lambda_{4}\leq\lambda_{5}\leq\cdots.$

In other words, the ordered multiplicity lists realizable by matrices in
$\mathcal{S}(G)$ are the refinements of $(2,\ldots,2)$ or $(1,2,\ldots,2,1)$
when $n$ is even and are the refinements of $(2,\ldots,2,1)$ or
$(1,2,\ldots,2)$ when $n$ is odd. We will see that these four maximal ordered
multiplicity lists can be achieved with the SMP, so we have the following
theorem.

######  Theorem 4.2.

Every ordered multiplicity list that can be achieved by a matrix in
$\mathcal{S}(C_{n})$ can be achieved by a matrix in $\mathcal{S}(C_{n})$ with
the SMP.

###### Proof.

The IEP-$G$ has been solved for small graphs up to $5$ vertices; see [3] and
the references therein. So we know $(2,1)$ and $(1,2)$ can be realized by
matrices in $\mathcal{S}(C_{3})$ with the SSP (so the SMP); we also know
$(2,2)$ and $(1,2,1)$ can be realized by matrices in $\mathcal{S}(C_{4})$ with
the SSP (so the SMP).

Let $k\geq 2$. By [4, Theorem 48], for any even cycle $C_{2k}$ there is a
matrix $A\in\mathcal{S}(C_{2k})$ with the SMP and ${\bf m}(A)=(2,\ldots,2)$.
By the decontraction lemma [3, Lemma 6.12], for any odd cycle $C_{2k+1}$ there
are matrices $A_{1}^{\prime}$ and $A_{2}^{\prime}$ in $\mathcal{S}(C_{2k+1})$
with the SMP and ${\bf m}(A_{1}^{\prime})=(1,2,\ldots,2)$ and ${\bf
m}(A_{2}^{\prime})=(2,\ldots,2,1)$. By applying the decontraction lemma again
to $A_{1}^{\prime}$ or $A_{2}^{\prime}$, for any even cycle $C_{2k+2}$, there
is a matrix $A^{\prime\prime}\in\mathcal{S}(C_{2k+2})$ with the SMP and ${\bf
m}(A)=(1,2,\ldots,2,1)$. Combining all these results, we know for $n\geq 5$,
there are matrices with the SMP in $\mathcal{S}(C_{n})$ realizing the ordered
multiplicity lists $(2,\ldots,2)$ or $(1,2,\ldots,2,1)$ if $n$ is even and the
lists $(1,2,\ldots,2)$ and $(2,\ldots,2,1)$ if $n$ is odd.

By the bifurcation lemma (Corollary 3.4), the desired result holds. ∎

It is not yet known, however, whether every realizable spectrum of matrices in
$\mathcal{S}(C_{n})$ can be realized by a matrix in $\mathcal{S}(C_{n})$ with
the SSP.

##  5 Not necessarily symmetric matrices

The idea of bifurcation also applies to matrices that are not necessarily
symmetric and has applications to the study of sign patterns. A _sign pattern_
$P$ is an array whose entries are $+$, $-$, or $0$, and the _qualitative
class_ $\mathcal{Q}(P)$ is the set of all matrices of the same dimensions as
$P$ and the signs of whose entries are prescribed by $P$. We say $P^{\prime}$
is a _superpattern_ of $P$ if $P^{\prime}$ can be obtained from $P$ by
replacing some $0$’s with $+$’s or $-$’s. (Note that $P$ is also a
superpattern of itself.)

The terminology was introduced in [9] that an $n\times n$ sign pattern $P$ is
said to be a _spectrally arbitrary pattern_ if for each monic real-coefficient
polynomial $p(x)$ of degree $n$, there is a matrix $A\in\mathcal{Q}(P)$ whose
characteristic polynomial is $p(x)$, or in other words that every set of $n$
complex numbers that is invariant under conjugation can be realized by a
matrix $A\in\mathcal{Q}(P)$.

Let $P$ be an $n\times n$ sign pattern and $A\in\mathcal{Q}(P)$. The
nilpotent-centralizer method [12] states that if

  * •

$A$ is a nilpotent matrix of index $n$ and

  * •

$X=O$ is the only matrix satisfying $A\circ X=O$ and $[A,X^{\top}]=O$,

then any of its superpatterns is a spectrally arbitrary pattern. In the
following, we will build a more flexible version of this theorem and see that
it follows the same flavor of the bifurcation lemma.

Let $P=\begin{bmatrix}p_{ij}\end{bmatrix}$ be an $n\times n$ sign pattern. We
define $\mathcal{Q}^{\rm v}(P)$ as the set of matrices
$A=\begin{bmatrix}a_{ij}\end{bmatrix}\in\operatorname{Mat}_{n}(\mathbb{R})$
such that $a_{ij}=0$ if $p_{ij}=0$ (and $a_{ij}$ can be any real number if
$p_{ij}$ is $+$ or $-$). The set $\mathcal{Q}^{\rm v}(P)$ is a vector space;
indeed, it is the tangent space of $\mathcal{Q}(P)$ at any point.

######  Definition 5.1.

Let $A$ be an $n\times n$ matrix. Then $A$ has the _non-symmetric strong
spectral property_ (nSSP) if $X=O$ is the only matrix satisfying $A\circ X=O$
and $[A,X^{\top}]=O$.

######  Theorem 5.2 (Bifurcation lemma for non-symmetric matrices).

Let $P$ be an $n\times n$ sign pattern and $A\in\mathcal{Q}(P)$. If $A$ has
the nSSP, then there is $\epsilon>0$ such that for any $M$ with
$\|M-A\|<\epsilon$, a matrix $A^{\prime}\in\mathcal{Q}(P)$ exists such that
$A^{\prime}$ and $M$ are similar and $A^{\prime}$ has the nSSP.

###### Proof.

Given a matrix $A\in\mathcal{Q}(P)$, consider the function $F:\mathcal{Q}^{\rm
v}(P)\times\mathcal{B}_{n}\rightarrow\operatorname{Mat}_{n}(\mathbb{R})$
defined by

$F(B,L)=(I+L)^{-1}(A+B)(I+L).$

Let $\dot{F}=\dot{F}\Big{|}_{\begin{subarray}{c}B=O\\\ L=O\end{subarray}}$. By
direct computation, the range of $\dot{F}$ is

$\mathcal{Q}^{\rm v}(P)+\\{-LA+AL:L\in\operatorname{Mat}_{n}(\mathbb{R})\\}.$

Note that in the vector space $\operatorname{Mat}_{n}(\mathbb{R})$, the
orthogonal complement of $\mathcal{Q}^{\rm v}(P)$ is

$\\{X\in\operatorname{Mat}_{n}(\mathbb{R}):A\circ X=O\\},$

and the orthogonal complement of
$\\{-LA+AL:L\in\operatorname{Mat}_{n}(\mathbb{R})\\}$ is

$\\{X\in\operatorname{Mat}_{n}(\mathbb{R}):[A,X^{\top}]=O\\}$

since

$\displaystyle 0=\left\langle-LA+AL,X\right\rangle$
$\displaystyle=\operatorname{tr}(X^{\top}(-LA+AL))$
$\displaystyle=\operatorname{tr}(-X^{\top}LA+X^{\top}\\!AL)$
$\displaystyle=\operatorname{tr}(-LAX^{\top}+LX^{\top}\\!A)$
$\displaystyle=-\operatorname{tr}(L(AX^{\top}-X^{\top}\\!A))$
$\displaystyle=-\left\langle AX^{\top}-X^{\top}\\!A,L^{\top}\right\rangle,$

for $L\in\operatorname{Mat}_{n}(\mathbb{R})$. Therefore, $A$ has the nSSP if
and only if $\dot{F}$ is surjective.

By the inverse function theorem (Theorem 2.4), there is $\epsilon>0$ such that
for any $M\in\operatorname{Mat}_{n}(\mathbb{R})$ with $\|M-A\|<\epsilon$,
matrices $B^{\prime}\in\mathcal{Q}^{\rm v}(P)$ and
$L^{\prime}\in\operatorname{Mat}_{n}(\mathbb{R})$ exist with

$F(B^{\prime},L^{\prime})=(I+L^{\prime})^{-1}(A+B^{\prime})(I+L^{\prime})=M,$

which means $A^{\prime}=A+B^{\prime}$ is similar to $M$. When $\|M-A\|$ is
sufficiently small, $\|B^{\prime}\|$ is small and
$A^{\prime}\in\mathcal{Q}(P)$. Moreover, when the perturbation is sufficiently
small, the derivative of $F$ at $B=B^{\prime}$ and $L=L^{\prime}$ remains
surjective, so $A^{\prime}$ has the nSSP. ∎

The function $F$ used in the bifurcation lemma (Theorem 5.2) is a composition
of $M\mapsto(I+L)^{-1}M(I+L)$ and $M\mapsto M+B$. In the following, we will
see by changing the order of the composition, we will get the superpattern
lemma. In short, the bifurcation lemma allows us to find a matrix with the
same pattern but with a slightly different Jordan canonical form, while the
superpattern allows us to find a matrix with the same Jordan canonical form
but with a slightly different pattern. Note that the superpattern lemma is a
non-symmetric analogue of the supergraph lemma [4, Theorem 10].

######  Theorem 5.3 (Superpattern lemma).

Let $P$ be an $n\times n$ sign pattern and $A\in\mathcal{Q}(P)$. If $A$ has
the nSSP, then for any superpattern $P^{\prime}$ of $P$, a matrix
$A^{\prime}\in\mathcal{Q}(P^{\prime})$ exists such that $A^{\prime}$ and $A$
are similar and $A^{\prime}$ has the nSSP.

###### Proof.

Given a matrix $A\in\mathcal{Q}(P)$, consider the function $F:\mathcal{Q}^{\rm
v}(P)\times\mathcal{B}_{n}\rightarrow\operatorname{Mat}_{n}(\mathbb{R})$
defined by

$F(B,L)=(I+L)^{-1}A(I+L)+B.$

Let $\dot{F}=\dot{F}\Big{|}_{\begin{subarray}{c}B=O\\\ L=O\end{subarray}}$. By
the arguments in the proof of Theorem 5.2, $A$ has the nSSP if and only if
$\dot{F}$ is surjective.

By the inverse function theorem (Theorem 2.4), there is $\epsilon>0$ such that
for any $M\in\operatorname{Mat}_{n}(\mathbb{R})$ with $\|M-A\|<\epsilon$,
matrices $B^{\prime}\in\mathcal{Q}^{\rm v}(P)$ and
$L^{\prime}\in\operatorname{Mat}_{n}(\mathbb{R})$ with

$F(B^{\prime},L^{\prime})=(I+L^{\prime})^{-1}A(I+L^{\prime})+B^{\prime}=M$

exist, which means $A^{\prime}=M-B^{\prime}$ is similar to $A$. We may choose
$M$ as the matrix obtained from $A$ by adding $+s$ or $-s$ at the extra
nonzero entries in $P^{\prime}$ but not in $P$. The quantity $s$ can be chosen
sufficiently small so that $\|M-A\|<\epsilon$. Since $B^{\prime}$ is a small
perturbation on the nonzero entries of $A$, $A^{\prime}=M-B^{\prime}$ is a
matrix in $\mathcal{Q}(P^{\prime})$. When the perturbation is sufficiently
small, the derivative of $F$ at $B=B^{\prime}$ and $L=L^{\prime}$ remains
surjective, so $A^{\prime}$ has the nSSP. ∎

With the bifurcation lemma and the superpattern lemma, we are ready to prove
Corollary 5.6, a more flexible version of the nilpotent-centralizer method.
Note that in Corollary 5.6, the nilpotent matrix is no longer required to have
index $n$. Instead, all that is required is that the spectra within some
neighborhood of a nilpotent matrix include all sufficiently small spectra that
are invariant under conjugation. The following known result will allow us to
show that every nilpotent matrix meets this requirement.

######  Theorem 5.4.

[13, Theorem 2.3.4] If $A\in\operatorname{Mat}_{n}(\mathbb{R})$, there is an
orthogonal matrix $Q\in\operatorname{Mat}_{n}(\mathbb{R})$ such that

$Q^{\top}\\!AQ=\begin{bmatrix}A_{1}&~{}&~{}&~{}\\\
~{}&A_{2}&\lx@intercol\hfil\smash{\raisebox{6.0pt}{\Large$*$}}\hfil\lx@intercol\\\
~{}&~{}&\ddots&~{}\\\
\lx@intercol\hfil\smash{\raisebox{6.0pt}{\Large$O$}}\hfil\lx@intercol&~{}&A_{k}\end{bmatrix}\in\operatorname{Mat}_{n}(\mathbb{R}),$

where $1\leq k\leq n$ and each $A_{i}$ is a real $1\times 1$ matrix, or a real
$2\times 2$ matrix with a non-real pair of complex conjugate eigenvalues. The
diagonal blocks $A_{i}$ may be arranged in any prescribed order.

######  Corollary 5.5.

Let $A\in\operatorname{Mat}_{n}(\mathbb{R})$ be nilpotent and let $\epsilon>0$
be given. Then for any complex multiset
$\Lambda=\\{\lambda_{1},\ldots,\lambda_{n}\\}$, invariant under conjugation,
with

$\sum_{i=1}^{n}|\lambda_{i}|^{2}<\epsilon^{2},$

a matrix $M$ exists with $\|M-A\|<\epsilon$ and
$\operatorname{spec}(M)=\Lambda$.

###### Proof.

Since $\|M-A\|=\|Q^{\top}MQ-Q^{\top}AQ\|$ for any orthogonal matrix $Q$, by
Theorem 5.4 we may assume without loss of generality that $A$ is strictly
upper triangular, with all diagonal entries equal to $0$. For each real
eigenvalue $\lambda_{i}$ the perturbation of a $1\times 1$ diagonal block from
$[0]\mbox{ in }A\mbox{ to }[\lambda_{i}]\mbox{ in }M$ contributes exactly
$|\lambda_{i}|^{2}$ to $\|M-A\|^{2}$. For each non-real conjugate pair
$\\{\lambda_{i},\lambda_{j}\\}$ whose real part is $a$, and the absolute value
of whose imaginary part is $b>0$, the perturbation of some $2\times 2$
diagonal block

$\mbox{ from }\begin{bmatrix}0&x\\\ 0&0\end{bmatrix}\mbox{ in }A\ \
\begin{cases}\mbox{ to }\begin{bmatrix}a&-b\\\ b&a\end{bmatrix}\mbox{ in
}M,&-b\leq x<0\\\ ~{}&{}\textstyle\\\ \mbox{ to }\begin{bmatrix}a&b\\\
-b&a\end{bmatrix}\mbox{ in }M,&0\leq x\leq b\\\ ~{}&{}\textstyle\\\ \mbox{ to
}\begin{bmatrix}a&x\\\ \frac{-b^{2}}{x}&a\end{bmatrix}\mbox{ in
}M,&|x|>b\end{cases}$

contributes no more than $|\lambda_{i}|^{2}+|\lambda_{j}|^{2}=2a^{2}+2b^{2}$
to $\|M-A\|^{2}$ in every case, regardless of the value of $x$. It follows
that $\|M-A\|^{2}\leq\epsilon^{2}$ holds, and thus $\|M-A\|<\epsilon$, for the
perturbed matrix $M$ with spectrum $\Lambda$. ∎

######  Corollary 5.6.

Let $P$ be an $n\times n$ sign pattern and $A\in\mathcal{Q}(P)$. If $A$ is
nilpotent and has the nSSP, then any superpattern of $P$ is a spectrally
arbitrary pattern.

###### Proof.

By the bifurcation lemma for non-symmetric matrices (Theorem 5.2), there is
$\epsilon>0$ such that for any $M$ with $\|M-A\|<\epsilon$, a matrix
$A^{\prime}\in\mathcal{Q}(P)$ exists such that $A^{\prime}$ and $M$ are
similar and $A^{\prime}$ has the nSSP.

By Corollary 5.5, for any set of complex numbers
$\Lambda=\\{\lambda_{1},\ldots,\lambda_{n}\\}$, invariant under conjugation,
with

$\sum_{i=1}^{n}|\lambda_{i}|^{2}<\epsilon^{2},$

a matrix $M$ exists with $\|M-A\|<\epsilon$ and
$\operatorname{spec}(M)=\Lambda$.

Combining the above results, $P$ allows any sufficiently small spectrum that
is invariant under conjugation. By scaling $A^{\prime}$ to $kA^{\prime}$, $P$
allows any spectrum that is invariant under conjugation. Moreover, by the
superpattern lemma (Theorem 5.3), any superpattern of $P$ is also a spectrally
arbitrary pattern since $P$ is a spectrally arbitrary pattern and the matrices
$A$, $A^{\prime}$, and $kA^{\prime}$ have the nSSP. ∎

This leads to a theorem developed by Pereira [17]. Recall that a sign pattern
is _full_ if each of its entries is nonzero. Also, every matrix in the
qualitative class of a full sign pattern naturally has the nSSP by definition.

######  Corollary 5.7.

[17, Theorem 1.2] If $P$ is a full $n\times n$ sign pattern and
$\mathcal{Q}(P)$ contains a nilpotent matrix, then $P$ is a spectrally
arbitrary pattern.

######  Remark 5.8.

Comparing to the nilpotent-centralizer method, Corollary 5.6 provides a more
flexible condition for finding a spectrally arbitrary pattern since the
nilpotent matrix $A$ is not necessarily of index $n$. However, as we can see
later in Corollary 5.10, a sign pattern $P$ can be verified as a spectrally
arbitrary pattern by the nilpotent-centralizer method if and only if $P$ can
be verified as a spectrally arbitrary pattern by Corollary 5.6.

######  Theorem 5.9.

[13, Theorem 3.1.11] Let $A\in\operatorname{Mat}_{n}(\mathbb{R})$ be a matrix
with only real eigenvalues. Then there is a nonsingular matrix
$Q\in\operatorname{Mat}_{n}(\mathbb{R})$ such that $A=QJQ^{-1}$, where $J$ is
the Jordan canonical form of $A$.

######  Corollary 5.10.

Let $P$ be a sign pattern. If there is a nilpotent matrix $A\in\mathcal{Q}(P)$
with the nSSP, then there is a nilpotent matrix $A^{\prime}\in\mathcal{Q}(P)$
of index $n$ and with the nSSP.

###### Proof.

According to Theorem 5.9, every $n\times n$ nilpotent matrix has a nilpotent
matrix of index $n$ that is arbitrarily close to it. Thus, the desired result
follows from the bifurcation lemma for non-symmetric matrices (Theorem 5.2). ∎

The nilpotent-Jacobian method introduced in [9] is another method for
verifying a spectrally arbitrary pattern, and it was developed earlier than
the nilpotent-centralizer method. Roughly speaking, the nilpotent-Jacobian
method considers a map $f$ from $n$ nonzero entries on an $n\times n$
nilpotent matrix $A\in\mathcal{Q}(P)$ to the $n$ non-leading coefficients of
the characteristic polynomial $\det(xI-A)$, and it states that if the
derivative of $f$ is surjective (equivalently, invertible) then any
superpattern of $P$ is spectrally arbitrary. On the one hand, for the
nilpotent-centralizer method, it was shown that if $A$ is a nilpotent matrix
of index $n$ and $A$ has the nSSP, then the map $f$ with the desired
properties for the nilpotent-Jacobian method exists [12]. On the other hand,
in [6], it was shown that such a map $f$ exists only when the nilpotent matrix
$A$ has index $n$. In summary, when $A$ is a nilpotent matrix, the map $f$ for
the nilpotent-Jacobian method exists if and only if $A$ is of index $n$ and
$A$ has the nSSP. From this point of view, the nilpotent-Jacobian method and
the nilpotent-centralizer method are somehow equivalent, while the later one
avoid the hassle of finding the appropriate $n$ entries. Example 5.11 provides
some reasoning of why the previous two methods require the nilpotency of index
$n$ while Corollary 5.6 only needs the nilpotency.

######  Example 5.11.

Let

$A=\begin{bmatrix}-1&1&-1\\\ -2&2&-2\\\ -1&1&-1\\\ \end{bmatrix}\text{ and
}B=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\\ x_{21}&x_{22}&x_{23}\\\
x_{31}&x_{32}&x_{33}\\\ \end{bmatrix}.$

Then $A$ is a nilpotent matrix of index $2$, which is smaller than the size of
$A$. Let $\det(xI-(A+B))=c_{0}+c_{1}x+c_{2}x^{2}+x^{3}$ such that
$c_{0},c_{1},c_{2}$ are polynomials in variables in $B$. Let $f$ be the map
$B\mapsto(c_{0},c_{1},c_{2})$. In particular,

$c_{0}=\det(-(A+B))=(-1)^{3}\det(A+B).$

Notice that at $B=O$, no single variable in $B$ is able to change the value of
$\det(A+B)$ since $\operatorname{rank}(A)=1$ and all $2\times 2$ submatrices
are singular. Therefore, the derivative of $c_{0}$ at $B=O$ with respect to
any $x_{ij}$ is $0$, and the derivative of $f$ is not surjective.
Consequently, the nilpotent-Jacobian method and the nilpotent-centralizer
method do not apply in this case.

In contrast, the variables in $B$ naturally perturb $A$ into any matrices
nearby $A$, so Corollary 5.6 still applies.

The bifurcation lemma also has application to the possible inertia sets of a
sign pattern. Let $A$ be an $n\times n$ matrix. The _inertia_ of a not
necessarily symmetric $A$ is

$\operatorname{in}(A)=(n_{+}(A),n_{-}(A),n_{0}(A)),$

where $n_{+}(A)$, $n_{-}(A)$, and $n_{0}(A)$ are the number of eigenvalues
with positive, negative, and zero real part. The _refined inertia_ was
considered in [14] and is defined as

$\operatorname{rin}(A)=(n_{+}(A),n_{-}(A),n_{z}(A),2n_{p}(A)),$

where $n_{+}(A)$ and $n_{-}(A)$ are the defined as those in the inertia while
$n_{z}(A)$ and $2n_{p}(A)$ are the number of zero eigenvalues and the number
of nonzero pure-imaginary eigenvalues, respectively. Also, an $n\times n$ sign
pattern is called an _inertially arbitrary pattern_ if it can realize all
possible inertia $(n_{+},n_{-},n_{0})$ with $n_{+}+n_{-}+n_{0}=n$.

######  Corollary 5.12.

Let $P$ be an $n\times n$ sign pattern and $A\in\mathcal{Q}(P)$. If
$n_{0}(A)=n$, $n_{z}(A)\geq 2$, and $A$ has the nSSP, then $P$ is an
inertially arbitrary pattern.

###### Proof.

According to the bifurcation lemma for non-symmetric matrices (Theorem 5.2), a
zero eigenvalue can be perturbed into any nearby real eigenvalue, while a
conjugate pair of nonzero pure-imaginary eigenvalues can be perturbed into two
eigenvalues whose real parts are of the same sign.

Suppose $(p,q,n-p-q)$ is the target inertia. If $2n_{p}(A)\geq p$, then we
perturb $\left\lfloor\frac{p}{2}\right\rfloor$ conjugate pairs of nonzero
pure-imaginary eigenvalues to have positive real parts, and, if in addition
$p$ is odd, perturb a zero eigenvalue be a positive eigenvalue. If not, we
perturb all $n_{p}(A)$ conjugate pairs of nonzero pure-imaginary eigenvalues
to have positive real parts, and perturb $p-2n_{p}(A)$ zero eigenvalues to be
positive. After doing similar perturbations to make $q$ eigenvalues with
negative real parts, we see that $P$ is an inertially arbitrary pattern. ∎

##  6 Concluding remarks

The idea of the bifurcation lemma was motivated by some of the work in [2],
and the same condition as the nSSP is mentioned in [2] for the study of versal
deformation and in [15] for extreme nonnegative matrices. In most of recent
studies of the strong properties, e.g., [4, 3], the implicit function theorem
is used for building a new symmetric matrix with additional nonzero entries.
The technique that we have here employed to prove the bifurcation lemma is to
use the inverse function theorem instead, without creating more nonzero
entries. As we have seen, the notion of bifurcation works well with various
strong properties and applies for both the symmetric and the non-symmetric
cases. It is foreseeable that this technique can be used in other
circumstances, such as new strong properties, matrices with zero diagonal, and
so on.

##  7 Acknowledgements

Shaun M. Fallat was supported in part by an NSERC Discovery Research Grant,
Application No.: RGPIN–2019–03934. Jephian C.-H. Lin was supported by the
Young Scholar Fellowship Program (grant no. MOST-110-2628-M-110-003) from the
Ministry of Science and Technology in Taiwan.

## References

  * [1] M. Arav, F. J. Hall, Z. Li, and H. van der Holst. The inertia set of a signed graph. _Linear Algebra Appl._ , 439:1506–1529, 2013.
  * [2] V. I. Arnol’d. On matrices depending on parameters. (Russian) _Uspehi Mat. Nauk,_ 26:101–114, 1971. (English translation in _Russian Math. Surveys_ , 26:29–43, 1971.)
  * [3] W. Barrett, S. Butler, S. M. Fallat, H. T. Hall, L. Hogben, J. C.-H. Lin, B. L. Shader, and M. Young.  The inverse eigenvalue problem of a graph: Multiplicities and minors.  J. Combin. Theory Ser. B, 142:276–306, 2020.
  * [4] W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, J. C.-H. Lin, and B. L. Shader.  Generalizations of the Strong Arnold Property and the minimum number of distinct eigenvalues of a graph.  Electron. J. Combin., 24:#P2.40, 2017.
  * [5] W. Barrett, H. T. Hall, and R. Loewy. The inverse inertia problems for graphs: Cut vertices, trees, and a counterexample. _Linear Algebra Appl._ , 431:1147–1191, 2009.
  * [6] H. Bergsma, K. N. Vander Meulen, and A. Van Tuyl. Potentially nilpotent patterns and the nilpotent-Jacobian method. _Linear Algebra Appl._ , 436:4433–4445, 2011.
  * [7] Y. Colin de Verdière.  Sur un nouvel invariant des graphes et un critère de planarité.  J. Combin. Theory Ser. B, 50:11–21, 1990.
  * [8] Y. Colin de Verdière.  On a new graph invariant and a criterion for planarity.  In Graph Structure Theory, pp. 137–147, American Mathematical Society, Providence, RI, 1993.
  * [9] J. H. Drew, C. R. Johnson, D. D. Olesky, and P. van den Driessche. Spectrally arbitrary patterns. _Linear Algebra Appl._ , 308:121–137, 2000.
  * [10] W. E. Ferguson, Jr.  The construction of Jacobi and periodic Jacobi matrices with prescribed spectra.  Math. Comp., 35:1203–1220, 1980.
  * [11] P. M. Gadea, J. Muñoz Masqué, and I. V. Mykytyuk. _Analysis and Algebra on Differentiable Manifolds_. Springer Netherlands, 2nd edition, 2013.
  * [12] C. Garnett and B. L. Shader. The Nilpotent-Centralizer Method for spectrally arbitrary patterns. _Linear Algebra Appl._ , 438:3836–3850, 2013.
  * [13] R. A. Horn and C. R. Johnson. _Matrix Analysis_. Cambridge University Press, New York, 1985.
  * [14] I.-J. Kim, D. D. Olesky, B. L. Shader, P. van den Driessche, H. van der Holst, and K. N. Vander Meulen. Generating potentially nilpotent full sign patterns. _Electron. J. Linear Algebra_ , 18:162–175, 2009.
  * [15] T. J. Laffey. Extreme nonnegative matrices. _Linear Algebra Appl._ , 275–276:349–357, 1998.
  * [16] S. Parter. On the eigenvalues and eigenvectors of a class of matrices. _J. Soc. Indust. Appl. Math._ , 8:376–388, 1960.
  * [17] R. Pereira. Nilpotent matrices and spectrally arbitrary sign patterns. _Electron. J. Linear Algebra_ , 16:232–236, 2007.
  * [18] G. Wiener. Spectral multiplicity and splitting results for a class of qualitative matrices. _Linear Algebra Appl._ , 61:15–29, 1984.


* Alvarado Garcia and Le Dantec (2018) Adriana Alvarado Garcia and Christopher A. Le Dantec. 2018.  Quotidian Report: Grassroots Data Practices to Address Public Safety.  _Proc. ACM Hum.-Comput. Interact._ 2, CSCW, Article 17 (nov 2018), 18 pages.  https://doi.org/10.1145/3274286
  * Amnesty International (2020) Amnesty International. 2020.  _Syria: ’Nowhere is Safe for Us’: Unlawful Attacks and Mass Displacement in North-West Syria_.  Technical Report.  https://www.amnesty.org/en/documents/document/?indexNumber=MDE24%2f2089%2f2020&language=en
  * Arif et al. (2017) Ahmer Arif, John J. Robinson, Stephanie A. Stanek, Elodie S. Fichet, Paul Townsend, Zena Worku, and Kate Starbird. 2017.  A Closer Look at the Self-Correcting Crowd: Examining Corrections in Online Rumors. In _Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing_ _(CSCW ’17)_. ACM, Portland Oregon USA, 155–168.  https://doi.org/10.1145/2998181.2998294
  * Aula and Russell (2008) Anne Aula and Daniel M Russell. 2008.  Complex and exploratory web search. In _Information Seeking Support Systems Workshop (ISSS 2008), Chapel Hill, NC, USA_. Citeseer.
  * Beckett (2017) Charlie Beckett. 2017.  Wikitribune: can crowd-sourced journalism solve the crisis of trust in news?  _POLIS: journalism and society at the LSE_ (2017).
  * Belghith et al. (2022) Yasmine Belghith, Sukrit Venkatagiri, and Kurt Luther. 2022.  Compete, Collaborate, Investigate: Exploring the Social Structures of Open Source Intelligence Investigations. In _Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems_ _(CHI ’22)_. Association for Computing Machinery, New York, NY, USA, 1–18.  https://doi.org/10.1145/3491102.3517526
  * Bellingcat Investigation Team (2015) Bellingcat Investigation Team. 2015.  Diversifying OSINT: Women Experts.  https://www.bellingcat.com/resources/articles/2015/12/08/women-in-osint-diversifying-the-field/
  * Bernstein et al. (2010) Michael S Bernstein, Greg Little, Robert C Miller, Björn Hartmann, Mark S Ackerman, David R Karger, David Crowell, and Katrina Panovich. 2010.  Soylent: a word processor with a crowd inside. In _Proceedings of the 23nd annual ACM symposium on User interface software and technology_. ACM, 313–322.
  * Bittner et al. (2016) Christian Bittner, Boris Michel, and Cate Turk. 2016.  Turning the spotlight on the crowd: Examining the participatory ethics and practices of crisis mapping.  _ACME: An International Journal for Critical Geographies_ 15, 1 (2016), 207–229.
  * Brands et al. (2018) Bert Jan Brands, Todd Graham, and Marcel Broersma. 2018.  Social media sourcing practices: How Dutch newspapers use tweets in political news coverage.  _Managing democracy in the digital age: Internet regulation, social media use, and online civic engagement_ (2018), 159–178.
  * Braun and Clarke (2006) Virginia Braun and Victoria Clarke. 2006.  Using thematic analysis in psychology.  _Qualitative research in psychology_ 3, 2 (Jan. 2006), 77–101.  https://doi.org/10.1191/1478088706qp063oa Publisher: Routledge _eprint: https://www.tandfonline.com/doi/pdf/10.1191/1478088706qp063oa.
  * Broughton et al. (2014) Andrea Broughton, Beth Foley, Stefanie Ledermaier, and Annette Cox. 2014.  The use of social media in the recruitment process. (2014).  81 (2014).
  * Cao (2023) Chen Cao. 2023.  Leveraging Large Language Model and Story-Based Gamification in Intelligent Tutoring System to Scaffold Introductory Programming Courses: A Design-Based Research Study.  _arXiv preprint arXiv:2302.12834_ (2023).
  * Carneiro et al. (2019) Guilherme Carneiro, Miguel Nacenta, Alice Toniolo, Gonzalo Mendez, and Aaron J Quigley. 2019.  Deb8: A tool for collaborative analysis of video. In _Proceedings of the 2019 ACM International Conference on Interactive Experiences for TV and Online Video_. 47–58.
  * Center (2021) Southern Poverty Law Center. 2021.  The Road to Jan. 6: A Year of Extremist Mobilization.  https://www.splcenter.org/news/2021/12/30/road-jan-6-year-extremist-mobilization
  * Chan et al. (2018) Joel Chan, Joseph Chee Chang, Tom Hope, Dafna Shahaf, and Aniket Kittur. 2018.  SOLVENT: A Mixed Initiative System for Finding Analogies Between Research Papers.  2 (2018), 31:1–31:21.  Issue CSCW. https://doi.org/10.1145/3274300
  * Cobb et al. (2003) Paul Cobb, Jere Confrey, Andrea DiSessa, Richard Lehrer, and Leona Schauble. 2003.  Design experiments in educational research.  _Educational researcher_ 32, 1 (2003), 9–13.
  * Cochrane (2022) Josie Cochrane. 2022.  Citizen OSINT Analysts: Motivations of Open-Source Intelligence Volunteers.
  * Correia et al. (2023) António Correia, Andrea Grover, Daniel Schneider, Ana Paula Pimentel, Ramon Chaves, Marcos Antonio De Almeida, and Benjamim Fonseca. 2023.  Designing for Hybrid Intelligence: A Taxonomy and Survey of Crowd-Machine Interaction.  _Applied Sciences_ 13, 4 (2023), 2198.
  * Cox (2018) Joseph Cox. 2018.  The Hackers Hunting Down Missing People: Nonprofit TraceLabs ran DEF CON’s first crowdsourced event for tracking missing people through public information.  _Vice_ (2018).  https://www.vice.com/en_us/article/qvmm3x/hackers-hunting-missing-people-osint-defcon-tracelabs
  * Dailey and Starbird (2014) Dharma Dailey and Kate Starbird. 2014.  Journalists as Crowdsourcerers: Responding to Crisis by Reporting with a Crowd.  _Computer Supported Cooperative Work (CSCW)_ 23, 4 (01 Dec 2014), 445–481.  https://doi.org/10.1007/s10606-014-9208-z
  * Dailey and Starbird (2015) Dharma Dailey and Kate Starbird. 2015.  ”It’s Raining Dispersants”: Collective Sensemaking of Complex Information in Crisis Contexts. In _Proceedings of the 18th ACM Conference Companion on Computer Supported Cooperative Work and; Social Computing_ (Vancouver, BC, Canada) _(CSCW’15 Companion)_. Association for Computing Machinery, New York, NY, USA, 155–158.  https://doi.org/10.1145/2685553.2698995
  * Diakopoulos et al. (2021) Nicholas Diakopoulos, Daniel Trielli, and Grace Lee. 2021.  Towards Understanding and Supporting Journalistic Practices Using Semi-Automated News Discovery Tools.  _Proceedings of the ACM on Human-Computer Interaction_ 5, CSCW2 (Oct. 2021), 406:1–406:30.  https://doi.org/10.1145/3479550
  * Doroudi et al. (2016) Shayan Doroudi, Ece Kamar, Emma Brunskill, and Eric Horvitz. 2016.  Toward a Learning Science for Complex Crowdsourcing Tasks. In _Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems_ _(CHI ’16)_. Association for Computing Machinery, New York, NY, USA, 2623–2634.  https://doi.org/10.1145/2858036.2858268
  * Dow et al. (2012) Steven Dow, Anand Kulkarni, Scott Klemmer, and Björn Hartmann. 2012.  Shepherding the Crowd Yields Better Work. In _Proceedings of the ACM 2012 Conference on Computer Supported Cooperative Work_ (Seattle, Washington, USA) _(CSCW ’12)_. Association for Computing Machinery, New York, NY, USA, 1013–1022.  https://doi.org/10.1145/2145204.2145355
  * Dubberley et al. (2020) Sam Dubberley, Alexa Koenig, and Daragh Murray (Eds.). 2020.  _Digital Witness: Using Open Source Information for Human Rights Investigation, Documentation, and Accountability_.  Oxford University Press, Oxford, New York.
  * Easterday et al. (2014) Matthew W Easterday, Daniel Rees Lewis, and Elizabeth M Gerber. 2014.  Design-based research process: Problems, phases, and applications.  Boulder, CO: International Society of the Learning Sciences.
  * Erete (2015) Sheena L. Erete. 2015.  Engaging Around Neighborhood Issues: How Online Communication Affects Offline Behavior. In _Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing_ _(CSCW ’15)_. Association for Computing Machinery, New York, NY, USA, 1590–1601.  https://doi.org/10.1145/2675133.2675182
  * Esteban Borges (2019) Esteban Borges. 2019.  SecurityTrails | OSINT Framework: The Perfect Cybersecurity Intel Gathering Tool.  https://securitytrails.com/blog/osint-framework
  * Fiorella (2021) Giancarlo Fiorella. 2021.  _First Steps to Getting Started in Open Source Research_.  https://www.bellingcat.com/resources/2021/11/09/first-steps-to-getting-started-in-open-source-research/
  * Fisher et al. (2012) Kristie Fisher, Scott Counts, and Aniket Kittur. 2012.  Distributed Sensemaking: Improving Sensemaking by Leveraging the Efforts of Previous Users. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ (New York, NY, USA) _(CHI ’12)_. ACM, New York, NY, USA, 247–256.  https://doi.org/10.1145/2207676.2207711
  * Fletcher et al. (2018) Richard Fletcher, Alessio Cornia, Lucas Graves, and Rasmus Kleis Nielsen. 2018.  Measuring the reach of” fake news” and online disinformation in Europe.  _Australasian Policing_ 10, 2 (2018).
  * Flores-Saviaga et al. (2022) Claudia Flores-Saviaga, Shangbin Feng, and Saiph Savage. 2022.  Datavoidant: An AI System for Addressing Political Data Voids on Social Media.  _Proceedings of the ACM on Human-Computer Interaction_ 6, CSCW2 (2022), 1–29.
  * Ghioni et al. (2022) Riccardo Ghioni, Mariarosaria Taddeo, and Luciano Floridi. 2022.  Open Source Intelligence and AI: a Systematic Review of the GELSI Literature.  _AI & Society_ (2022).
  * Glassman and Kang (2012) Michael Glassman and Min Ju Kang. 2012.  Intelligence in the internet age: The emergence and evolution of Open Source Intelligence (OSINT).  _Computers in Human Behavior_ 28, 2 (March 2012), 673–682.  https://doi.org/10.1016/j.chb.2011.11.014
  * Godel et al. (2021) William Godel, Zeve Sanderson, Kevin Aslett, Jonathan Nagler, Richard Bonneau, Nathaniel Persily, and Joshua A Tucker. 2021.  Moderating with the mob: Evaluating the efficacy of real-time crowdsourced fact-checking.  _Journal of Online Trust and Safety_ 1, 1 (2021).
  * Gong et al. (2019) Miaomiao Gong, Yuling Sun, and Liang He. 2019.  A Social Network Engaged Crowdsourcing Framework for Expert Tasks. In _2019 IEEE 23rd International Conference on Computer Supported Cooperative Work in Design (CSCWD)_. IEEE, 249–254.  https://doi.org/10.1109/CSCWD.2019.8791923
  * Grevet and Gilbert (2015) Catherine Grevet and Eric Gilbert. 2015.  Piggyback prototyping: Using existing, large-scale social computing systems to prototype new ones. In _Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems_. 4047–4056.
  * Gutierrez and Torpey (2015) Pablo Gutierrez and Paul Torpey. 2015.  How Digital Detectives Say They Proved Ukraine Attacks Came from Russia.  _The Guardian_ (2015).
  * Hahn et al. (2016) Nathan Hahn, Joseph Chang, Ji Eun Kim, and Aniket Kittur. 2016.  The Knowledge Accelerator: Big Picture Thinking in Small Pieces. In _Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems_ (New York, NY, USA) _(CHI ’16)_. ACM, 2258–2270.  http://doi.acm.org/10.1145/2858036.2858364
  * Hanham and Shin (2020) Melissa Hanham and Jaewoo Shin. 2020.  Ethics in the Age of OSINT Innocence.  _Stanley Center for Peace and Security_ (May 2020), 6.  https://stanleycenter.org/publications/ethics-osint-innocence/
  * Harris et al. (2019) Alexa M Harris, Diego Gómez-Zará, Leslie A DeChurch, and Noshir S Contractor. 2019.  Joining together online: the trajectory of CSCW scholarship on group formation.  _Proceedings of the ACM on Human-Computer Interaction_ 3, CSCW (2019), 1–27.
  * Hassan et al. (2017) Naeemul Hassan, Gensheng Zhang, Fatma Arslan, Josue Caraballo, Damian Jimenez, Siddhant Gawsane, Shohedul Hasan, Minumol Joseph, Aaditya Kulkarni, Anil Kumar Nayak, Vikas Sable, Chengkai Li, and Mark Tremayne. 2017.  ClaimBuster: the first-ever end-to-end fact-checking system.  _Proceedings of the VLDB Endowment_ 10, 12 (Aug. 2017), 1945–1948.  https://doi.org/10.14778/3137765.3137815
  * Higgins (2021a) Annique Mossou Higgins, Ross. 2021a.  _A Beginner’s Guide to Social Media Verification_.  https://www.bellingcat.com/resources/2021/11/01/a-beginners-guide-to-social-media-verification/
  * Higgins (2021b) Eliot Higgins. 2021b.  _We Are Bellingcat : An Intelligence Agency for the People_.  Bloomsbury Publishing, London.
  * Hswe et al. (2009) Patricia Hswe, Joanne Kaczmarek, Leah Houser, and Janet Eke. 2009.  The Web Archives Workbench (WAW) Tool Suite: Taking an Archival Approach to the Preservation of Web Content.  _Library Trends_ 57, 3 (2009), 442–460.  https://doi.org/10.1353/lib.0.0046 Publisher: Johns Hopkins University Press.
  * Huang et al. (2015) Y. Linlin Huang, Kate Starbird, Mania Orand, Stephanie A. Stanek, and Heather T. Pedersen. 2015.  Connected Through Crisis: Emotional Proximity and the Spread of Misinformation Online. In _Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing_ _(CSCW ’15)_. Association for Computing Machinery, New York, NY, USA, 969–980.  https://doi.org/10.1145/2675133.2675202
  * Hulnick (2002) Arthur S. Hulnick. 2002.  The Downside of Open Source Intelligence.  _International Journal of Intelligence and CounterIntelligence_ 15, 4 (Nov. 2002), 565–579.  https://doi.org/10.1080/08850600290101767
  * Iorga et al. (2021) Denis Iorga, Octavian Grigorescu, Mihai Predoiu, Cristian Sandescu, Mihai Dascalu, and Razvan Rughinis. 2021.  Early Usability Evaluation to Enhance User Interfaces-A Use Case on the Yggdrasil Cybersecurity Mockup.. In _RoCHI_. 103–110.
  * Kermode et al. (2020) Lachlan Kermode, Jan Freyberg, Alican Akturk, Robert Trafford, Denis Kochetkov, Rafael Pardinas, Eyal Weizman, and Julien Cornebise. 2020.  Objects of violence: synthetic data for practical ML in human rights investigations.  _arXiv:2004.01030 [cs]_ (April 2020), 12.  http://arxiv.org/abs/2004.01030 arXiv: 2004.01030.
  * Kim et al. (2020) Sung-Kyung Kim, Eun-Tae Jang, and Ki-Woong Park. 2020.  Toward a fine-grained evaluation of the Pwnable CTF. In _Information Security Applications: 21st International Conference, WISA 2020, Jeju Island, South Korea, August 26–28, 2020, Revised Selected Papers_. Springer, 179–190.
  * Kim et al. (2018) Yongsung Kim, Darren Gergle, and Haoqi Zhang. 2018.  Hit-or-wait: Coordinating opportunistic low-effort contributions to achieve global outcomes in on-the-go crowdsourcing. In _Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems_. 1–12.
  * Kittur et al. (2014) Aniket Kittur, Andrew M. Peters, Abdigani Diriye, and Michael Bove. 2014.  Standing on the Schemas of Giants: Socially Augmented Information Foraging. In _Proceedings of the 17th ACM Conference on Computer Supported Cooperative Work & Social Computing_ (New York, NY, USA) _(CSCW ’14)_. ACM, 999–1010.  https://doi.org/10.1145/2531602.2531644
  * Kittur et al. (2011) Aniket Kittur, Boris Smus, Susheel Khamkar, and Robert E. Kraut. 2011.  CrowdForge: crowdsourcing complex work. In _Proceedings of the 24th annual ACM symposium on User interface software and technology_ (New York, NY, USA) _(UIST ’11)_. ACM, 43–52.  https://doi.org/10.1145/2047196.2047202
  * Kolb and Kolb (2017) Alice Kolb and David Kolb. 2017.  Experiential Learning Theory as a Guide for Experiential Educators in Higher Education.  _Experiential Learning & Teaching in Higher Education_ 1, 1 (June 2017), 7–44.  https://nsuworks.nova.edu/elthe/vol1/iss1/7
  * Kornfield (2021) Meryl Kornfield. 2021.  _The wrong ID: Retired firefighter, comedian and Chuck Norris falsely accused of being Capitol rioters_.  Washington Post.  https://www.washingtonpost.com/technology/2021/01/16/sleuths-falsely-identify-rioters/
  * Lave and Wenger (1991) Jean Lave and Etienne Wenger. 1991.  _Situated Learning: Legitimate Peripheral Participation_.  Cambridge University Press, Cambridge, UK.  Google-Books-ID: CAVIOrW3vYAC.
  * Li et al. (2018) Tianyi Li, Kurt Luther, and Chris North. 2018.  CrowdIA: Solving Mysteries with Crowdsourced Sensemaking.  2 (2018), 105:1–105:29.  Issue CSCW. https://doi.org/10.1145/3274374
  * Li et al. (2019) Tianyi Li, Chandler J Manns, Chris North, and Kurt Luther. 2019.  Dropping the baton? Understanding errors and bottlenecks in a crowdsourced sensemaking pipeline.  _Proceedings of the ACM on Human-Computer Interaction_ 3, CSCW (2019), 1–26.
  * Matatov et al. (2018) Hana Matatov, Adina Bechhofer, Lora Aroyo, Ofra Amir, and Mor Naaman. 2018.  DejaVu: A System for Journalists to Collaboratively Address Visual Misinformation.
  * McClure Haughey et al. (2020) Melinda McClure Haughey, Meena Devii Muralikumar, Cameron A. Wood, and Kate Starbird. 2020.  On the Misinformation Beat: Understanding the Work of Investigative Journalists Reporting on Problematic Information Online.  _Proc. ACM Hum.-Comput. Interact._ 4, CSCW2, Article 133 (Oct. 2020), 22 pages.  https://doi.org/10.1145/3415204
  * McKeown et al. (2014) Sean McKeown, David Maxwell, Leif Azzopardi, and William Bradley Glisson. 2014.  Investigating people: a qualitative analysis of the search behaviours of open-source intelligence analysts. In _Proceedings of the 5th Information Interaction in Context Symposium_ _(IIiX ’14)_. Association for Computing Machinery, New York, NY, USA, 175–184.  https://doi.org/10.1145/2637002.2637023
  * Mercado (2004) Stephen C. Mercado. 2004.  _Sailing the sea of OSINT in the information age. Technical Report_.  dataset, American Psychological Association. type.  https://doi.org/10.1037/e741272011-005
  * Metaxas and Finn (2017) Panagiotis Metaxas and Samantha T Finn. 2017.  The infamous# Pizzagate conspiracy theory: Insight from a TwitterTrails investigation.  (2017).
  * Micallef et al. (2022) Nicholas Micallef, Vivienne Armacost, Nasir Memon, and Sameer Patil. 2022.  True or False: Studying the Work Practices of Professional Fact-Checkers.  _Proceedings of the ACM on Human-Computer Interaction_ 6, CSCW1 (2022), 1–44.
  * Mitra et al. (2015) Tanushree Mitra, Clayton J Hutto, and Eric Gilbert. 2015.  Comparing person-and process-centric strategies for obtaining quality data on amazon mechanical turk. In _Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems_. 1345–1354.
  * Müller and Wiik (2021) Nina C. Müller and Jenny Wiik. 2021.  From Gatekeeper to Gate-opener: Open-Source Spaces in Investigative Journalism.  _Journalism Practice_ 0, 0 (May 2021), 1–20.  https://doi.org/10.1080/17512786.2021.1919543 Publisher: Routledge _eprint: https://doi.org/10.1080/17512786.2021.1919543.
  * Nhan et al. (2017) Johnny Nhan, Laura Huey, and Ryan Broll. 2017.  Digilantism: An analysis of crowdsourcing and the Boston marathon bombings.  _The British journal of criminology_ 57, 2 (March 2017), 341–361.  https://doi.org/10.1093/bjc/azv118
  * Noronha et al. (2011) Jon Noronha, Eric Hysen, Haoqi Zhang, and Krzysztof Z Gajos. 2011.  Platemate: crowdsourcing nutritional analysis from food photographs. In _Proceedings of the 24th annual ACM symposium on User interface software and technology_. 1–12.
  * of Homeland Security (2010) Department of Homeland Security. 2010.  (U//FOUO//LES) DHS Terrorist Use of Social Networking Facebook Case Study | Public Intelligence.  https://publicintelligence.net/ufouoles-dhs-terrorist-use-of-social-networking-facebook-case-study/
  * of Technology (2023) Massachusetts Institute of Technology. 2023.  Urban Cyber Defense: Cybersecurity Clinic.  http://urbancyberdefense.mit.edu/cybersecurityclinic Accessed: 2023-10-02.
  * Oleson et al. (2013) David Oleson, Alexander Sorokin, Greg Laughlin, Vaughn Hester, John Le, Christopher R Van Pelt, and Lukas A Biewald. 2013.  Evaluating a worker in performing crowd sourced tasks and providing in-task training through programmatically generated test tasks.  US Patent 8,554,605.
  * Papoutsaki et al. (2015) Alexandra Papoutsaki, Hua Guo, Danae Metaxa-Kakavouli, Connor Gramazio, Jeff Rasley, Wenting Xie, Guan Wang, and Jeff Huang. 2015.  Crowdsourcing from Scratch: A Pragmatic Experiment in Data Collection by Novice Requesters. In _Third AAAI Conference on Human Computation and Crowdsourcing_.  https://www.aaai.org/ocs/index.php/HCOMP/HCOMP15/paper/view/11582
  * Pennycook and Rand (2019) Gordon Pennycook and David G. Rand. 2019.  Fighting misinformation on social media using crowdsourced judgments of news source quality.  _Proceedings of the National Academy of Sciences_ 116, 7 (Feb. 2019), 2521–2526.  https://doi.org/10.1073/pnas.1806781116 Publisher: National Academy of Sciences Section: Social Sciences.
  * Pintrich (2004) Paul R Pintrich. 2004.  A conceptual framework for assessing motivation and self-regulated learning in college students.  _Educational psychology review_ 16, 4 (2004), 385–407.
  * Plomp et al. (2013) Tjeerd Plomp et al. 2013\.  Educational design research: An introduction.  _Educational design research_ (2013), 11–50.
  * Poelman et al. (2012) Ronald Poelman, Oytun Akman, Stephan Lukosch, and Pieter Jonker. 2012.  As if being there: mediated reality for crime scene investigation. In _Proceedings of the ACM 2012 conference on Computer Supported Cooperative Work_ _(CSCW ’12)_. Association for Computing Machinery, New York, NY, USA, 1267–1276.  https://doi.org/10.1145/2145204.2145394
  * Rechkemmer and Yin (2020) Amy Rechkemmer and Ming Yin. 2020.  Motivating Novice Crowd Workers through Goal Setting: An Investigation into the Effects on Complex Crowdsourcing Task Training.  _Proceedings of the AAAI Conference on Human Computation and Crowdsourcing_ 8 (Oct. 2020), 122–131.  https://doi.org/10.1609/hcomp.v8i1.7470
  * Retelny et al. (2017) Daniela Retelny, Michael S. Bernstein, and Melissa A. Valentine. 2017.  No Workflow Can Ever Be Enough: How Crowdsourcing Workflows Constrain Complex Work.  _Proc. ACM Hum.-Comput. Interact._ 1, CSCW, Article 89 (Dec. 2017), 23 pages.  https://doi.org/10.1145/3134724
  * Rouach and Santi (2001) Daniel Rouach and Patrice Santi. 2001.  Competitive Intelligence Adds Value:: Five Intelligence Attitudes.  _European Management Journal_ 19, 5 (Oct. 2001), 552–559.  https://doi.org/10.1016/S0263-2373(01)00069-X
  * Ryan Hunt (2012) Ryan Hunt. 2012.  Thirty-Seven Percent of Companies Use Social Networks to Research Potential Job Candidates, According to New CareerBuilder Survey - Apr 18, 2012.  http://press.careerbuilder.com/2012-04-18-Thirty-Seven-Percent-of-Companies-Use-Social-Networks-to-Research-Potential-Job-Candidates-According-to-New-CareerBuilder-Survey
  * Saeed et al. (2022) Mohammed Saeed, Nicolas Traub, Maelle Nicolas, Gianluca Demartini, and Paolo Papotti. 2022.  Crowdsourced Fact-Checking at Twitter: How Does the Crowd Compare With Experts?. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. 1736–1746.
  * Schumacher-Matos (2012) Edward Schumacher-Matos. 2012.  Election 1: Fact Checking The NPR Fact Checkers.  _NPR_ (Oct. 2012).  https://www.npr.org/sections/publiceditor/2012/10/28/161839145/election-1-fact-checking-the-npr-fact-checkers
  * Sethi and Rangaraju (2018) Ricky Sethi and Raghuram Rangaraju. 2018.  Extinguishing the backfire effect: using emotions in online social collaborative argumentation for fact checking. In _2018 IEEE International conference on web services (ICWS)_. IEEE, 363–366.
  * Shao et al. (2016) Chengcheng Shao, Giovanni Luca Ciampaglia, Alessandro Flammini, and Filippo Menczer. 2016.  Hoaxy: A Platform for Tracking Online Misinformation. In _Proceedings of the 25th International Conference Companion on World Wide Web_ _(WWW ’16 Companion)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 745–750.  https://doi.org/10.1145/2872518.2890098
  * Silverman (2013) Craig Silverman. 2013.  Verification Handbook: A Definitive Guide to Verifying Digital Content for Emergency Coverage.  http://verificationhandbook.com/
  * Steiger et al. (2021) Miriah Steiger, Timir J Bharucha, Sukrit Venkatagiri, Martin J. Riedl, and Matthew Lease. 2021.  The Psychological Well-Being of Content Moderators: The Emotional Labor of Commercial Moderation and Avenues for Improving Support. In _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ (Yokohama, Japan) _(CHI ’21)_. Association for Computing Machinery, New York, NY, USA, Article 341, 14 pages.  https://doi.org/10.1145/3411764.3445092
  * Suzuki et al. (2016) Ryo Suzuki, Niloufar Salehi, Michelle S. Lam, Juan C. Marroquin, and Michael S. Bernstein. 2016.  Atelier: Repurposing Expert Crowdsourcing Tasks As Micro-internships. In _Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems_ _(CHI ’16)_. ACM, New York, NY, USA, 2645–2656.  https://doi.org/10.1145/2858036.2858121
  * Tausczik and Boons (2018) Yla Tausczik and Mark Boons. 2018.  Distributed Knowledge in Crowds: Crowd Performance on Hidden Profile Tasks. In _Twelfth International AAAI Conference on Web and Social Media_.  https://aaai.org/ocs/index.php/ICWSM/ICWSM18/paper/view/17817
  * Tekian et al. (2017) Ara Tekian, Christopher J Watling, Trudie E Roberts, Yvonne Steinert, and John Norcini. 2017.  Qualitative and quantitative feedback in the context of competency-based education.  _Medical teacher_ 39, 12 (2017), 1245–1249.
  * Trottier (2017) Daniel Trottier. 2017.  Digital vigilantism as weaponisation of visibility.  _Philosophy & Technology_ 30, 1 (March 2017), 55–72.  https://doi.org/10.1007/s13347-016-0216-4
  * Varma (2010) Roli Varma. 2010.  Why so few women enroll in computing? Gender and ethnic differences in students’ perception.  _Computer Science Education_ 20, 4 (2010), 301–316.
  * Venkatagiri (2022) Sukrit Venkatagiri. 2022.  _Supporting and Transforming High-Stakes Investigations with Expert-Led Crowdsourcing_.  Ph. D. Dissertation. Virginia Tech.
  * Venkatagiri et al. (2021) Sukrit Venkatagiri, Aakash Gautam, and Kurt Luther. 2021.  CrowdSolve: Managing Tensions in an Expert-Led Crowdsourced Investigation.  _Proc. ACM Hum.-Comput. Interact._ 5, CSCW1, Article 118 (April 2021), 30 pages.  https://doi.org/10.1145/3449192
  * Venkatagiri et al. (2023) Sukrit Venkatagiri, Anirban Mukhopadhyay, David Hicks, Aaron Brantly, and Kurt Luther. 2023.  CoSINT: Designing a Collaborative Capture the Flag Competition to Investigate Misinformation. In _Proceedings of the 2023 ACM Designing Interactive Systems Conference_ (Pittsburgh, PA, USA) _(DIS ’23)_. Association for Computing Machinery, New York, NY, USA, 2551–2572.  https://doi.org/10.1145/3563657.3595997
  * Venkatagiri et al. (2019) Sukrit Venkatagiri, Jacob Thebault-Spieker, Rachel Kohler, John Purviance, Rifat Sabbir Mansur, and Kurt Luther. 2019.  GroundTruth: Augmenting Expert Image Geolocation with Crowdsourcing and Shared Representations.  _Proc. ACM Hum.-Comput. Interact._ 3, CSCW, Article 107 (Nov. 2019), 30 pages.  https://doi.org/10.1145/3359209
  * Vogt et al. (2011) Katherine Vogt, Lauren Bradel, Christopher Andrews, Chris North, Alex Endert, and Duke Hutchings. 2011.  Co-located Collaborative Sensemaking on a Large High-Resolution Display with Multiple Input Devices. In _Human-Computer Interaction – INTERACT 2011_. Springer Berlin Heidelberg, Berlin, Heidelberg, 589–604.
  * Wang et al. (2018) Nai-Ching Wang, David Hicks, and Kurt Luther. 2018.  Exploring Trade-Offs Between Learning and Productivity in Crowdsourced History.  _Proc. ACM Hum.-Comput. Interact._ 2, CSCW (Nov. 2018), 178:1–178:24.  https://doi.org/10.1145/3274447
  * Wardle (2014) Claire Wardle. 2014.  Verifying user-generated content.  _Verification handbook: A definitive guide to verifying digital content for emergency coverage_ (2014), 24–33.
  * Wardle and Derakhshan (2017) Claire Wardle and Hossein Derakhshan. 2017.  Information disorder: Toward an interdisciplinary framework for research and policymaking.
  * Wenger et al. (1998) Etienne Wenger et al. 1998\.  Communities of practice: Learning as a social system.  _Systems thinker_ 9, 5 (1998), 2–3.
  * White et al. (2014) Joanne I White, Leysia Palen, and Kenneth M Anderson. 2014.  Digital mobilization in disaster response: the work & self-organization of on-line pet advocates in response to hurricane sandy. In _Proceedings of the 17th ACM Conference on Computer Supported Cooperative Work & Social Computing_. ACM, 866–876.
  * Williams and Blum (2018a) Heather J. Williams and Ilana Blum. 2018a.  _Defining Second Generation Open Source Intelligence (OSINT) for the Defense Enterprise_.  Technical Report. RAND Corporation.  https://www.rand.org/pubs/research_reports/RR1964.html
  * Williams and Blum (2018b) Heather J. Williams and Ilana Blum. 2018b.  _Defining second generation open source intelligence (OSINT) for the defense enterprise. Technical Report_.  RAND Corporation Santa Monica United States.
  * Williams et al. (2016) Joseph Jay Williams, Juho Kim, Anna Rafferty, Samuel Maldonado, Krzysztof Z Gajos, Walter S Lasecki, and Neil Heffernan. 2016.  Axis: Generating explanations at scale with learnersourcing and machine learning. In _Proceedings of the Third (2016) ACM Conference on Learning@ Scale_. 379–388.
  * Xu et al. (2015) Anbang Xu, Huaming Rao, Steven P Dow, and Brian P Bailey. 2015.  A classroom study of using crowd feedback in the iterative design process. In _Proceedings of the 18th ACM conference on computer supported cooperative work & social computing_. 1637–1648.
  * Zhang et al. (2017) Haoqi Zhang, Matthew W Easterday, Elizabeth M Gerber, Daniel Rees Lewis, and Leesha Maliakal. 2017.  Agile research studios: Orchestrating communities of practice to advance research training. In _Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing_. 220–232.
  * Zhu et al. (2014) Haiyi Zhu, Steven P Dow, Robert E Kraut, and Aniket Kittur. 2014.  Reviewing versus doing: Learning and performance in crowd assessment. In _Proceedings of the 17th ACM conference on Computer supported cooperative work & social computing_. 1445–1455.
  * Ünver (2018) H. Akın Ünver. 2018.  _Digital Open Source Intelligence and International Security: A Primer_.  Technical Report. Centre for Economics and Foreign Policy Studies.  https://www.jstor.org/stable/resrep21048

##  Appendix A Appendix

###  A.1. Reflection Survey

Task

  1. (1)

What is your name? *

  2. (2)

What was your team name? *

  3. (3)

What task was assigned to your team? *

Coordination with Expert

  1. (1)

How was your overall experience working with the expert investigator? *

  2. (2)

What did you like about the expert collaboration? What could have been better?

Teamwork

  1. (1)

How successful was your team overall for the investigative task(s)? *
On a scale of 1-5, where 1 is not successful and 5 is very successful.

  2. (2)

How did your team work together (or not) on the task(s)? How effective was
this?

  3. (3)

What did you specifically do to help your team solve the task(s)?

Overall

  1. (1)

How confident were you about applying the practised skill in real
investigations? *
On a scale of 1-5, where 1 is not confident at all and 5 is very confident.

  2. (2)

How difficult were the task(s) overall? *
On a scale of 1-5, where 1 is very easy at all and 5 is very difficult.

  3. (3)

How enjoyable was the session?
On a scale of 1-5, where 1 is not enjoyable at all and 5 is very enjoyable.

Figure 2. Snapshot of the spreadsheet containing crowd submissions and
corresponding expert feedback for session 4. This session was led by an
investigative journalist (E4). The goal of investigation was to identify
discourse around anti-vaccine protests occurring throughout Europe as well as
the groups involved. The investigation involved the discovery task and
verification tasks like geolocation and source analysis.

###  A.2. Interview Guide for Crowdworkers

Focus group interviews with 3-4 students at a time. [45 minutes]

  1. (1)

How did you form your teams and how did the relationship with teammates evolve
over time? What were some issues that you faced as a part of the team?

  2. (2)

What changes did you notice over time in your performance during expert
sessions? Quality/quantity?

  3. (3)

Can you tell me about your favorite task among the ones used during practice
or expert sessions? [prompt - list of tasks slide]

    1. (a)

What tools and techniques did you use for the task?

    2. (b)

Why did you like it? How is it different from other tasks?

  4. (4)

Can you tell me about your hardest task among the ones used during practice or
expert sessions? [prompt - list of tasks slideshare]

    1. (a)

What tools and techniques did you use for the task?

    2. (b)

Why did you find it to be hard? How is it different from other tasks?

    3. (c)

What helped you continue to work on the tasks when relevant information was
hard to find?

  5. (5)

Can you tell me about your favorite expert session? What were the best parts
of the session?

  6. (6)

Can you tell me about your least favorite expert session? What were the parts
you did not like?

  7. (7)

Did the self-evaluation measures help you cover the requirements of the tasks?
Why/why not?

  8. (8)

What else did you enjoy during this experience?

  9. (9)

What could be improved during this experience?

###  A.3. Interview guide for Experts

Post-session Individual interview with expert [35-40 minutes]

  1. (1)

What techniques do you use for discovery and verification in your
investigation? How do you collect the required information?

  2. (2)

How useful are the defined tasks (OSINT macrotasks) in your own
investigations? Please rate each task. Follow-ups:

     * •

Can the student crowd perform the task in the same way? Why/why not?

     * •

How does this setup act differently?

  3. (3)

What are your thoughts about the investigative tasks used in the session? Can
you share examples of where you can incorporate these tasks into your work?

  4. (4)

Why did you choose the particular tasks from the list of tasks for working
with the crowd?

  5. (5)

Only if not answered previously - When would you say that these tasks are
successfully completed?

  6. (6)

What information did you decide to give the crowd before the session? Is there
other information you wish you had given them?

  7. (7)

How did you plan to spend your time during the session, and what did you end
up doing?

  8. (8)

How (if at all) did you interact/communicate with the crowd during the
session? Any major communication issues?

  9. (9)

How well did the students respond to your interventions during the session?

  10. (10)

Any blockers in the collaborative setup?

  11. (11)

Overall, what did you think about the information submitted by the class in
your investigation in terms of quality and quantity?

  12. (12)

Will you use it for your investigation? If yes, how? If not, why not?

  13. (13)

Do you have any experience with crowdsourcing for reporting? If yes, can you
describe your experiences? If not, any particular reason?

  14. (14)

How would you describe the effectiveness of the students (compared to the
general crowd)?

  15. (15)

What did you think about the crowd’s self-evaluation of the submissions?

  16. (16)

What else did you enjoy during this experience?

  17. (17)

What could be improved during this experience?

  18. (18)

Would you want to work with a crowd again this way in the future? Why / why
not?

  19. (19)

Can you provide an example where you could have used the crowd in your
investigation