# Faster Peace via Inclusivity: An Efficient Paradigm to Understand
Populations in Conflict Zones

Jordan Bilich
Remesh
<EMAIL_ADDRESS>
Michael Varga
Remesh
<EMAIL_ADDRESS>
Daanish Masood
United Nations
<EMAIL_ADDRESS>
Andrew Konya
Remesh
<EMAIL_ADDRESS>

###### Abstract

United Nations practice shows that inclusivity is vital for mediation to be
successful in helping end violent conflict and establish lasting peace.
However, current methods for understanding the views and needs of populations
during dynamic situations create tension between inclusivity and efficiency.
This work introduces a novel paradigm to mitigate such tension. In partnership
with collaborators at the United Nations we develop a realtime large-scale
synchronous dialogue process (RLSDP) to understand stakeholder populations on
an hour timescale. We demonstrate a machine learning model which enables each
dialogue cycle to take place on a minute-timescale. We manage a key risk
related to machine learning result trustworthiness by computing result
confidence from a fast and reliable estimation of posterior variance. Lastly,
we highlight a constellation of risks stemming from this new paradigm and
suggest policies to mitigate them.

##  1 Introduction

Violent conflict leads to deaths, poor health, degraded education, inequality,
and economic loss. Since 2011, conflicts worldwide have killed up to 100,000
people a year [1], with indirect deaths estimated to be 3-15 times greater
[2]. By 2030, over half of the world’s poor is projected to be living in
countries affected by high levels of violence [1]. Migration, malnutrition,
destroyed infrastructure, and distressed environments due to conflict lead to
poor health [3], increased infant mortality [4], and decreases in the quality
of childhood education [5]. Conflict tends to disproportionately impact those
with lower socio-economic status, leading to increased economic inequality
[6]. And, the overall economic losses due to conflict have doubled over the
last decade to an estimated $1.02 trillion per year ($3 billion per day) [7].

While ceasefires are helpful in preventing escalation once a conflict has
begun, long-term peace often requires a successful dialogue and mediation
process between the parties. Consequently, over $27b is spent annually on
peacebuilding efforts [7]. Article 33 of the Charter of the United Nations
stresses that “the parties to any dispute, the continuance of which is likely
to endanger the maintenance of international peace and security, shall, first
of all, seek a solution by negotiation, enquiry, mediation, conciliation,
arbitration, judicial settlement” [8]. UN practice shows that for a mediation
and dialogue process to be successful, inclusivity is vital. The UN defines
“inclusivity” as the extent and manner in which the views and needs of
conflict parties and other stakeholders are represented and integrated into
the process and outcome of a [conflict] mediation effort [9]. Given the large
number of stakeholders in most conflicts, mediators are often hard-pressed for
ways to poll the positions, needs, and interests of stakeholder populations.
Further, the reality that the positions of these populations tend to shift, as
the dynamics of a conflict or dialogue process evolve, presents a unique
challenge.

Consequently, mediators have to grapple with potential tensions between
inclusivity and efficiency [10]. Additionally, while machine learning has the
potential to increase efficiency, it is often viewed as too risky for high-
stakes decisions [11], suffering from a lack of result trustworthiness [12].
As a means to decreasing these tensions, in partnership with collaborators at
the UN, we develop a realtime large-scale synchronous dialogue process (RLSDP)
enabled by machine learning and manage risk related to result trustworthiness
by computing result confidence from a reliable estimation of posterior
variance. Further, we highlight risks stemming from this new paradigm and
suggest policies to mitigate them.

##  2 Methods

Dialgoue process. Prior methods to gather the views and needs of stakeholder
populations for inclusivity include asynchronous dialogue platforms, surveys,
focus groups, and social media analysis [10]. However, these methods manifest
a tradeoff between conversational agility and statistical reliability. We aim
to bridge this tradeoff by designing an approach with the agile dynamics of
live conversation at a statistically relevant scale.

We specify a RLSDP to be characterized by a continuous sequence of minute-
scale exchanges between dialogue moderators and a large participating
population. Each minute-scale cycle of the dialogue process includes four
phases:

  1. (i)

An open ended question is sent by the dialogue moderators.

  2. (ii)

The participating population responds with natural language answers then votes
on other participants’ responses.

  3. (iii)

Results are computed which include the fraction of the participating
population predicted to agree with each answer and the confidence of each
prediction.

  4. (iv)

The dialogue moderators review the results and derive learnings which can
inform the next dialogue cycle.

Model. During phase (ii) of the RLSDP we employ two types of voting exercise:
agreement and pair choice. In the first, a participant is shown a response and
asked if they agree with it. We denote the the event that participant $i$
reports agreement with response $j$ by $a_{ij}$, and disagreement by $d_{ij}$.
In the second, the participant is shown two responses and asked which they
prefer. We denote the event that participant $i$ reports preference of
response $j$ over response $k$ by $c_{ijk}$. The minute-scale timing of the
cycle constrains the total number of exercises per person to be on the order
ten. However, the number of participants and thus the number of expected
responses is much larger. As a consequence, the first challenge is reminiscent
of compressed sensing: given a sparse sampling of exercise data, maximize
accuracy in predicting the fraction of participants which agree with each
response.

As a baseline, we consider the representative agent model of choice where each
response has a utility (independent of the participant) $m_{j}$, so that
$p(a_{ij}|m_{j})=\sigma(m_{j})=q_{j}$ [13]. We will refer to this as the
binomial model of choice. A prominent example is of individual-level choice is
probabilistic matrix factorization (PMF) [14], popularized by its success in
the famous Netflix prize competition. In this context, choice is modeled at
the individual level, at the cost of making strict assumptions on the number
of factors involved in decision making. This amounts to an upper bound on the
rank of the participant-to-item utility matrix. A closely related approach,
matrix completion, drops these assumptions and instead uses the low-rank
promoting nuclear norm prior. [15]

Letting
$A=\\{i,j\,|\,a_{ij}\\},D=\\{i,j\,|\,d_{ij}\\},C=\\{i,j,k\,|\,c_{ijk}\\}$, and
denoting the logistic function by $\sigma$, yields the likelihood

$p(A,D,B\,|\,M)=\prod_{i,j\in A}\sigma(m_{ij}+b_{i})\prod_{i,j\in
D}(1-\sigma(m_{ij}+b_{i}))\prod_{i,j,k\in C}\sigma(m_{ij}-m_{ik}).$

We now define the nuclear norm $||\cdot||*$. Let $X\in\mathbb{R}^{d_{1}\times
d_{2}}$ be any arbitrary matrix with singular value decomposition $X=U\Sigma
V^{*}$. Then $||X||*:=\mathrm{tr}(\Sigma)$ is the sum of the positive singular
values $\sigma_{1}\geq\sigma_{2}\geq\dots\geq\sigma_{r}>0$ of $X$. As insig
for nuclear norm minimization in low-rank matrix completion, we remark that
one may also view $||\cdot||_{*}$ as the L1 norm of the vector of singular
values and thus one may roughly translate the sparsity inducing effects of L1
regularization into rank minimizing effects of the nuclear norm.

We apply a uniform prior over the nuclear norm ball of radius $\tau$. Hence
the posterior is

$p(M\,|\,A,D,B)=\frac{1}{Z}p(A,D,B\,|\,M)\cdot\mathbf{1}_{||M||*<\tau}$

$Z:=\int_{\mathbb{R}^{n\times
m}}p(A,D,B\,|\,M)\cdot\mathbf{1}_{||M||*<\tau}\mathrm{d}M.$

The second challenge is to estimate the posterior variance needed to compute
confidence in predictions within the live timescale. Sufficiently simple
models such as the binomial model may admit exact computation of posterior
variance. In the case of more realistic models of individual choice, it is
necessary to make an approximation. The canonical approaches to approximation
of posterior variance and other probabalistic quantities of interest are
variational inference [16], and Markov chain Monte Carlo methods (MCMC) [17].
Recently, stochastic weight averaging (SWA) [18] has emerged as a promising
local approximant to the posterior. Here, we compare SWA and MCMC methods to
obtain confidence estimates in the context of a RLS dialog. For sampling
techniques, it suffices to instead work with the unnormalized posterior
$p(A,B\ |\ M)\mathbf{1}{||M||*<\tau}$. The stochastic weight averaging begins
from an MLE or MAP estimator, and runs stochastic gradient descent at a high
learning rate $\eta=1$. The iterates are taken as a local surrogate for
samples from the posterior.

##  3 Data and Implementation

Experiments were conducted in a low risk environment. Data was obtained from a
sample of 110 participants solicited through the Amazon Mechanical Turk
crowdworking platform. The task description was "participate in a live online
conversation about your experience as a crowdworker." Participants were
instructed to "write a brief, thoughtful response, and evaluate and compare
each others’ responses." They were asked five questions [A1]. For each
question, an average of 136 responses, 1537 agreement exercises, and 1453
pair-choice exercises were collected over the course of 4 minutes.

We implemented the SWA model in PyTorch, and used a Hamiltonian Monte Carlo
(HMC) model with the same loss function using Tensorflow and the Tensorflow
probability library. As a proxy for repeating the data collection with the
same questions and varying duration, the data was split fifty times into
training sets including between 5% and 95% of the data. We used samples from
each model to approximate the posterior standard deviation of the marginal
distribution of agreement for each response
$\frac{1}{N}\sum_{i}\sigma(m_{ij})$. We analytically computed posterior
standard deviation for the binomial model with an uninformative
$\mathrm{Beta}(\frac{1}{2},\frac{1}{2})$ prior for agreement with each
response.

##  4 Results

We compute the accuracy of the model on a holdout set of agreement voting
exercise as the total data-points per participant used to train the model is
varied [figure 1(a)]. An equal number of agreement and choice tasks was
determined to be near optimal [A2] and thus used at training time. Accuracy
increases linearly initially and the levels off at around 15 data points per
participant to about 70-80% using SWA. We note that the parameters obtained
via SWA are significantly better predictors than their HMC counterparts over
all ranges, most likely due to their relative proximity to the MLE.

Confidence is probed by computing the posterior standard deviation of the
marginal distribution of population agreement for each response. We compare
our model trained using SWA and HMC with a representative agent baseline over
a range of data points per participant [figure 1(b)]. Over the entire range
explored our model significantly outperforms the baseline for both training
methods. At 15 data points per person our model yields a one statndard
deviation confidence range of $\pm 1.5\%$. The average mean absolute error
(MAE) between confidence from SWA and HMC is computed for different ranges of
data points per person [table 1]. At less than 2 data points per person SWA
appears to significantly overestimate confidence. As the number of data points
per person increase confidence estimates from SWA and HMC converge, with mean
absolute error converging to about $0.2\%$ at 15 data points per participant.
Over this range, SWA runtimes are observed to be less than $1/100^{th}$ as
long as those from HMC.

Figure 1: Training results as a function of data per participant. Ranges shown
for validation accuracy and posterior standard deviation. Means denoted as
solid line.

(a) Model validation$5$$10$$15$$20$$50\%$$60\%$$70\%$$80\%$data per
participantvalidation accuracySWAHMC

(b) Confidence comparison$5$$10$$15$$20$$0\%$$5\%$$10\%$$15\%$$20\%$data per
participantposterior std. devSWAHMCBinomial

Table 1: Comparison of runtimes and mean absolute error (MAE) between
confidence estimates for SWA and HMC across ranges of data per participant
(DPP). Mean runtime ($s$)
---
DPP | SWA | HMC | MAE
$2.5$-$5$ | $9.44$ | $356.31$ | $9.63\text{\times}{10}^{-3}$
$5$-$7.5$ | $12.33$ | $567.74$ | $7.10\text{\times}{10}^{-3}$
$7.5$-$10$ | $11.10$ | $833.41$ | $5.95\text{\times}{10}^{-3}$
$10$-$12.5$ | $10.45$ | $1186.67$ | $4.77\text{\times}{10}^{-3}$
$12.5$-$15$ | $11.28$ | $1216.39$ | $3.18\text{\times}{10}^{-3}$
$15$-$17.5$ | $10.53$ | $1407.59$ | $1.90\text{\times}{10}^{-3}$
$17.5$-$20$ | $9.82$ | $1809.92$ | $2.03\text{\times}{10}^{-3}$
$20$-$22.5$ | $9.71$ | $1881.24$ | $1.96\text{\times}{10}^{-3}$

##  5 Conclusions, Risks, and Policies

We conclude that at 15 data points per person our ML model predicts the
fraction of a participating population which agrees with a response with
reasonably high confidence and that SWA can be used to reliably estimate
confidence in seconds. This translates to feasibly executing phases ii and iii
of an RLSDP in about 2 minutes. At this timescale, many cycles of an RLSDP can
reliably take place over the course of a one hour dialogue process. Our next
step is to pilot an RLSDP in the context of a mediation process, and impose
de-risking policies, before deploying it into mediation of active conflicts.
If successful deployment of an RLSDP is able to decrease the time to resolve
one major conflict by one week, we estimate it could save 230 lives and $380
million in economic loss [A3].

Any deployment of a realtime large-scale synchronous dialogue process (RLSDP)
warrants managing at least three categories of risk. The first risk is
inaccurate results due to non-representative data. This can result from bias
in questions, disengaged participants, or a participating population which is
not representative. The latter can be the result of poor sampling or malicious
actors. A policy to manage this first risk may include requirements that (a)
dialogue moderators be trained in asking unbiased questions, (b) an
appropriate population sampling and participant validation scheme be applied,
and (c) randomized human verification of general data quality be conducted.
The second risk is inaccurate results due to poor performance of a prediction
model. This can result from a faulty machine learning model or programming
errors. A policy to manage this risk may include the requirement for
appropriate model verification to take place on production deployments. The
third risk is inaccurate conclusions due to misinterpretation of results. This
can happen because the results are interpreted in the absence of proper
context or confidence in the results are miscalibrated. A policy to manage
this risk may include the requirements that (a) proper context be identified
and integrated into the interpretation of results and (b) all ML-based results
include estimates of confidence.

## References

[1] United Nations; World Bank. 2018. Pathways for Peace : Inclusive
Approaches to Preventing Violent Conflict. Washington, DC: World Bank. © World
Bank. https://openknowledge.worldbank.org/handle/10986/28337 License: CC BY
3.0 IGO.

[2] Geneva Declaration Secretariat (2008). Global Burden of Armed Violence.
Geneva Declaration, Available from:
https://www.refworld.org/docid/494a455d2.html (accessed 6 September 2019)

[3] Iqbal, Z. (2006). Health and Human Security: The Public Health Impact of
Violent Conflict. International Studies Quarterly Vol. 50, No. 3 (Sep., 2006),
pp. 631-649

[4] Wagner, Z., Heft-Neal, S., Bhutta, Z. A., Black, R. E., Burke, M., &
Bendavid, E. (2018). Armed Conflict and Child Mortality in Africa: A
Geospatial Analysis. The Lancet. doi:10.1016/s0140-6736(18)31437-5

[5] Kadir, A., Shenoda, S., Goldhagen, J., Pitterman, S. (2018). The Effects
of Armed Conflict on Children: Section on International Child Health.
Pediatrics Dec 2018, 142. (6) e20182586; doi:10.1542/peds.2018-2586

[6] Bircan, C., Brück, T., Vothknecht, M. (2010) Violent conflict and
inequality. IZA Discussion Papers, No. 4990, Institute for the Study of Labor
(IZA), Bonn

[7] Institute for Economics & Peace. (2018). The Economic Value of Peace 2018:
Measuring the Global Economic Impact of Violence and Conflict, Sydney.
Available from: http://visionofhumanity.org/ (accessed 6 September 2019)

[8] United Nations, Charter of the United Nations, 24 October 1945, 1 UNTS
XVI, available at: https://treaties.un.org/doc/publication/ctc/uncharter.pdf
(accessed 06 September 2019)

[9] Strengthening the role of mediation in the peaceful settlement of
disputes, conflict prevention and resolution, UN General Assembly, 66th sess,
Agenda item 34 (a), UN Doc A/66/811 (25 June 2012), available at:
https://peacemaker.un.org/sites/peacemaker.un.org/files/SGReport_Strenghtening-
theRoleofMediation_A66811_0.pdf (accessed 06 September 2019)

[10] United Nations Department of Political and Peacebuilding Affairs and
Centre for Humanitarian Dialogue (2019). Digital Technologies and Mediation in
Armed Conflict.

[11] Rudin, C. (2018). Please Stop Explaining Black Box Models for High-Stakes
Decisions. ArXiv, abs/1811.10154v2

[12] Heinrich, J., Kim, B., Guan, M.Y., Gupta, M. (2018). To Trust Or Not To
Trust A Classifier. 32nd Conference on Neural Information Processing Systems
(NeurIPS 2018), Montréal, Canada

[13] Daniel L. McFadden – Prize Lecture. NobelPrize.org. Nobel Media AB 2019.
Fri. 6 Sep 2019. <https://www.nobelprize.org/prizes/economic-
sciences/2000/mcfadden/lecture/>

[14] Salakhutdinov, R. & Mnih., A. (2007). Probabilistic Matrix Factorization.
In Proceedings of the 20th International Conference on Neural Information
Processing Systems (NIPS’07), J. C. Platt, D. Koller, Y. Singer, and S. T.
Roweis (Eds.). Curran Associates Inc., USA, 1257-1264.

[15] Maddox, W., Garipov, T., Izmailov, P., Vetrov, D.P., & Wilson, A.G.
(2019). A Simple Baseline for Bayesian Uncertainty in Deep Learning. ArXiv,
abs/1902.02476.

[16] Candes, E.J. & Plan, Y. (2010). Matrix Completion With Noise. Proceedings
of the IEEE, 98. 925 - 936. 10.1109/JPROC.2009.2035722.

[17] Wainwright, M.J., & Jordan, M.I. (2008). Graphical Models, Exponential
Families, and Variational Inference. Foundations and Trends in Machine
Learning Vol. 1: No. 1–2, pp 1-305.

[18] Salakhutdinov, R. & Mnih. A. (2008). Bayesian probabilistic matrix
factorization using Markov chain Monte Carlo. In Proceedings of the 25th
international conference on Machine learning, (ICML ’08). ACM, New York, NY,
USA, 880-887. DOI=http://dx.doi.org/10.1145/1390156.1390267

[19] Dupuy, K. & Rustad, S.A. (2018). Trends in Armed Conflict, 1946–2017.
Conflict Trends, 5. Oslo: PRIO.

## Appendix

### A1

Summary of data collected for each question including number of participants,
text responses submitted, agree/disagree votes collected, and number of paired
comparison votes collected. Note that participants could submit multiple text
responses per question.

Question | Participants | Responses | Agree/Disagree | Paired comparisons
---|---|---|---|---
What is your favorite thing to do in your free time? | 111 | 108 | 2030 | 1951
What motivates you the most in life, and why? | 108 | 154 | 1489 | 1367
What will be the most important political issue in 5 years? | 95 | 136 | 1345 | 1262
What could Amazon do to improve your experience on Mechanical Turk? | 101 | 147 | 1283 | 1232

### A2

Validation accuracy in predicting agreement voting exercises as the mixture of
agreement and pair-choice voting exercises was varied and the total voting
exercises was held fix. Ranges shown for validation accuracy with mean denoted
as solid line.

$25\%$$50\%$$75\%$$68\%$$70\%$$72\%$agree-to-total exercise ratiovalidation
accuracySWA

### A3

Taking 100k people killed in conflict per year [1] plus the average of 5 times
more indirect deaths [2] gives a total of 600k deaths per year due to
conflict. We note $1 trillion in economic loss per year [7] and 49 conflicts
per year [19]. This means the average conflict causes about 12k deaths and
$20b in economic loss per year or about 230 deaths and $380m per week.


Some regular signed graphs with only two distinct eigenvalues
Farzaneh Ramezani

Department of Mathematics,

K.N.Toosi University of Technology, Tehran, Iran

P.O. Box 16315-1618
[1]Email<EMAIL_ADDRESS>
We consider signed graphs, i.e, graphs with positive or negative
signs on their edges. We determine the admissible parameters for the $\{5,6,\ldots,10\}$-regular signed graphs which have only two distinct eigenvalues. For each obtained parameter we provide some examples of signed graphs having two distinct eigenvalues. It turns out to construction of infinitely many signed graphs of each mentioned valency with only two distinct eigenvalues. We prove that for any $k\geq 5$ there are infinitely many connected signed $k$-regular graphs having maximum eigenvalue $\sqrt{k}$. Moreover for each $m\geq 4$ we construct a signed $8$-regular graph with spectrum $[4^m,-2^{2m}]$. These yield infinite family of $k$-regular Ramanujan graphs, for each $k$.

Keywords: Signed graphs, two distinct eigenvalues.

Mathematics Subject Classification: 05C50, 05C22.

§ INTRODUCTION

We consider only simple graphs, i.e., graphs with out loops and
multiple edges. A signature
on a graph $\Gamma=(V_{\Gamma},E_{\Gamma})$ is a function $\sigma:E_{\Gamma}\rightarrow \{1,-1\}$. A graph
$\Gamma$ provided with a signature $\sigma$ is called a signed
graph, and will be denoted by $\Sigma=(\Gamma,\sigma)$. We call the graph $\Gamma$ the
ground graph of the signed graph $\Sigma$, and denote it by $|\Sigma|$. Two signed graphs $\Sigma_1$ and $\Sigma_2$
are isomorphic, denoted by $\Sigma_1\cong \Sigma_2$, if there is a graph isomorphism from $|\Sigma_1|$ to $|\Sigma_2|$, which preserves the signs of edges. For a subset $X$ of vertices of a signed graph $\Sigma=(\Gamma,\sigma)$, the signed graph of $\Sigma$ induced on $X$ is a signed graph where the ground is the subgraph of $|\Sigma|$ induced on $X$ where the corresponding sign function is the restriction of $\sigma$ to $E_{\langle X\rangle}$. By $\Sigma\setminus X$ we mean the signed graph induced on $V_{|\sum|}\setminus X$. With a signed $k$-regular graph, we mean a signed graph whose ground is $k$-regular. For a graph $\Gamma$, by $\Gamma^+$ (resp. $\Gamma^-$) we mean the all positive (resp. the all negative) signed graph with ground $\Gamma$. For a signed graph $\Sigma=(\Gamma,\sigma)$, by $-\Sigma$, we mean the signed graph $(\Gamma,-\sigma)$.

The adjacency matrix, $A_{\Sigma}$ of the signed graph $\Sigma=(\Gamma,\sigma)$ on
the vertex set $V=\{v_1,v_2,\ldots,v_n\}$, is an $n\times n$
matrix whose entries are
\begin{array}{ll}
\sigma(v_iv_j), & \hbox{if $v_i$ is adjacent to $v_j$;} \\
0, & \hbox{otherwise.}
\end{array}
\right.
The ordinary adjacency matrix of the graph $\Gamma$, is denoted by $A_{\Gamma}$. Whose entries
are the absolute values of the entries of $A_{\Sigma}$.

The spectrum of a signed graph is the eigenvalues of its
adjacency matrix and will be denoted by $[\lambda_1^{m_1},\lambda_2^{m_2},\ldots,\lambda_s^{m_s}]$, where $m_i$ is the multiplicity of eigenvalue $\lambda_i$, for $i=1,2,\ldots,s$. By $m(\lambda)=m_{\Sigma}(\lambda)$, we denote the multiplicity of $\lambda$ as an eigenvalue of the signed graph $\Sigma$. By $O_n$, $J_n$ and $I_n$, we mean the all zero
matrix, all one matrix, and identity matrix of order $n$,
respectively. If $n$ is already known, then we
simply use $O,J,I$. For a matrix $X$ of order $m\times n$, by $X_i$ we mean the $i$th row of $X$, for $i=1,2,\ldots,m$.

An $n\times n$ matrix $C$, with $(0,\pm 1)$-entries is called a weighing matrix, if $CC^t=C^tC=\alpha I_n$, where $\alpha$ is a positive integer, called the weight of the weighing matrix $C$. A signed graph is called weighing if its adjacency matrix is a weighing matrix. Weighing matrices are well studied in the literature and several constructions and examples are known, see for instance [7, 15, 16].

The following is definition of a FSRSG which is introduced in [19] and updated in [20].
A signed regular graph $\Sigma$ is called FSRSG
whenever it satisfies the following conditions:

(i) $|\Sigma|$ is $k$-regular, with $n$ vertices,

(ii) if $\Sigma$ contains at least one positive edge, then there
exist $t\in \mathbb{Z}$ such that $t_{xy}^+-t_{xy}^-=t$, for any edges $xy$,

(iii) there exist $\rho\in \mathbb{Z}$ such that
$\rho_{xy}^+-\rho_{xy}^-=\rho$, for all non-adjacent vertices $x$ and $y$, where $\rho_{xy}^+$, $\rho_{xy}^-$ are the numbers of positive
and negative length two paths joining the vertices. We denote a FSRSG having just mentioned parameters with FSRSG$(n,k,t,\rho)$.

We refer to a signed graph with only two distinct eigenvalues, by STE. The following is a general determination of STE's. The result is independently obtained in [19] and [21].

A signed graph is a STE if and only if it is a FSRSG with $\rho=0$.

Recently some problems on the spectrum of signed adjacency matrices have attracted many studies. The authors of [3] has settled few open problems in the spectral theory of signed graphs. The construction problem of STE's is also mentioned there. There  are some results on the problem in literature, see [13, 18, 19, 21]. It is known that the only graphs with two distinct eigenvalues of the ordinary adjacency matrix are the complete graphs, which is extensively far from the known results for the signed graphs. We consider the same problem for signed graphs. We use the well known method, called the star complement technique, for construction of STE's. For more details on the notions and definitions see [4, 22]. It is well adopted for the family of signed graphs as well as any other symmetric matrices, see [2, 19]. During the preparation of this paper we encounter interesting results from other combinatorial areas such as symmetric weighing matrices, Hadamard matrices, Conference matrices and Ramanujan graphs.

§ PRELIMINARIES

The adjacency matrix of a FSRSG satisfies a quadratic equation of the form

\begin{equation}\label{qu1}
A_{\Sigma}^2-tA_{\Sigma}-kI=\rho \overline{A},
\end{equation}

where $\overline{A}$ is the complement of $|\Sigma|$, and $t$, $k$, $\rho$ are as in the definition of FSRSG's. From the equality (<ref>), for any STE the corresponding $\rho$ parameter leads to be zero, hence for the adjacency matrix of a STE, the following equality must hold.

\begin{equation}\label{qu2}
\end{equation}

Therefore the eigenvalues of a STE must be as follows.
$$\lambda_1=\frac{t+\sqrt{t^2+4k}}{2},\hspace{0.7 cm}\lambda_2=\frac{t-\sqrt{t^2+4k}}{2}.$$

From now on, we denote $t^2+4k$, by $b$. It is well-known that if a monic integral polynomial admits a non-integral root $\alpha$, then $\alpha$ is irrational and the algebraic conjugate of $\alpha$ is a root of the polynomial with the same multiplicity.  This leads to the following useful lemma.

Let $\Sigma=(\Gamma,\sigma)$ be a STE, then one of the followings holds.

* $t=0$ and $A_{\Sigma}$ is a weighing matrix of weight $k$, or

* $t\neq 0$, then $b$ must be a perfect square.

Proof. The first part follows by putting $t=0$, in (<ref>). For the second part as contradiction suppose that $b$ is not a perfect square, so $\frac{-t+\sqrt{b}}{2}$ is irrational. Therefore since the characteristic polynomial of $\Sigma$ is a monic integral polynomial, the algebraic conjugate of $\frac{-t+\sqrt{b}}{2}$, that is, $\frac{t-\sqrt{b}}{2}$ must be an eigenvalue of $\Sigma$ with the same multiplicity, say $m$. By the assumption $\Sigma$ has the spectrum $(\frac{t+\sqrt{b}}{2})^m$, $(\frac{t-\sqrt{b}}{2})^m$. On the other hand trace of $A_{\Sigma}$ is zero, thus we have the following equality,
which implies $mt=0$, so $t=0$, a contradiction. Hence $b$ must be a perfect square. $\square$

Note that in a signed $k$-regular graphr, $t$ may be an integer in the interval $[-k+1,k-1]$. Regarding the previous statements a triple $(t,\lambda_1,\lambda_2)$ is called admissible for a STE, if for $k=-\lambda_1\lambda_2$, either $b=t^2+4k$ is a perfect square or $t$ is zero. With a simple calculation we observe the following.

The following parameters are all possible admissible $(t,\lambda_1,\lambda_2)$'s of the STE's with valencies $5,6,\ldots,10$.

$k=5$     ($4,$ $5,$ $-1$),   ($0,$ $\sqrt{5},$$-\sqrt{5}$),  ($-4,$ $1$,$-5$)
$k=6$     ($5,$  $6$, $-1$),  ($1,$  $3$, $-2$),  ($0,$ $\sqrt{6}$, $-\sqrt{6}$),   ($-1,$   $2$, $-3$),  ($-5,$  $1$, $-6$)
$k=7$      ($6,$ $7,$ $-1$),  ($0,$ $\sqrt{7},$$-\sqrt{7}$),  ($-6,$ $1,$ $-7$)
$k=8$     ($7,$ $8,$ $-1$),  ($2,$ $4,$ $-2$), ($0,$ $\sqrt{8},$$-\sqrt{8}$),  ($-2,$ $-4,$ $2$), ($-7,$ $1,$ $-8$)
$k=9$      ($8,$ $9,$ $-1$),  ($0$, $3$, $-3$),  ($-8,$ $1,$ $-9$)
$k=10$     ($9,$ $10,$ $-1$),  ($3,$ $5,$ $-2$),  ($0,$ $\sqrt{10},$$-\sqrt{10}$),  ($-3,$ $2,$ $-5$),  ($-9,$ $1,$ $-10$)

$$\textbf{Table 1.} \textrm{The admissible parameters for the  STE's with $\{5,6,\ldots,10\}$-regular grounds}$$

The notion of line of signed graphs is defined in [25]. The line graph of $\Sigma$ is the signed graph $\Lambda(\Sigma)=(\Lambda(G),\sigma_{\Lambda})$, where $\Lambda(G)$ is the ordinary
line graph of the underlying graph and $\sigma_{\Lambda}$ is a sign function such that every cycle in $\Sigma$ becomes a cycle
with the same sign in the line graph, and any three edges incident with a common vertex become a
negative triangle in the line graph. The adjacency matrix is $A_{\Lambda(\Sigma)} = 2I_m-H(\Sigma)^tH(\Sigma)$. Where $H(\Sigma)$ is the incidence matrix of a signed graph $\Sigma$ on $n$ vertices with $m$ edges, which is defined in [24], as follows. It is the $n\times m$ matrix $H(\Sigma)=[\eta_{i,j}]$, where

\begin{array}{ll}
0, & \hbox{if $v_i$ is not incident with $e_j$;} \\
\pm 1, & \hbox{if $v_i$ is incident with $e_j$.}
\end{array}
\right.

such that for an edge $v_iv_j$, the equality $\eta_{ik}\eta_{jk}=\sigma(v_iv_j)$ holds. The incidence matrix
is unique up to negation of columns.
The following theorem from <cit.> will be useful.

Assume $\Sigma$ is a signed $k$-regular graph. Let the eigenvalues of $\Sigma$
be $\lambda_1$, $\ldots$, $\lambda_{b(-\Sigma)}=-k$, $-k<\lambda_{b(-\Sigma)+1},\ldots,\lambda_{n-b(\Sigma)}<k$, and $\lambda_{n-b(\Sigma)},\ldots \lambda_n=k$.
The line graph $\Lambda(\Sigma)$ has eigenvalues $\lambda_{b(-\Sigma)+1}-k+2,\ldots, \lambda_{n-b(\Sigma)}-k+2$  and eigenvalue $2$ with multiplicity $m-n+b(\Sigma)$.

Note that $b(\Sigma)$ is the number of balanced components of $\Sigma$.

§.§ The star complement technique

In the following we will summarize the method which is extensively surveyed in [4, 22].

Let $A$ be an $n\times n$ matrix, and $\mu$ be an eigenvalue of $A$ having multiplicity $k$. A $k$-subset $X$ of the vertex set is called a star set if the sub-matrix of $A$, obtained by removing rows and columns corresponding to $X$ does not have $\mu$ as an eigenvalue. In signed graph context, a star set for an eigenvalue $\mu$ in a signed graph $\Sigma$ is a subset $X$ of vertices such that $\mu$ is not an eigenvalue of $\Sigma\setminus X$. The signed graph $\Sigma\setminus X$ is called a star complement for $\mu$ in $\Sigma$. The following theorem, known as the reconstruction theorem, will be useful later.
[4]  Let $X$ be a set of $k$ vertices in a signed graph $\Sigma$ and suppose the matrix $A_{\Sigma}$ is of the following form

\begin{array}{cc}
A_X & B \\
B^t & C \\
\end{array}
\right),$$
where $A_X$ is the adjacency matrix of the signed graph of $\Sigma$ induced on $X$. Then $X$ is a star set for $\mu$ in $\Sigma$ if and only if $\mu$ is not an eigenvalue of $C$ and
$$\mu I-A_X=B(\mu I-C)^{-1}B^t.$$

The star complement method will also be used for the construction of STE's, we state the following immediate consequence of Theorem <ref> and the fact that any real symmetric matrix has a partition to star complements, [6], with out proof.

A signed graph $\Sigma$ on $n$ vertices, have spectrum $[\lambda_1^a,\lambda_2^{n-a}]$ if and only if the vertex set of $\Sigma$ has a partition $X,Y$  such that the matrix $A_{\Sigma}$ can be written as the following
\begin{array}{cc}
A_X & B \\
B^t & A_Y \\
\end{array}
\right),
such that $A_X$ ($A_Y$) doesn't have eigenvalue $\lambda_1$ ($\lambda_2$) and the following equalities hold.
$$\lambda_2 I-A_X=B(\lambda_2 I-A_Y)^{-1}B^t, \hspace{1cm}\lambda_1 I-A_Y=B^t(\lambda_1 I-A_X)^{-1}B.$$

§ CONSTRUCTIONS

We have the following consequence of Theorem <ref> for the line graph of the all positive complete graph.

Let $\Sigma$ be the all positive signed graph on the complete graph $K_n$, that is $K_n^+$. Then $\Lambda(K_n^+)$ is a signed graph with the following spectrum.
$$[(2-n)^{n-1},2^{{n\choose 2}-n+1}].$$
Moreover the spectrum of the signed graph $-\Lambda(K_n^+)$ is
$$[(n-2)^{n-1},(-2)^{{n\choose 2}-n+1}].$$

Proof. It follows by Theorem <ref> and the fact that $K_n^+$ has spectrum $[(n-1)^1, -1^{n-1}]$. $\square$

Note that the admissible $(t,\lambda_1,\lambda_2)$ parameters of STE's on $k$-regular graphs, with $5\leq k\leq 10$, presented in Table $1$, have the following general types. We will treat each of them seperately.

* Type 1. $(n-2,n-1,-1)$, or its negation $(-n+2,1,-n+1)$,

* Type 2. $(\frac{k}{2}-2,\frac{k}{2},-2)$, or its negation $(-\frac{k}{2}+2,2,-\frac{k}{2})$,

* Type 3. $(0,\sqrt{k},-\sqrt{k})$.

Where $n$, $k$ respectively denote the number of vertices, and valency of the signed graph $\Sigma$ which is an STE with the given parameters.

We recall that in a STE's we have $k=-\lambda_1\lambda_2$ and $t=\lambda_1+\lambda_2$. Also from the triples $(t,\lambda_1,\lambda_2)$ and $(-t,-\lambda_1,-\lambda_2)$, we only need to treat one of them, as if $\Sigma$ is a STE with parameters $(t,\lambda_1,\lambda_2)$, then $-\Sigma$ have parameters $(-t,-\lambda_2,-\lambda_1)$. Note also the only signed graphs posing the parameters $(n-2,n-1,-1)$ are the all positive complete graph. Thus we only need to consider the two remained cases.

§.§ STE's with parameters $\mathbf{(\frac{k}{2}-2,\frac{k}{2},-2)}$

We will present two family of examples of STE's posing the parameters $(\frac{k}{2}-2,\frac{k}{2},-2)$. First we assert the following relation on the multiplicities of the eigenvalues of STE's having the parameters $(\frac{k}{2}-2,\frac{k}{2},-2)$, which follows by considering the trace of $A_{\Sigma}$.
$$m(\frac{k}{2})=\frac{4n}{4+k},\hspace{0.7cm} m(-2)=\frac{nk}{4+k}.$$

The followings hold.

* The signed graph $\Lambda(K_{5})$ is $6$-regular, having spectrum $[3^4, -2^6]$.

* The signed graph $\Lambda(K_{6})$ is $8$-regular, having spectrum $[4^5, -2^{10}]$.

* The signed graph $\Lambda(K_{7})$ is $10$-regular, having spectrum $[5^6, -2^{15}]$.

Proof. The assertion follows by Proposition <ref>. $\square$

The following is a signed graph with spectrum $[3^4, -2^6]$.

[regular polygon,regular polygon sides=,minimum size=5cm] (p) ;
in 1,...,[mystyle] (p) at (p.corner );
in 1,...,-1
(p1) – (p6)[red];
(p1) – (p7)[red];
(p1) – (p9)[red];
(p1) – (p5)[blue];
(p1) – (p8)[blue];
(p1) – (p10)[blue];
(p2) – (p4)[blue];
(p2) – (p7)[blue];
(p2) – (p8)[blue];
(p2) – (p3)[red];
(p2) – (p5)[red];
(p2) – (p9)[red];
(p3) – (p4)[blue];
(p3) – (p5)[blue];
(p3) – (p9)[blue];
(p3) – (p6)[red];
(p3) – (p10)[red];
(p4) – (p6)[red];
(p4) – (p10)[red];
(p4) – (p7)[blue];
(p4) – (p8)[blue];
(p5) – (p9)[blue];
(p5) – (p8)[blue];
(p5) – (p10)[blue];
(p6) – (p9)[blue];
(p6) – (p7)[blue];
(p6) – (p10)[blue];
(p7) – (p9)[blue];
(p7) – (p8)[blue];
(p8) – (p10)[blue];

$$\textbf{Figure 1.} \textrm{ The signed graph $-\Lambda(K_5)$}$$

§.§ $8$-regular signed graphs with spectrum $4^m,-2^{2m}$

Using Proposition <ref>, we find out the signed graph $\Lambda(K_6)$ has spectrum $4^5,-2^{10}$. At this part using Proposition <ref>, we construct STE's with spectrum $4^m,-2^{2m}$. The following lemma has crucial role in that regard.

Let $W_1$, $W_2$ be two weighing matrices of order $m$ and weight $4$. The following matrix has spectrum $[4^m,-2^{2m}]$.

\begin{array}{ccc}
O_m & W_1 & W_2 \\
W_1^t & O_m & \frac{1}{2}W_1^tW_2 \\
W_2^t & \frac{1}{2}W_2^tW_1 & O_m \\
\end{array}
\right).$$

Proof. We prove that the subset $\{1,2,\ldots,m\}$ is a star set for $4$, and the subset $\{m+1,m+2,\ldots,3m\}$ is a star set for $-2$. Let $C_1$, $C_2$ be the submatrices corresponding to the mentioned vertex sets respectively. That is,
$$C_1=O_m,\textrm{ and }C_2=\left(
\begin{array}{cc}
O_m& \frac{1}{2}W_1^tW_2 \\
\frac{1}{2}W_2^tW_1 & O_m\\
\end{array}
\right).
We set $B=(W_1|W_2)$, now by Theorem <ref>, it suffices to prove the following equalities.

By a simple calculation we obtain the following equality,
\begin{array}{cc}
\frac{1}{3}I_m & \frac{W_1^tW_2}{24} \\
\frac{W_2^tW_1}{24}  & \frac{1}{3}I_m  \\
\end{array}
\right).

Therefore we obtain the followings by the view of the equalities $W_1W_1^t=W_2W_2^t=4I_m$.
\begin{array}{cc}
\frac{1}{3}I_m & \frac{W_1^tW_2}{24} \\
\frac{W_2^tW_1}{24}  & \frac{1}{3}I_m  \\
\end{array}
\right)\left(
\begin{array}{c}
W_1^t \\
W_2^t \\
\end{array}
\right)=(W_1|W_2)\left(\begin{array}{c}
\frac{1}{2}W_1^t \\
\frac{1}{2}W_2^t \\

\end{array} \right)=4I_m.$$

Thus the first equality holds, now we prove the second equality. Note that $(-2I_{n}-C_1)^{-1}=\frac{-1}{2}I_n$, therefore we need to prove the following so that the assertion follows.
\begin{array}{c}
W_1^t \\
W_2^t \\
\end{array}
\right)(W_1|W_2)=\frac{-1}{2}\left(
\begin{array}{cc}
W_1^tW_1 & W_1^tW_2\\
W_2^tW_1 &  W_2^tW_2  \\
\end{array}
\right)=-2I_{2m}-C_2.

Now the assertion follows by Theorem <ref>. $\square$

If the weighing matrices $W_1$ and $W_2$ are chosen so that the matrix $\frac{1}{2}W_1^tW_2$ has $0,\pm 1$ entries, or equivalently the matrix $W_1^tW_2$ has $0,\pm 2$ entries, then the matrix $\mathcal{A}(W_1,W_2)$ is corresponding to a $8$-regular graph on $3m$ vertices, having spectrum $[4^m,-2^{2m}]$.

If two weighing matrices $W_1$ and $W_2$ of weight $4$ are so that the matrix $W_1^tW_2$ has $0,\pm 2$ entries, then we call them semi-orthogonal weighing matrices. In the following we provide examples of semi-orthogonal weighing matrices of any even order $m\geq 6$. We should mention that a family of weighing matrices of even order is presented in [7], but our method provides a different matrix. We make use of the following two pattern matrices $X$ and $Y$ of order $\frac{m}{2}$. For $i,j=1,2,\ldots,\frac{m}{2},$ the $(i,j)$'th entries of $X$ and $Y$ follows.

\begin{array}{cc}
\begin{array}{ll}
1, &j-i\equiv 0,1 \hbox{ mod }\frac{m}{2};  \\
0, & \hbox{other wise.}
\end{array}
\right. & \hspace{0.5cm}Y(i,j)=\left\{
\begin{array}{ll}
1, &j-i\equiv 1, \frac{m}{2}-2 \hbox{ mod }\frac{m}{2};  \\
0, & \hbox{other wise.}
\end{array}
\right. \\
\end{array}

Note that the matrices $X,Y$ have two entry $1$ at each row and each column. Moreover $X,Y$ do not share a common entry $1$. We define the matrix $W_1$, similarly $W_2$ as the following.

* The first $\frac{m}{2}\times m$ block of $W_1$, say $F=F_X$, is filled as follows. In fact the matrix $X$ is expanded to the matrix $F$ of size $\frac{m}{2}\times m$. For $i,j=1,2,\ldots,\frac{m}{2},$ if $X(i,j)=0$, then replace the $(i,j)$'th entry of $X$ with $[0,0]$, for $j=1,2,\ldots,m/2$ if in the $j$'th column the one entries occur in the coordinates $(i_0,j)$, and $(i_1,j)$, where $i_0<i_1$, then replace the $(i_0,j)$'th entry with $[1,1]$, and the $(i_1,j)$'th entries with $[1,-1]$.

* The next $\frac{m}{2}\times m$ block of $W_1$, say $R=R_X$, is filled as follows. The entries of $R_X$ in the corresponding zero coordinates of $F_X$ are zero. For $i=1,2,\ldots,\frac{m}{2},$ if non-zero entries of $F_X$ occur in the coordinates $(i,j_0)$, $(i,j_1)$, $(i,j_2)$, $(i,j_3)$, where $j_0<j_1<j_2<j_3$, then we set
$$R_X(i,j_0)=F_X(i,j_0), R_X(i,j_1)=F_X(i,j_1),$$

$$ R_X(i,j_2)=-F_X(i,j_2), R_X(i,j_3)=-F_X(i,j_3).$$

Now set $W_1$ to be the $m\times m$ matrix, $\left(
\begin{array}{c}
F \\
R \\
\end{array}
\right)
$. The matrix $W_2$ is constructed similarly by considering $Y$ instead of $X$. See the following matrices for illustration.

$${\scriptsize X=\left(
\begin{array}{ccccccc}
1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 \\
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 \\
\end{array}
\right),\hspace{1cm}Y=\left(
\begin{array}{ccccccc}
0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 \\
1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 \\
1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
\end{array}
\right).}

$${\scriptsize F_X=\left(
\begin{array}{cccccccccccccc}
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 \\
1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - \\
\end{array}
\right)\hspace{0.5cm}R_X=\left(
\begin{array}{cccccccccccccc}
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} - &\hspace{-0.2cm} - \\
1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 \\
\end{array}
\right)}

$${\scriptsize F_Y=\left(
\begin{array}{cccccccccccccc}
0&\hspace{-0.2cm}0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0&\hspace{-0.2cm}0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm} 1 \\
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- \\
1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
\end{array}
\right), \hspace{0.5cm}R_Y=\left(
\begin{array}{cccccccccccccc}
0&\hspace{-0.2cm}0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm}- &\hspace{-0.2cm} 0&\hspace{-0.2cm}0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm} - \\
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm}1 \\
1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
\end{array}
\right).}$$

$${\scriptsize W_1=\left(
\begin{array}{cccccccccccccc}
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 \\
1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - \\
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} - &\hspace{-0.2cm} - \\
1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} - &\hspace{-0.2cm} - &\hspace{-0.2cm} 1 \\
\end{array}
\right),\hspace{0.5cm}W_2=\left(
\begin{array}{cccccccccccccc}
0&\hspace{-0.2cm}0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0&\hspace{-0.2cm}0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm} 1 \\
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- \\
1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0&\hspace{-0.2cm}0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm}- &\hspace{-0.2cm} 0&\hspace{-0.2cm}0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm} - \\
1 &\hspace{-0.2cm} 1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm} - &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 \\
0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm}0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm}1 \\
1&\hspace{-0.2cm}- &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} -&\hspace{-0.2cm}1 &\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0&\hspace{-0.2cm} 0 &\hspace{-0.2cm} 0 \\
\end{array}
\right).}

We now prove some properties of the obtained matrices.

The matrix $W_1$, $(W_2)$ obtained above, is a weighing matrix of weight four.

Proof. We first prove that $W_1$ is orthogonal. Equivalently we prove that any two distinct rows of $W_1$ are orthogonal. We first treat rows of $R$ and $F$ separately. Let $F_i$, $F_j$ be the $i$th and $j$th rows of $F$ respectively ($i<j$). Then one of the followings hold.

* The $1$ entries of $X_i$ and $X_j$ occur on different column. In this case, $F_i$, $F_j$ wouldn't have common columns of non-zero entries, which means they are orthogonal.

* $X_i(k)=X_j(k)=1$ for only one column number, say $1\leq k\leq m$. In this case, by the definition we have $F(i,2k-1)=F(i,2k)=1$, while $F(j,2k-1)=1$, $F(j,2k)=-1$. But for the other entries, $l\neq 2k-1,2k$ either of $F_i(l)$ or $F_j(l)$ are zero, hence we have

Thus $F_i$ and $F_j$ are orthogonal.

The orthogonality of row vectors of $R$ can be seen similarly. Now we prove that for any $i,j=1,\ldots,m/2$, the vectors $F_i$ and $R_j$, are orthogonal. The following two cases may occur.

* $i=j;$ In this case, by the definition, we have

Where $j_0,j_1$ are the numbers of non-zero columns of $X_i$. Hence $F_i.R_i=F(i,2j_0-1)^2+F(i,2j_0)^2-F(i,2j_1-1)^2-F(i,2j_1)^2=1+1-1-1=0.$

* $i\neq j;$ In this case either $X_i$, $X_j$, and then $R_i$, $F_j$ have no common column having non-zero coordinates or $X_i$, $X_j$ share only one common column of non-zero elements. In the former case $R_i$, $F_j$ have zero inner product, indeed. In the case that $X_i$, $X_j$ share only one common column of non-zero elements, let $k$ be the index of the common column of non-zero entry. By the definition we will have $X_i(k)=X_j(k)=1$, so at first we have $F_j(2k-1)=F_i(2k-1),$ $F_j(2k)=-F_i(2k-1),$ now depending on the occurrence of $k$, one of the followings may occur:
$$R_j(2k-1)=F_i(2k-1)\textrm{, }R_j(2k)=-F_i(2k-1), \textrm{ or }$$

$$R_j(2k-1)=-F_i(2k-1)\textrm{, }R_j(2k)=F_i(2k-1).$$
In both cases the orthogonality of $F_i$ and $R_j$ follows.

Note that the matrix $X$ has two $1$ entries at each row and column, and in $W_1$, any entry $1$ of $X$ is replaced with $[1,1]$ or $[1,-1]$. Hence each row and column of $W_1$ has four entries equal to $\pm 1$, then $W_1$ has weight four, as desired. $\square$

Now we prove the semi-orthogonality of $W_1$, and $W_2$.

The matrices $W_1$ and $W_2$ are semi-orthogonal.

Proof. It suffices to prove for any appropriate $i,j$ the inner product of the $i$'th row of ${W_1}$ with the $j$'th row of ${W_2}$ is equal to $0,\pm 2$. Note that the matrices $X$ and $Y$ is chosen so that they never have equal rows. This implies that $X_i$ and $Y_j$ have at most one common $1$-entry. Hence the $i$'th row of ${W_1}$ and the $j$'th row of ${W_2}$ has either no common columns having non-zero coordinate or exactly two common columns having non-zero coordinates. In both cases depending on the corresponding entries, the inner product may be $0,$ or $\pm 2$. $\square$

The above statements result in the following theorem.

Let $W_1$, and $W_2$ be two semi-orthogonal weighing matrices of order $m$. Then the signed graph with adjacency matrix $\mathcal{A}(W_1,W_2)$ has spectrum $[4^{m},-2^{2m}]$.

Using Lemma <ref> and the mentioned construction of matrices $W_1$ and $W_2$ we may construct signed $8$-regular graphs on $3m$ nods, ($m$ even) having  spectrum $[4^m,-2^{2m}]$, for $m\geq6$. Using computer search we find the following instance with $12$ vertices.

[regular polygon,regular polygon sides=,minimum size=6cm] (p) ;
in 1,...,[mystyle] (p) at (p.corner );
in 1,...,-1
in ,...,
(p1) – (p5)[red];
(p1) – (p11)[red];
(p1) – (p8)[blue];
(p1) – (p7)[red];
(p1) – (p12)[red];
(p1) – (p9)[red];
(p1) – (p10)[red];
(p1) – (p6)[red];
(p5) – (p3)[blue];
(p5) – (p11)[red];
(p5) – (p12)[blue];
(p5) – (p9)[blue];
(p5) – (p10)[blue];
(p5) – (p2)[red];
(p5) – (p4)[red];
(p3) – (p8)[blue];
(p3) – (p11)[red];
(p3) – (p6)[red];
(p3) – (p7)[blue];
(p3) – (p12)[red];
(p3) – (p9)[blue];
(p3) – (p10)[blue];
(p8) – (p11)[red];
(p8) – (p12)[red];
(p8) – (p2)[red];
(p8) – (p4)[blue];
(p8) – (p9)[red];
(p8) – (p10)[blue];
(p2) – (p11)[blue];
(p11) – (p4)[blue];
(p11) – (p6)[blue];
(p11) – (p7)[blue];
(p8) – (p6)[blue];
(p6) – (p2)[red];
(p6) – (p4)[blue];
(p6) – (p9)[red];
(p6) – (p10)[blue];
(p7) – (p12)[red];
(p7) – (p4)[blue];
(p7) – (p9)[blue];
(p7) – (p10)[blue];
(p7) – (p2)[blue];
(p12) – (p4)[red];
(p12) – (p2)[red];
(p9) – (p2)[blue];
(p9) – (p4)[red];
(p10) – (p2)[red];
(p10) – (p4)[blue];

$$\textbf{Figure 2.}\textrm{ A signed graph with spectrum } [4^4,-2^8],$$

§.§ STE's with parameters $\mathbf{(0,\sqrt{k},-\sqrt{k})}$

Signed graphs with spectrum $\sqrt{k}^{\frac{n}{2}},-\sqrt{k}^{\frac{n}{2}}$ are in correspondence with symmetric weighing matrices. Symmetric weighing matrices of small weights have been studied extensively and some constructions are announced, for more details see [7, 15, 16]. Recently Huang [14]
has proved the Sensitivity Conjecture from theoretical computer science, by presenting a special signing of hypercubes. The obtained signed hypercubes admit spectrum $\pm\sqrt{k}$. His method is improved in [3] to a construction of symmetric weighing matrices. The following is their construction.

[3] If $\Sigma$ is a signed $k$-regular graph of order $n$ with spectrum $[\sqrt{k}^{\frac{n}{2}},-\sqrt{k}^{\frac{n}{2}}]$, then the following is the adjacency matrix of a signed $(k+1)$-regular graph with spectrum $\sqrt{k+1}^{n},-\sqrt{k+1}^{n}$.
\begin{array}{cc}
A_{\Sigma} & I_n \\
I_n & -A_{\Sigma} \\
\end{array}
\right).

In [13] the authors have provided a family containing infinitely many signed $4$-regular graphs having just two distinct eigenvalues $2,-2$. More precisely for each $m\geq3$, they construct a signed $4$-regular graph with spectrum $[2^m,-2^m]$. We call their examples, the $4$STE's. This yields the following result.

For any $k\geq 4$ there are infinitely many connected signed $k$-regular graphs with distinct eigenvalues $\pm\sqrt{k}$.

Proof. Note the graph $K_2$ has spectrum $\pm1$. Now repeatedly applying Theorem <ref>, for any positive $k$ we find a signed $k$-regular graph with distinct eigenvalues $\pm\sqrt{k}$. It is easily seen that the grounds of the signed graphs which are just constructed, are connected. As already discussed for any $m\geq3$, a signed $4$-regular graph with spectrum $[2^m,-2^m]$ exists. Let $\Sigma$ be a signed graph with spectrum $[2^m,-2^m]$. Then $Ac(\Sigma)$ would give a signed graph with spectrum $[\sqrt{5}^{2m},-\sqrt{5}^{2m}]$. By repeating the procedure we get a signed graph with spectrum $[\sqrt{6}^{4m},-\sqrt{6}^{4m}]$, $[\sqrt{7}^{8m},-\sqrt{7}^{8m}]$, $\ldots$, $[\sqrt{k}^{2^{k-4}m},-\sqrt{k}^{2^{k-4}m}]$. Since $m$ belongs to an infinite set of integer numbers hence the assertion follows. $\square$

The above theorem provides an infinite family of connected signed $k$-regular graphs having eigenvalues $\pm\sqrt{k}$. The ground of the mentioned graphs are bipartite. By the similar construction, starting with a symmetric conference matrix of order $6$, we provide other examples of signed $k$-regular graphs having eigenvalues $\pm\sqrt{k}$. In this case the ground is not bipartite. The following is the corresponding signed $5$-regular graph.

[regular polygon,regular polygon sides=,minimum size=4cm] (p) ;
in 1,...,[mystyle] (p) at (p.corner );
in 1,...,-1
in ,...,
(p) – (p)[blue];
(p2) – (p3)[red];
(p2) – (p4)[red];
(p3) – (p5)[red];
(p4) – (p6)[red];
(p5) – (p6)[red];

$$\textbf{ Figure 3. }\textrm{The Pentagon, its spectrum is }[\sqrt{5}^3,-\sqrt{5}^3] $$

Therefore we have the following result.

For any $k\geq 5$ there is a signed $k$-regular graph on $3.2^{k-5}$ vertices with distinct eigenvalues $\pm\sqrt{k}$, in which the ground is not bipartite.

Proof. By applying the method stated in Theorem <ref>, on the signed graph of Figure $3$, the assertion follows. $\square$

§.§ Concluding Remarks

The vertex number of STE's which are provided at this paper are summarized at the following table. We proposed two infinite families of connected STE's.

$(t,\lambda_1,\lambda_2)$      number of vertices of instances
$(1,3,-2)$     $10$

$(2,4,-2)$     $15$, $6q$, $q\geq2$

$(3,5,-2)$     $21$

$(0,\sqrt{k},-\sqrt{k})$    $3.2^{k-4}$, $2^{k-3}m$, $m=3,4,\ldots$

In [5] the authors have conjectured that every connected $k$-regular graph $\Gamma$ has a sign function $\sigma$ such that the maximum spectrum of the corresponding signed graph is at most $2\sqrt{k-1}$. Then they propose to construct new families of Ramanujan graphs by using lift of graphs. Our instance of signed $8$-regular graphs have maximum eigenvalue $4$, which is smaller than $2\sqrt{7}$. Hence an infinite family of $8$-regular Ramanujan graphs can be constructed. Also by Theorem <ref> for any $k\geq 4$ an infinite family of signed graphs with maximum eigenvalue $\sqrt{k}$ is constructed, which again yields an infinite family of $k$-regular Ramanujan graphs.

Moreover it is well-known that the Kronecker product of two weighing matrices of orders $m$, $n$, and weights $\alpha,\beta,$ respectively, yields an orthogonal matrix of order $mn$, with weight $\alpha\beta$. Hence by the Kronecker product of the known weighing matrices with the above obtained matrices some new instances will be constructed.

[1]
B.D. Acharya, Spectral criterion for cycle balance in
networks, J. Graph Theory 4(1) (1980) 1–11.

[2]
F. Belardo, E. M. Li Marzi, S. Simic, Signed line graphs with least eigenvalue $2$: The star complement technique, Discrete Applied Mathematics
207, (2016), 29–38.

[3]
F. Belardo, S. M. Cioaba, J. H. Koolen, J. Wang, Open problems in the spectral theory of signed graphs, arXiv:1907.04349v1.

[5]
Y. Bilu and N. Linial, Lifts, discrepancy and nearly optimal
spectral gap. Combinatorica , 26(5) (2006)

[6]
D. M. Cvetkovic, P. Rowlinson and S. K. Simic, Eigenspaces of graphs,
Encyclopedia of Mathematics and its Applications, 66, Cambridge University Press,
Cambridge, (1997).

[7]
D. Best, H. Kharaghani, H. Ramp, On unit weighing matrices with small weight, Discrete Mathematics 313 (2013) 855–-864.

[11]
E. R. van Dam , Graphs with few eigenvalues; An
interplay between combinatorics and algebra Ph.D thesis, Tilburg University, (1996).

[12]
K.A. Germina, K. Shahul Hameed, T. Zaslavsky,
On products and line graphs of signed graphs, their eigenvalues and energy
Linear Algebra Appl., 435 (10) (2010), 2432–2450.

[13]
Y. Hou, Z. Tang, D. Wang, On signed graphs with just two distinct adjacency eigenvalues, Discrete Mathematics
342 (2019).

[14]
H. Huang, Induced graphs of the hypercube and a proof of the Sensitivity Conjecture, to appear in Annals of Mathematics.

[15]
H. Kharaghani, On a class of symmetric balanced generalized weighing matrices, Designs, Codes and Cryptography, 30 (2003) 139–-149.

[16]
C. Koukouvinos, J. Seberry, Weighing matrices and their applications, Journal of Statistical Planning and
Inference 62 (1997) 91–101.

[17]
S. Liu, N. Peyerimhoff, and A. Vdovina, Signatures,
lifts, and eigenvalues of graphs, arXiv:1412.6841 [math.CO].

[18]
F. Ramezani, Signed graphs with two distinct eigenvalues,
Utilitas Mathematica, to appear.

[19]
F. Ramezani, Constructing signed strongly regular graphs via
star complement technique, Mathematical Sciences
12 (2018) 157–161.

[20]
F. Ramezani, Constructing strongly regular signed graphs, Submitted.

[4]
P. Rowlinson, Star complements in finite graphs: a survey, Rendiconti del Seminario Matematico di Messina Serie II, 8 (2002) (Supplemento), 145–162.

[21]
Z. Stanic On strongly regular signed graphs, Discrete Appl. Math., to appear.

[22]
B. Tayfeh-Rezaei, Starcomplement technique, Online Lecture note, URL: "http://math.ipm.ac.ir/ tayfeh-r/papersandpreprints/starcompl.pdf".

[24]
T. Zaslavsky, Signed graphs. Discrete Appl. Math.,
4(1982), 47–74.

[25]
T. Zaslavsky,  Matrices  in  the  theory  of  signed
simple graphs,  Adv. Discrete Math. Appl., 13 (2010), 207–229.