# On the Moore-Penrose pseudo-inversion of block symmetric matrices and its
application in the graph theory

Soňa Pavlíková1 1 Alexander Dubček University of Trenčín, Slovakia  and
Daniel Ševčovič2 2 Department of Applied Mathematics and Statistics, Faculty
of Mathematics Physics and Informatics, Comenius University, Mlynská dolina,
842 48, Bratislava, Slovakia. Corresponding author<EMAIL_ADDRESS>
###### Abstract.

The purpose of this paper is to analyze the Moore-Penrose pseudo-inversion of
symmetric real matrices with application in the graph theory. We introduce a
novel concept of positively and negatively pseudo-inverse matrices and graphs.
We also give sufficient conditions on the elements of a block symmetric matrix
yielding an explicit form of its Moore-Penrose pseudo-inversion. Using the
explicit form of the pseudo-inverse matrix we can construct pseudo-inverse
graphs for a class of graphs which are constructed from the original graph by
adding pendent vertices or pendant paths.

Keywords: Pseudo-invertible matrix and graph; positively and negatively
pseudo-invertibility; bridged graph generalized Schur complement;

2000 MSC: 05C50 05B20 05C22 15A09 15A18 15B36

Acknowledgments: Support of the Slovak Research and Development Agency under
the projects APVV-19-0308 (SP), and APVV-20-0311 (DS) is kindly acknowledged.

##  1\. Introduction

In this paper we investigate the Moore-Penrose pseudo-inversion of block
symmetric matrices with application in the graph theory. We present sufficient
conditions on the elements of a block matrix yielding an explicit block matrix
form of its Moore-Penrose inversion. We also introduce a novel concept of
positively and negatively pseudo-invertible matrix. In the context of the
graph theory we extend the concept of positive and negative invertibility of a
graph due to Godsil [9], Pavlíková and Ševčovič [19] to the case when its
adjacency matrix is not invertible.

In the past decades various ways of introducing inverses of graphs have been
proposed. They are based on inversion of the adjacency matrix. Except of the
trivial case when the graph is a union of isolated edges, the inverse matrix
need not define a graph again because it may contain negative entries (cf.
[13]). A successful approach how to overcome this difficulty was proposed by
Godsil [9] who defined a graph to be invertible if the inverse of its non-
singular adjacency matrix is diagonally similar (cf. [27]) to a nonnegative
integral matrix representing the adjacency matrix of the inverse graph in
which positive labels determine edge multiplicities. In [19], Pavlíková and
Ševčovič extended this notion to a wider class of graphs by introducing the
concept of negative invertibility of a graph. Both positively and negatively
invertible graphs have the appealing property that inverting an inverse graph
gives back the original graph. For a survey of results and other approaches to
graph inverse, we recommend [16]. Godsil’s ideas have been further developed
in several ways. Akbari and Kirkland [14], Kirkland and Tifenbach [15], and
Bapat and Ghorbani [1] studied inverses of edge-labeled graphs with labels in
a ring, Ye _et al._ [25] considered connections of graph inverses with median
eigenvalues, and Pavlíková [18] developed constructive methods for generating
invertible graphs by edge overlapping. A large number of related results,
including a unifying approach to inverting graphs, were proposed in a recent
survey paper by McLeman and McNicholas [16], with emphasis on inverses of
bipartite graphs and diagonal similarity to nonnegative matrices.

In theoretical chemistry, biology, or statistics, spectral indices and
properties of graphs representing structure of chemical molecules or
transition diagrams for finite Markov chains play an important role (cf.
Cvetković [6, 8], Brouwer and Haemers [4] and references therein). Various
graph energies and indices have been proposed and analyzed. For instance, the
sum of absolute values of eigenvalues is referred to as the matching energy
index (cf. Chen and Liu [34]), the maximum of the absolute values of the least
positive and largest negative eigenvalue is known as the HOMO-LUMO index (see
Mohar [35, 36], Li _et al._ [37], Jaklić _et al._ [38], Fowler _et al._ [40]),
their difference is the HOMO-LUMO separation gap (cf. Gutman and Rouvray [41],
Li _et al._ [37], Zhang and An [42], Fowler _et al._ [39]). It turns out that
properties of maximal and minimal eigenvalues of the inverse graph can be used
in order to analyze the least positive and largest negative eigenvalues of an
adjacency matrix.

Recently, McDonald, Raju, and Sivakumar investigated Moore-Penrose inverses of
matrices associated with certain graph classes [31] whose adjacency matrices
are singular. They derived formulae for pseudo-inverses of matrices that are
associated with a class of digraphs obtained from stars. This new class
contains both bipartite and non-bipartite graphs. A blockwise representation
of the (pseudo)inverse of the adjacency matrix of the Dutch windmill graph is
also presented in [31]. In [33] Pavlíková, and Krivoňáková gave
characterization of pseudo-inverses of cycles. In the context of the Laplacian
of connections of a graph, Hessert and Mallik [30] and Gago [32] studied
Moore-Penrose inverses of the signless Laplacian and edge-Laplacian of graphs
or networks. They found combinatorial formulae of the Moore-Penrose inverses
for trees and odd unicyclic graphs. In [22] Pavlíková and Širáň constructed a
pseudo-inverse of a weighted tree, based solely on considering maximum
matchings and alternating paths.

Recall that the complete list due to McKay of simple connected graphs is
available at http://users.cecs.anu.edu.au/~bdm/data/graphs.html. In Section 3
(see Table 1) we present our computations of total numbers of simple connected
graphs based on the McKay’s list together with a survey of integrally
positive/negative invertible graphs (see Pavlíková and Ševčovič [23]). When
the number of vertices increases we can observe less proportion of positively
or negatively invertible graphs although all adjacency matrices are pseudo-
invertible in the Moore-Penrose sense. It is the main purpose of this paper to
introduce and analyze concept of positively and negatively pseudo-invertible
graphs. We also present possible applications in the spectral graph theory.
Furthermore, we are concerned with spectral properties of real block symmetric
matrices of the form

(1) $\mathscr{M}=\left(\begin{array}[]{cc}A&K\\\ K^{T}&B\end{array}\right),$

where $A$, and $B$ are $n\times n$, and $m\times m$ real symmetric matrices,
and $K$ is an $n\times m$ real matrix. Such an adjacency matrix $\mathscr{M}$
corresponds to the graph $G_{\mathcal{M}}$ on $n+m$ vertices which is obtained
by bridging the vertices of the graph $G_{A}$ to the vertices of $G_{B}$
through the $(n,m)$-bipartite graph $G_{K}$ (cf. Pavlíková and Ševčovič [21,
20]), i. e., its adjacency matrix ${\mathcal{M}}$ of the graph
$G_{\mathcal{M}}$ has the form of (1) (see Fig. 1). Using the explicit form of
the Moore-Penrose pseudo-inverse of the block matrix $\mathscr{M}$ we derive
explicit form of pseudo-inverse graphs for graphs which are constructed from a
given graph by adding pendant vertices or pendant paths.

Figure 1.  Graphs $G_{A}$, $G_{B}$, and a bipartite graph $G_{K}$ (left). A
bridged graph through a bipartite graph $G_{K}$ (right).

The rest of the paper are organized as follows. In Section 2 we recall the
classical concept of the Moore-Penrose pseudo-inversion
$\mathscr{M}^{\dagger}$ of a matrix $\mathscr{M}$. Maximal and minimal
eigenvalues of a pseudo-inverse matrix $\mathscr{M}^{\dagger}$ are closely
related to the least positive $\lambda_{+}(\mathscr{M})>0$ and the largest
negative eigenvalues $\lambda_{-}(\mathscr{M})<0$ of a symmetric real matrix
$\mathscr{M}$. We present the key idea of derivation of the explicit
Banachiewicz–Schur form of the Moore-Penrose pseudo-inverse of a block
symmetric matrix. It can be used in order to characterize the least positive
and the largest negative eigenvalues in terms of semidefinite optimization
problem. Section 3 is devoted to pseudo-invertibility of simple connected
graphs. We introduce a novel concept of positively and negatively pseudo-
invertibility of a graphs. We also present a summary table containing number
of positively/negatively pseudo-invertible graphs. The list of graphs with no
more than 10 vertices contains complete information on various classes of
(pseudo)invertible graphs including their spectral properties. Furthermore, we
present special examples of pseudo-invertible graphs constructed from a given
graph by adding pendant vertices or pendant paths.

##  2\. Moore-Penrose pseudo-inversion of a block symmetric matrix and its
application in spectral theory

In this section we derive an explicit form of the Moore-Penrose pseudo-inverse
matrix for a given block symmetric matrix satisfying certain assumptions on
the entries of the block matrix. First, we recall the classical notion of the
Moore-Penrose pseudo-inverse matrix. Let
$\Lambda=diag\left(\lambda_{1},\ldots,\lambda_{N}\right)$ be a diagonal matrix
with real eigenvalues $\lambda_{i}\in\mathbb{R},i,\ldots,N$. For a diagonal
real matrix we can define the pseudo-inverse matrix as follows:

$\Lambda^{\dagger}=diag\left(\mu_{1},\ldots,\mu_{N}\right)\quad
where\quad\mu_{i}=1/\lambda_{i}\ \ if\ \lambda_{i}\neq 0,\ and,\ \mu_{i}=0\
if\ \lambda_{i}=0.$

If $\mathscr{M}$ is an $N\times N$ real symmetric matrix, then it is
orthogonally similar to a diagonal matrix $\Lambda$, i. e., there exists a
matrix $\mathscr{P}$ such that
$\mathscr{P}^{T}\mathscr{P}=\mathscr{P}\mathscr{P}^{T}=I$ and
$\mathscr{P}\mathscr{M}\mathscr{P}^{T}=\Lambda=\operatorname{diag}\left(\lambda_{1},\ldots,\lambda_{N}\right)$,
$\lambda_{i}$ being real eigenvalues of $\mathscr{M}$. Let
$\mathscr{M}^{\dagger}$ be the Moore-Penrose pseudo-inverse matrix satisfying
Moore-Penrose axioms for symmetric matrices, i. e.,

(2)
$\mathscr{M}\mathscr{M}^{\dagger}=\mathscr{M}^{\dagger}\mathscr{M},\quad\mathscr{M}\mathscr{M}^{\dagger}\mathscr{M}=\mathscr{M},\quad\mathscr{M}^{\dagger}\mathscr{M}\mathscr{M}^{\dagger}=\mathscr{M}^{\dagger}.$

Then $\mathscr{M}^{\dagger}$ can be uniquely defined as follows:
$\mathscr{M}^{\dagger}=\mathscr{P}^{T}\Lambda^{\dagger}\mathscr{P}$. Clearly,
$\mathscr{M}^{\dagger}$ is a symmetric matrix, and
$(\mathscr{M}^{\dagger})^{\dagger}=\mathscr{M}$. Furthermore,
$\mathscr{M}^{\dagger}=\mathscr{M}^{-1}$ provided that the matrix
$\mathscr{M}$ is invertible. If $K$ is an $n\times m$ real matrix, then its
Moore-Penrose inverse matrix is an $m\times n$ matrix $K^{\dagger}$ which is
uniquely determined by the Moore-Penrose identities:

(3)
$(KK^{\dagger})^{T}=KK^{\dagger},\quad(K^{\dagger}K)^{T}=K^{\dagger}K,\quad
KK^{\dagger}K=K,\quad K^{\dagger}KK^{\dagger}=K^{\dagger}.$

For further properties of generalized Moore-Penrose inverses we refer the
reader to [3].

Suppose that $\mathscr{M}$ is a symmetric real matrix having positive and
negative eigenvalues. This is a typical case when $\mathscr{M}$ represents an
adjacency matrix of a simple graph with no loops having zeros in its diagonal,
and so the largest eigenvalue is positive whereas the least eigenvalue is
negative. Clearly, the least positive $\lambda_{+}(\mathscr{M})$ and largest
negative $\lambda_{-}(\mathscr{M})$ eigenvalues of $\mathscr{M}$ can be
expressed as follows (see e.g. [19]):

(4)
$\lambda_{+}(\mathscr{M})=\lambda_{max}(\mathscr{M}^{\dagger})^{-1},\qquad\lambda_{-}(\mathscr{M})=\lambda_{min}(\mathscr{M}^{\dagger})^{-1}.$

Here $\lambda_{max}(\mathscr{M}^{\dagger})>0$ and
$\lambda_{min}(\mathscr{M}^{\dagger})=-\lambda_{max}(-\mathscr{M}^{\dagger})<0$
are the maximal and minimal eigenvalues of the inverse matrix
$\mathscr{M}^{\dagger}$, respectively.

In what follows, we denote by $\mathbb{R}^{n\times m}$ the vector space
consisting of all $n\times m$ real matrices. Suppose that
$A\in\mathbb{R}^{n\times n}$, $B\in\mathbb{R}^{m\times m}$ are symmetric
matrices, and $K\in\mathbb{R}^{n\times m}$. Consider the following
$\left(n+m\right)\times\left(n+m\right)$ real symmetric block matrix:

(5) $\mathscr{M}=\left(\begin{array}[]{cc}A&K\\\ K^{T}&B\end{array}\right).$

The Moore-Penrose inverse $\mathscr{M}^{\dagger}$ of a block symmetric matrix
$\mathscr{M}$ always exists and it has the block symmetric form:

(6) $\mathscr{M}^{\dagger}=\left(\begin{array}[]{cc}E&H\\\
H^{T}&F\end{array}\right).$

One can easily set up a system of matrix equations for the elements $E,F,H$ by
following the basic axioms for the Moore-Penrose inverse. On the other hand,
this system of nonlinear matrix equations need not have an explicit solution.
Assuming further conditions on $A,B$, and $K$ there exists the so-called
Banasiewicz-Schur explicit form of the Moore-Penrose pseudo-inverse matrix
$\mathscr{M}^{\dagger}$ of $\mathscr{M}$. Although the form of
$\mathscr{M}^{\dagger}$ is known in the literature (see e.g. [28], [29]), we
give a short sketch of its derivation for reader’s convenience. This way we
recall the method of block diagonalization of $\mathscr{M}$ and
$\mathscr{M}^{\dagger}$ which is important matrix algebra tool for
reformulation of the nonlinear eigenvalue problem as nonlinear optimization
problem with semi-definite matrix inequality constraints.  Generalized Moore-
Penrose inverses of bordered matrices have been studied by F. Hall in a series
of papers (see e.g. [11]). In the context of the graph theory integral
matrices play important role. Integral generalized inverses of integral
matrices have been studied by Batigne, Hall, and Katz in [12].

We apply the Schur complement trick. We define the matrix $\mathscr{Q}$ having
its inverse matrix $\mathscr{Q}^{-1}$ as follows:

$\mathscr{Q}=\left(\begin{array}[]{cc}I&-KB^{\dagger}\\\
0&I\end{array}\right),\qquad\qquad\mathscr{Q}^{-1}=\left(\begin{array}[]{cc}I&KB^{\dagger}\\\
0&I\end{array}\right).$

Assuming the structural condition $K\left(I-B^{\dagger}B\right)=0$, a
straightforward calculation yields the identity:

$\displaystyle\mathscr{Q}\mathscr{M}\mathscr{Q}^{T}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}S_{A}&K\left(I-B^{\dagger}B\right)\\\
\left(I-BB^{\dagger}\right)K^{T}&B\end{array}\right)=\left(\begin{array}[]{cc}S_{A}&0\\\
0&B\end{array}\right),$

where $S_{A}=A-KB^{\dagger}K^{T}$ is the generalized Schur complement of the
matrix $B$ matrix in $\mathscr{M}$. Next, following the ideas of the Schur
complement trick, we propose the pseudo-inverse matrix in the so-called
Banachiewicz–Schur form:

(8)
$\mathscr{M}^{\dagger}=\mathscr{Q}^{T}\left(\begin{array}[]{cc}S_{A}^{\dagger}&0\\\
0&B^{\dagger}\end{array}\right)\mathscr{Q}=\left(\begin{array}[]{cc}S_{A}^{\dagger}&-S_{A}^{\dagger}KB^{\dagger}\\\
-B^{\dagger}K^{T}S_{A}^{\dagger}&B^{\dagger}+B^{\dagger}K^{T}S_{A}^{\dagger}KB^{\dagger}\end{array}\right).$

Again, using the assumption $K\left(I-B^{\dagger}B\right)=0$ we obtain

$\displaystyle\mathscr{M}\mathscr{M}^{\dagger}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}S_{A}S_{A}^{\dagger}&(I-S_{A}S_{A}^{\dagger})KB^{\dagger}\\\
0&BB^{\dagger}\end{array}\right).$

Hence, $\mathscr{M}\mathscr{M}^{\dagger}=\mathscr{M}^{\dagger}\mathscr{M}$
provided that the condition $(I-S_{A}S_{A}^{\dagger})K=0$ is satisfied.
Finally, one can easily verify the remaining Moore-Penrose axioms, i. e.,
$\mathscr{M}\mathscr{M}^{\dagger}\mathscr{M}=\mathscr{M}$,
$\mathscr{M}^{\dagger}\mathscr{M}\mathscr{M}^{\dagger}=\mathscr{M}^{\dagger}$.

######  Definition 1.

Let $A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^{m\times m}$ be symmetric
matrices. We say that a matrix $K\in\mathbb{R}^{n\times m}$ is $(A,B)$
compatible, if $K\left(I-B^{\dagger}B\right)=0$ and
$(I-S_{A}S_{A}^{\dagger})K=0$ where $S_{A}=A-KB^{\dagger}K^{T}$.

Analogously, exchanging the role of $A$ and $B$ matrices we conclude that the
Moore-Penrose pseudo-inverse matrix in the form:

(12) $\displaystyle\mathscr{M}^{\dagger}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}A^{\dagger}+A^{\dagger}KS_{B}^{\dagger}K^{T}A^{\dagger}&-A^{\dagger}KS_{B}^{\dagger}\\\
-S_{B}^{\dagger}K^{T}A^{\dagger}&S_{B}^{\dagger}\end{array}\right),$

provided that $\left(I-AA^{\dagger}\right)K=0$, and
$K(I-S_{B}^{\dagger}S_{B})=0$. Since the Moore-Penrose pseudo-inverse matrix
$\mathscr{M}^{\dagger}$ is unique, we obtain the following proposition.

######  Proposition 1.

Let $A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^{m\times m}$ be symmetric
matrices, $K\in\mathbb{R}^{n\times m}$. Assume that
$K\left(I-B^{\dagger}B\right)=0$, $(I-S_{A}S_{A}^{\dagger})K=0$, and
$\left(I-AA^{\dagger}\right)K=0$, $K(I-S_{B}^{\dagger}S_{B})=0$, i. e., $K$ is
$(A,B)$ compatible and $K^{T}$ is $(B,A)$ compatible. Then for the generalized
Schur complements $S_{A}=A-KB^{\dagger}K^{T}$, and $S_{B}=B-K^{T}A^{\dagger}K$
the following identities hold:

  1. (1)

$S_{A}^{\dagger}KB^{\dagger}=A^{\dagger}KS_{B}^{\dagger}$,

  2. (2)

$S_{A}^{\dagger}=A^{\dagger}+A^{\dagger}KS_{B}^{\dagger}K^{T}A^{\dagger}$,

  3. (3)

$S_{B}^{\dagger}=B^{\dagger}+B^{\dagger}K^{T}S_{A}^{\dagger}KB^{\dagger}$.

######  Remark 1.

The structural conditions $K\left(I-B^{\dagger}B\right)=0$,
$(I-S_{A}S_{A}^{\dagger})K=0$ are independent of each other. Indeed, let us
consider the following simple example:

$A=A^{\dagger}=\left(\begin{array}[]{cc}1&0\\\ 0&0\end{array}\right),\quad
B=B^{\dagger}=\left(\begin{array}[]{cc}0&0\\\ 0&1\end{array}\right),\quad
K=\left(\begin{array}[]{cc}0&1\\\ 0&0\end{array}\right).$

Then, $K(I-B^{\dagger}B)=0$, but $S_{A}=0$, and so $S_{A}^{\dagger}=0$,
$(I-S_{A}S_{A}^{\dagger})K=K\not=0$. Similarly,
$\left(I-AA^{\dagger}\right)K=0$ but $S_{B}=0$, and so
$K(I-S_{B}^{\dagger}S_{B})=K\not=0$.

######  Proposition 2.

Let $\mathscr{M}$ be a block symmetric matrix of the form (5). If the matrix
$\mathscr{M}$ is invertible and $K\left(I-B^{\dagger}B\right)=0$, then the
generalized Schur complement matrix $S_{A}=A-KB^{\dagger}K^{T}$ is invertible.

###### Proof.

Suppose that $S_{A}x=0$, i. e., $Ax-KB^{\dagger}K^{T}x=0$. Take
$y=-B^{\dagger}K^{T}x$. Then $Ax+Ky=0$, and
$K^{T}x+By=\left(I-BB^{\dagger}\right)K^{T}x=0$. Hence
$\mathscr{M}(x,y)^{T}=0$. Since $\mathscr{M}$ is invertible, we conclude that
$x=y=0$, and $S_{A}$ is invertible as well. ∎

######  Remark 2.

The converse statement is not true, in general. Indeed, let us consider
$A=I,B=0$, and $K=0$. Then $\mathscr{M}$ is singular although $S_{A}=A=I$ is
invertible. On the other hand, if both $A$ and $B$ are invertible matrices,
then $\mathscr{M}$ is invertible if and only the Schur complement matrix
$S_{A}=A-KB^{-1}K^{T}$ is invertible (cf. [19]).

In the following definition we introduce a novel concept of positive and
negative pseudo-invertibility of a symmetric real matrix.

######  Definition 2.

Let $A$ be a symmetric real matrix. It is called positively pseudo-invertible
if the Moore-Penrose pseudo-inverse matrix $A^{\dagger}$ is signable to a
nonnegative matrix. That is there exists a diagonal $\pm 1$ signature matrix
$D$ such that the matrix $DA^{\dagger}D$ contains nonnegative elements only.
It is called negatively pseudo-invertible if there exists a diagonal $\pm 1$
signature matrix $D$ such that the matrix $DA^{\dagger}D$ contains nonpositive
elements only.

Positive and negative (pseudo)invertibility of a symmetric real matrix
generalizes the concept of a monotone matrix. Recall that a matrix $A$ is
monotone in the sense of Collatz if and only if the component-wise inequality
$Ax\geq 0$ implies $x\geq 0$. Every monotone matrix $A$ is invertible, and the
inverse matrix $A^{-1}\geq 0$ contains nonnegative elements. As a consequence,
for a monotone matrix $A$ the inequality $-b\leq Ax\leq b$ implies
$-A^{-1}b\leq x\leq A^{-1}b$. As a consequence,
$\|x\|_{\infty}\leq\|A^{-1}b\|_{\infty}\leq\|A^{-1}\|_{1}\|b\|_{\infty}$ where
$\|B\|_{1}=\sum_{i,j}|B_{ij}|$, and $\|b\|_{\infty}=\max_{i}|b_{i}|$. In the
following proposition we show that a similar property holds for positively or
negatively pseudo-invertible matrices which need not be monotone in general.

######  Proposition 3.

Suppose that $n\times n$ real symmetric matrix $A$ is positive (negative)
pseudo-invertible. If $-b\leq Ax\leq b$ for a nonnegative vector $b\geq
0$,then

$\|A^{\dagger}Ax\|_{\infty}\leq\|A^{\dagger}\|_{1}\|b\|_{\infty}.$

In particular, if the matrix $A$ is invertible, then
$\|x\|_{\infty}\leq\|A^{-1}\|_{1}\|b\|_{\infty}$.

###### Proof.

Notice that vector component-wise inequality $-b\leq y\leq b$ implies
$-\color[rgb]{0,0,0}b\color[rgb]{0,0,0}\leq
Dy\leq\color[rgb]{0,0,0}b\color[rgb]{0,0,0}$ for any diagonal signature matrix
$D$ containing $\pm 1$ elements. Without loss of generality suppose that $A$
is positively pseudo-invertible, i. e., there exists a signature matrix $D$
such that $DA^{\dagger}D\geq 0$. Notice that for a diagonal matrix $D$
containing $\pm 1$ elements only, we have $DD=I$. It means that $D^{-1}=D$.
The inequality $-b\leq Ax\leq b$ implies
$-\color[rgb]{0,0,0}b\color[rgb]{0,0,0}\leq
DAx\leq\color[rgb]{0,0,0}b\color[rgb]{0,0,0}$, and so $-DA^{\dagger}Db\leq
DA^{\dagger}DDAx\leq DA^{\dagger}Db$. As $D^{2}=I$, we obtain
$-DA^{\dagger}\color[rgb]{0,0,0}D\color[rgb]{0,0,0}b\leq DA^{\dagger}Ax\leq
DA^{\dagger}\color[rgb]{0,0,0}D\color[rgb]{0,0,0}b$. Finally, the inequality
$-DA^{\dagger}\color[rgb]{0,0,0}D\color[rgb]{0,0,0}b\leq A^{\dagger}Ax\leq
DA^{\dagger}\color[rgb]{0,0,0}D\color[rgb]{0,0,0}b$ implies
$\|A^{\dagger}Ax\|_{\infty}\leq\|DA^{\dagger}\|_{1}\|Db\|_{\infty}=\|A^{\dagger}\|_{1}\|b\|_{\infty}$,
as claimed. In the case $A$ is negatively pseudo-invertible the proof of the
estimate is similar. If $A$ is invertible, then $A^{\dagger}A=A^{-1}A=I$ and
the proof of proposition follows. ∎

######  Proposition 4.

Suppose that an $N\times N$ real symmetric matrix $A$ is positive and negative
pseudo-invertible. Then

  * i)

$D_{+}A^{\dagger}D_{+}=-D_{-}A^{\dagger}D_{-}$ where $D_{\pm}$ are signature
matrices signing $A^{\dagger}$ to nonnegative and nonpositive matrices,
respectively.

  * ii)

The spectrum $\sigma(A)$ is symmetric, i.e. $\lambda\in\sigma(A)$ iff
$-\lambda\in\sigma(A)$.

###### Proof.

Let $D_{\pm}$ be diagonal signature matrices such that $D_{+}A^{\dagger}D_{+}$
contains nonnegative elements and $D_{-}A^{\dagger}D_{-}$ contains nonpositive
elements only. Since
$(D_{\pm}A^{\dagger}D_{\pm})_{ij}=(D_{\pm})_{ii}(A^{\dagger})_{ij}(D_{\pm})_{jj}$,
we conclude that $(D_{\pm}A^{\dagger}D_{\pm})_{ij}\not=0$ if and only if
$(A^{\dagger})_{ij}\not=0$. As a consequence, we obtain
$(D_{+}A^{\dagger}D_{+})_{ij}=-(D_{-}A^{\dagger}D_{-})_{ij}$ for each $i,j$,
and the proof of the part i) follows.

Suppose that $\lambda\in\sigma(A),\lambda\not=0$. Then
$\mu=1/\lambda\in\sigma(A^{\dagger})$, and there exists an eigenvector
$x\not=0$ such that $A^{\dagger}x=\mu x$. As $D_{+}D_{+}=D_{-}D_{-}=I$, we
obtain
$A^{\dagger}=D_{+}D_{+}A^{\dagger}D_{+}D_{+}=-D_{+}D_{-}A^{\dagger}D_{-}D_{+}=-DA^{\dagger}D$
where $D=D_{+}D_{-}=D_{-}D_{+}$ is a signature matrix (see the part i)). Then
for the nontrivial vector $\tilde{x}=Dx=D_{+}D_{-}x$ we obtain,
$x=D\tilde{x}$, and

$A^{\dagger}\tilde{x}=-DA^{\dagger}D\tilde{x}=-DA^{\dagger}x=-\mu
Dx=-\mu\tilde{x}.$

Hence $-\mu\in\sigma(A^{\dagger})$. As a consequence, we obtain
$-\lambda\in\sigma(A)$, as claimed in the part ii). ∎

######  Remark 3.

The converse statement to the part ii) is not true, in general. Indeed, let us
consider the following $5\times 5$ block matrix

$\mathscr{M}=\left(\begin{array}[]{cc}0&K\\\
K^{T}&0\end{array}\right)\quad\text{where}\quad
K=\left(\begin{array}[]{ccc}1&1&0\\\ 0&1&1\end{array}\right).$

The spectrum $\sigma(\mathscr{M})=\\{\pm\sqrt{3},\pm 1,0\\}$ is symmetric. The
matrix $\mathscr{M}$ represents an adjacency matrix of the bipartite path
graph $\mathbb{P}_{5}$ shown in Fig. 2 (left). It is a simple connected graph
with smallest number of vertices with an adjacency matrix which is neither
positively, nor negatively pseudo-invertible.

We say that an $N\times N$ matrix $\mathscr{M}$ is permutationally similar to
an off-diagonal block matrix iff there exists a permutation matrix $P$ and an
$n\times m$ real matrix $K$, $n+m=N$, such that

(13) $P^{T}\mathscr{M}P=\left(\begin{array}[]{cc}0&K\\\
K^{T}&0\end{array}\right).$

######  Theorem 1.

Let $\mathscr{M}\in\mathbb{R}^{N\times N}$ be a real symmetric matrix.

  * i)

If $\mathscr{M}$ is a positive (negative) pseudo-invertible matrix which is
permutationaly similar to a block off-diagonal matrix (13), then $\mathscr{M}$
is also negative (positive) pseudo-invertible matrix.

  * ii)

If $\mathscr{M}$ is a positive and negative pseudo-invertible matrix, then
$\mathscr{M}$ is permutationaly similar to a block off-diagonal matrix of the
form (13).

  * iii)

An off-diagonal matrix $\mathscr{M}$ of the form (13) is positively and
negatively pseudo-invertible if and only if there are $n\times n$ and $m\times
m$ signature diagonal matrices $D_{A}$ and $D_{B}$ such that the matrix
$D_{B}K^{\dagger}D_{A}$ contains elements of the same sign.

###### Proof.

First, we note that for the Moore-Penrose inverse $\mathscr{M}^{\dagger}$ of
the following block symmetric matrix $\mathscr{M}$ we have the implication:

(14) $\mathscr{M}=\left(\begin{array}[]{cc}0&K\\\
K^{T}&0\end{array}\right)\quad\Longrightarrow\quad\mathscr{M}^{\dagger}=\left(\begin{array}[]{cc}0&(K^{\dagger})^{T}\\\
K^{\dagger}&0\end{array}\right),$

where $K^{\dagger}$ is the uniquely determined Moore-Penrose inverse of the
$n\times m$ matrix $K$.

In order to prove the part i), let us assume there is an $N\times N$
permutation matrix $P$ such that $P^{T}\mathscr{M}P$ has the block form of
(13). Without loss of generality, we may assume $P=I$ is the identical
permutation of indices. Assume $\mathscr{M}$ is positively pseudo-invertible.
We shall prove that $\mathscr{M}$ is also negatively pseudo-invertible, and
vice versa. Assuming that $\mathscr{M}$ is positively pseudo-invertible, then
there exists a signature matrix $D_{+}=diag(D_{A},D_{B})$ such that the matrix

(21) $\displaystyle D_{+}\mathscr{M}^{\dagger}D_{+}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}D_{A}&0\\\ 0&D_{B}\\\
\end{array}\right)\left(\begin{array}[]{cc}0&(K^{\dagger})^{T}\\\
K^{\dagger}&0\\\ \end{array}\right)\left(\begin{array}[]{cc}D_{A}&0\\\
0&D_{B}\\\ \end{array}\right)$ (24) $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}0&D_{A}(K^{\dagger})^{T}D_{B}\\\
D_{B}K^{\dagger}D_{A}&0\\\ \end{array}\right)$

contains nonnegative elements only. Here $D_{A}$ and $D_{B}$ are $n\times n$
and $m\times m$ signature diagonal matrices containing $\pm 1$ elements only.
Taking the signature diagonal matrix $D_{-}=diag(D_{A},-D_{B})$ the matrix

(25)
$D_{-}\mathscr{M}^{\dagger}D_{-}=\left(\begin{array}[]{cc}0&-D_{A}(K^{\dagger})^{T}D_{B}\\\
-D_{B}K^{\dagger}D_{A}&0\\\ \end{array}\right)$

contains nonpositive elements only. Hence the matrix $\mathscr{M}$ is also
negatively pseudo-invertible, and vice versa.

In order to prove the part ii), suppose that $\mathscr{M}$ is positively and
negatively pseudo-invertible matrix. With regard to Proposition 4 we obtain

(26) $D_{+}\mathscr{M}^{\dagger}D_{+}=-D_{-}\mathscr{M}^{\dagger}D_{-},$

where $D_{\pm}$ are diagonal signature matrices. Then there exists an $N\times
N$ permutation matrix $P$ such that

$P^{T}D_{+}D_{-}P=\left(\begin{array}[]{cc}I_{n}&0\\\ 0&-I_{m}\\\
\end{array}\right),\ \ i.\,e.,\quad
D_{+}D_{-}=D_{-}D_{+}=P\left(\begin{array}[]{cc}I_{n}&0\\\ 0&-I_{m}\\\
\end{array}\right)P^{T},$

where $I_{n}$, $I_{m}$ are the $n\times n$ and $m\times m$ identity matrices,
$n+m=N$. Here $n$ ($m$) is the number of positive (negative) units in the
matrix $D_{+}D_{-}$, respectively. It follows from (26) that

$\mathscr{M}^{\dagger}=-D_{+}D_{-}\mathscr{M}^{\dagger}D_{-}D_{+}=-P\left(\begin{array}[]{cc}I_{n}&0\\\
0&-I_{m}\\\
\end{array}\right)P^{T}\mathscr{M}^{\dagger}P\left(\begin{array}[]{cc}I_{n}&0\\\
0&-I_{m}\\\ \end{array}\right)P^{T}.$

Since $P^{T}P=PP^{T}=I$, we have

$P^{T}\mathscr{M}^{\dagger}P=-\left(\begin{array}[]{cc}I_{n}&0\\\ 0&-I_{m}\\\
\end{array}\right)P^{T}\mathscr{M}^{\dagger}P\left(\begin{array}[]{cc}I_{n}&0\\\
0&-I_{m}\\\ \end{array}\right)$

Writing $P^{T}\mathscr{M}^{\dagger}P$ in the form of a block matrix we obtain

$\displaystyle
P^{T}\mathscr{M}^{\dagger}P\equiv\left(\begin{array}[]{cc}V&H\\\ H^{T}&W\\\
\end{array}\right)$ $\displaystyle=$
$\displaystyle-\left(\begin{array}[]{cc}I_{n}&0\\\ 0&-I_{m}\\\
\end{array}\right)\left(\begin{array}[]{cc}V&H\\\ H^{T}&W\\\
\end{array}\right)\left(\begin{array}[]{cc}I_{n}&0\\\ 0&-I_{m}\\\
\end{array}\right)$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}-V&H\\\ H^{T}&-W\\\
\end{array}\right).$

It means that $V=W=0$. Hence

$P^{T}\mathscr{M}^{\dagger}P=\left(\begin{array}[]{cc}0&H\\\ H^{T}&0\\\
\end{array}\right)\ \Longrightarrow\
P^{T}\mathscr{M}P=\left(\begin{array}[]{cc}0&K\\\ K^{T}&0\\\
\end{array}\right).$

where $K=(H^{T})^{\dagger}$. It means that the matrix $\mathscr{M}$ is
permutationally similar to the block matrix (13), as claimed.

Finally, consider the diagonal $N\times N$ signature matrix
$D=diag(D_{B},D_{A})$. Then

$D\mathscr{M}^{\dagger}D=\left(\begin{array}[]{cc}0&D_{A}(K^{\dagger})^{T}D_{B}\\\
D_{B}K^{\dagger}D_{A}&0\end{array}\right)$

contains elements of the same sign iff $D_{B}K^{\dagger}D_{A}$ contains
elements of the same sign, and the proof of the part iii) follows. ∎

In the following theorem we present sufficient conditions for a general block
symmetric matrix to be positively or negatively pseudo-invertible.

######  Theorem 2.

Let $A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^{m\times m}$ be real
symmetric matrices, $K\in\mathbb{R}^{n\times m}$. Let
$S_{A}=A-KB^{\dagger}K^{T}$ be the Schur complement of $B$ in the block matrix
$\mathscr{M}$ in (5). Assume that $S_{A}$ and $B$ are both positively
(negatively) pseudo-invertible signable to a nonnegative (nonpositive)
matrices by the signature matrices $D_{A}$ and $D_{B}$, respectively. Assume
that the real matrix $K\in\mathbb{R}^{n\times m}$ is $(A,B)$ compatible and
such that $D_{A}KD_{B}$ contains elements of the same signs. Then the block
matrix $\mathscr{M}$ of the form (5) is positively (negatively) pseudo-
invertible.

###### Proof.

First, we assume both $S_{A}$ and $B$ are positively pseudo-invertible and the
matrix $D_{A}KD_{B}$ is nonnegative. We consider the signature matrix
$D=diag(D_{A},-D_{B})$. If $D_{A}KD_{B}$ is nonpositive, then we take
$D=diag(D_{A},D_{B})$. In what follows, we shall prove that
$\mathscr{M}^{\dagger}$ is signable to a nonnegative real matrix by the
signature matrix $D$. We have

$D\mathscr{M}^{\dagger}D=\left(\begin{array}[]{cc}D_{A}S_{A}^{\dagger}D_{A}&D_{A}S_{A}^{\dagger}KB^{\dagger}D_{B}\\\
D_{B}B^{\dagger}K^{T}S_{A}^{\dagger}D_{A}&D_{B}B^{\dagger}D_{B}+D_{B}B^{\dagger}K^{T}S_{A}^{\dagger}KB^{\dagger}D_{B}\end{array}\right).$

Since $D_{A}D_{A}=I_{n},D_{B}D_{B}=I_{m}$, we have

$\displaystyle D_{A}S_{A}^{\dagger}KB^{\dagger}D_{B}$ $\displaystyle=$
$\displaystyle(D_{A}S_{A}^{\dagger}D_{A})(D_{A}KD_{B})(D_{B}B^{\dagger}D_{B})\geq
0,$ $\displaystyle D_{B}B^{\dagger}K^{T}S_{A}^{\dagger}KB^{\dagger}D_{B}$
$\displaystyle=$
$\displaystyle(D_{B}B^{\dagger}D_{B})(D_{B}K^{T}D_{A})(D_{A}S_{A}^{\dagger}D_{A})(D_{A}KD_{B})(D_{B}B^{\dagger}D_{B})\geq
0,$

are matrices with nonnegative elements only. Hence the matrix $\mathscr{M}$ is
positively pseudo-invertible, as claimed. In the case $S_{A}$ and $B$ are both
negatively pseudo-invertible the proof of negatively pseudo-invertibility of
$\mathscr{M}$ is analogous. ∎

In the rest of this section we apply the previous results for characterization
of the least positive and largest negative eigenvalues of a block matrix (13).
As usual, we let denote by $\preceq$ the Löwner partial ordering on symmetric
matrices, i. e., $A\preceq B$ iff the matrix $B-A$ is a positive semidefinite
matrix, that is $B-A\succeq 0$. Following [5], [8], and using the Löwner
ordering, the maximal positive and minimal negative eigenvalues of
$\mathscr{M}^{\dagger}$ can be expressed as follows:

$0<\lambda_{max}(\mathscr{M}^{\dagger})=\min_{\mathscr{M}^{\dagger}\preceq
tI}t,\qquad
0>\lambda_{min}(\mathscr{M}^{\dagger})=\max_{sI\preceq\mathscr{M}^{\dagger}}s.$

Suppose that $\mathscr{M}$ is a symmetric real matrix such that
$\lambda_{min}(\mathscr{M})<0<\lambda_{max}(\mathscr{M})$. With regard to (4)
we have
$\lambda_{+}(\mathscr{M})=\lambda_{max}(\mathscr{M}^{\dagger})^{-1},\lambda_{-}(\mathscr{M})=\lambda_{min}(\mathscr{M}^{\dagger})^{-1}$.
Introducing the new variables $\mu=1/t,\eta=-1/s$, we deduce that the least
positive and largest negative eigenvalues of the matrix $\mathscr{M}$ can be
expressed as follows:

(29) $\lambda_{+}(\mathscr{M})=\max_{\mu\mathscr{M}^{\dagger}\preceq
I}\mu,\qquad\lambda_{-}(\mathscr{M})=-\max_{-\eta\mathscr{M}^{\dagger}\preceq
I}\eta.$

Let us denote by
$\Lambda^{HL}_{sg}(\mathscr{M})=\lambda_{+}(\mathscr{M})-\lambda_{-}(\mathscr{M})$
and
$\Lambda^{HL}_{ind}(\mathscr{M})=\max(|\lambda_{+}(\mathscr{M})|,|\lambda_{-}(\mathscr{M}|)$
the HOMO-LUMO spectral gap $\Lambda^{HL}_{sg}$ and the index
$\Lambda^{HL}_{ind}$ of a symmetric matrix $\mathscr{M}$ representing the
difference between the least positive and largest negative eigenvalue of the
matrix $\mathscr{M}$. In the context of the spectral graph theory the
eigenvalues of the adjacency matrix representing an organic molecule play an
important role. The spectral gap $\Lambda^{HL}_{sg}(\mathscr{M})$ is also
referred to as the HOMO-LUMO energy separation gap of the energy of the
highest occupied molecular orbital (HOMO) and the lowest unoccupied molecular
orbital orbital (LUMO). The bigger the spectral gap is the molecule is more
stable. Generalizing the results by Pavlíková and Ševčovič [21, 20], the HOMO-
LUMO spectral gap and index of the matrix $\mathscr{M}$ can be expressed in
terms of the following nonlinear programming problem:

(30) $\displaystyle\Lambda^{HL}_{sg}(\mathscr{M})$ $\displaystyle=$
$\displaystyle\max_{\mu,\eta\geq 0}\quad\mu+\eta$
$\displaystyle\Lambda^{HL}_{ind}(\mathscr{M})$ $\displaystyle=$
$\displaystyle\max_{\mu,\eta\geq 0}\quad\max(\mu,\eta)$
$\displaystyle\text{s.t.}\quad\mu\mathscr{M}^{\dagger}\preceq I,\ \
-\eta\mathscr{M}^{\dagger}\preceq I.$

Assume $\mathscr{M}$ has a block symmetric matrix of the form (5). Then, for
any $\mu\geq 0$, we have $\mu\mathscr{M}^{\dagger}\preceq I$ if and only if

$\mu\left(\begin{array}[]{cc}S_{A}^{\dagger}&0\\\
0&B^{\dagger}\end{array}\right)=\mu(\mathscr{Q}^{-1})^{T}\mathscr{M}^{\dagger}\mathscr{Q}^{-1}\preceq(\mathscr{Q}^{-1})^{T}\mathscr{Q}^{-1}\quad\hbox{where}\
\ \mathscr{Q}^{-1}=\left(\begin{array}[]{cc}I&KB^{\dagger}\\\
0&I\end{array}\right).$

Therefore,

(32) $\mu\mathscr{M}^{\dagger}\preceq
I\quad\Leftrightarrow\quad\left(\begin{array}[]{cc}I-\mu
S_{A}^{\dagger}&KB^{\dagger}\\\ B^{\dagger}K^{T}&I-\mu
B^{\dagger}+B^{\dagger}K^{T}KB^{\dagger}\end{array}\right)\succeq 0.$

Similarly, for $\eta\geq 0$, we have

(33) $-\eta\mathscr{M}^{\dagger}\preceq
I\quad\Leftrightarrow\quad\left(\begin{array}[]{cc}I+\eta
S_{A}^{\dagger}&KB^{\dagger}\\\ B^{\dagger}K^{T}&I+\eta
B^{\dagger}+B^{\dagger}K^{T}KB^{\dagger}\end{array}\right)\succeq 0.$

The semi-definite constraints appearing in the right-hand sides of (32), and
(33) can be viewed as linear matrix inequalities. Such inequalities can be
utilized in order to optimize the least positive and largest negative
eigenvalues $\lambda_{+}(\mathscr{M})$, and $\lambda_{-}(\mathscr{M})$ of a
block matrix $\mathscr{M}$ with respect to matrix elements $A,B$, and $K$,
respectively (cf. [20], [21]).

##  3\. Applications of block matrix pseudo-inversion in the graph theory

Inverse graphs are of interest in estimating the least positive eigenvalue in
families of graphs, a task for which there appears to be lack of suitable
bounds. However, if the graphs are invertible, then one can apply one of the
(many) known upper bounds on largest eigenvalues of the inverse graphs instead
(cf. [17, 18]). Properties of the spectra of inverse graphs can also be used
to estimate the difference between the minimal positive and maximal negative
eigenvalue (the so-called HOMO-LUMO gap) for structural models of chemical
molecules, as it was done e.g. for graphene structures in [26].

Let $G$ be an undirected simple graph, possibly with multiple edges, and with
a symmetric binary adjacency matrix $A$. Conversely, if $A$ is a binary
symmetric matrix, then we will use the symbol $G_{A}$ to denote the graph with
the adjacency matrix $A$. The spectrum $\sigma(G)$ of $G$ consists of
eigenvalues (i. e., including multiplicities) of $A_{G}$ (cf. [7, 6]). If the
spectrum does not contain zero, then the adjacency matrix $A$ is invertible.
We begin with a definition of an integrally invertible graph.

######  Definition 3.

A graph $G=G_{A}$ is said to be integrally invertible if the inverse $A^{-1}$
of its adjacency matrix exists and is integral.

It is well known (cf. [14]) that a graph $G_{A}$ is integrally invertible if
and only if $det(A)=\pm 1$. Next, we recall the classical concept graph
positive invertibility introduced by Godsil in [9] which was extended by
Pavlíková and Ševčovič to negatively invertible graphs [19]. Note that, in
such a case the inverse matrix $A^{-1}$ need not represent a graph as it may
contain negative entries. To overcome this difficulty in defining the inverse
graph we restrict our attention to those graphs whose adjacency matrix is
positively or negatively (pseudo)invertible. Next, we extend the concept of
positive/negative invertibility to graphs whose adjacency matrices are not
invertible.

######  Definition 4.

A graph $G_{A}$ is called positively (negatively) integrally invertible if
$det(A)=\pm 1$, and $A^{-1}$ is signable to a nonnegative (nonpositive)
integral matrix. If $D$ is the corresponding signature matrix, then the
positive (negative) inverse graph $H=G_{A}^{-1}$ is defined by the adjacency
matrix $A_{H}=DA^{-1}D$ ($A_{H}=-DA^{-1}D$).

The concept of positive integral invertibility coincides with the original
notion of integral invertibility introduced by Godsil [9]. Definition 4
extends Godsil’s concept to a larger class of integrally invertible graphs
with inverses of adjacency matrices signable to nonpositive matrices.

######  Definition 5.

A graph $G_{A}$ is called positively (negatively) pseudo-invertible if the
Moore-Penrose pseudo-inverse matrix $A^{\dagger}$ is signable to a nonnegative
(nonpositive) matrix. If $D$ is the corresponding signature matrix, then the
positively (negatively) pseudo-inverse graph $H=G_{A}^{\dagger}$ is defined by
the weighted nonnegative adjacency matrix $A_{H}=DA^{\dagger}D$
($A_{H}=-DA^{\dagger}D$).

Note that the positively (negatively) pseudo-inverse graph $H^{\dagger}$ is
defined by the nonnegative weighted adjacency matrix $DA^{\dagger}D$
($-DA^{\dagger}D$). The matrix $(DA^{\dagger}D)^{\dagger}$ is signable by the
same signature matrix, and
$D(DA^{\dagger}D)^{\dagger}D=DD(A^{\dagger})^{\dagger}DD=A$. One can proceed
similarly if $G$ is a negatively pseudo-invertible graph. As a consequence, we
obtain

$(G^{\dagger})^{\dagger}=G.$

Furthermore, it is easy to verify by a simple contradiction argument that the
weighted pseudo-inverse graph $G^{\dagger}_{A}$ is connected provided that the
original graph $G_{A}$ is connected.

In Table 1 we show the number of all connected graphs with $m\leq 10$
vertices, number of invertible, and number of integrally/positively/negatively
invertible graphs. We employed McKay’s list of connected graphs available from
http://users.cecs.anu.edu.au/~bdm/data/graphs.html. The complete list of
positively, negatively pseudo-invertible and pseudo-invertible graphs on
$m\leq 10$ including their spectrum and signature matrices can be found at:
http://www.iam.fmph.uniba.sk/institute/sevcovic/inversegraphs/ (see [23]).

Table 1. Number of invertible ($det(A)\not=0$) and integrally invertible
($det(A)=\pm 1$) simple connected graphs $G_{A}$ with $m\leq 10$ vertices. The
number of positively but not negatively invertible graphs ($+$signable). The
number of negatively but not positively pseudo-invertible graphs
($-$signable). The number of positively and negatively invertible and pseudo-
invertible graphs ($\pm$signable).

| $m=2$ | $m=3$ | $m=4$ | $m=5$ | $m=6$ | $m=7$ | $m=8$ | $m=9$ | $m=10$
---|---|---|---|---|---|---|---|---|---
all conn. graphs | 1 | 2 | 6 | 21 | 112 | 853 | 11117 | 261080 | 11716571
Invertible graphs
$det(A)\not=0$ | 1 | 1 | 3 | 8 | 52 | 342 | 5724 | 141063 | 7860195
Integrally invertible graphs
int. invertible | 1 | - | 2 | - | 29 | - | 2381 | - | 1940904
$+$signable | 0 | - | 1 | - | 20 | - | 1601 | - | 1073991
$-$signable | 0 | - | 0 | - | 4 | - | 235 | - | 105363
$\pm$signable | 1 | - | 1 | - | 4 | - | 25 | - | 349
Signable pseudo-invertible graphs
$+$signable | 0 | 0 | 1 | 3 | 27 | 111 | 2001 | 15310 | 1247128
$-$signable | 0 | 0 | 0 | 1 | 7 | 60 | 638 | 11643 | 376137
$\pm$signable | 1 | 1 | 3 | 4 | 13 | 25 | 93 | 270 | 1243

Source: own computations [23],
http://www.iam.fmph.uniba.sk/institute/sevcovic/inversegraphs/

######  Theorem 3.

Let $G_{\mathscr{M}}$ be a simple connected graph.

  * i)

If $G_{\mathscr{M}}$ is a bipartite graph which is positively (negatively)
pseudo-invertible, then it is also negatively (positively) pseudo-invertible.

  * ii)

If $G_{\mathscr{M}}$ is a positively and negatively pseudo-invertible graph,
then it is a bipartite graph.

###### Proof.

The part i) is a consequence of Theorem 1, i). Indeed, the adjacency matrix
$\mathscr{M}$ of a bipartite graph $G_{\mathscr{M}}$ is permutationaly similar
to a block off-diagonal matrix (13). With regard to Theorem 1, i), if
$\mathscr{M}$ is positive (negative) pseudo-invertible, then it also negative
(positive) pseudo-invertible matrix, as claimed in the part i).

If the adjacency matrix $\mathscr{M}$ is positive and negative pseudo-
invertible, then $\mathscr{M}$ is permutationaly similar to a block off-
diagonal matrix of the form (13) (see Theorem 1, ii)), and the proof of the
theorem follows. ∎

######  Remark 4.

In general, bipartitness of a graph does not imply its positive and negative
(pseudo)invertibility. A smallest example is the path $\mathbb{P}_{5}$ (shown
in Fig. 2 (left)) which is a bipartite graph with the adjacency matrix of the
form (13). It is neither positively nor negatively pseudo-invertible, and its
spectrum is symmetric $\sigma(\mathbb{P}_{5})=\\{0,\pm 1,\pm\sqrt{3}\\}$ (see
also Remark 3). In Fig. 2 (middle) we show a bipartite graph $G_{A}$ on 6
vertices with symmetric spectrum $\sigma(A)=\\{0,0,\pm 1.1756,\pm 1.9021\\}$.
Again it is neither positively nor negatively pseudo-invertible. In Fig. 2
(right) we show a bipartite graph $G_{A}$ on 8 vertices which is integrally
invertible with a symmetric spectrum $\sigma(A)=\\{\pm 2.5231,\pm 1.4413,\pm
0.5669,\pm 0.4851\\}$. This is a smallest example of an integrally invertible
bipartite graph which is neither positively nor negatively invertible.

Figure 2. Examples of bipartite graphs which are neither positively nor
negatively (pseudo)invertible.

######  Example 1.

Let us denote $\mathbb{S}_{n+1}$ the bipartite star graph on $n+1$ vertices
(see example in Fig. 6 (right) for $n+1=6$). Its adjacency matrix
$\mathscr{M}$ has the block form (13) with
$K=(1,\ldots,1)^{T}\in\mathbb{R}^{n}$. It is easy to verify that
$K^{\dagger}=\frac{1}{n}K^{T}$. According to Theorem 1, iii),
$\mathbb{S}_{n+1}$ is positively and negatively pseudo-invertible. The
adjacency matrix $\mathbb{S}_{n+1}^{\dagger}$ is equal to
$\frac{1}{n}\mathscr{M}$, and its spectrum
$\sigma(\mathbb{S}_{n+1})=\\{0,\ldots,0,\pm\sqrt{n}\\}$.

######  Remark 5.

According to the Theorem 8.8.2 due to Godsil and Royle [10] (see also Brouwer
and Hamers [4, Proposition 3.4.1]) a graph is bipartite if and only if its
spectrum is symmetric. In Remark 4 we showed the the bipartitness (or symmetry
of the spectrum) does not imply positively or negatively
(pseudo)invertibility.

If $A$ is an $m\times n$ matrix and $B$ is a $p\times q$ matrix, then the
Kronecker product $A\otimes B$ is the $pm\times qn$ block matrix with blocks
$(a_{ij}B)_{i=1,...,m,\ j=1,...,n}$.

######  Proposition 5.

Assume $B\in\mathbb{R}^{m\times m}$ is a symmetric nonsingular matrix. Let us
consider the block matrix

(34) $\mathscr{M}=\left(\begin{array}[]{cc}0&K\\\ K^{T}&B\end{array}\right),$

where $K=(I,\ldots,I)^{T}\in\mathbb{R}^{km\times m}$, $I$ is the $m\times m$
identity matrix, and $0$ is the $n\times n$ zero matrix, $n=km$ where
$k\in\mathbb{N}$. Then the spectrum consists of real eigenvalues:

$\sigma(\mathscr{M})=\\{\lambda\in\mathbb{R},\ \lambda=0,\ \text{or}\ \
\lambda=(\mu\pm\sqrt{\mu^{2}+4k})/2,\ \text{for some}\ \mu\in\sigma(B)\\}.$

Furthermore, the spectrum $\sigma(\mathscr{M})$ is symmetric if and only if
the spectrum $\sigma(B)$ is symmetric. Finally,

(35) $\mathscr{M}^{\dagger}=\frac{1}{k^{2}}\left(\begin{array}[]{cc}-{\bf
1}\otimes B&kK\\\ kK^{T}&0\end{array}\right)$

where $\otimes$ denotes the Kronecker product of matrices where ${\bf 1}$ is
the $k\times k$ matrix consisting of ones. The matrix $\mathscr{M}$ is
negatively pseudo-invertible. If there exists an $m\times m$ signature matrix
$D_{-}$ such that $D_{-}BD_{-}\leq 0$, then $\mathscr{M}$ is also positively
pseudo-invertible.

###### Proof.

It is easy to verify that $\lambda$ is a nonzero eigenvalue of $\mathscr{M}$
iff $\mu=\lambda-k/\lambda$ is an eigenvalue of $B$. Hence the spectrum
$\sigma(\mathscr{M})$ is symmetric if and only if the spectrum $\sigma(B)$ is
symmetric, and all nonzero eigenvalues of $\mathscr{M}$ are given by
$\lambda=(\mu\pm\sqrt{\mu^{2}+4k})/2$ for some $\mu\in\sigma(B)$. For the
Schur complement $S_{A}$ we have

$S_{A}=A-KB^{-1}K^{T}=-KB^{-1}K^{T}=-{\bf 1}\otimes B^{-1},$

where $\bf 1$ is the $k\times k$ matrix consisting of units. For example, if
$k=2$, then we have

$S_{A}=A-KB^{-1}K^{T}=-\left(\begin{array}[]{cc}B^{-1}&B^{-1}\\\
B^{-1}&B^{-1}\end{array}\right).$

Then it is easy to verify that

$S_{A}^{\dagger}=-\frac{1}{k^{2}}{\bf 1}\otimes B\quad\text{and}\quad
S_{A}S_{A}^{\dagger}=\frac{1}{k}{\bf 1}\otimes I.$

Therefore, $(I-S_{A}S_{A}^{\dagger})K=0_{n\times m}$ and $K(I-B^{-1}B)=0$, i.
e., $K$ is a $(0,B)$ compatible matrix. Furthermore,
$S_{A}^{\dagger}KB^{-1}=-\frac{1}{k}K$, and
$B^{-1}+B^{-1}K^{T}S_{A}^{\dagger}KB^{-1}=B^{-1}-\frac{1}{k}B^{-1}K^{T}K=B^{-1}-B^{-1}=0$.
Now, it follows from (8) that $\mathscr{M}^{\dagger}$ is given by (35). In
particular, if $k=2$, then

$\mathscr{M}^{\dagger}=\frac{1}{4}\left(\begin{array}[]{ccc}-B&-B&2I\\\
-B&-B&2I\\\ 2I&2I&0\end{array}\right).$

Hence $\mathscr{M}^{\dagger}$ is signable to nonpositive matrix by the
signature matrix $D=diag(I,\ldots,I,-I)$. Finally, if there exists an $m\times
m$ signature matrix $D_{-}$ such that $D_{-}BD_{-}\leq 0$, then $\mathscr{M}$
is signable to nonnegative matrix by the signature matrix
$D=diag(D_{-},\ldots,D_{-},D_{-})$, as claimed. ∎

######  Remark 6.

$G_{B}$ is a bipartite graph iff there exists a signature matrix $D_{-}$ such
that $D_{-}BD_{-}\leq 0$. Indeed, if we set $(D_{-})_{ii}=1$ for a vertex $i$
belongs to first bipartition, and $(D_{-})_{jj}=-1$ for a vertex $j$ belongs
to the second bipartition, then $D_{-}BD_{-}\leq 0$. On the other hand, if
there exists a signature matrix $D_{-}$ such that $D_{-}BD_{-}\leq 0$, then
there exists a bipartition of $G_{B}$, each of two bipartions consisting of
vertices with the same sign of $D_{-}$.

######  Proposition 6.

Assume $G_{B}$ is a graph on $m$ vertices whose adjacency matrix $B$ is
invertible. Let us denote by $G_{B}^{k,1}$ the graph which is constructed from
$G_{B}$ by adding $k\in\mathbb{N}$ pendant vertices to each vertex of $G_{B}$.
Then $G_{B}^{k,1}$ is negatively pseudo-invertible. If there exist an $m\times
m$ signature matrix $D_{-}$ such that $D_{-}BD_{-}\leq 0$, then $G_{B}^{k,1}$
is also positively pseudo-invertible graph.

###### Proof.

The adjacency matrix $\mathscr{M}$ of $G_{B}^{k,1}$ has the form (35). The
rest of the proof follows from Proposition 5. ∎

The following result is a consequence of Proposition 6 for the case of $k=1$
pendant vertex added to vertices of $G_{B}$. It is a generalization of [2,
Theorem 3.38] stating that, if a tree is invertible, then it is isomorphic to
itself iff it is a corona tree obtained from a tree $G_{B}$ by adding a
pendant vertex to every vertex of $G_{B}$.

######  Corollary 1.

Assume $G_{B}$ is a graph on $m$ vertices with an adjacency matrix $B$. Then
the graph $G^{1,1}_{B}$ is negatively self pseudo-invertible, i. e.,
$(G^{1,1}_{B})^{\dagger}\cong G^{1,1}_{B}$. If $G_{B}$ is a bipartite graph,
then $G^{1,1}_{B}$ is also positively self pseudo-invertible.

In Fig. 3 and Fig. 4 we show the simple path graph $G_{B}=\mathbb{P}_{2}$ on
two vertices and the graph graph $G_{B}=F_{0}$ representing fulvene organic
molecule. We also show the graphs $G_{B}^{2,1}$ constructed from $G_{B}$ by
adding two pendant vertices and their negatively pseudo-invertible graphs
$(G_{B}^{2,1})^{\dagger}$. For $G_{B}=\mathbb{P}_{2}$ the graph
$(G_{B}^{2,1})^{\dagger}$ is also positively pseudo-invertible bipartite
graph.

Figure 3. The path graph $G_{B}=\mathbb{P}_{2}$ with two vertices (left), the
graph $G_{B}^{2,1}$ constructed from the path graph $\mathbb{P}_{2}$ by adding
two pendant vertices (middle), its positive pseudo-inverse graph
$(G_{B}^{2,1})^{\dagger}$ (right).

Figure 4. The negatively invertible fulvene graph $G_{B}=F_{0}$ (left), the
graph $G_{B}^{2,1}$ constructed from $F_{0}$ by adding two pendant vertices
(middle), its negative pseudo-inverse graph $(G_{B}^{2,1})^{\dagger}$ (right).

######  Proposition 7.

Assume $G_{B}$ is a graph on $m$ vertices whose adjacency matrix $B$ is
invertible. Let us denote by $G_{B}^{1,l},l\in\mathbb{N}$, the graph which is
constructed from $G_{B}$ by adding pendant paths $\mathbb{P}_{l}$ to each
vertex of $G_{B}$. Then the adjacency matrix $\mathscr{M}$ of $G_{B}^{1,l}$ is
invertible.

  1. (1)

If $l$ is odd, then $G_{B}^{1,l}$ is a negatively integrally invertible graph.
Moreover, if there exists a signature matrix $D_{-}$ such that
$D_{-}BD_{-}\leq 0$, then $G_{B}^{1,l}$ is a positively integrally invertible
graph.

  2. (2)

If $l$ is even, then $G_{B}^{1,l}$ is a positively/negatively invertible graph
provided that $G_{B}$ is positively/negatively invertible graph.

Figure 5. The positively invertible graph $G_{B}$ on four vertices (left), the
graph $G_{B}^{1,2}$ constructed from $G_{B}$ by adding pendant paths
$\mathbb{P}_{2}$ on each vertex (middle), its pseudo-inverse graph
$(G_{B}^{1,2})^{\dagger}$ (right).

###### Proof.

The adjacency matrix $\mathscr{M}\in\mathbb{R}^{(l+1)m\times(l+1)m}$ of the
graph $G^{1,l}_{B}$ has the block form (5) where the block matrices
$A\in\mathbb{R}^{lm\times lm}$, and $K\in\mathbb{R}^{lm\times m}$ have the
form:

$A=\mathscr{A}\otimes I=\begin{pmatrix}0&I&&&&\\\ I&0&I&&&\\\ &I&0&\ddots&&\\\
&&\ddots&\ddots&I&\\\ &&&I&0&\\\ \end{pmatrix}\qquad K=e\otimes
I=(I,0,\dots,0)^{T},$

where $I=I_{m}$ is the identity matrix,
$e=(1,0,\dots,0)^{T}\in\mathbb{R}^{l}$, and $\mathscr{A}$ is the adjacency
matrix of the path graph $\mathbb{P}_{l}$, i. e., $\mathscr{A}_{ij}=1$ for
$|i-j|=1$, and $\mathscr{A}_{ij}=0$, otherwise. An example of a graph
$G_{B}^{1,2}$ is shown in Fig. 5). The Schur complement matrix
$S_{A}=A-KB^{-1}K^{T}=\mathscr{A}\otimes I-e\otimes IB^{-1}e^{T}\otimes
I=\mathscr{A}\otimes I-ee^{T}\otimes B^{-1}$. It is straightforward to verify
that the matrix $S_{A}$ is invertible, and it has the block cyclic form:

$\underbrace{S_{A}^{-1}}_{l=2}=\begin{pmatrix}0&I\\\
I&B^{-1}\end{pmatrix},\qquad\underbrace{S_{A}^{-1}}_{l=3}=\begin{pmatrix}-B&0&B\\\
0&0&I\\\ B&I&-B\end{pmatrix},$
$\underbrace{S_{A}^{-1}}_{l=4}=\begin{pmatrix}0&I&0&-I\\\
I&B^{-1}&0&-B^{-1}\\\ 0&0&0&I\\\
-I&-B^{-1}&I&B^{-1}\end{pmatrix},\quad\underbrace{S_{A}^{-1}}_{l=5}=\begin{pmatrix}-B&0&B&0&-B\\\
0&0&I&0&-I\\\ B&I&-B&0&B\\\ 0&0&0&0&I\\\ -B&-I&B&I&-B\end{pmatrix},$

etc. In general, if $l$ is odd, then the matrix $S_{A}^{-1}$ contains the
matrix $B$, whereas, if $l$ is even, then it contains the inverse matrix
$B^{-1}$. As the inverse matrices $B^{-1}$ and $S_{A}^{-1}$ exist then the
matrix $K$ is $(A,B)$ compatible. Moreover, if $l$ is odd, then we have
$S_{A}^{-1}KB^{-1}=(-I,0,I,0,\dots)^{T}$, and so
$B^{-1}K^{T}S_{A}^{-1}KB^{-1}=0$. If $l$ is even, then we have
$S_{A}^{-1}KB^{-1}=(0,B^{-1},0,-B^{-1},\dots)^{T}$, and so
$B^{-1}K^{T}S_{A}^{-1}KB^{-1}=-B^{-1}$. The matrix $\mathscr{M}$ is
invertible, and it has the block matrix form:

$\underbrace{\mathscr{M}^{-1}}_{l=2}=\begin{pmatrix}0&I&B^{-1}\\\
I&B^{-1}&B^{-1}\\\ 0&B^{-1}&B^{-1}\\\
\end{pmatrix},\qquad\underbrace{\mathscr{M}^{-1}}_{l=3}=\begin{pmatrix}-B&0&B&I\\\
0&0&I&0\\\ B&I&-B&-I\\\ I&0&-I&0\end{pmatrix},$
$\underbrace{\mathscr{M}^{-1}}_{l=4}=\begin{pmatrix}0&I&0&-I&0\\\
I&B^{-1}&0&-B^{-1}&-B^{-1}\\\ 0&0&0&I&0\\\ -I&-B^{-1}&I&B^{-1}&B^{-1}\\\
0&-B^{-1}&0&B^{-1}&B^{-1}\\\
\end{pmatrix},\quad\underbrace{\mathscr{M}^{-1}}_{l=5}=\begin{pmatrix}-B&0&B&0&-B&I\\\
0&0&I&0&-I&0\\\ B&I&-B&0&B&-I\\\ 0&0&0&0&I&0\\\ -B&-I&B&I&-B&I\\\
I&0&-I&0&I&0\end{pmatrix},$

etc. Now, if $l$ is odd, then the matrix $\mathscr{M}^{-1}$ is integral and
$det(\mathscr{M})=\pm 1$. Clearly, the matrix $\mathscr{M}^{-1}$ is signable
to a nonpositive matrix by the signature matrix:
$D=diag([I,[I,-I],-[I,-I],\dots,(-1)^{k-1}[I,-I],-I])$ where $l=2k+1$. If
there exists a signature matrix $D_{-}$ such that $D_{-}BD_{-}\leq 0$, then
the matrix $\mathscr{M}^{-1}$ is signable to a nonnegative matrix by the
signature matrix:
$D=diag([D_{-},-[D_{-},D_{-}],[D_{-},D_{-}],\dots,(-1)^{k}[D_{-},D_{-}],D_{-}])$
where $l=2k+1$.

Suppose that $l=2k$ is even. If $B$ is positively pseudo-invertible, then
there exists a signature matrix $D_{+}$ su that $D_{+}B^{-1}D_{+}\geq 0$. Then
the matrix $\mathscr{M}$ is positively pseudo-invertible because
$D\mathscr{M}^{-1}D\geq 0$ where
$D=diag([D_{+},D_{+}],-[D_{+},D_{+}],\dots,,(-1)^{k-1}[D_{+},D_{+}],-D_{+}])$.
If $B$ is negatively pseudo-invertible, then there exists a signature matrix
$D_{-}$ su that $D_{-}B^{-1}D_{-}\leq 0$. Then the matrix $\mathscr{M}$ is
negatively pseudo-invertible as $D\mathscr{M}^{-1}D\leq 0$ where
$D=diag([D_{-},-D_{-}],-[D_{-},-D_{-}],\dots,,(-1)^{k-1}[D_{-},-D_{-}],D_{-}])$,
as claimed.

∎

Figure 6. Top row: examples of positively (left), negatively (middle),
positively and negatively (bipartite) pseudo-invertible graphs with adjacency
matrix $det(B)\not=\pm 1$ on $m=5$ vertices. Corresponding graph pseudo-
inversions (bottom row).

Figure 7. Top row: examples of positively (left), negatively (middle),
positively and negatively (bipartite) integrally invertible graphs on $m=6$
vertices. Corresponding graph inversions (bottom row).

In Fig. 7 (middle) we show the graph $F_{0}$ with 6 vertices representing the
organic molecule of the fulvene hydrocarbon
(5-methylidenecyclopenta-1,3-diene). The graph $F_{0}$ is negatively (but not
positively) invertible with the integral inverse graph $(F_{0})^{-1}$ depicted
in Fig. 7 (middle). The nonsymmetric spectrum consists of the following
eigenvalues $\sigma(F_{0})=\\{-1.8608,-q,-0.2541,1/q,1,2.1149\\}$ where
$q=(\sqrt{5}+1)/2$ is the golden ratio with the least positive eigenvalue
$\lambda_{+}(F_{0})=1/q$. The inverse adjacency matrix $A_{F_{0}}^{-1}$ is
signable to a nonpositively integral matrix by the signature matrix
$D=diag(-1,-1,1,1,1-1)$. The inverse graph is depicted in Fig. 7 (middle).

Figure 8. Top row: examples of positively (left), negatively (middle),
positively and negatively (bipartite) pseudo-invertible graphs with singular
adjacency matrix on $m=6$ vertices (top row). Corresponding weighted pseudo-
inverse graphs (bottom row).

Figure 9. Top row: an example of a positively and negatively (bipartite)
pseudo-invertible graph on $m=9$ vertices (left). Its pseudo-inverse weighted
graph (right)

Figure 10. Examples of two positively and negatively (bipartite) pseudo-
invertible graphs with singular adjacency matrices on $m=10$ vertices.

##  4\. Conclusions

In this paper we investigated the Moore-Penrose pseudo-inversion
$\mathscr{M}^{\dagger}$ of a block symmetric matrix $\mathscr{M}$ with
applications in the graph theory. We showed that maximal and minimal
eigenvalues of a pseudo-inverse matrix $\mathscr{M}^{\dagger}$ are related to
the least positive $\lambda_{+}(\mathscr{M})>0$ and largest negative
eigenvalues $\lambda_{-}(\mathscr{M})<0$ of a symmetric real matrix
$\mathscr{M}$. We also present the key idea of derivation of the explicit
Banachiewicz–Schur form of the Moore-Penrose pseudo-inverse of a block
symmetric matrix. It can be used in order to characterize the least positive
and largest negative eigenvalues in terms of a mixed integer-nonlinear
optimization problem. We introduced and analyzed a novel concept of positive
and negative pseudo-invertibility of a symmetric matrix and graphs. We present
a summary table containing number of positively/negatively pseudo-invertible
graphs. The list of graphs with no more than 10 vertices contains complete
information on various classes of (pseudo)invertible graphs including their
spectral properties. Furthermore, we present special examples of pseudo-
invertible graphs constructed from a given graph by adding hanging vertices or
paths.

## References

  * [1] R. B. Bapat, and E. Ghorbani, Inverses of triangular matrices and bipartite graphs, Linear Algebra and its Applications 447 (2014), 68-73.
  * [2] R. B. Bapat, Graphs and Matrices. Universitext. Springer, London; Hindustan Book Agency, New Delhi, 2nd edition, 2014, 193 pp., ISBN: 978-1-4471-6569-9.
  * [3] A. Ben-Israel, T.N.E. Greville, Generalized Inverses: Theory and Applications, CMS Books Math., Springer, 2003.
  * [4] Brouwer, A., Haemers, W.. Spectra of graphs. Universitext. Springer, New York, 2012. xiv+250 pp. ISBN: 978-1-4614-1938-9.
  * [5] S. Boyd and L. Vandenberghe,  _Convex Optimization_ ,  Cambridge University Press New York, NY, USA, 2004.
  * [6] D. Cvetković, M. Doob, and H. Sachs, Spectra of graphs - Theory and application, Deutscher Verlag der Wissenchaften, Berlin, 1980; Academic Press, New York, 1980.
  * [7] D. Cvetković, I. Gutman, and S. Simić, On selfpseudo-inverse graphs, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. fiz., No. 602 – 633, (1978), 111–117.
  * [8] D. Cvetković, P. Hansen and V. Kovačevič-Vučič,  On some interconnections between combinatorial optimization and extremal graph theory,  _Yugoslav Journal of Operations Research_ , 14 (2004), 147–154.
  * [9] C. D. Godsil, Inverses of Trees, Combinatorica 5 (1985), 33–39.
  * [10] Godsil, C, Royle, G., Algebraic graph theory. Graduate Texts in Mathematics, 207. Springer-Verlag, New York, 2001. xx+439.
  * [11] F. J. Hall,  Generalized Inverses of a Bordered Matrix of Operators,  _SIAM Journal on Applied Mathematics_ , 29 (1975), 152–163.
  * [12] D. R. Batigne, F. J. Hall, and I. J. Katz,  Further results on integral generalized inverses of integral matrices,  _Linear and Multilinear Algebra_ , 6 (1978), 233–241.
  * [13] F. Harary and H. Minc, Which nonnegative matrices are self-inverse? Math. Mag. (Math. Assoc. of America) 49 (1976) 2, 91–92.
  * [14] S. J. Kirkland, and S. Akbari, On unimodular graphs, Linear Algebra and its Applications 421 (2007), 3–15.
  * [15] S. J. Kirkland, and R. M. Tifenbach, Directed intervals and the dual of a graph, Linear Algebra and its Applications 431 (2009), 792–807.
  * [16] C. McLeman, and A. McNicholas, Graph invertibility, Graphs Combin. 30 (2014), 977–1002.
  * [17] S. Pavlíková, and J. Krč-Jediný, On the inverse and dual index of a tree, Linear and Multilinear Algebra 28 (1990), 93–109.
  * [18] S. Pavlíková, A note on inverses of labeled graphs, Australasian Journal on Combinatorics, 67(2) (2017), 222–234.
  * [19] S. Pavlíková, and D. Ševčovič,  On a construction of integrally invertible graphs and their spectral properties,  _Linear Algebra and its Applications_ , 532 (2017), 512–533.
  * [20] S. Pavlíková, and D. Ševčovič,  Maximization of the spectral gap for chemical graphs by means of a solution to a mixed integer semidefinite program,  _Computer Methods in Materials Science_ , 4 (2016), 169–176.
  * [21] S. Pavlíková, and D. Ševčovič,  On Construction of Upper and Lower Bounds for the HOMO-LUMO Spectral Gap by Means of Semidefinite Relaxation Techniques,  _Numerical Algebra, Control and Optimization_ , 9 (2019), 53–69.
  * [22] S. Pavlíková, and nd J. Širáň,  Inverting non-invertible weighted trees,  Australasian J. Combin., 75 (2019), 246–255.
  * [23] S. Pavlíková, and D. Ševčovič,  Invertible and pseudo-invertible simple connected graphs, their spectra, positive and negative (pseudo)invertibility. Available online at: http://www.iam.fmph.uniba.sk/institute/sevcovic/inversegraphs/, July 2022.
  * [24] D. Ševčovič and M. Trnovská,  Solution to the inverse Wulff problem by means of the enhanced semidefinite relaxation method,  _Journal of Inverse and III-posed Problems_ , 23 (2015), 263–285.
  * [25] D. Ye, Y. Yang, B. Manda, and D. J. Klein, Graph invertibility and median eigenvalues, Linear Algebra and its ApplicaNtions, 513(15) (2017), 304–323.
  * [26] D.J. Klein,Y. Yang, and D. Ye, HUMO-LUMO Gaps for Sub-graphenic and Sub-buckytubic Species, Proceedings of the Royal Society A, 471 (2180) (2015), 20150138.
  * [27] T. Zaslavsky,  Signed graphs,  _Discrete Applied Math._ , 4 (1982), 47–74.
  * [28] N. Castro-González, M.F. Martínez-Serrano, J. Robles,  Expressions for the Moore–Penrose inverse of block matrices involving the Schur complement,  _Linear Algebra and its Applications_ , 471 (2015), 353–368.
  * [29] Y. Tian, Y. Takane,  More on generalized inverses of partitioned matrices with Banachiewicz–Schur forms,  _Linear Algebra and its Applications_ , 430 (2009) 1641–1655.
  * [30] R. Hessert, S. Mallik, Moore-Penrose inverses of the signless Laplacian and edge-Laplacian of graphs, Discrete Mathematics 344 (2021), 112451.
  * [31] J. McDonald, N. Raju, and K. C. Sivakumar,  Group inverses of matrices associated with certain graph classes.  The Electronic Journal of Linear Algebra 38 (2022), 204-220.
  * [32] S. Gago,  Group inverse of the Laplacian of connections of networks.  Discrete Applied Mathematics 263 (2019), 152-159.
  * [33] S. Pavlíková, and N. Krivoňáková,  Generalized inverses of cycles.  Conference proceedings of Mathematics Information Technologies and Applied Sciences, University of Defence, Brno, 2018, pp. 110-117.
  * [34] Lin Chen and Jinfeng Liu,  Extremal values of matching energies of one class of graphs,  _Applied Mathematics and Computation_ , 273 (2016), 976–992.
  * [35] B. Mohar,  Median eigenvalues of bipartite planar graphs,  _MATCH Commun. Math. Comput. Chem._ 70 (2013), 79–84.
  * [36] M. Mohar,  Median eigenvalues and the HOMO-LUMO index of graphs,  _Journal of Combinatorial Theory, Series B_ , 112 (2015), 78–92.
  * [37] Xueliang Li, Yiyang Li, Yongtang Shi and I. Gutman,  Note on the HOMO-LUMO index of graphs,  _MATCH Commun. Math. Comput. Chem._ , 70 (2013), 85–96.
  * [38] G. Jaklić,  HL-index of a graph,  _Ars Mathematica Contemporanea_ , 5 (2012), 99–105.
  * [39] P. W. Fowler, P. Hansen, G. Caporosi and A. Soncini,  Polyenes with maximum HOMO-LUMO gap,  _Chemical Physics Letters_ , 342 (2001), 105–112.
  * [40] P. V. Fowler,  HOMO-LUMO maps for chemical graphs,  _MATCH Commun. Math. Comput. Chem._ , 64 (2010), 373–390.
  * [41] I. Gutman and D.H. Rouvray,  An Aproximate TopologicaI Formula for the HOMO-LUMO Separation in Alternant Hydrocarboons,  _Chemical-Physic Letters_ , 72 (1979), 384–388.
  * [42] F. Zhang and Z. Chen,  Ordering graphs with small index and its application,  _Discrete Applied Mathematics_ , 121 (2002), 295–306.