# Fingerprint Membership and Identity Inference Against
Generative Adversarial Networks111The work was partially supported by the
European Union under the Italian National Recovery and Resilience Plan (NRRP)
of NextGenerationEU, partnership on “Telecommunications of the Future”
(PE00000001 - program “RESTART”).

Saverio Cavasin<EMAIL_ADDRESS>Daniele Mari
<EMAIL_ADDRESS>Simone Milani<EMAIL_ADDRESS>Mauro
Conti<EMAIL_ADDRESS>
###### Abstract

Generative models are gaining significant attention as potential catalysts for
a novel industrial revolution. Since automated sample generation can be useful
to solve privacy and data scarcity issues that usually affect learned
biometric models, such technologies became widely spread in this field.
In this paper, we assess the vulnerabilities of generative machine learning
models concerning identity protection by designing and testing an identity
inference attack on fingerprint datasets created by means of a generative
adversarial network. Experimental results show that the proposed solution
proves to be effective under different configurations and easily extendable to
other biometric measurements.

###### keywords:

Membership Inference , Identity Inference , Fingerprints , Biometrics , GANs ,
Media Forensics , Explainable forensics

[math]organization=Department of Mathematics, University of
Padova,addressline=Via Trieste, 63, city=Padova, postcode=35131

cariparocariparofootnotetext: Daniele Mari’s activities were supported by
Fondazione CaRiPaRo under the grants “Dottorati di Ricerca” 2021/2022.

[dei]organization=Department of Information Engineering, University of Padova,
addressline=Via Gradenigo 6A, city=Padova, postcode=35131

##  1 Introduction

Biometric signals are among the most robust and simple means to perform the
identification or the authentication of a user for a wide variety of
applications (e.g., home banking, payment apps).

To increase the accuracy of these systems, Deep Learning (DL) techniques have
been explored and introduced also in biometrics [1, 2, 3, 4, 5],  but the
adoption of learned strategies implies the availability of large datasets
(otherwise the final accuracy collapses), as well as the risk of possible
information leakage concerning the training data (thus revealing sensitive
data about some of the users) [6, 7, 8, 9].

To tackle these problems, multiple researchers have proposed the adoption of
generative models, like Generative Adversarial Networks (GANs) [10], which
automatically create new original biometric samples [11] extending the
datasets with new synthetic IDs. Indeed, scientific literature has recently
proposed the use of GANs for faces, voices, fingerprints. In this way,
biometric training data could be generated by means of some GAN APIs that
provide as many samples as required, thus improving users’ privacy since no
real acquisitions would need to be shared.

Although this seems to solve the aforementioned problems, the inherent learned
nature of such solutions poses the same security threats, since it allows an
attacker to partially identify samples belonging to the original dataset
(e.g., Membership Inference Attack (MIA) on GANs [9]).

The vulnerable nature of biometric data is an issue perfectly addressed by
generative methods. By exploiting synthetic data, unnecessary privacy leakage
is avoided. For example, in an access control system implemented through
fingerprints, the sensors and the software can be trained and tuned with
generated samples as long as their properties are representative of the real
data they are emulating. Nevertheless, the models that provide such systems
still need privacy assessment methodologies in order to protect themself from
leaking unwanted information. Indeed, as displayed by our proposed method, the
cross comparison of different acquisitions of the same fingers represents a
serious threat. Even in a scenario where the subject providing the model is
able to protect the original dataset, the attack methodology we carry is still
going to be effective, as long as different acquisitions of the same finger
are obtained. This means that if the attackers access different samples, by
any source, by any mean, they can carry the very same attack against the
models trained by a privacy-compliant source. Eventually, such consideration
imply that even in the case of a privacy-compliant supply strategy by a given
company, their models are still threatened by possible data leakages from
different, less compliant companies.

In this paper, we push forward this possibility by showing that it is possible
to infer the identity of the subjects adopted to train the generative models.
This task is relatively new among inference attacks since the attacker does
not need to verify if a specific biometric sample has been used to train the
algorithm (MIA): he just needs a new acquisition from a specific user and
infer if it could possibly match with the unknown training set (Identity
Inference Attack). This working condition applies to many more realistic
scenarios, since the assumption that the attacker possesses some of the
training samples (MIA) is much stronger. Moreover, Identity Inference Attack
(IIA) analysis can be exploited for different purposes that go beyond privacy
applications, e.g., highlighting eventual flaws or ill conditions in the
training dataset and procedures (overfitting, naive models, poor diversity in
the data) [8]. We tested such a possibility on fingerprint-generating GANs
since inference attacks have not been conducted on this domain before.
However, due to the difficulties in acquiring new samples, the use of
generative strategies has become increasingly studied thus requiring an
analysis of the related inference problem.

The main contributions of the current paper can be summarized as follows.

  * 1.

We propose an IIA attack for biometric generative models that infers whether
some unknown biometric samples from a target user were employed in training
the analyzed model. This work departs from [9] since it is intended to infer
the identity of the user, instead of the data membership (i.e., whether a
given sample has been used in training). Indeed, IIA proves to be extremely
recent and timely [12], while being at its very first investigation stages. To
the best of our knowledge, this is the first work to tackle such problems on
fingerprint GANs.

  * 2.

MIA and IIA have been tested on fingerprint generating GANs. This work is the
first analysis on information inference issues for fingerprint generative
neural networks, which proves to be crucial given privacy and acquisition
difficulties in creating a sufficiently-exhaustive and legally-shareable
fingerprint datasets. This analysis is extremely useful with respect to the
current state-of-the-art in biometric generative schemes.

  * 3.

The presented GAN inference attack is optimized using the Inception Score
metric thus enabling an attacker to guess the best parameters and strategies
with respect to the victim GAN.

In the following, Section 2 overviews the existing literature on this subject,
while Section 3 describes the proposed attack. Section 4 introduces the
experimental setting and Section 5 presents the relative results. In the end,
Section 6 discusses the possible implications, and Section 7 draws the final
conclusions.

##  2 Related Works

One of the most recent trends in the privacy protection fields for fingerprint
images consists in using GANs [10] to  extend the training set for machine
learning algorithms. On the other hand, researchers in the MIA community have
proposed various black and white box attacks on generative models.

###  2.1 Generative Algorithms for fingerprints data

GANs have been widely used in the literature as a tool to generate new
fingerprints with high-quality minutiae [13, 14, 15, 16] or to reconstruct
partially degraded ones [17, 18]. In particular, in [13] they use DC-GAN [19]
together with a connectivity regularization loss to generate faithful
fingerprint images. Then in [14] the authors use I-WGAN [20] together with an
identity loss that allows to generate fingerprints from the same user. In
[15], fingerprints are generated in two steps: first, a StyleGAN-2 [11] based
model is used to produce the skeleton of the fingerprint; then, [21] applies
CycleGAN to perform style transfer and transform these skeletons into actual
images. This allows to obtain very high-quality images compared to previous
methods.

Finally, the approach in [16] also uses StyleGAN2 to generate samples, but the
input signal is created by an encoder that permits selecting the position of
the minutiae thus generating fingerprints with consistent identities.

###  2.2 Membership inference attacks

Given a set of data points, and a machine learning model, MIA consists in
guessing which of the samples were used to train the algorithm i.e., that are
members of the training set. In general, the MIA is said to be white-box if
the attacker has access to the weights of the model while it is said to be
black-box if he can only analyze the predictions. The latter can be further
subdivided by incrementally removing information (e.g., when attacking a model
that only returns the top-n predicted classes).

One of the first works to introduce MIAs is [6] where “machine learning as a
service” classification models were attacked. This is a good example of a
black box setting since even the Machine Learning (ML) algorithm is unknown to
the attacker. The authors’ strategy was to train multiple shadow models (one
for each class) to mimic the behavior of the attacked one. Afterward, they
train a classifier to assess the membership of the samples using the shadow
models as a proxy for the attacked one allowing the classifier to be later
used to attack the actual black box cloud API.

Following this idea, many works have proposed more reliable and effective
attacks and countermeasures [8, 22, 23]. In [22] the correctness of the
prediction and the loss value are used as discriminative factors, in [23] the
prediction entropy is used as a feature instead.

Additionally, many other MIAs have been designed to work on different types of
models (e.g., generative ones), for example in [9] the authors propose the
first MIA attack on GANs. In the white-box scenario, the authors use the
discriminator prediction confidence as the discriminative factor between
members and non-members, while, in the black-box scenario, they train a GAN to
mimic the target model and then they exploit the newly trained discriminator
to perform the white box attack. On the other hand in [24] the authors use
Monte Carlo integration to approximate the probability that the item is a
member.

Expanding MIAs some researchers have shown that it is not only possible to
assess the membership of a sample in the training set but also of the user
depicted in the photo himself. In particular, in [12] it is shown that it is
possible to understand if photos of a user were used to train a metric
embedding learned system by looking at how tightly some images of the person
are clustered by the network. And additionally, these images don’t even need
to have been used as training samples, showing that the model is actually
memorizing the user identity in its weights. Some additional works have shown
that IIAs can be carried out also to assess authorship of samples used to
train language models [25] and to find out if someone’s voice was used to
train some voice services [26].

##  3 Identity inference on GANs

In order to evaluate the feasibility of identity inference for biometric
generative models, we considered Convolutional Generative Adversarial Networks
(C-GANs) approaches since they are the most frequently adopted in biometric
applications and allow us to generalize the obtained results to the whole
family of models.

The black box attack that we carry out against all the trained models is
compliant with the state of the art concerning membership inference on
generative networks proposed in in [9] (see scheme in Figure 1). Our main
assumptions are that the attacker  has access to some APIs that allow
generating from the target C-GAN $\\{\mathcal{G}_{a},\mathcal{D}_{a}\\}$ as
many samples as he wants (the structure of the target model is not known) and
he/she is in possession of a dataset containing some of the samples used to
train $\\{\mathcal{G}_{a},\mathcal{D}_{a}\\}$ (called the query dataset).

Fig. 1: Schema of the attack

The attacker trains a shadow GAN $\\{\mathcal{G}_{s},\mathcal{D}_{s}\\}$ to
mimic $\\{\mathcal{G}_{a},\mathcal{D}_{a}$ } .  More precisely,
$\mathcal{G}_{s}$ is trained to generate samples as close as possible to those
produced by $\mathcal{G}_{a}$, while the discriminator $\mathcal{D}_{s}$
classifies whether the sample was generated by $\mathcal{G}_{a}$ or
$\mathcal{G}_{s}$. In this way, $\mathcal{D}_{s}$ will  infer some peculiar
features that $\mathcal{G}_{a}$ inadvertently introduces in the generated
samples (likely due to overfitting). At this point,  the confidence values
outputted by $\mathcal{D}_{s}$ make it possible to sort the samples in the
query dataset. Ideally, the top $k$ samples are going to have a higher
likelihood of being members  of the training set, thus achieving a successful
MIA.

The main intuition behind this attack is that $\mathcal{D}_{s}$ should be able
to better recognize images used to train
$\\{\mathcal{G}_{a},\mathcal{D}_{a}\\}$ since they should present features
that are more similar to the ones displayed in samples generated by
$\mathcal{G}_{a}$.

In [9] the authors show how the attack performance improves with the training
time,  but knowing in advance a sufficient number of iterations permits
reducing the computational burden.

In this work, we show that by exploiting Inception Score (IS) [27] as the
metric for early stopping it is possible to obtain good MIA performance. In
particular, we stop training when the IS of the shadow model is similar to the
one of the attacked one.

The score is proposed in [27] as:

$\exp(\mathbf{E}_{x}[KL(p(y|x)||p(y)]),$ (1)

where:

  1. 1.

KL is the Kullback–Leibler divergence, denoted by $D_{KL}(P||Q)$, i.e., a
statistical distance measuring how much the probability distribution P is
different from a reference probability distribution Q.

  2. 2.

The results are modeled through exponentiation to allow easier comparisons
between values.

The implementation of the Inception Score in the attacking strategy is
motivated by the will of replicating a scenario where the attacker needs a
quantitative method to assess the possible quality of his attempts. Leading
the training of his networks according to the score obtained from the victims’
generated images, the attacker increases his chances of replicating a truthful
overfitting, hence creating shadow models able to replicate some
characteristics of the victims’ model behaviour. Different metrics are often
used in literature to quantify generated images quality, as the Frechet
Inception Distance [28]. Nevertheless, in our task based on black and white
fingerprints, the IS implemented through a pretrained ImageNet classifier
provided the necessary results.

Lastly, we also explore the task of IIA. In this case, the aim is not only to
determine if a given impression was used during training but also to infer if
the specific finger (i.e., identity) itself was used in the training process.
In this case the assumptions formulated above slightly change, in particular,
the query dataset is modified so that it does not contain the same impression
of the finger used in the training datasets. This is a more realistic scenario
since it is unlikely for an attacker to use the same biometric samples. The
black box attack remains exactly identical to the one carried out in the MIA
case since also in IIA we would like $\mathcal{D}_{s}$ to recognize features
of the fingerprints that were present in the training set, and thus also on
other impressions of the same fingerprints.

##  4 Experimental Setup

Fig. 2: 4 different impressions of the same finger Fig. 3: Architectures of
$\mathcal{G}_{a},\mathcal{D}_{a}$

In our experimental set-up, we trained different C-GANs using impressions from
the CASIA-FingerprintV5 dataset [29] which contains 20.000 fingerpint images
of 500 subjects. These were captured using URU 4000 sensor. Each volunteer
contributed with 40 fingerprint images obtained by getting five scans
($328\times 356$ resolution) out of eight different fingers. The volunteers
varied rotation and pressure generating significant differences in the quality
of the different acquisitions (see Figure 2).

The attacked architecture is defined in Figure 3, we use LeakyReLU as an
activation function made exception for the last layer of the generator where
we use TANH and in the last layer of the discriminator where we use Sigmoid
(these implementation choices are rather generic and shared by most of the GAN
architectures in the literature). The  attacking GAN model was trained using
Adam optimizer and the standard loss, however, we noticed that the
discriminator was producing a very skewed prediction distribution making it
hard to distinguish between samples where it had high and low confidence. To
address this we added label smoothing with a smoothing factor equal to $0.2$.

From the attacker’s point of view, in addition to the aforementioned change to
the discriminator loss, following the requirements set by the Inception Score
compatibility, all the main training parameters were modified (e.g., buffer
size, batch size, epochs). $\mathcal{G}_{s}$ first layer was increased by half
the size in the number of neurons, and the Adam optimizer was tuned
accordingly. The attacking discriminators on the other hand was built adding
convolutional layers. Empirically, our results suggest that the quality of the
inference (i.e., the relative overfitting) is jointly improved by both the
widening of the $\mathcal{G}_{s}$ and the deepening and sharpening of
$\mathcal{D}_{s}$ capability, with the latter introducing the highest
influence (the attack produces decent results even with the generator being
smaller and the discriminator being less deep, but without label smoothing the
results are way less significant).

In order to assess the robustness of the trained models against MIAs, the
considered C-GANs were retrained using all the dataset splits specified in
Table 1.  In all the data splits we only keep 3 acquisitions per finger in the
training dataset, while the others are added to the IIA query dataset. Table 1
is composed by the number of samples the victim’s GAN used to train. The total
number of samples is computed as $n\\_fingers\times n\\_user\times
n\\_fingerprints$, where $n\\_fingers=8$, while $n\\_user$ and
$n\\_fingerprints$ are specified in the table for each case.

On the other hand, for what concerns the attacking model, we performed model
selection using the IS metric (as mentioned above) similarly to what a black
box attack would need to do in a real scenario. As a result, we created
diverse architectures with different parameters depending on the dataset that
was originally used to train $\\{\mathcal{G}_{a},\mathcal{D}_{a}\\}$ . Also in
this case, the different networks were obtained by stacking convolutional
layers (with a structure similar to the one of the attacked GAN) whose number
was varied in order to satisfy the IS criterion. The different configurations
are here omitted for the sake of conciseness.

##  5 Results

Fig. 4: 4 generated fingerprints impressions Fig. 5: On the left, highest confidence fingerprints that are actual members. On the right highest scoring images that are different impressions of training samples. (Gan_2400 and Gan_4800) Name | Real Images | D1 | D2 | D3 | D4
---|---|---|---|---|---
Samples / Users / Fingerprints | 2000/50/5 | 9600/400/3 | 4800/200/3 | 2400/100/3 | 1200/50/3
IS Mean | 1639.2 | 1620.13 | 1563.79 | 1570.89 | 1571.28
IS STD | 7.92 | 11.95 | 15.99 | 18.66 | 10.29
Table 1: Datasets splits and inception score metrics on the trained GANs for each of them | MIA | IIA
---|---|---
GAN | top 20 | top 200 | top 50% | top 20 | top 200 | top 50%
Gan_9600 | 14/20 | 126/200 | 1172/2000 | 12/20 | 114/200 | 1161/2000
Gan_4800 | 19/20 | 144/200 | 1133/2000 | 18/20 | 140/200 | 1133/2000
Gan_2400 | 12/20 | 108/200 | 869/1600 | 13/20 | 105/200 | 869/1600
Gan_1200 | 13/20 | 132/200 | 526/800 | 12/20 | 137/200 | 540/800
Table 2: MIA and IIA Results.

First experimental considerations concern the quality of the generated images
and the effectiveness in using IS as a termination criterion.

Figure 4 shows that the generated fingerprint images consistently present
level 1 (ridge orientation and singular points) and 2 (minutiae) features,
with the sporadic presence of level 3 (pores) features as well. This is
further highlighted by the IS values obtained on the generated images, which
are comparable to those computed on fingerprints. It is also possible to
notice that the lower the amount of training images the lower the IS value.

We implement the statistical attack on a query dataset built with two sets of
images:

  1. 1.

samples associated to users that did not contribute to the attacked gan
($G_{a}$) training set.

  2. 2.

samples associated to users that contributed to the attacked gan ($G_{a}$)
training set.

The former are the negative samples, i.e., the ones that should not be
detected as being part of the dataset, while the latter are the positive
samples. For MIA the positive samples are those that were actually used to
train the attacked gan $G_{a}$ while in the case of IIA they are other
impressions of fingerprints used to train $G_{a}$.

Since four GANs were trained with a decreasing number of samples (i.e., fewer
users contributed to the dataset), to assess the effect of the dataset size on
the attack performance, the query datasets can contain at most as many
fingerprints as the ones available for the IIA attacks (i.e.,
$2number\\_training\\_users$). For this reason two query datasets contain 4000
samples (2000 positive and 2000 negative) while two have fewer fingerprints,
respectively 3200 (1600 positive and 1600 negative) and 1600 (800 positive and
800 negative) samples, since fewer users were used to train the GAN.

Following previous works from the literature we report the performance of the
algorithm in terms of positive samples in the top-20, top-200 and top-50%
samples (here we use top-50% instead of top-2000 because, as aforementioned,
in two cases fewer than 4000 query samples were available) sorted according to
the rank assigned to the fingerprints by the shadow discriminator. Note that
the top-50% configuration should have been top-2000, however, since 2000
samples per query dataset only the top 50% samples were considered) In such a
scenario, if the discriminator was actually random guessing, the number of
positive and negative samples would be very close to 10, 100 and 25% of the
total for all the models. However, although this happens at time, in all cases
reported in Table 2 the number of positive samples is greater than the number
of negative samples at times being very close to 100% (18/20, 19/20, etc.)
showing that there is indeed some sort of information leakage.

Additionally, it is possible to see that the performance of the attack is only
slightly worse when performing IIA compared to MIA showing that, even in the
more challenging scenario, private information about the users that
contributed in the dataset creation is leaked to the attacker.

This demonstrates the effectiveness of MIA and IIA in detecting sample and
finger membership in the training dataset for a GAN. As a matter of fact, the
attacks lead to near-perfect recognition of many fingerprints as belonging to
the targeted sample in both scenarios.

An additional proof that the success of the attack is provided by a visual
inspection of images where $\mathcal{D}_{s}$ confidence suggests that they are
more likely to belong to the training dataset. These indeed exhibit various
similarities especially within the Level 1 features as can be seen from Figure
5.

Especially in the case of the GAN trained on 4800 samples, out of the 20
flagged images with the highest scores, 19 of them are indeed from the
training dataset. Once the actual training images are swapped with a set of
”remaining” acquisitions, i.e., different samples of the same fingers, the
result remains high with 18 out of 20 correctly identified showing how much
information these types of models can actually leak even though they were
designed in the first place to avoid privacy concerns.

##  6 Discussion

From Table 2 it is possible to see that all the trained models could be
attacked by the proposed approach.  Additionally, since the attack was
successful on all the four cases, it is possible to conclude that IS might be
a good heuristic when choosing when to stop the training procedure.

Despite this, experimental tests did not reveal how the number of training
samples affects the attack performance since the general success is also
strongly dependent on other factors such as how well-trained the attacked
model is or the batch size and optimizer, to mention some of them. However,
considering other results on MIA presented in the literature, it is reasonable
to believe that increasing the total number of samples by a significant amount
implies improving the robustness against MIAs and IIAs.

##  7 Conclusion

This work illustrates the main vulnerabilities of generative adversarial
networks as a mean to solve the data shortage and privacy issues for learned
biometric architectures. More precisely, Membership and Identity Inference
Attacks on fingerprint GANs are described and evaluated showing how it is
possible to infer users’ identity from a trained black box model.

To the best of our knowledge, we are the first to notice the severity of the
problem on fingerprint data showing that it is possible to assess membership
of a sample and to detect if a person contributed to the creation of a dataset
without having access to any of the training data.

A possible follow up implementation of this work stands within the specific-
sample research methods. Here we proved the vulnerability on the information
leakage of the discussed models. By looking at the distributions of the shadow
discriminator, it is possible for the attacker to notice significant patterns
that can help to predict whether new fingerprints are related to the training
set of the attacked model or not. In Figure 6 we show plots of distribution
kernels for the attacking queries in two instances (1200, 4800). We propose to
use the information given by these distributions to create classifications
methods able to cluster unforeseen data to allow the attackers to link it to
the training set. A possible approach could be the training of either
supervised or unsupervised models to respectively learn to fit the relative
distributions or to learn intrinsic patterns that differentiate the shadow
discriminator judgement.

Being the proposed scheme quite generalizable, our future research will
analyze IIA problem on other kinds of biometric samples and architectures, and
will focus on the design of defense strategies.

Fig. 6: Kernels distributions of the attacking discriminators against the
generated images of the Gans with 1200 and 4800 samples.

## References

  * [1] M. M. Kasar, D. Bhattacharyya, T. Kim, Face recognition using neural network: a review, International Journal of Security and Its Applications 10 (3) (2016) 81–100.
  * [2] G. Guo, N. Zhang, A survey on deep learning based face recognition, Computer vision and image understanding 189 (2019) 102805.
  * [3] Y. Liu, B. Zhou, C. Han, T. Guo, J. Qin, A novel method based on deep learning for aligned fingerprints matching, Applied Intelligence 50 (2020) 397–416.
  * [4] B. Rim, J. Kim, M. Hong, Fingerprint classification using deep learning approach, Multimedia Tools and Applications 80 (2021) 35809–35825.
  * [5] K. Sundararajan, D. L. Woodard, Deep learning for biometrics: A survey, ACM Computing Surveys (CSUR) 51 (3) (2018) 1–34.
  * [6] R. Shokri, M. Stronati, C. Song, V. Shmatikov, Membership inference attacks against machine learning models, in: 2017 IEEE symposium on security and privacy (SP), 2017, pp. 3–18.
  * [7] C. A. Choquette-Choo, F. Tramer, N. Carlini, N. Papernot, Label-only membership inference attacks, in: International conference on machine learning, 2021, pp. 1964–1974.
  * [8] H. Hu, Z. Salcic, L. Sun, G. Dobbie, P. S. Yu, X. Zhang, Membership inference attacks on machine learning: A survey, ACM Computing Surveys (CSUR) 54 (11s) (2022) 1–37.
  * [9] J. Hayes, L. Melis, G. Danezis, E. De Cristofaro, Logan: Membership inference attacks against generative models, arXiv preprint arXiv:1705.07663 (2017).
  * [10] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio, Generative adversarial networks, Communications of the ACM 63 (11) (2020) 139–144.
  * [11] T. Karras, S. Laine, M. Aittala, J. Hellsten, J. Lehtinen, T. Aila, Analyzing and improving the image quality of stylegan, in: Proc.of the IEEE/CVF CVPR 2020, 2020, pp. 8110–8119.
  * [12] G. Li, S. Rezaei, X. Liu, User-level membership inference attack against metric embedding learning, arXiv preprint arXiv:2203.02077 (2022).
  * [13] S. Minaee, A. Abdolrashidi, Finger-gan: Generating realistic fingerprint images using connectivity imposed gan, arXiv preprint arXiv:1812.10482 (2018).
  * [14] V. Mistry, J. J. Engelsma, A. K. Jain, Fingerprint synthesis: Search with 100 million prints, in: 2020 IEEE International Joint Conference on Biometrics (IJCB), 2020, pp. 1–10.
  * [15] A. Sams, H. H. Shomee, S. M. Rahman, Hq-fingan: High-quality synthetic fingerprint generation using gans, Circuits, Systems, and Signal Processing 41 (11) (2022) 6354–6369.
  * [16] R. Bouzaglo, Y. Keller, Synthesis and reconstruction of fingerprints using generative adversarial networks, arXiv preprint arXiv:2201.06164 (2022).
  * [17] X. Huang, P. Qian, M. Liu, Latent fingerprint image enhancement based on progressive generative adversarial network, in: Proc. of the IEEE/CVF CVPR Workshops 2020, 2020, pp. 800–801.
  * [18] I. Joshi, A. Anand, M. Vatsa, R. Singh, S. D. Roy, P. Kalra, Latent fingerprint enhancement using generative adversarial networks, in: Proc. of IEEE WACV 2019, 2019, pp. 895–903.
  * [19] A. Radford, L. Metz, S. Chintala, Unsupervised representation learning with deep convolutional generative adversarial networks, arXiv preprint arXiv:1511.06434 (2015).
  * [20] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, A. C. Courville, Improved training of wasserstein gans, Advances in neural information processing systems 30 (2017).
  * [21] J.-Y. Zhu, T. Park, P. Isola, A. A. Efros, Unpaired image-to-image translation using cycle-consistent adversarial networks, in: Proceedings of the IEEE ICCV 2017, 2017, pp. 2223–2232.
  * [22] S. Yeom, I. Giacomelli, M. Fredrikson, S. Jha, Privacy risk in machine learning: Analyzing the connection to overfitting, in: 2018 IEEE 31st computer security foundations symposium (CSF), 2018, pp. 268–282.
  * [23] A. Salem, Y. Zhang, M. Humbert, M. Fritz, M. Backes, Ml-leaks: Model and data independent membership inference attacks and defenses on machine learning models, in: Network and Distributed Systems Security Symposium 2019, 2019.
  * [24] B. Hilprecht, M. Härterich, D. Bernau, Monte carlo and reconstruction membership inference attacks against generative models., Proc. Priv. Enhancing Technol. 2019 (4) (2019) 232–249.
  * [25] C. Song, V. Shmatikov, Auditing data provenance in text-generation models, in: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 196–206.
  * [26] Y. Miao, X. Minhui, C. Chen, L. Pan, J. Zhang, B. Z. H. Zhao, D. Kaafar, Y. Xiang, The audio auditor: user-level membership inference in internet of things voice services, Proceedings on Privacy Enhancing Technologies 2021 (2021) 209–228.
  * [27] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, X. Chen, Improved techniques for training gans, Advances in neural information processing systems 29 (2016).
  * [28] Y. Yu, W. Zhang, Y. Deng, Frechet inception distance (fid) for evaluating gans, China University of Mining Technology Beijing Graduate School: Beijing, China (2021).
  * [29] Chinese academy of sciences’ institute of automation casia-fingerprint-v5 dataset, http://biometrics.idealtest.org/ (Last Accessd 15/06/2023).


# Signed graphs and inverses of their incidence matrices

Abdullah Alazemi  Department of Mathematics, Kuwait University, Safat 13060,
Kuwait<EMAIL_ADDRESS>,  Milica Anđelić  Department of
Mathematics, Kuwait University, Safat 13060, Kuwait, and Department of Natural
and Mathematical Sciences, State University of Novi Pazar, Serbia
<EMAIL_ADDRESS>and  Sudipta Mallik  Department of Mathematics and
Statistics, Northern Arizona University, 801 S. Osborne Dr., PO Box: 5717,
Flagstaff, AZ 86011, USA<EMAIL_ADDRESS>
###### Abstract.

The Laplacian matrix $L$ of a signed graph $G$ may or may not be invertible.
We present a combinatorial formula of the Moore-Penrose inverse of $L$. This
is achieved by finding a combinatorial formula for the Moore-Penrose inverse
of an incidence matrix of $G$. This work generalizes related known results on
incidence and Laplacian matrices of an unsigned graph. Several examples are
provided to show the usefulness of these combinatorial formulas.

###### Key words and phrases:

Moore-Penrose inverse; signed graphs; incidence matrix; Laplacian matrix

###### 2000 Mathematics Subject Classification:

05C50, 15A09

##  1\. Introduction

A signed graph is a graph in which each of its edges is positive or negative.
More formally, a signed graph $\Gamma$ is a pair $\Gamma=(G,\sigma)$ where
$G=(V,E)$ is a graph, called the underlying graph, with vertex and edge sets
$V=\\{1,2,\ldots,n\\}$ and $E=\\{e_{1},e_{2},\ldots,e_{m}\\}$ respectively and
$\sigma:E\rightarrow\\{-1,1\\}$ is the sign function or signature. An edge
$e_{\ell}$ is positive (resp. negative) if $\sigma(e_{\ell})=1$ (resp.
$\sigma(e_{\ell})=-1$). By $E^{-}(\Gamma)$ (resp. $E^{+}(\Gamma)$) we denote
the set of negative (resp. positive) edges in $\Gamma$. Throughout this
article, we consider only simple signed graphs, i.e., signed graphs that do
not have loops and multiple edges.

A cycle $C$ in $\Gamma$ is balanced if it contains an even number of negative
edges. $\Gamma$ is said to be balanced if all its cycles are balanced,
otherwise it is unbalanced. The adjacency matrix of $\Gamma=(G,\sigma)$ is
$A(\Gamma)=[a^{\sigma}_{ij}]$ with $a^{\sigma}_{ij}=\sigma(ij)a_{ij}$, where
$A=[a_{ij}]$ is the adjacency matrix of the underlying graph $G$. The
corresponding Laplacian matrix $L(\Gamma)=D(G)-A(\Gamma)$, where $D(G)$ is the
diagonal matrix of vertex degrees. Before we define incidence matrix of
$\Gamma$ in details, note that $L(\Gamma)=NN^{\intercal}$ for any incidence
matrix $N$ of $\Gamma$.

An incidence matrix $N=[n_{ij}]$ of $\Gamma$ is an $n\times m$ binary matrix
with rows indexed by vertices and columns indexed by edges such that each of
its columns has exactly two nonzero entries as follows:

  1. (a)

when $e_{\ell}=\\{i,j\\}$ is a negative edge, $n_{i\ell}=n_{j\ell}$ and it is
either $1$ or $-1$, and

  2. (b)

when $e_{\ell}=\\{i,j\\}$ is a positive edge, $n_{i\ell}=-n_{j\ell}$ and it is
either $1$ or $-1$.

Multiple incidence matrices can be associated with $\Gamma$. In particular, if
$\Gamma=(G,\sigma)$ has all negative edges, then the incidence matrix of the
underlying graph $G$ is an incidence matrix of $\Gamma$. Similarly, if
$\Gamma=(G,\sigma)$ has all positive edges, then an oriented incidence matrix
of the underlying graph $G$ is an incidence matrix of $\Gamma$. It is
important to mention that an oriented incidence matrix $N=[n_{ij}]$ of $G$
gives each of its edges an orientation as follows [7, 4]: when
$n_{i\ell}=-n_{j\ell}=1$, edge $e_{\ell}=\\{i,j\\}$ is oriented as $(i,j)$
which is directed from vertex $i$ to vertex $j$.

We get a fixed incidence matrix of $\Gamma=(G,\sigma)$ if each of its edges
has a bi-direction in which each edge has two arrowheads at the ends. We
define $n_{i\ell}=\eta(i,e_{\ell})$ where $\eta:V\times E\to\\{+1,-1,0\\}$ is
defined as follows:

  * (i)

$\eta(i,e_{\ell})=0$ if $i\notin e_{\ell}$,

  * (ii)

$\eta(i,e_{\ell})=-1$ (resp. $+1$) if an arrow at $i$ goes into (resp. out of)
$i$ and $e_{\ell}=\\{i,j\\}$,

  * (iii)

$\eta(i,e_{\ell})\eta(j,e_{\ell})=-\sigma(e_{\ell})$ for $e_{\ell}=\\{i,j\\}$.

Note that the last two conditions imply that two arrows of a positive (resp.
negative) edge have the same direction (resp. opposite directions). In the
literature of signed graphs the signs in condition (ii) are reversed. We
changed it to be consistent with the literature of oriented incidence matrix
of an unsigned graph [7, 4]. This work is a generalization of work on graphs
to signed graphs and we did not want to contradict the existing results on the
Moore-Penrose inverse of an oriented matrix of a graph [4].

For $A\in\mathbb{R}^{n\times m}$, a matrix $X\in\mathbb{R}^{m\times n}$ is
called the Moore-Penrose inverse of $A$ if

(1.1) $AXA=A,\,\,XAX=X,\,\,(AX)^{\intercal}=AX,\,\,(XA)^{\intercal}=XA,$

and it is denoted by $A^{\dagger}.$

In 1965, Ijiri first studied the Moore-Penrose inverse of the oriented
incidence matrix of a graph in [12]. Bapat did the same for the Laplacian and
oriented incidence matrices of trees [4]. Further research studied the same
topic for different graphs such as distance regular graphs [2, 3]. With the
emergence of research on the signless Laplacian of graphs [8, 9], Hessert and
Mallik studied the Moore-Penrose inverses of the incidence matrix and signless
Laplacian of a tree and an unicyclic graph in [10, 11]. Ipsen and Mallik
studied wheel graphs in the same context [13]. Alazemi, Alhalabi, and Anđelić
did the same for a larger graph class namely bipartite graphs [1]. Since a
signed graph is a generalization of an unsigned graph, it is a natural open
problem to extend the investigation regarding Moore-Penrose inverse to signed
graphs. In this article we find combinatorial formula for the entries of the
Moore-Penrose inverse of the Laplacian and incidence matrices of a signed
graph.

The content of the present paper is organized as follows. In Section 2 we
deliver several preliminary results. Section 3 covers combinatorial formulas
for the Moore-Penrose inverse of incidence matrices of signed trees and
unbalanced unicyclic signed graphs. Section 4 extends the results of Section 3
to incidence matrices of connected signed graphs. Results related to Laplacian
matrix are subject of Section 5. Several open problems are reported in Section
6.

##  2\. Preliminaries

We recall several results from [4, 6], essential for some initial
considerations regarding the rank and minors of incidence matrices of signed
graphs.

######  Lemma 2.1.

([6, Lemma 3.4]) Let $N$ be the incidence matrix of a connected signed graph
$\Gamma$ of order $n$. Then

${\rm rank}(N)=\begin{cases}n-1&\text{ if \,$\Gamma$ is balanced,}\\\ n&\text{
if \,$\Gamma$ is unbalanced.}\end{cases}$

For a matrix $N$, $N(i;\,)$ denotes the submatrix of $N$ with deleted row $i$.

######  Lemma 2.2.

([6, Lemma 3.7]) Let $N$ be the incidence matrix of a signed graph $\Gamma$.
If $\Gamma$ is a tree, then $\det(N(i;\,))=\pm 1$, and if $\Gamma$ is an
unbalanced unicyclic graph, then $\det(N(i;\,))=\pm 2.$

For an $n\times m$ real matrix $A$ and a positive integer $r\leq n,m$, ${\rm
vol}\,A$ denotes the square root of the sum of squares of all $r\times r$
minors of $A$ and $A(i_{1},i_{2},\ldots,i_{r}),\;1\leq
i_{1}<i_{2}<\cdots<i_{r}\leq m$ denotes the matrix obtained from $A$ by
replacing all the columns of $A$ that are different from columns
$i_{1},i_{2},\ldots,i_{r}$ by zero vectors. Then the Moore-Penrose inverse of
$A$ can be computed in the following way.

######  Theorem 2.3.

([4, 1]) Let $A$ be an $n\times m$ real matrix of rank $r>0$. Then

(2.1) $A^{\dagger}=\frac{1}{{\rm
vol}^{2}A}\sum_{(i_{1},i_{2},\ldots,i_{r})\in\mathcal{M}}{\rm
vol}^{2}A(i_{1},i_{2},\ldots,i_{r})A(i_{1},i_{2},\ldots,i_{r})^{\dagger},$

where

$\mathcal{M}=\\{(i_{1},i_{2},\ldots,i_{r})\in\mathbb{Z}^{r}\;|\;1\leq
i_{1}<i_{2}<\cdots<i_{r}\leq m,\;{\rm
rank}(A(i_{1},i_{2},\ldots,i_{r}))=r\\}.$

According to Lemma 2.1 the rank of an incidence matrix of a signed graph
$\Gamma$ is either $n-1$, if $\Gamma$ is balanced or $n$ if $\Gamma$ is
unbalanced. In addition, by Lemma 2.2, maximal rank is attained through
spanning trees, in case $\Gamma$ is balanced or through unbalanced unicyclic
graphs for $\Gamma$ balanced.

A signed $TU$-subgraph $H$ of $\Gamma$ is a subgraph whose components are
trees or unbalanced unicyclic graphs with $c(H)$ denoting the number of
unbalanced unicyclic components. By Lemmas 2.1 and 2.2, we have the following.

######  Theorem 2.4.

Let $\Gamma$ be a connected signed graph on $n\geq 2$ vertices $1,2,\ldots,n$
with incidence matrix $N$. Let $H$ be a spanning signed subgraph of $\Gamma$
with incidence matrix $N_{H}$.

  1. (a)

If $\Gamma$ is balanced and $H$ is a spanning tree of $\Gamma$, then ${\rm
rank}(N)={\rm rank}(N_{H})=n-1$ and for all $i=1,2,\ldots,n$,

$\det(N_{H}(i;))=\pm 1,$

and consequently ${\rm vol}^{2}(N_{H})=n$. If $H$ is any other kind of
spanning subgraph of $\Gamma$ with $n-1$ edges, then $\det(N_{H}(i;))=0$ for
all $i=1,2,\ldots,n$.

  2. (b)

If $\Gamma$ is unbalanced and $H$ is a spanning $TU$-subgraph of $\Gamma$ with
$n$ edges consisting of $c(H)$ unbalanced unicyclic graphs, then ${\rm
rank}(N)={\rm rank}(N_{H})=n$ and

$\det(N_{H})=\pm 2^{c(H)},$

and consequently ${\rm vol}^{2}(N_{H})=4^{c(H)}$. If $H$ is any other kind of
spanning subgraph of $\Gamma$ with $n$ edges, then $\det(N_{H})=0$.

###### Proof.

(a) Suppose $\Gamma$ is balanced and $H$ is a spanning tree of $\Gamma$. By
Lemmas 2.1, 2.2, ${\rm rank}(N)={\rm rank}(N_{H})=n-1$ and for
$i\in\\{1,2,\ldots,n\\}$, $\det(N_{H}(i;))=\pm 1$. Then

${\rm vol}^{2}(N_{H})=\sum_{i=1}^{n}(\det(N_{H}(i;)))^{2}=n.$

Now suppose $H$ is a spanning subgraph of $\Gamma$ with $n-1$ edges that is
not a spanning tree of $\Gamma$. Then $H$ has more than one connected
(balanced) component and consequently ${\rm rank}(N_{H}(i;))<n-1$. Thus
$\det(N_{H}(i;))=0$.

(b) Suppose $\Gamma$ is unbalanced and $H$ is a spanning $TU$-subgraph of
$\Gamma$ with $n$ edges consisting of $c(H)$ unbalanced unicyclic graphs. By
Lemma 2.1, ${\rm rank}(N)={\rm rank}(N_{H})=n$. By Lemma 2.2 the determinant
of the submatrix of $N_{H}$ corresponding to each unbalanced unicyclic graph
is $\pm 2$. Thus $\det(N_{H})=(\pm 2)^{c(H)}$. Then

${\rm vol}^{2}(N_{H})=(\det(N_{H}))^{2}=4^{c(H)}.$

Now suppose $H$ is a spanning subgraph of $\Gamma$ with $n$ edges whose
connected components are not all unbalanced unicyclic graphs. If $H$ has a
component $H_{1}$ such that $|E(H_{1})|<|V(H_{1})|$, then the columns of
$N_{H}$ corresponding to $V(H_{1})$ are linearly dependent and consequently
$\det(N_{H})=0$. Now suppose $H$ has $t$ unicyclic components
$H_{1},H_{2},\ldots,H_{t}$. Since not all of $H_{1},H_{2},\ldots,H_{t}$ are
unbalanced, say $H_{1}$ is balanced. Then the determinant of the submatrix of
$N_{H}$ corresponding to $H_{1}$ is $0$. Thus

$\det(N_{H})=\pm\prod_{i=1}^{n}\det(N_{H_{i}})=0.$

∎

In what follows by $\tau(\Gamma)$ we denote the number of spanning trees of
$\Gamma$, while by $\mathcal{TU}_{n}(\Gamma)$ we denote the set of
$TU$-subgraphs of $\Gamma$ on $n$ edges.

######  Corollary 2.5.

Let $\Gamma$ be a connected signed graph on $n$ vertices with an incidence
matrix $N$ and Laplacian matrix $L$.

  1. (a)

If $\Gamma$ is balanced, then $\det(L)=0$ and ${\rm
vol}^{2}(N)=n\tau(\Gamma)$.

  2. (b)

If $\Gamma$ is unbalanced, then

$\det(L)={\rm vol}^{2}(N)=\sum_{H\in\mathcal{TU}_{n}(\Gamma)}4^{c(H)}.$

Moreover, $\frac{\det(L)}{4}\geq$ the number of unbalanced unicyclic graphs in
$G$ and the equality holds if and only if $G$ is balanced or an unbalanced
unicyclic graph.

In order to implement (2.1) to compute $N^{\dagger}$ as main ingredients we
need formulas for the Moore-Penrose inverse of the incidence matrix of a tree
as well of an unbalanced unicyclic graph. These are covered in subsequent
sections.

##  3\. Signed trees and unbalanced unicyclic signed graphs

We first introduce necessary notation. For a given signed tree $T$ on $n$
vertices $1,2,\ldots,n$, we introduce the head and tail components in
$T\setminus e$ for any edge $e$.

  * •

If $e_{i}=\\{l_{i},m_{i}\\}$ such that $l_{i}<m_{i}$ is a negative edge, then
the head component of $T\setminus e_{i}$, denoted by $T_{h}(e_{i})$, is the
connected component of $T\setminus e_{i}$ containing the vertex $m_{i}$. The
tail component of $T\setminus e_{i}$, denoted by $T_{t}(e_{i})$, is the
connected component of $T\setminus e_{i}$ containing the vertex $l_{i}$.

  * •

If $e_{i}=(l_{i},m_{i})$ is a positive edge, directed from $l_{i}$ to $m_{i}$,
then the head component of $T\setminus e_{i}$ is the component containing
$m_{i}$, while the tail component contains $l_{i}$.

We recall that $|T_{h}(e_{i})|+|T_{t}(e_{i})|=n$, while according to [10,
Lemma 2.4]

$\sum_{e_{p}\in E_{h}(i)}|T_{t}(e_{p})|+\sum_{e_{q}\in
E_{T}(i)}|T_{h}(e_{q})|=n-1,$

where

$E_{h}(i)=\\{e_{k}\in E(G):e_{k}\text{ is incident at }i\text{ and }i\in
T_{h}(e_{k})\\},$ $E_{t}(i)=\\{e_{k}\in E(G):e_{k}\text{ is incident at
}i\text{ and }i\in T_{t}(e_{k})\\}.$

The shortest path between a vertex $j$ and an edge $e_{i}$, that does not
contain $e_{i}$ is denoted by $P_{e_{i}-j}$. The product of $\sigma(e_{k})$,
for $e_{k}$ being on the path $P_{e_{i}-j}$ is denoted by ${\rm
sgn}(P_{e_{i}-j})$.

For a connected balanced graph $\Gamma$ on $n$ vertices $1,2,\ldots,n$, we
define a new $n\times n$ matrix $S=[s_{ij}]$, we call the path sign matrix of
$\Gamma$, $s_{ii}=1$ for all $i$ and $s_{ij}=1$ ($-1$) if there is a positive
(resp. negative) path between distinct vertices $i$ and $j$. The corresponding
sign we denote by ${\rm sgn}(P_{i-j})$. The role of $S$ in computation of
Moore-Penrose inverse of balanced graphs is justified in following theorem.

######  Theorem 3.1.

Let $\Gamma=(G,\sigma)$ be a connected signed graph on $n\geq 2$ vertices
$1,2,\ldots,n$ with an incidence matrix $N$.

  1. (a)

If $\Gamma$ is unbalanced, then $NN^{\dagger}=I_{n}$.

  2. (b)

If $\Gamma$ is balanced, then

$NN^{\dagger}=I_{n}-\frac{1}{n}S,$

where $S$ is the path sign matrix of $\Gamma$.

###### Proof.

Since $NN^{\dagger}N=N$, $(I_{n}-NN^{\dagger})N=O_{n,m}$. Then each row of
$I_{n}-NN^{\dagger}$ is orthogonal to each column of $N$. Suppose
$x^{T}=[x_{1},x_{2},\ldots,x_{n}]$ is orthogonal to each column of $N$. Then
$x_{i}-x_{j}=0$ for any positive edge $\\{i,j\\}$ and $x_{i}+x_{j}=0$ for any
negative edge $\\{i,j\\}$ in $\Gamma$. Therefore, if there is a path $P_{i-j}$
between $i$ and $j$, then $x_{i}={\rm sgn}(P_{i-j})x_{j}$.

(a) If $\Gamma$ is unbalanced, then by Lemma 2.1, ${\rm rank}\,N=n$ and $N$ is
invertible, hence $N^{\dagger}=N^{-1}$.

(b) Suppose $\Gamma$ is balanced. Then ${\rm rank}\,N=n-1$ and all paths
between two distinct vertices in $G$ have the same sign. For a fixed vertex
$i$ of $G$, $x_{v}={\rm sgn}(P_{i-v})x_{i}$ for any vertex $v$ of $G$. Thus

$[x_{1},x_{2},\ldots,x_{n}]=x_{i}[{\rm sgn}(P_{i-1}),{\rm
sgn}(P_{i-2}),\ldots,{\rm sgn}(P_{i-n})].$

Consequently any row of $I_{n}-NN^{\dagger}$ is a multiple of $[{\rm
sgn}(P_{i-1}),{\rm sgn}(P_{i-2}),\ldots,{\rm sgn}(P_{i-n})]$. Suppose for each
$i=1,2,\ldots,n$, $i$th row of $I_{n}-NN^{\dagger}$ is

$c_{i}[{\rm sgn}(P_{i-1}),{\rm sgn}(P_{i-2}),\ldots,{\rm sgn}(P_{i-n})].$

Note that if $c_{1}=c_{2}=\cdots=c_{n}=0$, then $NN^{\dagger}=I_{n}$ and
consequently $n={\rm rank}(NN^{\dagger})\leq{\rm rank}(N)=n-1$, a
contradiction. Thus $c_{i}\neq 0$ for some $i$ and by symmetry of
$NN^{\dagger}$, $c_{i}\neq 0$ for all $i=1,2,\ldots,n$. Now observe that
$(I_{n}-NN^{\dagger})^{2}=I_{n}-NN^{\dagger}$ because
$N^{\dagger}NN^{\dagger}=N^{\dagger}$. Then the $(i,i)$-entry of
$(I_{n}-NN^{\dagger})^{2}$, that is $c_{i}^{2}n$, is same as the $(i,i)$-entry
of $I_{n}-NN^{\dagger}$, which is $c_{i}{\rm sgn}(P_{i-i})=c_{i}$. Thus
$c_{i}=\frac{1}{n}$ and the $(i,j)$-entry of $I_{n}-NN^{\dagger}$ is
$\frac{{\rm sgn}(P_{i-j})}{n}$. ∎

We next give combinatorial expression for the Moore-Penrose inverse of the
incidence matrix of a tree.

######  Theorem 3.2.

Let $\Gamma=(T,\sigma)$ be a signed tree on $n\geq 2$ vertices $1,2,\ldots,n$
and $n-1$ edges $e_{1},e_{2},\ldots,e_{n-1}$. Let $N$ be an incidence matrix
of $\Gamma$. Then the Moore-Penrose inverse $N^{\dagger}=[n_{i,j}^{\dagger}]$
of $N$ is given by

(3.1) $n_{i,j}^{\dagger}=\frac{{\rm
sgn}(P_{e_{i}-j})w(e_{i})}{n}\begin{cases}|T_{h}(e_{i})|&\text{ if }j\in
T_{t}(e_{i})\\\ -\sigma(e_{i})|T_{t}(e_{i})|&\text{ if }j\in
T_{h}(e_{i}),\end{cases}$

where

$w(e_{i})=\begin{cases}-1&\text{if $e_{i}$ is negative with both negative
ends}\\\ \,\,\,\,1&\text{otherwise.}\end{cases}$

###### Proof.

We first consider the case, when every negative edge has both positive ends.
Let $H=[h_{i,j}]$ be the $(n-1)\times n$ matrix given by (3.1). Then,

(3.2) $h_{i,j}=\frac{{\rm
sgn}(P_{e_{i}-j})}{n}\begin{cases}|T_{h}(e_{i})|&\text{ if }j\in
T_{t}(e_{i})\\\ |T_{t}(e_{i})|&\text{ if }j\in T_{h}(e_{i}),\;e_{i}\in
E^{-}(\Gamma)\\\ -|T_{t}(e_{i})|&\text{ if }j\in T_{h}(e_{i}),\;e_{i}\in
E^{+}(\Gamma).\end{cases}$

We show that $H=N^{\dagger}$, by proving $HN=I_{n-1}$.

For $i,j\in\\{1,\ldots,n-1\\}$, suppose $e_{i}=\\{l,m\\}$ where $l<m$ and
$e_{j}=\\{r,s\\}$. For $N=[n_{i,j}]$, the $(i,j)$-entry of $HN$ is given by

$(HN)_{i,j}=\sum^{n}_{k=1}h_{i,k}n_{k,j}=\begin{cases}h_{i,r}+h_{i,s}&\text{
if }e_{j}\in E^{-}(\Gamma)\\\ h_{i,r}-h_{i,s}&\text{ if }e_{j}=(r,s)\in
E^{+}(\Gamma)\\\ -h_{i,r}+h_{i,s}&\text{ if }e_{j}=(s,r)\in
E^{+}(\Gamma).\end{cases}$

The values of $(HN)_{i,j}$ are computed through the following cases and
subcases.

Case 1. $i=j$.
First note that ${\rm sgn}(P_{e_{i}-l})={\rm sgn}(P_{e_{i}-m})=1$ (being the
empty product).
Let $e_{i}\in E^{-}(\Gamma)$. Since $l<m$, $l\in T_{t}(e_{i})$ and $m\in
T_{h}(e_{i})$. Then

$(HN)_{i,i}=\frac{{\rm sgn}(P_{e_{i}-l})}{n}|T_{h}(e_{i})|+\frac{{\rm
sgn}(P_{e_{i}-m})}{n}|T_{t}(e_{i})|=\frac{1}{n}|T_{h}(e_{i})|+\frac{1}{n}|T_{t}(e_{i})|=\frac{1}{n}n=1.$

Let $e_{i}\in E^{+}(\Gamma)$. Since $e_{j}=(l,m)$, then $l\in T_{t}(e_{i})$,
$m\in T_{h}(e_{i})$, and

$(HN)_{i,i}=\frac{{\rm sgn}(P_{e_{i}-l})}{n}|T_{h}(e_{i})|-\frac{-{\rm
sgn}(P_{e_{i}-m})}{n}|T_{t}(e_{i})|=\frac{1}{n}|T_{h}(e_{i})|+\frac{1}{n}|T_{t}(e_{i})|=\frac{1}{n}n=1.$

If $e_{i}=(m,l)$, then $m\in T_{t}(e_{i})$, $l\in T_{h}(e_{i})$, and

$(HN)_{i,i}=-\frac{-{\rm sgn}(P_{e_{i}-l})}{n}|T_{t}(e_{i})|+\frac{{\rm
sgn}(P_{e_{i}-m})}{n}|T_{h}(e_{i})|=\frac{1}{n}|T_{t}(e_{i})|+\frac{1}{n}|T_{h}(e_{i})|=\frac{1}{n}n=1.$

Case 2. $i\neq j$.
Since $e_{i}\not=e_{j}=\\{r,s\\}$ and $T$ is a tree, either both $r,s\in
T_{h}(e_{i})$ or both $r,s\in T_{t}(e_{i})$.

Subcase (a) $r,s\in T_{t}(e_{i})$.
Either ${\rm sgn}(P_{e_{i}-r})={\rm sgn}(P_{l-r})={\rm
sgn}(P_{e_{i}-s})\sigma(e_{j})$ or ${\rm sgn}(P_{e_{i}-s})={\rm
sgn}(P_{l-s})={\rm sgn}(P_{e_{i}-r})\sigma(e_{j})$.

If $e_{j}\in E^{-}(\Gamma)$, then ${\rm sgn}(P_{e_{i}-r})$ and ${\rm
sgn}(P_{e_{i}-s})$ have the opposite signs and

$(HN)_{i,j}=\frac{{\rm sgn}(P_{e_{i}-r})}{n}|T_{h}(e_{i})|+\frac{{\rm
sgn}(P_{e_{i}-s})}{n}|T_{h}(e_{i})|=0.$

If $e_{j}\in E^{+}(\Gamma)$, then ${\rm sgn}(P_{e_{i}-r})$ and ${\rm
sgn}(P_{e_{i}-s})$ have the same sign and

$(HN)_{i,j}=\frac{{\rm sgn}(P_{e_{i}-r})}{n}|T_{h}(e_{i})|-\frac{{\rm
sgn}(P_{e_{i}-s})}{n}|T_{h}(e_{i})|=0.$

Subcase (b) $r,s\in T_{h}(e_{i})$.
Either ${\rm sgn}(P_{e_{i}-r})={\rm sgn}(P_{m-r})={\rm
sgn}(P_{e_{i}-s})\sigma(e_{j})$ or ${\rm sgn}(P_{e_{i}-s})={\rm
sgn}(P_{m-s})={\rm sgn}(P_{e_{i}-r})\sigma(e_{j})$.

If $e_{j}\in E^{-}(\Gamma)$, then ${\rm sgn}(P_{e_{i}-r})$ and ${\rm
sgn}(P_{e_{i}-s})$ have the opposite signs and

$(HN)_{i,j}=h_{i,r}+h_{i,s}=\frac{-{\rm
sgn}(P_{e_{i}-r})}{n}|T_{t}(e_{i})|+\frac{-{\rm
sgn}(P_{e_{i}-s})}{n}|T_{t}(e_{i})|=0.$

If $e_{j}\in E^{+}(\Gamma)$, then ${\rm sgn}(P_{e_{i}-r})$ and ${\rm
sgn}(P_{e_{i}-s})$ have the same sign and

$(HN)_{i,j}=h_{i,r}-h_{i,s}=\frac{{\rm
sgn}(P_{e_{i}-r})}{n}|T_{t}(e_{i})|-\frac{{\rm
sgn}(P_{e_{i}-s})}{n}|T_{t}(e_{i})|=0.$

Thus $HN=I_{n-1}$, $HN$ is symmetric, $HNH=H$, and $NHN=N$. It remains to show
that $NH$ is symmetric as well. We show it by proving that

$(NH)_{ij}=-\frac{{\rm sgn}(P_{i-j})}{n}.$

We distinguish the following subsets of $E^{+}(\Gamma)$, resp.
$E^{-}(\Gamma)$. Let

$\displaystyle E^{+}_{h}(i)$ $\displaystyle:=\\{e_{k}\in
E^{+}(\Gamma)|\,e_{k}\,\mbox{is incident at}\,i\,\mbox{and}\,i\in
T_{h}(e_{k})\\},$ $\displaystyle E^{+}_{t}(i)$ $\displaystyle:=\\{e_{k}\in
E^{+}(\Gamma)|\,e_{k}\,\mbox{is incident at}\,i\,\mbox{and}\,i\in
T_{t}(e_{k})\\},$ $\displaystyle E^{-}_{h}(i)$ $\displaystyle:=\\{e_{k}\in
E^{-}(\Gamma)|\,e_{k}\,\mbox{is incident at}\,i\,\mbox{and}\,i\in
T_{h}(e_{k})\\},$ $\displaystyle E^{+}_{t}(i)$ $\displaystyle:=\\{e_{k}\in
E^{-}(\Gamma)|\,e_{k}\,\mbox{is incident at}\,i\,\mbox{and}\,i\in
T_{t}(e_{k})\\}.$

The values of

$(NH)_{ij}=-\sum_{k:k\in E^{+}_{h}(i)}h_{kj}+\sum_{k:k\in
E^{+}_{t}(i)}h_{kj}+\sum_{k:k\in E^{-}_{h}(i)}h_{kj}+\sum_{k:k\in
E^{-}_{t}(i)}h_{kj}$

are computed in subsequent cases.

Case 1. Let $i\neq j$, and suppose that $i-j$ path in $T$ uses the edge
$e_{l}\in E^{+}_{h}(i).$ Then

$nh_{kj}=\begin{cases}{\rm
sgn}(P_{e_{k}-j})|T_{h}(e_{k})|&\mbox{if}\,\,k=l;\\\ -{\rm
sgn}(P_{e_{k}-j})|T_{t}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{+}_{h}(i),k\neq l;\\\
{\rm sgn}(P_{e_{k}-j})|T_{h}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{+}_{t}(i),k\neq
l;\\\ {\rm sgn}(P_{e_{k}-j})|T_{t}(e_{k})|&\mbox{if}\,\,e_{k}\in
E^{-}_{h}(i),k\neq l;\\\ {\rm
sgn}(P_{e_{k}-j})|T_{h}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{-}_{t}(i),k\neq
l,\end{cases}$

and

$\displaystyle n(NH)_{ij}$ $\displaystyle=-{\rm
sgn}(P_{e_{l}-j})|T_{h}(e_{l})|+\sum_{k:k\in E^{+}_{h}(i),\atop k\neq l}{\rm
sgn}(P_{e_{k}-j})|T_{t}(e_{k})|+\sum_{k:k\in E^{+}_{t}(i),\atop k\neq l}{\rm
sgn}(P_{e_{k}-j})|T_{h}(e_{k})|$ $\displaystyle+\sum_{k:k\in
E^{-}_{h}(i),\atop k\neq l}{\rm sgn}(P_{e_{k}-j})|T_{t}(e_{k})|+\sum_{k:k\in
E^{-}_{t}(i),\atop k\neq l}{\rm sgn}(P_{e_{k}-j})|T_{h}(e_{k})|$
$\displaystyle={\rm sgn}(P_{i-j})\Big{(}-|T_{h}(e_{l})|+\sum_{k:k\in
E^{+}_{h}(i),\atop k\neq l}|T_{t}(e_{k})|+\sum_{k:k\in E^{+}_{t}(i),\atop
k\neq l}|T_{h}(e_{k})|+\sum_{k:k\in E^{-}_{h}(i),\atop k\neq l}|T_{t}(e_{k})|$
$\displaystyle+\sum_{k:k\in E^{-}_{t}(i),\atop k\neq l}|T_{h}(e_{k})|\Big{)}$
$\displaystyle=-{\rm sgn}(P_{i-j})(-|T_{h}(e_{l})|-|T_{t}(e_{l})|+\sum_{e\in
E_{h}(i)}|T_{t}(e)|+\sum_{e\in E_{t}(i)}|T_{h}(e)|$
$\displaystyle=-n+(n-1)=-1=-{\rm sgn}(P_{i-j}).$

Case 2. Let $i\neq j$, and suppose that $i-j$ path in $T$ uses the edge
$e_{r}\in E^{+}_{t}(i).$ Then

$nh_{kj}=\begin{cases}-{\rm
sgn}(P_{e_{k}-j})|T_{t}(e_{k})|&\mbox{if}\,\,k=r;\\\ -{\rm
sgn}(P_{e_{k}-j})|T_{t}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{+}_{h}(i),k\neq r;\\\
{\rm sgn}(P_{e_{k}-j})|T_{h}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{+}_{t}(i),k\neq
r;\\\ {\rm sgn}(P_{e_{k}-j})|T_{t}(e_{k})|&\mbox{if}\,\,e_{k}\in
E^{-}_{h}(i),k\neq r;\\\ {\rm
sgn}(P_{e_{k}-j})|T_{h}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{-}_{t}(i),k\neq
r\end{cases}$

and

$\displaystyle n(NH)_{ij}$ $\displaystyle=-{\rm
sgn}(P_{e_{r}-j})|T_{t}(e_{r})|+\sum_{k:k\in E^{+}_{h}(i),\atop k\neq r}{\rm
sgn}(P_{e_{k}-j})|T_{t}(e_{k})|+\sum_{k:k\in E^{+}_{t}(i),\atop k\neq r}{\rm
sgn}(P_{e_{k}-j})|T_{h}(e_{k})|$ $\displaystyle+\sum_{k:k\in
E^{-}_{h}(i),\atop k\neq r}{\rm sgn}(P_{e_{k}-j})|T_{t}(e_{k})|\sum_{k:k\in
E^{-}_{t}(i),\atop k\neq r}{\rm sgn}(P_{e_{k}-j})|T_{h}(e_{k})|$
$\displaystyle={\rm sgn}(P_{i-j})\Big{(}-|T_{t}(e_{r})|+\sum_{k:k\in
E^{+}_{h}(i),\atop k\neq r}|T_{t}(e_{k})|+\sum_{k:k\in E^{+}_{t}(i),\atop
k\neq r}|T_{h}(e_{k})|+\sum_{k:k\in E^{-}_{h}(i),\atop k\neq r}|T_{t}(e_{k})|$
$\displaystyle+\sum_{k:k\in E^{-}_{t}(i),\atop k\neq
r}|T_{h}(e_{k})|\Big{)}={\rm sgn}(P_{i-j})(-n+n-1)=-{\rm sgn}(P_{i-j}).$

Case 3. Let $i\neq j$, and suppose that $i-j$ path in $T$ uses the edge
$e_{p}\in E^{-}_{h}(i).$ Then

$nh_{kj}=\begin{cases}{\rm
sgn}(P_{e_{p}-j})|T_{h}(e_{p})|&\mbox{if}\,\,k=p;\\\ {\rm
sgn}(P_{e_{k}-j})|T_{t}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{-}_{h}(i),k\neq p;\\\
{\rm sgn}(P_{e_{k}-j})|T_{h}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{-}_{t}(i),k\neq
p;\\\ -{\rm sgn}(P_{e_{k}-j})|T_{t}(e_{k})|&\mbox{if}\,\,e_{k}\in
E^{+}_{h}(i),k\neq p;\\\ {\rm
sgn}(P_{e_{k}-j})|T_{h}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{+}_{t}(i),k\neq
p\end{cases}$

and

$\displaystyle n(NH)_{ij}$ $\displaystyle={\rm
sgn}(P_{e_{p}-j})|T_{h}(e_{p})|+\sum_{k:k\in E^{+}_{h}(i),\atop k\neq p}{\rm
sgn}(P_{e_{k}-j})|T_{t}(e_{k})|+\sum_{k:k\in E^{+}_{t}(i),\atop k\neq p}{\rm
sgn}(P_{e_{k}-j})|T_{h}(e_{k})|$ $\displaystyle+\sum_{k:k\in
E^{-}_{h}(i),\atop k\neq p}{\rm sgn}(P_{e_{k}-j})|T_{t}(e_{k})|+\sum_{k:k\in
E^{-}_{t}(i),\atop k\neq p}{\rm sgn}(P_{e_{k}-j})|T_{h}(e_{k})|$
$\displaystyle={\rm sgn}(P_{i-j})\Big{(}-|T_{h}(e_{p})|+\sum_{k:k\in
E^{+}_{h}(i),\atop k\neq p}|T_{t}(e_{k})|+\sum_{k:k\in E^{+}_{t}(i),\atop
k\neq p}|T_{h}(e_{k})|$ $\displaystyle+\sum_{k:k\in E^{-}_{h}(i),\atop k\neq
p}|T_{t}(e_{k})|+\sum_{k:k\in E^{-}_{t}(i),\atop k\neq
p}|T_{h}(e_{k})|\Big{)}=-{\rm sgn}(P_{i-j}).$

Case 4. Let $i\neq j$, and suppose that $i-j$ path in $T$ uses the edge
$e_{q}\in E^{-}_{t}(i).$ Then

$nh_{kj}=\begin{cases}{\rm
sgn}(P_{e_{q}-j})|T_{t}(e_{q})|&\mbox{if}\,\,k=q;\\\ {\rm
sgn}(P_{e_{k}-j})|T_{t}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{-}_{h}(i),k\neq q;\\\
{\rm sgn}(P_{e_{k}-j})|T_{h}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{-}_{t}(i),k\neq
q;\\\ -{\rm sgn}(P_{e_{q}-j})|T_{t}(e_{k})|&\mbox{if}\,\,e_{k}\in
E^{+}_{h}(i),k\neq q;\\\ {\rm
sgn}(P_{e_{q}-j})|T_{h}(e_{k})|&\mbox{if}\,\,e_{k}\in E^{+}_{t}(i),k\neq
q\end{cases}$

and

$\displaystyle n(NH)_{ij}$ $\displaystyle={\rm
sgn}(P_{e_{q}-j})|T_{t}(e_{q})|+\sum_{k:k\in E^{+}_{h}(i),\atop k\neq q}{\rm
sgn}(P_{e_{q}-j})|T_{t}(e_{k})|+\sum_{k:k\in E^{+}_{t}(i),\atop k\neq q}{\rm
sgn}(P_{e_{q}-j})|T_{h}(e_{k})|$ $\displaystyle+\sum_{k:k\in
E^{-}_{h}(i),\atop k\neq q}{\rm sgn}(P_{e_{k}-j})|T_{t}(e_{k})|+\sum_{k:k\in
E^{-}_{t}(i),\atop k\neq q}{\rm sgn}(P_{e_{k}-j})|T_{h}(e_{k})|$
$\displaystyle={\rm sgn}(P_{i-j})\Big{(}-|T_{t}(e_{q})|+\sum_{k:k\in
E^{+}_{h}(i),\atop k\neq q}|T_{t}(e_{k})|+\sum_{k:k\in E^{+}_{t}(i),\atop
k\neq q}|T_{h}(e_{k})|$ $\displaystyle+\sum_{k:k\in E^{-}_{h}(i),\atop k\neq
q}|T_{t}(e_{k})|+\sum_{k:k\in E^{-}_{t}(i),\atop k\neq
q}|T_{h}(e_{k})|\Big{)}=-{\rm sgn}(P_{i-j}).$

If $i=j$, then

$\displaystyle(NH)_{ii}$ $\displaystyle=-\sum_{k:k\in
E^{+}_{h}(i)}h_{ki}+\sum_{k:k\in E^{+}_{t}(i)}h_{ki}+\sum_{k:k\in
E^{-}_{h}(i)}h_{ki}+\sum_{k:k\in E^{-}_{t}(i)}h_{ki}$
$\displaystyle=\sum_{k:k\in E^{+}_{h}(i)}|T_{t}(e_{k})|+\sum_{k:k\in
E^{+}_{t}(i)}|T_{h}(e_{i})|+\sum_{k:k\in
E^{-}_{h}(i)}|T_{t}(e_{i})|+\sum_{k:k\in E^{-}_{t}(i)}|T_{h}(e_{i})|=n-1$

If a negative edge has both negative ends, then the corresponding row in
$N^{\dagger}$ is multiplied by $-1$. ∎

######  Example 3.3.

Consider the signed tree depicted in Figure 3.1.

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$_ $6$$3$$1$$2$$7$$5$$4$ Figure 3.1. The smallest
asymmetric tree.

Then the incidence matrix

$N=\left[\begin{array}[]{rrrrrr}0&1&1&0&0&1\\\ 1&0&1&0&0&0\\\ 0&0&0&0&-1&-1\\\
0&0&0&-1&0&0\\\ 1&0&0&1&0&0\\\ 0&0&0&0&-1&0\\\
0&-1&0&0&0&0\end{array}\right]\text{ and
}N^{\dagger}=\frac{1}{7}\left[\begin{array}[]{rrrrrrr}-2&2&-2&5&5&2&-2\\\
1&-1&1&1&1&-1&-6\\\ 3&4&3&-4&-4&-3&3\\\ 1&-1&1&-6&1&-1&1\\\
-1&1&-1&-1&-1&-6&-1\\\ 2&-2&-5&2&2&5&2\end{array}\right].$
$(N^{\dagger})_{54}=-\frac{{\rm sgn}(P_{e_{5}-4})w(e_{5})}{7}{\rm
sgn}(e_{5})|T_{t}(e_{5})|=-\frac{1\cdot(-1)}{7}\cdot(-1)\cdot 1=-\frac{1}{7}$

since $4\in T_{h}(e_{5})$ and $w(e_{5})=-1$.

######  Remark 3.4.

If $\Gamma$ be a signed tree with all positive edges, then (3.1) boils down to

$n_{i,j}^{\dagger}=\frac{1}{n}\begin{cases}|T_{h}(e_{i})|&\text{ if }j\in
T_{t}(e_{i})\\\ -|T_{t}(e_{i})|&\text{ if }j\in T_{h}(e_{i}),\end{cases}$

i.e., our formula matches with the known formula given in [4].

If $\Gamma$ be a signed tree with all negative edges having both ends equal to
$1$, then

$n_{i,j}^{\dagger}=\frac{(-1)^{d(e_{i},j)}}{n}\begin{cases}|T_{h}(e_{i})|&\text{
if }j\in T_{t}(e_{i})\\\ |T_{t}(e_{i})|&\text{ if }j\in
T_{h}(e_{i}).\end{cases}$

In other words, formula (3.1) is matching the one given in [1].

We recall the notation introduced in [11]. Let $G$ be a uniyclic graph with
the unique cycle $C$. Then $G\setminus e_{i}[C]$ is the connected component of
$G\setminus e_{i}$ that contains $C$ if $e_{i}\notin C$ and $G\setminus e_{i}$
otherwise. Similarly, $G\setminus e_{i}(C)$ is the connected component of
$G\setminus e_{i}$ that does not contain $C$ if $e_{i}\in C$ and empty graph,
otherwise. It $e_{i}\notin C$, then by $G_{h}(e_{i})$ we denote the component
of $G$ that contains the head of $e_{i}.$

As pointed out in Theorem 3.1 incidence matrix of any unbalanced signed graph
is nonsingular. We next give combinatorial expressions for the entries of its
inverse.

######  Theorem 3.5.

Let $\Gamma=(G,\sigma)$ be an unbalanced unicyclic signed graph on $n$
vertices $1,2,\ldots,n$ and edges $e_{1},e_{2},\ldots,e_{n}$ with the cycle
$C$ and the incidence matrix $N$. Then $N$ is invertible and

(3.3) $(N^{-1})_{ij}=w(e_{i})\begin{cases}\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-j}\right)&\text{ if }e_{i}\in C\\\ 0&\text{ if
}e_{i}\not\in C\text{ and }j\in G\setminus e_{i}[C]\\\ -{\rm
sgn}(P_{e_{i}-j})&\text{ if }e_{i}\in E^{+}(\Gamma)\setminus E(C)\text{ and
}j\not\in G\setminus e_{i}[C]\text{ and }j\in G_{h}(e_{i})\\\ {\rm
sgn}(P_{e_{i}-j})&\text{ otherwise, }\end{cases}$

where $P_{e_{i}^{t}-j}$ denotes the path between the tail of $e_{i}\in C$ and
$j$ in the tree $G\setminus e_{i}$ and $w(e_{i})=-1$ if $e_{i}$ is a negative
edge with both negative ends and $1$ otherwise.

###### Proof.

Again we prove that the result holds for signed graphs in which all negative
edges have both positive ends. The final formula follows similarly as in the
proof Theorem 3.2.

Since $G$ is unbalanced, ${\rm rank}\,N=n$ and $N$ is invertible. Let
$A=[a_{ij}]$ where $a_{ij}$ is defined as in (3.3). It remains to show that
$AN=I_{n}$.

$(AN)_{ij}=\begin{cases}a_{iu}+a_{iv}&\text{ if }e_{j}=\\{u,v\\}\in
E^{-}(\Gamma)\\\ a_{iu}-a_{iv}&\text{ if }e_{j}=(u,v)\in E^{+}(\Gamma)\\\
-a_{iu}+a_{iv}&\text{ if }e_{j}=(v,u)\in E^{+}(\Gamma).\end{cases}$

First suppose $i=j$. If $e_{i}=e_{j}\in C$, then ($C$ being unbalanced)

$(AN)_{ij}=\begin{cases}\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-u}\right)+\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-v}\right)=\frac{1}{2}+\frac{1}{2}=1&\text{ if
}e_{j}=\\{u,v\\}\in E^{-}(\Gamma)\\\ \frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-u}\right)-\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-v}\right)=\frac{1}{2}-(-\frac{1}{2})=1&\text{ if
}e_{j}=(u,v)\in E^{+}(\Gamma)\\\ -\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-u}\right)+\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-v}\right)=-(-\frac{1}{2})+\frac{1}{2}=1&\text{ if
}e_{j}=(v,u)\in E^{+}(\Gamma).\end{cases}$

If $e_{i}=e_{j}\notin C$, then WLOG let $u\in G\setminus e_{i}[C]$ and
$v\notin G\setminus e_{i}[C]$. Then $a_{iu}=0$, $a_{iv}=\pm{\rm
sgn}(P_{e_{i}-v})$, and

$(AN)_{ij}=\begin{cases}0-(-{\rm sgn}(P_{e_{i}-v}))=1&\text{ if
}e_{j}=(u,v)\in E^{+}(\Gamma)\\\ -0+{\rm sgn}(P_{e_{i}-v})=1&\text{
otherwise}.\end{cases}$

Now suppose $i\neq j$ and $e_{j}=\\{u,v\\}$. Based on the positions of
$e_{i},e_{j}$ with respect to $C$ we separate the following cases.

Case 1. $e_{i}\notin C$ and $e_{j}\in C.$

Since $e_{i}\notin C$ and $u,v\in G\setminus e_{i}[C]$, $a_{iu}=a_{iv}=0$ and
$(AN)_{ij}=0$.

Case 2. $e_{i},e_{j}\in C.$

If $e_{j}\in E^{-}(\Gamma)$, then ${\rm sgn}\left(P_{e_{i}^{t}-u}\right)$ and
${\rm sgn}\left(P_{e_{i}^{t}-v}\right)$ are of the opposite signs ($C$ being
unbalanced) and

$(AN)_{ij}=a_{iu}+a_{iv}=\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-u}\right)+\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-v}\right)=0.$

If $e_{j}\in E^{+}(\Gamma)$, then ${\rm sgn}\left(P_{e_{i}^{t}-u}\right)$ and
${\rm sgn}\left(P_{e_{i}^{t}-v}\right)$ have the same sign and

$(AN)_{ij}=\pm(a_{iu}-a_{iv})=\pm\left(\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-u}\right)-\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-v}\right)\right)=0.$

Case 3. $e_{i},e_{j}\notin C.$

WLOG let $u$ be the vertex on $e_{j}$ that is closest to $e_{i}$. Then ${\rm
sgn}(P_{e_{i}-v})=\sigma(e_{j}){\rm sgn}(P_{e_{i}-u})$.

If $e_{j}\in E^{-}(\Gamma)$, then ${\rm sgn}(P_{e_{i}-u})=-{\rm
sgn}(P_{e_{i}-v})$ and

$(AN)_{ij}=a_{iu}+a_{iv}={\rm sgn}(P_{e_{i}-u})+{\rm sgn}(P_{e_{i}-v})=0.$

If $e_{j}\in E^{+}(\Gamma)$, then ${\rm sgn}(P_{e_{i}-u})={\rm
sgn}(P_{e_{i}-v})$ and

$(AN)_{ij}=\pm(a_{iu}-a_{iv})=\pm\left({\rm sgn}(P_{e_{i}-u})-{\rm
sgn}(P_{e_{i}-v})\right)=0.$

Case 4. $e_{i}\in C$ and $e_{j}\notin C$

WLOG let $u$ be the vertex on $e_{j}$ that is closest to the tail of $e_{i}$
in the tree $G\setminus e_{i}$. Then ${\rm
sgn}\left(P_{e_{i}^{t}-v}\right)=\sigma(e_{j}){\rm
sgn}\left(P_{e_{i}^{t}-u}\right)$.

If $e_{j}\in E^{-}(\Gamma)$, then ${\rm sgn}\left(P_{e_{i}^{t}-u}\right)$ and
${\rm sgn}\left(P_{e_{i}^{t}-v}\right)$ have opposite signs and

$(AN)_{ij}=a_{iu}+a_{iv}=\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-u}\right)+\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-v}\right)=0.$

If $e_{j}\in E^{+}(\Gamma)$, then ${\rm sgn}\left(P_{e_{i}^{t}-u}\right)$ and
${\rm sgn}\left(P_{e_{i}^{t}-v}\right)$ have the same sign and

$(AN)_{ij}=\pm(a_{iu}-a_{iv})=\pm\left(\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-u}\right)-\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-v}\right)\right)=0.$

This completes the proof. ∎

######  Example 3.6.

For the signed unbalanced graph depicted in Figure 3.2, the results of Theorem
3.5 are exemplified in computations of $(N^{-1})_{74}$ and $(N^{-1})_{26}.$

$(N^{-1})_{74}=\frac{1}{2}w(e_{7}){\rm sgn}(P_{e_{7}^{t}-4})=\frac{1}{2}\cdot
1\cdot(-1)=-\frac{1}{2}$ $(N^{-1})_{26}=w(e_{2}){\rm
sgn}(P_{e_{2}-6})=(-1)\cdot 1=-1.$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$6$$8$$9$$4$$7$$1$$3$$5$$2$ Figure 3.2. An unbalanced even unicyclic graph
$\Gamma_{1}$.

In particular,

$\scriptsize N=\left[\begin{array}[]{rrrrrrrrr}0&0&1&0&0&0&0&0&0\\\
0&0&1&1&1&0&0&0&0\\\ 0&0&0&0&-1&0&0&0&0\\\ 1&-1&0&0&0&0&-1&0&1\\\
0&0&0&1&0&1&0&1&0\\\ 0&-1&0&0&0&0&0&0&0\\\ 0&0&0&0&0&1&0&0&1\\\
-1&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&1&1&0\end{array}\right],\;N^{-1}=\frac{1}{2}\left[\begin{array}[]{rrrrrrrrr}0&0&0&0&0&0&0&-2&0\\\
0&0&0&0&0&-2&0&0&0\\\ 2&0&0&0&0&0&0&0&0\\\ -2&2&2&0&0&0&0&0&0\\\
0&0&-2&0&0&0&0&0&0\\\ 1&-1&-1&-1&1&1&1&-1&-1\\\ -1&1&1&-1&-1&1&1&-1&1\\\
1&-1&-1&1&1&-1&-1&1&1\\\ -1&1&1&1&-1&-1&1&1&1\end{array}\right]$

######  Remark 3.7.

If $\Gamma$ is an unbalanced odd unicyclic signed graph with all negative
edges, with both positive ends, then the general formula (3.3) is matching the
known formula given in [11]:

$(N^{-1})_{ij}=\begin{cases}\frac{1}{2}(-1)^{d(e_{i},j)}&\text{ if }e_{i}\in
C\\\ 0&\text{ if }e_{i}\not\in C\text{ and }j\in V(G)\setminus e_{i}[C]\\\
(-1)^{d(e_{i},j)}&\text{ if }e_{i}\notin E(C)\text{ and }j\not\in
V(G)\setminus e_{i}[C],\end{cases}$

due to $w(e_{i})=1$ for any $e_{i}\in E(\Gamma)$.

##  4\. Moore-Penrose inverse of the incidence matrix of a signed graph

In this section we implement results of previous two, in order to obtain
expression for the Moore-Penrose inverse of the incidence matrix of any
connected signed graph.

######  Theorem 4.1.

Let $\Gamma=(G,\sigma)$ be a connected signed graph on $n\geq 2$ vertices
$1,2,\ldots,n$ and $m$ edges $e_{1},e_{2},\ldots,e_{m}$ with incidence matrix
$N$, $w(e_{i})$ being $-1$ for negative edges with both negative ends and $1$,
otherwise.

  1. (a)

If $\Gamma$ is balanced, then

(4.1)
$(N^{\dagger})_{ij}=\frac{1}{\tau(\Gamma)}\sum_{\begin{subarray}{c}T\in\mathcal{S}(\Gamma)\\\
e_{i}\in T\end{subarray}}(N_{T}^{\dagger})_{ij},$

where $\mathcal{S}(\Gamma)$ is the set of all spanning trees $T$ of $\Gamma$
and when $e_{i}\in T$,

(4.2) $(N_{T}^{\dagger})_{ij}=\frac{w(e_{i}){\rm
sgn}(P_{e_{i}-j})}{n}\begin{cases}|T_{h}(e_{i})|&\text{ if }j\in
T_{t}(e_{i})\\\ -\sigma(e_{i})|T_{t}(e_{i})|&\text{ if }j\in
T_{h}(e_{i})\end{cases}$

($P_{e_{i}-j}$ being in $T$).

  2. (b)

If $\Gamma$ is unbalanced, then

(4.3)
$(N^{-1})_{ij}=\frac{1}{\sum_{H\in\mathcal{TU}_{n}(\Gamma)}4^{c(H)}}\sum_{\begin{subarray}{c}H\in\mathcal{TU}_{n}(\Gamma)\\\
e_{i}\in H\end{subarray}}4^{c(H)}(N_{H}^{-1})_{ij},$

where $\mathcal{TU}_{n}(\Gamma)$ is the set of all spanning $TU$-subgraphs $H$
of $\Gamma$ with $n$ edges consisting of $c(H)$ unbalanced unicyclic graphs
$U^{H}_{1},U^{H}_{2},\ldots,U^{H}_{c(H)}$ with cycles
$C^{H}_{1},C^{H}_{2},\ldots,C^{H}_{c(H)}$ respectively and when $e_{i}\in
U^{H}_{r}$ for some $r$,

(4.4) $(N_{H}^{-1})_{ij}=\begin{cases}\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-j}\right)&\text{ if }e_{i}\in C^{H}_{r}\\\ 0&\text{ if
}e_{i}\not\in C_{r}\text{ and }j\in U^{H}_{r}\setminus e_{i}[C^{H}_{r}]\\\
-{\rm sgn}(P_{e_{i}-j})&\text{ if }e_{i}\in E^{+}(U^{H}_{r})\setminus
E(C^{H}_{r})\text{ and }j\not\in U^{H}_{r}\setminus e_{i}[C^{H}_{r}]\text{ and
}j\in(U^{H}_{r})_{h}(e_{i})\\\ {\rm sgn}(P_{e_{i}-j})&\text{ otherwise,
}\end{cases}$

where $P_{e_{i}^{t}-j}$ denotes the path between the tail of $e_{i}\in
C^{H}_{r}$ and $j$ in the tree $U_{r}^{H}\setminus e_{i}$.

###### Proof.

The formulas follow by (2.1) and Theorems 2.4, 3.2, 3.5 taking into account
that for a $TU$-spanning subgraph $H$ of $\Gamma$ with $c(H)$ unbalanced
unicyclic graphs, $U^{H}_{1},\ldots,U^{H}_{c(H)}$, with unique odd cycles
$C^{H}_{1},\ldots,C^{H}_{c(H)}$ respectively, the incidence matrix $N_{H}$ is
of the form

$N_{H}=\begin{pmatrix}N_{U^{H}_{1}}\oplus\cdots\oplus
N_{U^{H}_{c(H)}}&O\end{pmatrix}P,$

where $N_{U^{H}_{\ell}}$ denotes the incidence matrix of $U^{H}_{\ell}$,
$1\leq\ell\leq c(H)$ and $P$ is the corresponding permutation matrix. Then

$(N_{H})^{\dagger}=P^{\intercal}\begin{pmatrix}(N_{U^{H}_{1}})^{-1}\oplus\cdots\oplus(N_{U^{H}_{c(H)}})^{-1}\\\
O\end{pmatrix},$

taking into account that $P^{\intercal}=P^{-1}$. ∎

Next, we provide the explicit formula for the Moore-Penrose inverse of
balanced unicyclic graph.

######  Theorem 4.2.

Let $\Gamma=(G,\sigma)$ be a connected balanced unicyclic graph on $n$
vertices $1,2,\ldots,n$ with incidence matrix $N$, the unique cycle $C$ with
$E(C)=\\{e_{1},\ldots,e_{|C|}\\}$, $T_{k}=G\setminus e_{k}$, $1\leq k\leq|C|$
and $w(e_{i})$ being $-1$ for negative edges with both negative ends and $1$,
otherwise. Then the following holds.

  * (a)

If $e_{i}\notin C$ and $j\in G\setminus e_{i}[C]$, then either $j\in
T_{h}^{T_{k}}(e_{i})$ for all $k\in\\{1,\ldots,|C|\\}$ or $j\in
T_{t}^{T_{k}}(e_{i})$ for all $k\in\\{1,\ldots,|C|\\}$.

  * (b)

$(N^{\dagger})_{ij}=\frac{w(e_{i}){\rm
sgn}(P_{e_{i}-j})}{n|C|}\cdot\begin{cases}|C||G\setminus
e_{i}(C)|\,\,\,\mbox{if}\,\,\,e_{i}\notin E(C),j\in G\setminus e_{i}[C],j\in
T_{t}^{T_{k}}(e_{i})\mbox{ for some $T_{k}$,}\\\ -{\rm
sgn}(e_{i})|C||G\setminus e_{i}[C]|\,\,\,\mbox{if}\,\,\,e_{i}\notin E(C),j\in
G\setminus e_{i}[C],j\in T_{h}^{T_{k}}(e_{i})\mbox{ for some $T_{k}$,}\\\
\sum_{k=1\atop e_{i}\in
T_{k}}^{|C|}\phi_{T_{k}}(e_{i},j)\,\,\,\mbox{if}\,\,\,e_{i}\in E(C),j\in
V(G),\end{cases}$

where

$\phi_{T}(e_{i},j)=\begin{cases}|T_{h}(e_{i})|\mbox{ if }j\in T_{t}(e_{i})\\\
-\sigma(e_{i})|T_{t}(e_{i})|\mbox{ if }j\in T_{h}(e_{i}).\end{cases}$

###### Proof.

Since $\Gamma$ is connected balanced unicyclic graph, the number of spanning
trees is $\tau(G)=|C|$ and the spanning trees are $T_{k},1\leq k\leq|C|$. Let
$e_{i}\notin C,$ and $j\in G\setminus e_{i}[C]$. Then for all $k$,
$T_{k}\setminus e_{i}$ contains $j$ either in the tail or in the head. In
addition, $|T^{T_{k}}_{t}(e_{i})|=|G\setminus e_{i}(C)|,$ while
$|T^{T_{k}}_{h}(e_{i})|=|G\setminus e_{i}[C)].$

By Theorem 4.1 (a)

$(N^{\dagger})_{ij}=\frac{1}{|C|}\sum_{k=1}^{|C|}(N^{\dagger}_{T_{k}})_{ij},$

where

$(N^{\dagger}_{T_{k}})_{ij}=\frac{w(e_{i}){\rm
sgn}(P_{e_{i}-j})}{n}\begin{cases}|G\setminus e_{i}(C)|&\mbox{ if $e_{i}\notin
E(C),j\in G\setminus e_{i}[C],j\in T_{t}^{T_{k}}(e_{i})$ }\\\ |G\setminus
e_{i}[C]|&\mbox{ if $e_{i}\notin E(C),j\in G\setminus e_{i}[C],j\in
T_{h}^{T_{k}}(e_{i})$ }\\\ |T^{T_{k}}_{h}(e_{i})|&\mbox{ if $e_{i}\in C,j\in
T^{T_{k}}_{t}(e_{i})$ }\\\ -\sigma(e_{i})|T^{T_{k}}_{t}(e_{i})|&\mbox{ if
$e_{i}\in C,j\in T^{T_{k}}_{h}(e_{i})$. }\end{cases}$

Hence,

$\sum_{k=1}^{|C|}(N^{\dagger}_{T_{k}})_{ij}=\frac{w(e_{i}){\rm
sgn}(P_{e_{i}-j})}{n}\begin{cases}|C||G\setminus e_{i}(C)|&\mbox{ if
$e_{i}\notin E(C),j\in G\setminus e_{i}[C],j\in T_{t}^{T_{k}}(e_{i})$ }\\\
|C||G\setminus e_{i}[C]|&\mbox{ if $e_{i}\notin E(C),j\in G\setminus
e_{i}[C],j\in T_{h}^{T_{k}}(e_{i})$ }\\\ \sum_{k=1\atop e_{i}\in
T_{k}}^{|C|}\phi_{T_{k}}(e_{i},j)&\mbox{ if}\,\,\,e_{i}\in E(C),j\in
V(G).\end{cases}$

Finally, devision by $|C|$ in the previous equality leads to
$(N^{\dagger})_{ij}$, i.e., to the expression given in (b). ∎

######  Example 4.3.

For the unbalanced graph, $\Gamma_{2}$ depicted in Figure 4.1, spanning
$TU$-subgraphs on $9$ edges are enclosed in Figure 4.2.

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$_
$6$$8$$9$$4$$7$$1$$3$$5$$2$ Figure 4.1. An unbalanced bicyclic graph
$\Gamma_{2}$.

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$_
$6$$8$$9$$7$$3$$1$$4$$5$$2$$G_{11}$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$_
$6$$8$$9$$7$$3$$1$$4$$5$$2$$G_{12}$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$_
$6$$8$$9$$7$$3$$1$$4$$5$$2$$G_{13}$

Figure 4.2. Spanning $TU$-subgraphs of $\Gamma_{2}$ on $9$ edges.

In this case ${\rm vol}^{2}N=4+4+4=12.$ Then,

$(N^{\dagger})_{53}=\frac{1}{12}(4\cdot(-{\rm
sgn}_{G_{12}}(P_{e_{5}-3}))+4(-{\rm
sgn}_{G_{13}}(P_{e_{5}-3})))=-\frac{8}{12}=-\frac{2}{3}.$

######  Example 4.4.

In this example we consider unbalanced bicyclic graphs $\Gamma_{3}$ with two
negative cycles.

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$ Figure 4.3. A bicyclic graph $\Gamma_{2}$
that contains two odd cycles.

Spanning subgraphs on $n=9$ edges of $\Gamma_{3}$ are depicted in Figure 4.4.

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$

_$-e_{5}$_ $w(e_{5})=-1$_$+e_{6}$__$+e_{2}$__$-e_{3}$_ $w(e_{3})=1$_$-e_{1}$_
$w(e_{1})=1$_$+e_{4}$__$-e_{2}$_
$w(e_{2})=-1$_$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{2}$__$+e_{1}$__$-e_{9}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$__$-e_{10}$__$-e_{2}$__$-e_{9}$__$+e_{1}$__$+e_{7}$__$-e_{6}$__$-e_{8}$__$-e_{4}$__$-e_{3}$__$+e_{5}$_
$+e_{10}$$6$$8$$9$$7$$3$$1$$4$$5$$2$

Figure 4.4. Spanning $TU$ subgraphs of $H$

Therefore,

${\rm vol}^{2}N=7\cdot 4+4^{2}=44$

and

$(N^{\dagger})_{53}=\frac{1}{44}\big{(}-4\cdot\frac{1}{2}-4\cdot\frac{1}{2}-4\cdot
1-4\cdot\frac{1}{2}-4\cdot
1-4\cdot\frac{1}{2}-4^{2}\cdot\frac{1}{2}\big{)}=-\frac{24}{44}=-\frac{6}{11}.$

######  Remark 4.5.

If $\Gamma$ is a connected signed graph with all positive edges, then general
formula is matching the known formula from [4]. If $\Gamma$ is a connected
signed graph with all negative edges, then general formula matches the one
given in [1].

##  5\. Moore-Penrose inverse of the Laplacian matrix of a signed graph

In this final section we consider the Moore-Penrose inverse of the Laplacian
matrix of a connected signed graph.

######  Theorem 5.1.

Let $\Gamma=(G,\sigma)$ be a connected signed graph on $n\geq 2$ vertices
$1,2,\ldots,n$ and $m$ edges $e_{1},e_{2},\ldots,e_{m}$ with the Laplacian
matrix $L$.

  1. (a)

If $\Gamma$ is balanced, then

(5.1)
$(L^{\dagger})_{ij}=\frac{1}{n^{2}\tau(\Gamma)^{2}}\sum_{k=1}^{m}\sum_{\begin{subarray}{c}T_{r},T_{s}\in\mathcal{S}(\Gamma)\\\
e_{k}\in T_{r},T_{s}\end{subarray}}{\rm sgn}(P_{T_{r}}(e_{k}-i)){\rm
sgn}(P_{T_{s}}(e_{k}-j))\Psi(e_{k},i,j),$

where

(5.2)
$\Psi(e_{k},i,j)=\begin{cases}|T^{T_{r}}_{h}(e_{k})||T^{T_{s}}_{h}(e_{k})|&\text{
if }i\in T^{T_{r}}_{t}(e_{k})\text{ and }j\in T^{T_{s}}_{t}(e_{k})\\\
|T^{T_{r}}_{t}(e_{k})||T^{T_{s}}_{t}(e_{k})|&\text{ if }i\in
T^{T_{r}}_{h}(e_{k})\text{ and }j\in T^{T_{s}}_{h}(e_{k})\\\ -{\rm
sgn}(e_{k})|T^{T_{r}}_{h}(e_{k})||T^{T_{s}}_{t}(e_{k})|&\text{
otherwise}.\end{cases}$

  2. (b)

If $\Gamma$ is unbalanced, then

(5.3)
$(L^{-1})_{ij}=\frac{1}{(\sum_{H\in\mathcal{TU}_{n}(\Gamma)}4^{c(H)})^{2}}\sum_{k=1}^{m}\sum_{\begin{subarray}{c}H\in\mathcal{TU}_{n}(\Gamma)\\\
e_{k}\in
H\end{subarray}}4^{c(H)}(N_{H}^{+})_{ki}\sum_{\begin{subarray}{c}H\in\mathcal{TU}_{n}(\Gamma)\\\
e_{k}\in H\end{subarray}}4^{c(H)}(N_{H}^{+})_{kj},$

where $\mathcal{TU}_{n}(\Gamma)$ is the set of all spanning $TU$-subgraphs $H$
of $\Gamma$ with $n$ edges consisting of $c(H)$ unbalanced unicyclic graphs
$U^{H}_{1},U^{H}_{2},\ldots,U^{H}_{c(H)}$ with cycles
$C^{H}_{1},C^{H}_{2},\ldots,C^{H}_{c(H)}$ respectively and when $e_{i}\in
U^{H}_{r}$ for some $r$, then

(5.4) $(N_{H}^{\dagger})_{ij}=\begin{cases}\frac{1}{2}{\rm
sgn}\left(P_{e_{i}^{t}-j}\right)&\text{ if }e_{i}\in C^{H}_{r}\\\ 0&\text{ if
}e_{i}\not\in C_{r}\text{ and }j\in U^{H}_{r}\setminus e_{i}[C^{H}_{r}]\\\
-{\rm sgn}(P_{e_{i}-j})&\text{ if }e_{i}\in E^{+}(U^{H}_{r})\setminus
E(C^{H}_{r})\text{ and }j\not\in U^{H}_{r}\setminus e_{i}[C^{H}_{r}]\text{ and
}j\in(U^{H}_{r})_{h}(e_{i})\\\ {\rm sgn}(P_{e_{i}-j})&\text{ otherwise,
}\end{cases}$

where $P_{e_{i}^{t}-j}$ denotes the path between the tail of $e_{i}\in
C^{H}_{r}$ and $j$ in the tree $U_{r}^{H}\setminus e_{i}$.

###### Proof.

The expressions follow from

$L=NN^{\intercal}\implies L^{\dagger}=(N^{\dagger})^{\intercal}N^{\dagger}.$

(a) For $N^{\dagger}=[n_{ij}]$,

$(L^{\dagger})_{ij}=\sum_{k=1}^{m}n_{ki}n_{kj}=\frac{1}{n\tau(\Gamma)}\sum_{T\in
S(\Gamma)\atop e_{k}\in
T}({N_{T}^{\dagger}})_{ki}\frac{1}{n\tau(\Gamma)}\sum_{T\in S(\Gamma)\atop
e_{k}\in
T}({N_{T}^{\dagger}})_{kj}=\frac{1}{n^{2}\tau(\Gamma)^{2}}\sum_{T_{t},T_{s}\in
S(\Gamma)\atop e_{k}\in
T_{r},T_{s}}({N_{T}^{\dagger}})_{ki}({N_{T}^{\dagger}})_{kj}$

Taking into account the results on $N_{T}^{\dagger}$ given in Theorem 3.2 we
arrive to

$({N_{T}^{\dagger}})_{ki}({N_{T}^{\dagger}})_{kj}={\rm
sgn}(P_{T_{r}}(e_{k}-i)){\rm sgn}(P_{T_{s}}(e_{k}-j))\Psi(e_{k},i,j),$

as desired.

The proof of (b) follows in a similar way. ∎

##  6\. Open problems

It can be verified that for a signed graph $\Gamma$,

$\ell^{\dagger}_{ii}+\ell^{\dagger}_{jj}-2{\rm
sgn}(P_{i-j})\ell^{\dagger}_{ij}=d(i,j).$

This property can lead to the definition of resistance matrix $R$,
$r_{ij}=\ell^{\dagger}_{ii}+\ell^{\dagger}_{jj}-2{\rm
sgn}(P_{i-j})\ell^{\dagger}_{ij}$ of signed graphs. It might be worth
considering the properties of this matrix as well as its rise to the Kemany’s
constant of signed graphs (as suggested in [14]).

Barik et al. introduced some complex matrices associated with a multidigraph
via a certain weighted graph [5]. It will be interesting to find out what
their Moore-Penrose inverses tell us about the associated multidigraph.

######  Question 6.1.

Find combinatorial formulas for the following matrices for a connected
multidigraph: (a) complex incidence and complex Laplacian matrices, and (b)
complex signless incidence and complex signless Laplacian matrices.

Acknowledgments
The authors would like to thank Thomas Zaslavsky for inspiring them to look
into signed graphs in the study of Moore-Penrose inverses of the associated
matrices.

The research of the second author is partially supported by the Science Fund
of the Republic of Serbia; grant number 7749676: Spectrally Constrained Signed
Graphs with Applications in Coding Theory and Control Theory – SCSG-ctct.

## References

  * [1] A. Alazemi, O. Alhalabi, M. Anđelić, Moore-Penrose inverse of the signless Laplacians of bipartite graphs, Bull. Iran. Math. Soc. 49, 51 (2023).
  * [2] A. Azimi and R.B. Bapat, Moore-Penrose inverse of the incidence matrix of a distance regular graph, Linear Algebra Appl. 551 (2018) 92–103.
  * [3] A. Azimi, R.B. Bapat, and E. Estaji, Moore-Penrose inverse of incidence matrix of graphs with complete and cyclic blocks, Discrete Mathematics 342 (2019) 10–17.
  * [4] R.B. Bapat, Moore-Penrose inverse of the incidence matrix of a tree, Linear Multilinear Algebra 42 (1997) 159–167.
  * [5] Barik, S., Reddy, S. U., and Sahoo, G., On singularity and properties of eigenvectors of complex Laplacian matrix of multidigraphs, AKCE Int. J. Graphs Comb. 20(2):125–133.
  * [6] F. Belardo, S.K. Simić, On the Laplacian coefficients of signed graphs, Linear Algebra Appl. 475 (2015), 94–113.
  * [7] Andries E. Brouwer and Williem H. Haemers, Spectra of Graphs, Springer-Verlag New York (2012).
  * [8] Dragoš Cvetković, Peter Rowlinson, and Slobodan K. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423 (2007) 155–171.
  * [9] Keivan Hassani Monfared and Sudipta Mallik, An analog of matrix tree theorem for signless Laplacians, Linear Algebra Appl. 560 (2019) 43–55.
  * [10] Ryan Hessert and Sudipta Mallik, Moore-Penrose inverses of the signless Laplacian and edge-Laplacian of graphs, Discrete Mathematics 344 (2021) 112451.
  * [11] Ryan Hessert and Sudipta Mallik, The inverse of the incidence matrix of a unicyclic graph, Linear Multilinear Algebra, 71 (2023), 513–527.
  * [12] Yuji Ijiri, On the generalized inverse of an incidence matrix, Jour. Soc. Indust. Appl. Math., 13(3):827–836 (1965).
  * [13] Jerad Ipsen and Sudipta Mallik, Incidence and Laplacian matrices of wheel graphs and their inverses, American Journal of Combinatorics, 2 (2023), 1–19.
  * [14] Louis W. Shapiro, An electrical lemma, Mathematics Magazine, 60 (1987), 36–38.