\1cw  Verze 2.10
\pTM 2
\pBM 14
\pPL 120
\pLM 1
\pRM 65
\HD
\+
\+
\,
\-
\=
\HE
\+
\+
\,
\-
\=
\FD
\+
\+
\,
\-
\=
\FE
\+
\+
\,
\-
\=
\+
\+
\"1 7   I N V E R S E   M A T R I C E S\,
\-\1
\+
\+
\417.1 Introduction
\-\1
\+
\+
     It is rather easy to define \ an inverse element to an isola-\A
\-\/
\+
\+
ted element, \ as a number or \ a vector is. But \ this task becomes 
\-
\+
\+
conceptually \ difficult at \ whole systems \ represented by \ matrix 
\-
\+
\+
vectors. And it is mysterious, \ how to define inverse elements to 
\-
\+
\+
things. Can you \ tell, what your inverse is? \ The answer will de-\A
\-
\+
\+
pend, if you \ search your inner inverse as \ a person, only, or an 
\-\/
\+
\+
inverse element of you as a part of some system.\,
\-
\+
\+
   At first recall Chapter 4.4. There are two types of inverse e-\A
\-\/
\+
\+
lements, additive and multiplicative. Additive inverse is defined 
\-
\+
\+
by the identity \ a + b = 0, from it \ b = -a. The negative element 
\-
\+
\+
has the same \ value and opposite sign of \ its parent element. The 
\-
\+
\+
multiplicative inverse element is defined \ as the product ab = 1. 
\-
\+
\+
From it \ b = 1/a. We \ have already shown \ that the multiplicative 
\-\/
\+
\+
inverses are additive on the logarithmic scale.\,
\-
\+
\+
   At matrices, \ we can define \ also additive and \ multiplicative 
\-
\+
\+
inverse matrices with zero matrices \ \40 \1and unit diagonal matrices 
\-
\+
\+
\4I \1as unit elements. The additive \ inverses are trivial, they have 
\-
\+
\+
only inverse signs, but the multiplicative inverses are much more 
\-
\+
\+
interesting. \,
\-
\+
\+
   We can start with unit permutation matrices \4P\1, which represent 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1the symmetric group. Their inverses are their transposes \4P P \1= \4I\1.\,
\-
\+
\+
At diagonal \ matrices \7D \1the \ inverse elements of \ dö are elements 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+
1/dö. \ But if \ we combine \ a diagonal \ matrix with \ a permutation 
\-\2\ \ \ j
\+\1
\+
matrix, its inverse is not a simple sum of partial inverses.\,
\-
\+
\+
   The problem of inverses \ is moreover complicated at assymmetric 
\-
\+
\+
matrices, \ that they \ have two \ different inverses, \ one from the 
\-
\+
\+
left \ and one \ from the \ right, because \ multiplications from the 
\-
\+
\+
left have another effect than \ the multiplication from the right. 
\-
\+
\+
And last \ but not least, \ many matrices have \ no inverse, because 
\-
\+
\+
they \ are singular, \ it means \ that their \ spectrum contains some 
\-
\+
\+
zero eigenvalues. \,
\-
\+
\+
   We have worked with quadratic \ forms and it will be convenient 
\-\/
\+
\+
to define a third kind of \ inverses, the inner inverse of quadra-\A
\-
\+
\+\2
\1tic \ forms as \ a matrix \4R \1which \ gives, if \ it is multiplied from 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1both sides \ with a matrix \4M \1and \ its transposed form \ \4M  \1the unit 
\-\/
\+
\+\2
\1diagonal matrix:\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  T
\4\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ MRM  \1= \4I       \1(17.1)\,
\-\/
\+
\+\2
\1   It can be \ expressed also conventionally, \4MR \1is \ the left hand 
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ T
\1side inverse of  \4M  \1and \4RM  \1is \ the right hand side inverse of \4M\1. 
\-
\+
\+\2
\1We can point \ in this context on the \ definition of eigenvectors, 
\-
\+
\+\2
\1which give, when \ they have its matrix within, \ the diagonal mat-\A
\-
\+
\+\2
\1rix. If we correct the product by inverse eigenvalues, we get the 
\-
\+
\+\2
\1unit diagonal matrix, therefore, \ a matrix \4M \1weighted by inverses 
\-
\+
\+\2
\1of its eigenvalues \ is the inner inverse of \ its eigenvector mat-\A
\-\/
\+
\+\2
\1rix.\,
\-
\+
\+
\417.2 Matrix inversing\,
\-\1
\+
\+
   We have shown in Chapters \ dealing with matrices of combinato-\A
\-\/
\+
\+
rial numbers in triangular form, that their inverses are found by 
\-
\+
\+
the inclusion and exclusion technique. Another  technique suitab-\A
\-
\+
\+
le for finding of inverse matrices was already shown in the Chap-\A
\-
\+
\+
ter 16.12. Both techniques are equivalent in the the case of mat-\A
\-
\+
\+
rices in lower triangular form having the unit diagonal. The n-th 
\-
\+
\+
power of its \ difference with the unit diagonal \ matrix gives the 
\-
\+
\+
zero matrix \40\1. When we write all terms of this power and rearran-\A
\-\/
\+
\+
ge them suitably, we get \,
\-
\+
\+\2\ \ \ \ \ \ n-1\ \ \ \ \ n-2\ \ \ \ \ \ \ \ \ \ \ \ n-3\ \ \ \ \ \ \ \ \ \ 1
\4I \1= [\4M    \1- n\4M    \1+ n(n-1)/2\4M    \1-..+/- n\4M  \1+/-\4I\1]\4M    \1(17.2)\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -1
\1The right side matrix in brackets is the left hand side inverse \4M
\-\1
\+
\+
of the matrix in the lower \ triangular form \4M\1. This matrix can be 
\-
\+
\+
written also on the left hand side of the brackets.\,
\-
\+
\+
   Similar structure, only somewhat \ more complicated have matri-\A
\-\2\/
\+\1
\+
ces \4B    \1obtained \ from the Le \ Verrier-Faddeev-Frame technique, 
\-\2\ \ \ \ \ n-1
\+\1
\+
where coefficients of the polynomial are used for subtracting the 
\-
\+
\+
unit \ diagonal matrix \ on different \ steps of \ the multiplication 
\-\/
\+
\+
with the matrix \4M\1.\,
\-
\+
\+
   The \ inverse matrix \ can be \ formulated using \ the determinant 
\-
\+
\+
d(\4M\1) and determinants \ of all its submatrices \7döö\4M\1, \ known as the 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+
minors \4Aöö\1. \ \7d\4ööM \1is the \ matrix \4M \1with \ the ith row \ and the jth 
\-\2\ \ \ \ \ \ \ \ ij\ \ \ \ ij
\+\1
\+
column deleted.\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -1
\1   The inverse matrix \4M\1öö to a \ matrix \4M \1is the transposed matrix 
\-
\+
\+
of its minors Aöö divided \ by the determinant. If the determinant 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+
is \ zero, the \ inverse matrix \ \ is not \ defined from \ the obvious 
\-
\+
\+
reason: \ If we \ divide by \ zero, we \ obtain undetermined \ infinite 
\-
\+
\+
numbers. This gives also an \ answer, what your inverse element is. 
\-
\+
\+
It is your minor.\,
\-
\+
\+
   A multiplication \ of a matrix with \ its inverse is transformed 
\-
\+
\+
into the \ task of decomposition \ of its determinant \ according to 
\-
\+
\+
its \ rows or \ columns. If \ a \ row \ of minors \ is multiplied \ by a 
\-
\+
\+
transposed row \ of the corresponding \ matrix elements, we \ obtain 
\-
\+
\+
the \ determinant and \ because minors \ in the \ inverse matrix \ are 
\-
\+
\+
divided by \ it, the ratio \ 1. If unmatching \ rows are multiplied, 
\-
\+
\+
 it has the \ same effect as if the matrix \ had two identical rows 
\-
\+
\+
and the determinant given by this product is zero.\,
\-
\+
\+
   The inverse matrices, \ if they exist, can be \ used for solving 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -1
\1systems of linear equations \4Mx \1= \4b\1. We have simply \4x \1= \4M\ \ b\1.\,
\-
\+
\+
\417.3 Walk and path matrices\,
\-\1
\+
\+
   We have shown \ how the inverse matrix elements \ are related to 
\-
\+
\+
minors of the \ matrix elements. But in some \ cases these inverses 
\-
\+
\+
can be deduced \ directly from the structure of \ graphs without no 
\-
\+
\+
apparent connection with minors and determinants. \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1   It is \ the case of matrices \ \4SSö \1of oriented trees. \ They have 
\-
\+
\+
(n-1) rows and columns and are nonsingular, because corresponding 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1quadratic forms \4S\1ö\4S \ \1have just one zero eigenvalue. \ In a tree no 
\-
\+
\+
cycles are and therefore, there exist just one walk between each 
\-
\+
\+
pair of \ vertices ( in case \ of unoriented graphs we \ speek about 
\-
\+
\+
paths). \ We can \ define matrices \ which rows \ correspond to \ all 
\-
\+
\+
walks \ or paths \ in a \ tree, and \ columns represent \ the arcs \ or 
\-
\+
\+
edges, respectively. The elements wöö \ of these matrices are 1 if 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  ij
\+\1
\+
the \ arc \ or \ edge \ j \ is \ a \ part \ of \ the \ path or walk i and 0 
\-
\+
\+
otherwise. The \ problem is complicated, \ especially at unoriented 
\-
\+
\+
trees by signs necessary to eliminate unwanted elements when walk 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1matrices are multiplied with matrices \ \4GG\1ö which all elements are 
\-
\+
\+
positive. wöö \ has positive sign, \ if the edge \ j is in \ the even 
\-\2\ \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+
distance from \ the last edge \ in the block \ or the arc \ j has the 
\-
\+
\+
same orientation as the last arc and it has negative sign, if the 
\-
\+
\+
corresponding edge is in the odd \ distance from the last edge, or 
\-
\+
\+
the corresponding \ arc has the \ opposite orientation as \ the last 
\-
\+
\+
one.\,
\-
\+
\+
   It is \ interesting that the \ walk matrices of \ oriented linear 
\-
\+
\+
chains are identical with Petrie matrices of complete graphs, on-\A
\-\/
\+
\+
ly their elements have different interpretations.\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \   T
\1   The true inverses of quadratic forms \ \4GG  \1and \4SS  \1are 1/n mul-\A
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ \ \ \ \ \     T\ T
\1tiples corresponding quadratic forms \ \4W W\1, and matrices \4G W W \1and 
\-
\+
\+\2\ T\ T
\4S W W \ \1are right \ inverses of \ \4G \1or \4S\1, \ repectively, similarly as 
\-\/
\+
\+\2\ T\ \ \ \ \ \ \ \ T
\4W WG \1and \4W WS \1are left inverses \ of \4G \1or \4S\1. The diagonal elements 
\-
\+
\+\2
\1of both quadratic \ forms are numbers counting how \ many times the 
\-
\+
\+\2
\1corresponding arc \ or edge was \ used in all \ walks or paths, \ off 
\-
\+
\+\2
\1diagonal elements count common exploitations of the given pair of 
\-
\+
\+\2
\1lines. These numbers obtained as simply are simultaneously minors 
\-\/
\+
\+\2
\1of the corresponding quadratic forms of incidence matrices.\,
\-
\+
\+\2
\417.4.Inverse matrices of uneven unoriented cycles.\,
\-\1
\+
\+
\4   The incidence matrix G \1of \ a simple unoriented cycle C  has in 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n\/
\+\1
\+
its canonical form in each \ row two consecutive 1, g   = 1, g    = 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ii\ \ \ \ \  \ ii+1
\+\1
\+
1 { index (n  + 1) = 1}, g   = 0 otherwise. Both quadratic forms 
\-\2\ \ \ \ \ \ \ \ \ \       \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ \ \ \ \ T
\1are identical, their elements \ are g g   = 2, g g       = 1 {index 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ii\ \ \ \ \ \ \ \ \ ii+/-1\/
\+\1
\+\2
\10 = 1, (n+1) = 1}.\,
\-\2
\+\1
\+
   The search for the inverse we \ begin at the quadratic form of 
\-
\+
\+
a cycle matrix \ \4C\1. It is easy \ to find it for \ small cycles, e.g. 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ T\ \ -1
\1for 7 member cycle this symmetrical matrix (\4S\ S\1)\ \  begins\,
\-
\+
\+
-5  7  -5   3  -1  -1   3\,
\-
\+
\+
3  -5   7  -5   3  -1  -1\,
\-
\+
\+
.........................\,
\-
\+
\+
This \ matrix is \ obtained from \ a basic \ matrix of \ uneven cycles 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d(ij)
\1which elements cöö = (-1)ööööö. The upper indices are distances of 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+\2
\1vertices from the diagonal vertex. There are k positive and (k+ 1) 
\-\2
\+\1
\+\2
\1negative signs in each row an column, e.g.\,
\-\2
\+\1
\+
+1  -1  +1  -1  -1  +1  -1\,
\-
\+
\+
-1  +1  -1  +1  -1  -1  +1\,
\-
\+
\+
+1  -1  +1  -1  +1  -1  -1\,
\-
\+
\+
..........................\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ T\ \ \ \ 2
\1   Since \4C \1is \ symmetric \4C C \ \1= \4CC  \1= \4C \1. In \ quadratic forms \ the 
\-
\+
\+\2
\1sign s of neighbour elements are always opposite and their values 
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ T
\1difference is \  always 2. Therefore when \ multiplying \4CCö \1with \4GöG 
\-\1
\+
\+\2
\1we obtain for diagonal elements \,
\-
\+
\+
1*(2 - n) + 2*n + 1*(2 - n) = 4\,
\-
\+
\+
for the off-diagonal elements we obtain \,
\-
\+
\+
1*[2(k - 1) - n] + 2*(n - 2k) + 1*[2(k + 1) - n] = 0 \,
\-
\+
\+
   This result is obtained also for the middle elements +/-(1,1,-
\-\/
\+
\+
3) or +/-(-3,1,1). The cycle matrix \4C \1has the required property of 
\-
\+
\+
cycle matrices, namely \4CG \1= \40 \1mod 2. The \ neighbour elements are 
\-
\+
\+
mostly (+/ - 1) \ and if they have the equal \ sign, then their sum 
\-
\+
\+\2
\1is 2. The product is 2\4P\1, where \4P \1is the unit permutation matrix of 
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ \ \ T
\1a cycle. The next product \4CGG  \1= 2(\4P \1+ \4P \1).\,
\-
\+
\+\2
\1   These properties of partial products allow to define pseudoin-\A
\-\/
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1verse matrices of \4G \1and \4G  \1from both sides\,
\-
\+
\+\2\ -1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ 2\ \ \ \ \ \ \ \ \ \ \ T
\4G\ \  \1from the right = 1/4\4G\ C\  \1= +/-1/2\4CP\,
\-\1
\+
\+\2\ -1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2\ T\ \ \ \ \ \ \ \ \ \ T
\4G\   \1from the left  = 1/4\4C\ G\  \1= =/-1/2\4P\ C\,
\-\1
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1The permutation \ matrix \4Pö \1has \ unit elements p\4ööööööööööö\1. If it 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i,i+(n-1)/2
\+\1
\+
multiplies the matrix \4C \1from \ the right, it permutes its columns, 
\-
\+
\+
if from the \ left, it permutes its rows. Because \ the matrix \4C \1is 
\-
\+
\+
symmetric \ results of \ both \ permutations \ are identical \ and the 
\-
\+
\+
incidence \ matrix of \ an unoriented \ uneven  \ cycle has \ the true 
\-
\+
\+
inverse. Moreover if the cycle matrices act on the quadratic form 
\-
\+
\+\2\ T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\4G\ G \1from both sides, they diagonalize it, too : \4CG\ GC \1= 4\4I\1.\,
\-
\+
\+
\417.5. Inverse matrices of unoriented cyclic graphs\,
\-\1
\+
\+
    The \ existence \ of \ inverse \ matrices \ of \ quadratic forms of 
\-
\+
\+
incidence \ matrices of \ simple unoriented \ cycles arouse interest 
\-
\+
\+
about possibilities \ to find inverse matrices \ of these quadratic 
\-
\+
\+
forms of incidence matrices of cyclic graphs. From both quadratic 
\-
\+
\+\2\ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ \ T
\1forms \4G\1ö\4G \ \1and \4GG\1ö only the \ matrix of lesser dimension \ can have 
\-
\+
\+
the inverse. It means that at graphs with two or more cycles only 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1the \ form \ \4G\1ö\4G \ \1can \ be \ nonsingular, \ because \ \4GG\1ö \ is of higher 
\-
\+
\+
dimension.\,
\-
\+
\+
   Some examples \ of unoriented cyclic graphs \ having inverses of 
\-
\+
\+
the quadratic form were found easily (Fig. 17.1). Graph A has in-\A
\-\/
\+
\+
verses of both quadratic forms\,
\-
\+
\+\2   \ T\8pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \2T\ \ -1\ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\4G\ G  \8pp\12   1   1   0\8pp            \14(\4G\ G\1)\ \   \8pp \13  -1  -1   1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   2   1   0\8pp                      pp\1-1   3  -1   1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   1   3   1\8pp                      pp\1-1  -1   3  -3\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\10   0   1   1\8pp                      pp \11   1  -3   7\8pp\,
\-\1
\+
\+\2\ \ T\ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \2T\ -1\ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\4GG\   \8pp\12   1   1   0\8pp            \12(\4GG\ \1)\ \   \8pp \12  -1  -1   1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   2   1   1\8pp                      pp\1-1   2   0  -1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   1   2   1\8pp                      pp\1-1   0   2  -1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\10   1   1   2\8pp                      pp \11  -1  -1   1\8pp\,
\-\1
\+
\+
    Graph B\,
\-
\+
\+\2\ T\ \ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \2T\ \ -1\ \ \ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\4G\ G  \8pp\12   1   1   0   0\8pp     \124(\4G\ G\1)\ \     \8pp\117  -7  -3   1   1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   2   1   0   0\8pp                  pp\1-7  17  -3   1   1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   2   4   1   1\8pp                  pp\1-3  -3   9  -3  -3\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\10   0   1   2   1\8pp                  pp \11   1  -3  17  -7\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\10   0   1   1   2\8pp                  pp \11   1  -3  -7  17\8pp\,
\-\1
\+
\+\2
\1    Graph C\,
\-
\+
\+\2\ T\ \ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \2T\ \ -1\ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\4G G  \8pp\13   1   1   1\8pp            \14(\4G\ G\1)\ \   \8pp \12  -1  -1   0\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   2   0   1\8pp                      pp\1-1   3   1  -1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   0   2   1\8pp                      pp\1-1   1   3  -1\8pp\,
\-\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
     pp\11   1   1   3\8pp                      pp \10  -1  -1   2\8pp\,
\-\1
\+
\+
\417.6 Relations of spectra of graphs and complementary graphs\,
\-\1
\+
\+
    The characteristic polynomials of Laplace-Kirchhoff matrices 
\-\/
\+
\+
can be found by the same techniques as the characteristic polyno-\A
\-\/
\+
\+
mials of adjacency \ matrices, by \ counting characteristic figures 
\-\/
\+
\+
in which the vertex degrees v  represent \ loops or by Le Verrier-
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j\/
\+\1
\+
Faddeev-Frame technique.\,
\-
\+
\+\2\ \ \ \ \   
\1   The sum of inverses \ of Laplace-Kirchhoff submatrices ( \7d \4K\1)   
\-\2\ \ \ \ \ \ \    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ j\/
\+\1
\+\2
\1forms the generalized inverse \4E \1of the Laplace-Kirchhoff matrix \4E 
\-\2
\+\1
\+\2\ \ \ \ \ \ \ \ \ -1
\1= \7S \1(\7d \4K\1)   giving with it \ as the product the Laplace-Kirchhoff 
\-\2\ \ \ j\  j
\+\1
\+
matrix of the complete graph \4K \1: \4KE \1= \4K \1. The generalized inverse 
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ K\ \ \ \ \ \  \ K
\+
\+\2
\4E \1of the \ Laplace-Kirchhoff matrix is \ identical with the \ matrix 
\-\2
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n-1
\4B     \1of \ the Le \ Verrier-Faddeev-Frame technique \ \4K \1= \4K   \1-a \4K    
\-\2\ \ n-2\  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ n\ \ \ \ 1
\+\1
\+
+ ...a    \4K\1, where a  are coefficients of the characteristic poly-\A
\-\2\ \ \ \ \ \ \ n-1\ \ \ \ \ \ \ \ \ \ k
\+\1
\+
nomial and \ matrices \4K \1= \4KB    \1the Frame \ matrices \4B \1being obta-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n \ \ \ n-1
\+\1
\+\2
\1ined as \4B  \1=\4K  \1- a \4I\1. \4I \1is the unit diagonal matrix. The last Frame 
\-\2\ \ \ \ \ \ \ \ \ n\ \ \ n\ \ \ \ n
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ -1
\1matrix is \4B \1= \4K \1- a\4I \1= \40\1. It \ means that \4B    \1= 1/a   \4K  \1. At Lap-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ n\ \ \ n\ \ \ \ n\ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n-1\ \ \  \ \ n-1\/
\+\1
\+\2
\1lace-Kirchhoff matrices a  = 0, therefore \4K  \1= \40\1, \4J \1is the unit \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n\       \ \ \ \ \ \ \ \ \ n\ \ \ \ \ \               
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  
\1vector-column. Thus \4B   \1= \4K \1, a\ \ \ = n. It follows that \4E \1= \4B\ \ \  \1and \,
\-\2            \ \ \ \ \ \   \ \ n-1\ \ \ \ \ \ n-1       \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n-2
\+\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  
\+\2\ \ 2
\4EK\  \1= n\4K\1.\,
\-\2
\+\1
\+
   Moreover, if \ the Laplace-Kirchhoff matrix \4K \1of the graph G is\,
\-
\+
\+
multiplied by (\4E \1- \4I\1), the Laplace-Kirchhoff matrix of the comple-\,
\-
\+
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -
mentary graph \ G is obtained. From \ these results follow relations \,
\-
\+
\+
of eigenvalues \7l  \1of corresponding the Laplace-Kirchhoff matrices\4:\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -
\4E \1(\7l\ \1) = \4K\1(n/\7l\ \1) and \4K\1(G)(\7l\ \1) = \4K\1(G)(n - \7l\ \1).\,
\-\2\ \ \ \ j\ \ \ \ \ \ \ \ \ j\ \ \ \ \ \ \ \ \ \ \ \ j\ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+
   The eigenvalues \ of the Laplace-Kirchhoff \ matrices of comple-\A\,
\-
\+
\+
mentary graphs \ must be complementary \ to give as \ their sums the \,
\-
\+
\+
eigenvalues of the complete graph. For example, the star S  is the \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\+\1
\+
complementary graph of the complete graph K   and its spectrum is \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n-1
\+\1
\+\2\  \ \ n-2\ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  n-2
\1[n,1   ,0] which is complementary to [0,(n - 1)   ,0] of the Lap-\A
\-\/
\+
\+
lace-Kirchhoff matrix of the complete graph with (n -1) vertices.\,
\-
\+
\+
\417.7.Products of the Laplace-Kirchhoff matrices\,
\-\1
\+
\+
   Two graphs are considered equivalent, if their matrices can be  
\-\/
\+
\+
transformed by symmetrical permutations with the unit permutation \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1matrices \4P \1into each other : \4M\1(G ) = \4PM\1(G )\4P\1. An interesting pro-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i\ \ \ \ \ \ \ \ j\/
\+\1
\+
blem arises, how are \ related eigenvalues of corresponding matri-\A
\-
\+
\+
ces at such operations. It is customary to arrange eigenvalues in 
\-
\+
\+
increasing or decreasing order, but if a matrix is permuted, then 
\-
\+
\+
also its \ eigenvalues should be \ permuted to give \ different pro-\A
\-
\+
\+
ducts and therefore they can not \ be in all equivalent graphs ar-\A
\-
\+
\+
ranged similarly as in canonical form in an increasing or decrea-\A
\-\/
\+
\+
sing order.\,
\-
\+
\+
   When we multiply the Laplace-Kirchhoff matrices of twelve dif-\A
\-\2\/
\+\1
\+
ferently labeled linear chains L , we obtain 3 different results 
\-\2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4\/
\+\1
\+
depending on the number of common arcs and the given permutation. 
\-\/
\+
\+
From them we are interested on two extreme cases:\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2\ \ \ \ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\13 common arcs \4K\ \1(L\ ) \8pp \12  -3   1   0\8pp\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4\ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\1-3   6  -4   1\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
                     pp\ \11  -4   6  -3\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
                     pp \10   1  -3   2\8pp\,
\-\1
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\10 common arc \4K\1(L\ )\4K\1(L\ )\ \ \8pp\ \12  -1  -1   0\ \8pp\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4\ \ \ \ 4\ \ \ \8pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
                         pp\1-1   2   0  -1\ \8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
                         pp\1-1   0   2  -1\ \8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp
                         pp \10  -1  -1   2 \8pp\,
\-\1
\+
\+
 Lö \ is \ \ selfcomplementary \ and \ in \ the \ \ product \ of \ the \ two \,
\-\2\ \ 4
\+\1
\+
selfcomplementary graphs \ the eigenvalues are \ just multiplied in \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2
\1inversed order as eigenvalues in the quadratic \4K\ \1:\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1/2\ \ \ \ \ \ \ \ \ \ 1/2
\1Spectrum (L\ )   2+2\ \ \    2   2-2\ \ \    0\,
\-\2\ \ \ \ \ \ \ \ \ \ \ 4
\+\1\ \ \ \ \ \ \ \ \ \ _
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1/2\ \ \ \ \ \ \ \ \ \ 1/2
\1Spectrum (L\ )   2-2\ \ \    2   2+2\ \ \    0\,
\-\2\ \ \ \ \ \ \ \ \ \ \ 4
\+\1
\+
\8---------------------------------------\,
\-\1
\+
\+
Spectrum (C\ )   2        4     2      0\,
\-\2\ \ \ \ \ \ \ \ \ \ \ 4
\+\1
\+
The matrix product is the Laplace-Kirchhoff \ matrix of the cycle \,
\-
\+
\+
Cö and its eigenvalues are not ordered \ because the cycle \ itself \,
\-\2\ 4
\+\1
\+
is permuted \ from its standard form.\,
\-
\+
\+
   The result can be formulated \ in the theorem: If the Laplace-\,
\-
\+
\+
Kirchhoff matrix of a graph with simple arcs is multiplied by the \,
\-
\+
\+
Laplace-Kirchhoff matrix of its complementary graph, the eigenva-\A\,
\-
\+
\+
lues of the matrix product are eigenvalues of the parent Laplace-\,
\-
\+
\+
Kirchhoff matrix multiplied with themselves in the inverse order, \,
\-
\+
\+
except the zero eigenvalue.\,
\-
\+
\+
   The \ proof: \ From \ the \ complementary \ properties of both Lap-\,
\-
\+
\+
lace-Kirchhoff matrices follows \ that their off-diagonal elements \,
\-
\+
\+
forming adjacency matrices \ \4A \1have no effect on \ the trace of the \,
\-
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \   \ _
\+
product,Tr{\4A\1(G)\4A\1(G)} = 0. Therefore \ the diagonal elements of the \,
\-
\+
\+
product \ are vö{(n \ - 1) \ - vö} \ and simultaneously \ the trace is \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ j\ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+
according to the theorem the sum of eigenvalues products \7lö\1(n-\7l \1). \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j\ \ \ \ j
\+\1\ \ \ \ _
\+\2\ \ \ \ \ \ \ \ \ \ \ \ n\ \ \ \ \ \ \ \ \ \ \ \ \ 2\ \ \ \ \ \ n\ \ \ \ \ \ \ \ \ 2
\1Tr(\4KK\1) =  \7S\ \  \1{(n - v\ )- v\ } = \7S\ \   \1(n\7l\  \1-\7l \1).\,
\-\2\ \ \ \ \ \ \ \ \ \ \ j=1\ \      j\ \ \ \ j\ \ \ \ \ j=1\ \ \ \ j\ \ \ j
\+\1
\+
    The trace \ of the Laplace-Kirchhoff matrix \ is equal simulta-\A\,
\-
\+
\+
neously to the sum of vertex degrees \7S\1v  and to the sum of eigen-\A\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+
values \7Slö \1and the trace \ of the squared Laplace-Kirchhoff matrix \,
\-\2\ \ \ \ \ \ \ \ \ j
\+\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2\ \ \ \ \ \ \ \ 2\ \ \ \ \ \ \ \ \ \ \ \ 2
\1with simple arcs is \ Tr(\4Kö\1) = \ \7S\1(vö+övö) = \ \7Sölö\1, thus \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  j\  \ j\ \ \ \ \ \ \ \ j
\+\1\ \   _   
\+\2        \            \  2
\1Tr(\4KK\1)ö= nTr(\4K\1)ö-Tr( \4Kö\1). Going from the \ \ complementary graph and \,
\-
\+
\+
its Laplace-Kirchhoff matrix, and inserting (n -1 - v ) we obtain \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+
the same result.\,
\-
\+
\+
   The proof used properties of \ graph matrices with simple arcs, \,
\-
\+
\+
but the relation between eigenvalues \ is true also for multigraphs \,
\-
\+
\+
and their complementary graphs as calculated from the relation \,
\-
\+_\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \4_
\+\1
\4K \ \1= \4K\1(\4E \1- \4I\1), it \ is the difference \4K \1= \ \4K\1ö \2- \4K\1. For example\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ K
\+\1
\+
\,
\-
\+
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp
                              pp\1-1   1   0\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp
\+\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _\8pp\ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp
\4                             K\8pp \11   0  -1\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pp
                \              pp \10  -1   1\8pp\,
\-\1
\+
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -----------------
\1\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pppp\ \ \ \ \ \ \ \ \ \ pp
\+                pp \13  -2  -1\8pppp\1-5   4   1\8pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pppp\ \ \ \ \ \ \ \ \ \ pp
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pppp\ \ \ \ \ \ \ \ \ \ pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pppp\ \ \ \ \ \ \ \ \ \ pp
\+\4             K  \8pp\1-2   2   0\8pppp\ \14  -2  -2\8pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pppp\ \ \ \ \ \ \ \ \ \ pp
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pppp\ \ \ \ \ \ \ \ \ \ pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ pppp\ \ \ \ \ \ \ \ \ \ pp
\+                pp\1-1   0   1\8pppp\ \11  -2   1\8pp
\+\1
\,
\-
\+
\+
\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1/2 \ \ \ \      \ 1/2
\+\1Spectrum \4K \1: 3+3\ \ \ ,      3- 3\ \ ,\   0
\+
\ \ \ \ \ \ \ \ \ _\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1/2\ \ \ \     \ 1/2
\+\1Spectrum \4K \1: -3\ \ \ ,       3\ \ \ ,     0
\+\8--------------------------------------
\1\ \ \ \ \ \ \ \ \ \ _\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1/2\ \ \ \ \ \ 1/2
\+\1Spectrum \4KK\1: -(3+27\ \ \ ),  27\ \ \ -3,  0
\+
\,
\-
\+\ \ \ The proof can be made simple:
\+
\ \ \ \ \ \ _\ \ \ \ \ \ \ \ \ _\,
\-\2\ 2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\+\4K\  \1+ \4KK \1= \4K\1(\4K \1+ \4K\1) = \4KK\ \1= \4K\1(n\4I \1-\4JJ\ \1) = n\4IK \1+ \40 \1= n\4K\1.
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ K
\1\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\+\1    The unit vector-column \ \4J \1or the unit vector \ row \4J\1ö are zero 
\+
\,
\-
\+eigenvectors of the Laplace-Kirchhoff \ matrices of all graphs and 
\+
\,
\-
\+the Laplace-Kirchhoff \ matrices of all subgraphs \ of the complete 
\+
\,
\-
\+graph Kö are not orthonormal eigenvectors to its Laplace-Kirchhoff 
\+\2\ \ \ \ \ \ \ n
\1\,
\-
\+matrix.
\+
\,
\-
\+   The consequence \ of the properties of \ eigenvalues products is 
\+
\,
\-
\+that the \ spectra of selfcomlementary \ Laplace-Kirchhoff matrices 
\+
\,
\-
\+must \ be \ \ symmetrical, \ except \ their \ zero \ \ eigenvalue: 
\+
\,
\-
\+n/2 +/-(\7l \1-n/2).
\+\2\ \ \ \ \ \ \ \ \ j
\1\,
\-
\+\4
\+\1
\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\+
\+
\4\,
\-\1
\+
\+\2
\1\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+
\8\,
\-\1
\+
\+\2
\1\,
\-
\+
\+
\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+\6
\+\1
\,
\-
\+\6
\+\1
\,
\-
\+
\+
\,
\-
\+
\+
\,
\-\2
\+\1
\+
\,
\-
\+
\+
\,
\-\2
\+\1
\+
\,
\-
\+
\+
\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+
\,
\-
\+
\+\2
\1\,
\-
\+
\+\2
\1\,
\-
\+
\+\8
\1
\-
\+
\+\2
\1\,
\-\2
\+\1
\+
\,
\-\2
\+\1
\+
\,
\-\2
\+\1
\+
\,
\-\8
\+\1
\+
\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\+
\+
\,
\-
\=