\1cw  Verze 2.10
\pTM 4
\pBM 0
\pPL 124
\pLM 1
\pRM 65
\HD
\+

\=
\HE
\+

\=
\FD
\+

\=
\FE
\+

\=
\+
\+
\"1 4   G R A P H S   A N D   B L O C K S\,
\-\1
\+
\+
\414.1 Some historical notes\,
\-\1
\+
\+
     Graphs were invented, similarly as many others ideas in this 
\-\/
\+
\+
book, by \ Euler. Before World War \ II, all graph theory \ could be 
\-
\+
\+
cumulated \ in just \ one book \ written by \ Koenig. Today there are 
\-
\+
\+
specialized journals \ dealing with their theory \ and its applica-\A
\-\/
\+
\+
tions.\,
\-
\+
\+
     Euler formulated the basic idea \ of the graph theory solving 
\-\/
\+
\+
the puzzle of 7 bridges in Koenigsberg. Is it possible 
\-
\+
\+
to make a walk over all \ bridges, crossing each bridge just once? 
\-
\+
\+
Euler has \ shown that the \ demanded path exists \ only, if in \ all 
\-\/
\+
\+
crossing points of roads even number of roads meet.\,
\-
\+
\+
     One \ wonders, \ if \ such \ configuration \ of \ bridges \ were in 
\-\/
\+
\+
Athens, were \ its philosophers on their \ promenades interested in 
\-
\+
\+
such a trivial problem and could they solve it similarly as Euler 
\-
\+
\+
did, for all similar configurations of ways? Or, was the 7 bridge 
\-
\+
\+
puzzle not determined for children and needed some maturity to be 
\-
\+
\+
interested in relations which can not be seen but only imagined?\,
\-
\+
\+
     All problems in this book \ were solved till now by multipli-\A
\-\/
\+
\+
cations of different possibilities and summing them. Essentially, 
\-
\+
\+
old Greeks were \ able to solve them, but \ they were interested in 
\-
\+
\+
geometrical problems, where we \ see everything. A possible answer 
\-
\+
\+
on \ such questions \ is that \ multidimensional spaces \ are too ab-\A
\-\/
\+
\+
stract to start with. \,
\-
\+
\+
     An advantage of \ the graph theory is that \ graphs join abst-\A
\-\/
\+
\+
ract notions with concreteness. They can be \ drawn on a paper and 
\-\/
\+
\+
inspected consecutively as a system of points and lines.\,
\-
\+
\+
     Graphs \ are considered \ usually as \ binary relations \ of two 
\-\/
\+
\+
sets, vertices and \ edges or arcs. It is possible 
\-
\+
\+
to create \ a theory of anything and \ there appeared very interes-\A
\-
\+
\+
ting problems suitable to be \ studied by young adepts of academic 
\-
\+
\+
degrees as \ e.g. the game \ theory. But some \ graph problems found 
\-
\+
\+
very soon practical applications \ or analogies in physical scien-\A
\-
\+
\+
ces. Especially chemistry gave many impetuses for utilizations of 
\-
\+
\+
graph theory because \ graphs were found to be \ adequate models of 
\-
\+
\+
connectivities of atoms in molecules. It seems to be unsubstanti-\A
\-
\+
\+
al to study walks between vertices of graphs but when these walks 
\-
\+
\+
are connected directly with measurable complicated \ physical pro-\A
\-\/
\+
\+
perties \ of chemical \ compounds, as \ the boiling \ point is, then 
\-
\+
\+
such theoretical \ studies become pragmatical \ and give us \ a deep 
\-\/
\+
\+
insight how our world is constructed.\,
\-
\+
\+
     Graphs were connected with many different matrices: Inciden-\A
\-\/
\+
\+
ce \ matrices \4S \1and \ \4G\1, \ adjacency \ matrices \4A\1, \ distance matrices 
\-
\+
\+
\4D \1and other kinds of matrices. \ These matrices were used for cal-\A
\-
\+
\+
culations of eigenvalues and \ eigenvectors, but these values were 
\-
\+
\+
not connected into an \ unified system of matrices. Mathematicians 
\-
\+
\+
were satisfied with the fact that all graphs can be squeezed into 
\-
\+
\+
3 dimensional space and mapped \ onto 2 dimensional paper surface. 
\-
\+
\+
They ignored \ the problem of dimensionality \ of graphs. Different 
\-
\+
\+
authors considered \ them to be dimensionless \ objects, one dimen-\A
\-
\+
\+
sional objects, \ 2 dimensional objects. According \ to the Occam's 
\-
\+
\+
razor, it should not be introduced more factors than necessary to 
\-
\+
\+
explain observed \ facts. But treating \ graphs as multidimensional 
\-
\+
\+
vectors with special configurations unifies the theory, graphs a-\A
\-
\+
\+
re just \ a special class of \ vectors, sums or \ differences of two 
\-
\+
\+
vector strings. These vectors belong \ into the vector space. Pro-\A
\-
\+
\+
perties of sums or differences of \ two vector strings can be stu-\A
\-
\+
\+
died conveniently \ if they are imagined \ as graphs, compared with 
\-
\+
\+
existing objects, or at least with small samples of larger struc-\A
\-\/
\+
\+
tures.\,
\-
\+
\+
\414.2 Some basic notions of the graph theory\,
\-\1
\+
\+
     The graph theory has two basic notions. The first one is the 
\-\/
\+
\+
vertex which is usually depicted \ as a point, but a vertex can be 
\-
\+
\+
identified \ with anything, \ even with \ a surface comprising \ many 
\-
\+
\+
vertices, if \ the graph theory is \ applied on practical problems. 
\-
\+
\+
The second notion is the line representing a relation between two 
\-
\+
\+
vertices. \ Lines \ can \ be \ oriented, \ as \ vectors are, going from 
\-
\+
\+
a vertex into another, then they are called arcs, and unoriented, 
\-
\+
\+
just connecting 2 vertices without \ any preference. Then they are 
\-\/
\+
\+
called edges.\,
\-
\+
\+
     An \ arc \ is \ represented \ by \ a row of the \ incidence matrix 
\-\2\/
\+\1
\+
\4S \1formed by \ the difference of two \ unit vectors (\4e \1- \4e \1). Accor-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i\ \ \ j
\+\1
\+
ding our convention, both vectors \ act simultaneously and the be-\A
\-
\+
\+
ginning of \ the resulting vector can \ be placed on the \ vertex j. 
\-
\+
\+
The arc \ vector goes directly \ from the vertex \ j into the vertex 
\-
\+
\+
i. An edge is depicted as a simple line connecting two 
\-
\+
\+
vertices. Actually the sum of \ two unit vectors is orthogonal to 
\-
\+
\+
it. It is more instructive to \ draw an unoriented graph with con-\A
\-
\+
\+
necting lines. Nevertheless, from \ formal reasons we can consider 
\-
\+
\+
an unoriented \ graph as a string vectors \ where each \ \ member \ is 
\-\/
\+
\+
orthogonal to \ its oriented matching \ element. When the \ oriented 
\-
\+
\+
graph is \ a vector, then the \ unoriented graph must \ be a vector, 
\-\/
\+
\+
too.\,
\-
\+
\+
     A special line \ in graphs is a loop \ which connects a vertex 
\-\/
\+
\+
with \ itself. There \ appear formal \ difficulties, how \ to connect 
\-
\+
\+
oriented loops with matrices, because corresponding rows are zero \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \           \/
\+\1
\+
(\4e  \1- \4e \1) = \40\1. These difficulties are resulting from higher order 
\-\2\ \ j\ \ \ \ j\/
\+\1
\+
symmetries, \ an unoriented \ loop has \ a double intensity \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \/
\+\1
\+
     (\4e \1+ \4e \1) = 2\4e \1.\,
\-\2\ \ \ \ \ \ \ j\ \  j\ \ \    j
\+\1
\+
We will see later, how this fact is exploited.\,
\-\2
\+\1
\+
     Relations between things can be \ things, too. For example in 
\-\/
\+
\+
chemistry, if we identify atoms in a molecule with vertices, then 
\-
\+
\+
bonds between \ atoms, determining the structure \ of the molecule, 
\-
\+
\+
are bonding electrons. Sometimes each line is formed by an elec-\A
\-\/
\+
\+
tron pair and each unit vector represents an electron.\,
\-
\+
\+
     We can construct a line \ graph, canging lines into vertices, 
\-\2\/
\+\1
\+
and introducing new incidencies defined now by common vertices of 
\-\2
\+\1
\+\2
\1two original lines. \ If the parent graph had \ m edges, the sum of 
\-\2\/
\+\1
\+\2
\1its vertex degrees \ v  was 2m. Its line graph \ has m vertices and 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j\/
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2
\1the sum of its vertex degrees v  is \ \7S\1(v  - v ).\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i\ \      \ j\ \ \ \ j
\+\1
\+
     Each line in \ a graph can be splitted into \ two by inserting 
\-\/
\+
\+
into it a new vertex. The \ generated sbdivision graph has (n + m) 
\-
\+
\+
vertices and 2m lines. From \ calculations emerge even graphs with 
\-\/
\+
\+
imaginery lines.\,
\-
\+
\+
     A pair of \ vertices can be connected \ by more lines simulta-\A
\-\/
\+
\+
neously. \ Then we \ speak about \ multigraphs. A sophistication is, 
\-
\+
\+
when values \ of lines need not \ to weighted by whole \ numbers but 
\-\2
\+\1
\+
can be any weights w  . \,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+
     It is \ also possible to \ restrict graphs by \ joining sets of 
\-\/
\+
\+
vertices into new vertices and to leave only lines connecting new 
\-\/
\+
\+
vertices. This operation simplifies a graph.\,
\-
\+
\+
     Both elements of graphs can \ be indexed (labelled) and unla-\A
\-\/
\+
\+
belled. Usually \ only vertex labelled graphs \ are considered. La-\A
\-
\+
\+
belled graphs \ are partially indexed \ graphs. Only some \ of their 
\-
\+
\+
vertices \ are indexed, \ or several \ vertices have \ equal indices. 
\-\/
\+
\+
When only one vertex is labelled, we speak about the root. \,
\-
\+
\+
     A special \ labelling of \ graps is \ their coloring. \ We color 
\-\/
\+
\+
vertices in such a way that no incident vertices had the same co-\A
\-
\+
\+
lour. The number of colours indicates parts of the graph where a-\A
\-
\+
\+
ll vertices \ are disconnected. No \ line exists between \ them. The 
\-
\+
\+
least number of colours which are necessary to colour a connected 
\-
\+
\+
graph is 2. \ Then we speak about bipartite \ graphs. For colouring 
\-
\+
\+
of planar graphs, which lines do \ not intersect, we need four co-\A
\-\/
\+
\+
lours.\,
\-
\+
\+
     Bipartite graphs have an important property, their incidence 
\-\/
\+
\+
matrices (see below) \ can be separated into two \ blocks and their 
\-\/
\+
\+
quadratic forms split into two separate blocks.\,
\-
\+
\+
     Graphs are connected, \ if there exists at least \ one path or 
\-\/
\+
\+
walk between all pairs of vertices. It is uninterrupted string of 
\-
\+
\+
lines \ connecting given \ pair of \ vertices. Mutually \ unconnected 
\-
\+
\+
parts of a graphs are known as its components. At least (n-1) li-\A
\-
\+
\+
nes are needed \ to connect all n vertices of \ a graph and n lines \,
\-
\+
\+
to form a cycle. \ Connected graphs with (n-1) lines \ are known as 
\-
\+
\+
trees and they are acyclic.\,
\-
\+
\+
     We can find the center \ of a graph, determined as its inner-\A
\-\/
\+
\+
most vertex, \ or the diameter  \ of a graph, as if \ they were some 
\-
\+
\+
solid objects. But there appears some difficulties. When we defi-\A
\-
\+
\+
ne the center of a graph as the vertex which has the same distan-\A
\-
\+
\+
ce \ from the \ most distant \ vertices, then \ in linear chains with 
\-
\+
\+
even number of vertices, e.g. x-x-x-x-x-x, we have two candidates 
\-
\+
\+
on the \ nomination. It is better \ to speak about the \ centroid or 
\-\/
\+
\+
the central edge. Some graphs have no center at all.\,
\-
\+
\+
     To introduce \ all notions of the \ graph theory consecutively 
\-\/
\+
\+
in a short survey is perplexing. But it is necessary.\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  
\+
\+
     Linear chains \ L  are \ a special class \ of trees \ which all 
\-\2\ \ \ \ \             \ \ \ \ n\/
\+\1
\+
vertices \ except \ 2 have \ the \ degree \ v  \ = 2. The vertex degree 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+
counts lines incident to the \ vertex. Linear chains have the lon-\A
\-\2
\+\1
\+
gest distance \ between their extremal \ vertices and the \ greatest 
\-\2
\+\1
\+
diameters from \ all graphs. Another extremal \ trees are stars S \2.  
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \  n
\+\1
\+
(n-1) of their \ vertices are connected to the \ central vertex di-\A
\-
\+
\+
rectly. The \ diameter of stars \ is always 2. We already mentioned 
\-
\+
\+
decisive trees at logical functions. This are trees with one ver-\A
\-
\+
\+
tex of the \ degree 2 and all other vertices \ with degrees 3 or 1. 
\-
\+
\+
If the vertex \ of the degree 2 is chosen as \ the root 
\-
\+
\+
then on a walk it is necessary \ to make a binary decision on each 
\-\/
\+
\+
step which side \ to go. The vertices with degrees \ 1 are known as 
\-
\+
\+
leaves. They are connected to branches ot to the \ stem ff a tree. 
\-
\+
\+
We already know the decision trees as strings in unit cubes. In a 
\-
\+
\+
tree, they are joined into \ bifurcating branches. The indexing of 
\-
\+
\+
leaves is known as the binary coding. \,
\-
\+
\+
     The complete graph K  has n(n-1)/2 lines which connect mutu-\A
\-\2\ \ \ \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n\/
\+\1
\+
ally all \ its vertices. Its diameter \ is 1 and it has \ no center. 
\-
\+
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -
     The complement G of a graph G is defined as the set of lines 
\-\/
\+
\+
of the graph g missing in the complete graph G on the same verti-\A
\-
\+
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -
ces, or as the sum K = \ G + G. It follows, that the complementary 
\-
\+
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =
graph \ of the \ complementary graph \ G is the \ initial graph G and 
\-\/
\+
\+
that the complementary graph \ of the complete graph \ is the empty 
\-\/
\+
\+
graph with no lines.\,
\-
\+
\+
\414.3 Oriented and unoriented graphs as vector strings\,
\-\1
\+
\+
     If we \ draw the difference of \ two vectors (\4e  \1+ \4e \1), 
\-\2\ \ \ \ \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j\ \ \ \ i\/
\+\1
\+
 it corresponds to \ the accepted convention for drawing 
\-
\+
\+
arcs \ of oriented \ graphs. The \ incidence matrix \ \4S \1of a graph is 
\-\2\/
\+\1
\+
just the difference of two naive matrices  \4S \1= \4N  \1- \4N \1, as it was 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ b\ \ \ \ a
\+\1
\+
shown in Chapter 4.3. It \ is an operator which transfers a vector 
\-
\+
\+
string into another. A vector string \ is a continuous path in the 
\-
\+
\+
vector space, the operator transferring one vector string into a-\A
\-
\+
\+
nother is \ also continuous. It seems \ to be the area \ between two 
\-
\+
\+
strings, vector lines, and we \ could imagine it as a surface. But 
\-
\+
\+
when we \ make consecutive differences \ at all pairs \ of unit vec-\A
\-
\+
\+
tors, we get a linear vector \ again. A loop transfers a unit vec-\A
\-
\+
\+
tor into itself. All these vectors lie in the plane orthogonal to 
\-\2\/
\+\1
\+
the unit diagonal vector \4I \1.\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\+\1
\+
     The other \ possibility, how to interpret \ oriented graphs is 
\-
\+
\+
the \ difference \ inside \ a string \ itself. \ For example, a string 
\-
\+
\+
abcda contains transitions a into b, b into c, c into d and d in-\A
\-\/
\+
\+
to a. The difference is thus:\,
\-
\+
\+
     a -> b\,
\-
\+
\+
     b -> c\,
\-
\+
\+
     c -> d\,
\-
\+
\+
     d -> a.\,
\-
\+
\+
     Similarly we could compare differences at higher distances. \,
\-
\+
\+
     Unoriented graphs are vectors orthogonal to surfaces of cor-\A
\-\2\/
\+\1
\+
responding \ oriented graphs. \ The complete \ graphs K  are \ vector 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\+\1
\+
strings going from \ the coordinate center to the \ farthest end of 
\-
\+
\+
the unit cube which sides are diagonals of the n dimensional unit 
\-
\+
\+
cube. \ Another graphs correspond to 
\-
\+
\+
intermediate vertices of \ this cube. In the next \ chapter we will 
\-
\+
\+
see, that \ on some places more \ distinguishable graphs are placed 
\-
\+
\+
together. Edges and arcs form a space which symmetry is more com-\A
\-\/
\+
\+
plicated that the symmetry of naive matrices.\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1     The \ recursive definition \ of \ the \ incidence matrix \ \4S  \ \1of 
\-\/
\+
\+
the complete oriented graph K  is\,
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \          n 
\+\8\ \ \ \ \ \ \ \ \ p
\+\2\ \ \ \ \ \ T\ \ \8p
\4     S\   \8p \1-\4I\,
\-\2\ \ \ \ \ \ n-1
\+\8\ \ \ \ -----k---
\+\ \ \ \ \ \ \ \ \ p  \2T
\4     0   \8p \4J\,
\-\1
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1     where \ \40 \1and \ \4Jö \1are \ row vectors. \ Similarly, the canonical 
\-
\+
\+
form of the complete oriented graph K  is\,
\-
\+
\+\2\ \ \ \ \ \ T\ \ \8p
\4\ \ \ \  G\   \8p \1-\4I\,
\-\2\ \ \ \ \ \ n-1
\+\8\ \ \ \ -----k---
\+\ \ \ \ \ \ \ \ \ p  \2T
\4\ \ \ \  0   \8p \4J\,
\-\1
\+
\+
     Other \ graphs \ matrices \ are \ obtained \ by \ multiplying with 
\-
\+
\+
diagonal matrices \7D \1which elements are \ 1, if the arc or edge are 
\-
\+
\+
present \ in the \ given graph, \ or w\7ö \ \1if lines \ are weighted, \ as 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i
\+\1
\+
multiple arcs, \ and 0 for empty \ columns or rows, if \ the line is 
\-
\+
\+
missing.\,
\-
\+
\+
\414.4 Quadratic forms of the incidence matrices.\,
\-\1
\+
\+
     A simple \ exercise in \ matrix multiplication \ shows that the \,
\-\/
\+
\+
quadratic forms of the incidence \ matrices of unoriented and ori-\A
\-
\+
\+
ented graphs have the form\,
\-
\+
\+\2\ \ T\ \ \ \ T\ \ \ \ \ \ \ \  \ \ \ \ \ \ \ T\ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ T\ \ \  \ \ T
\1(\4N\  \1+ \4N\ \1) (\4N  \1+ \4N \1) = (\4N\  N  \1+ \4N\ N \1) + (\4N\ N  \1+ \4N\ N \1)     (14.1)\,
\-\2\ \ a\ \ \ \ b\ \ \ \ a\  \ \ b\ \ \ \ \ \ a\ \ a\ \ \ \ b\ b\ \ \ \ \ \ a\ b\ \  \ b\ a
\+\1
\+\2\ \ T\ \ \ \ T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ T\ \ \ \ \ \ T
\1(\4N\  \1- \4N\ \1) (\4N  \1- \4N \1) = (\4N\  N  \1+ \4N\ N \1) - (\4N\ N  \1+ \4N\ N \1)     (14.2)\,
\-\2\ \ b\ \ \ \ a\ \ \ \ b\ \ \ \ a\ \ \ \ \ \ a\ \ a\ \ \ \ b\ b\ \ \ \ \ \ a\ b\ \ \ \ b\ a
\+\1
\+
     The quadratical forms are composed \ from two parts: The dia-\A
\-\/
\+
\+
gonal matrix \ \4V \1formed by the sum \ of quadratic forms of \ the two 
\-\2
\+\1
\+
naive matrices \4N  \ \1and \4N \1. The diagonal elements \ v  are known as 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a\ \ \ \ \ \ \ b\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+
degrees of the corresponding \ vertices. Both quadratic increments 
\-
\+
\+
can be eventually separated into \ parts corresponding to the ori-\A
\-
\+
\+
ginal strings, into in-degrees counting \ arcs going into the ver-\A
\-
\+
\+
tex j and \ into out-degrees, counting arcs \ going from the vertex 
\-
\+
\+
j. This separation is assymmetric, in quadratic forms both degrees 
\-\/
\+
\+
are counted twice on both sides of the main diagonal.\,
\-
\+
\+\2\ \ \ \ \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ T
\1     The sum of scalar products (\4N N  \1+\4N N \1) forms the off-diago-\A
\-\2\ \ \ \ \ \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a b   b a\/
\+\1
\+
nal elements. It \ is known as the adjacency \ matrix \4A \1of a graph. 
\-\2
\+\1
\+
Its elements \ a   show which vertices are \ adjacent and in multi-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+
graphs how many lines connect both \ vertices. For it it is neces-\A
\-
\+
\+
sary to have \ in the incidence matrix identical \ unit rows or one 
\-\/
\+
\+
row with square root of the multiplicity of the line.\,
\-
\+
\+
     The diagonal matrix \4V \1and the \ adjacency matrix \4A \1can be ob-\A
\-\/
\+
\+
tained as \ the sum or the \ difference, respectively, of quadratic 
\-\/
\+
\+
forms of unoriented and oriented graph \,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \    T\ \ \ \ \ T
\4\^\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ V \1= 1/2(\4G\ G \1+ \4S\ S\1)    (14.3)\^\,
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ T
\4\^\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A \1= 1/2(\4G\ G \1- \4S\ S\1)    (14.4)\^\,
\-
\+
\+
 The Hilbert length of \ the diagonal vector \4V \1is 2m, 
\-\/
\+
\+
twice the number of rows in the incidence matrices. The adjacency 
\-
\+
\+\2
\1matrix vector \4A \1has \ the same length and it \ is opposite oriented 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ T
\1in both quadratic \ forms, thus \4S S \1and \4G G \ \1end on different pla-\A
\-\2
\+\1
\+\2
\1nes. If the graph is \ regular, v  = const, then the diagonal mat-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j
\+\1
\+\2
\1rix \4V \1has is  collinear with \ the unit diagonal vector \4I  \1and the 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n\/
\+\1
\+\2
\1adjacency matrix \4A \1has the same direction, too.\,
\-
\+
\+
     The diagonal elements of \ the adjacency matrix \4A \1are zeroes. 
\-\/
\+
\+
It is therefore possible to use \ them for noting loops of a graph 
\-
\+
\+
with loops. We noted, that \ at oriented graphs rows corresponding 
\-
\+
\+
loops are \ zeroes. But at unoriented \ graphs, we have as \ the row 
\-
\+
\+
corresponding \ to a loop \ value 2, \ which gives \ as the quadratic 
\-
\+
\+
4 and using formulas \ 14.3 and 14.4, we obtain \ as the loop value 
\-\/
\+
\+
2, it appears automatically.\,
\-
\+
\+\2\ \ \ \ \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ T
\1     The other quadratic \ forms \4G G \1and \4S S \1have \ on the diagonal 
\-\/
\+
\+\2
\12, the number of unit vectors in the rows of the incidence matri-\A
\-
\+
\+\2
\1ces. This is in accord with the fact that each line is registered 
\-
\+
\+\2
\1twice in matrix \4V \1as well asi \ in matrix \4A\1. Off diagonal elements 
\-
\+
\+\2
\1are +/-1, if \ two lines are adjacent having \ a common vertex. The 
\-
\+
\+\2
\1off-diagonal elements \ form in such a way \ the adjacency matrices 
\-
\+
\+\2
\1of line graphs. But at \ oriented graphs this explanation is comp-\A
\-
\+
\+\2
\1licated by signs \ which signs can be positive \ and negative. This 
\-
\+
\+\2
\1sign pattern depends on mutual \ orientation of arcs. It is unpre-\A
\-\/
\+
\+\2
\1dictable and must be determined separately.\,
\-
\+
\+
     The trees form a base of the graph space. \ They are smallest 
\-\/
\+
\+
connected graphs without loose vertices. They are bipartite, the-\A
\-
\+
\+
ir vertices can be divided into 2 groups in such a way that there 
\-
\+
\+
are no lines between vertices in each group. This allows to choo-\A
\-
\+
\+
se orientation \ of arcs in \ oriented trees so, \ that all arcs \ go 
\-
\+
\+
from one group of vertices into \ another, or they meet in it. The 
\-
\+
\+
consequence is \ that all off-diagonal \ elements of the \ adjacency 
\-
\+
\+
matrix of the line graph of \ a tree can be either positive or ne-\A
\-\/
\+
\+
gative. There need not be \ any difference between quadratic forms 
\-
\+
\+\2\ T\ \ \ \ \ \ \ T
\4G\ G \1and \4S\ S\1. The consequences will be exploited later.\,
\-
\+
\+
\414.5 Petrie matrices\,
\-\1
\+
\+
     Arcs of \ oriented graphs were defined \ as differences of two 
\-\2\/
\+\1
\+
unit vectors (\4e \1- \ \4e \1). There is another possibility, \ how to map 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j\ \ \ \ i
\+\1
\+
arcs and edges on matrices with unit elements. There exist Petrie 
\-
\+
\+
matrices, \ which are \ complementary with \ the incidence matrices. 
\-
\+
\+
They contain in their rows strings of unit symbols consecutively, 
\-
\+
\+
without an \ interruption, in each \ row one string \ instead of one 
\-
\+
\+
difference. \ The string \ of unit \ symbols in \ a Petrie matrix \ \4P\1e 
\-
\+
\+
(there is not \ inough of simple symbols for \ all different matri-\A
\-
\+
\+
ces) going from i till (p-1) \ corresponds to the arc between ver-\A
\-
\+
\+
tices i and p. \ The arc 1-2 is represented \ in a Petrie matrix by 
\-\/
\+
\+
just one unit, the arc 1-6 needs 5 units.\,
\-
\+
\+
     Petrie matrices have two important properties:\,
\-
\+
\+
1. A Petrie matrix of a graph G multiplied with the incidence ma-\A
\-\/
\+
\+
tix \4S \1of the linear chain L gives the incidence matrix of the gi-\A
\-
\+
\+
ven graph: \4S\1(G) = \4P\1e(G)\4S\1(L). From \ the consecutive units in a row 
\-
\+
\+
of the Petrie matrix only the \ first and the last ones are mapped 
\-
\+
\+
in the product, all intermediate pairs are anihilated by consecu-\A
\-
\+
\+
tive pairs of unit symbols with opposite signs from the incidence 
\-
\+
\+
matrix of the linear chain, which vertices are indexed consecuti-\A
\-\/
\+
\+
vely: 1-2-3-..-n.\ E. g.\,
\-
\+
\+\8\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
           p \1-1  1  0  0              \8p \1-1  1  0  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
           p  \10 -1  1  0              \8p  \10 -1  0  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
           p  \10  0 -1  1              \8p  \10  0 -1  1\,
\-
\+\8\ \ \ --------k-------------\ \ \ \ ---------k-------------
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1\ \ \  1  0  0\8p \1-1  1  0  0\ \ \ \   1  0  0\ \8p\ \1-1  1  0  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1\ \ \  0  1  0\8p  \10 -1  1  0\ \ \ \ \ \ 1  1  0\ \8p\ \1-1  0  1  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1\ \ \  0  0  1\8p  \10  0 -1  1\ \ \ \ \ \ 1  1  1\ \8p\ \1-1  0  0  1\,
\-\8\ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\1
\+
2. \ Only Petrie \ matrices of \ trees are \ nonsingular. Trees \ have 
\-
\+
\+
(n-1) \ arcs \ and \ therefore \ their \ Petrie \ matrices \ are \ square 
\-
\+
\+
matrices. \ Because \ trees \ are \ connected \ graphs, \ their \ Petrie 
\-
\+
\+
matrices \ are \ without \ empty \ columns. \ The \ importance \ of this 
\-
\+
\+
\+\4
\1property will be cleared in the Chapter 16.\,
\-
\+
\+
\414.6  Matrices coding trees\,
\-\1
\+
\+
     Petrie matrices defined trees in space of arcs. In the space \,
\-
\+
\+
of \ vertices, a \ line is \ determined by \ its vertex \ ends. It \ is \,
\-
\+
\+
possible \ to choose \ one vertex \ as the \ root and \ find all paths \,
\-
\+
\+
going from this vertex into all other vertices.\,
\-
\+
\+\4
\1     Since to each tree one Petrie matrix corresponds, there must 
\-
\+
\+\4
\1be \ the same \ number of \ \ code matrices \4C\ \1as Petrie matrices. The 
\-
\+
\+\4
\1relation between both matrices can be defined as  \,
\-
\+
\+\8\ \ \ \ \ \ \ \ \ \ \ p
\4     C \1= \4J \8p \40\,
\-\1
\+\8\ \ \ \ \ \ \ \ \ \ \ j---
\+\ \ \ \ \ \ \ \ \ \ \ p
           p \4Pe\,
\-\1
\+
\+
     The root vertex is expressed by the unit column \4J\1, each path 
\-\/
\+
\+
is defined by all vertices it starts, goes through, or ends, res-\A
\-\/
\+
\+
pectively. The \ elements of code matrices \ have inverse form than 
\-
\+
\+
the \ Petrie matrices, \ since they \ are related \ to the \ incidence 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \    \ \ \ \ \ \ \        -1
\1matrices as rooted \ inverses (\4Sö\1+ö\4eöö\1)öö  = \4C\1. \ For example using 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 11
\+\1
\+\2
\1the principle of inclusion and exclusion we get\,
\-\2
\+\1
\+\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                 p  \11  0  0  0\ \ \ \ \ \ \ \             \8p  \11  0  0  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                 p  \11  1  0  0\ \ \ \ \ \ \ \             \8p  \11  1  0  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                 p  \11  1  1  0\ \ \ \ \ \ \              \8p  \11  0  1  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
                 p  \11  1  1  1\ \ \ \ \ \ \ \             \8p  \11  0  0  1\,
\-
\+\8\ \ \ \ -------------k---------------\ \ \ \ \ ------------k-------------
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1     1  0  0  0\ \ \8p\ \ \11  0  0  0\ \ \ \ \ \ \ \ 1  0  0  0\ \ \8p\ \ \11  0  0  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1    -1  1  0  0  \8p  \10  1  0  0\ \ \ \ \ \ \ -1  1  0  0  \8p  \10  1  0  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1     0 -1  1  0  \8p  \10  0  1  0\ \ \ \ \ \ \ -1  0  1  0  \8p  \10  0  1  0\,
\-\8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
\1     0  0 -1  1  \8p  \10  0  0  1\ \ \ \ \ \ \ -1  0  0  1  \8p  \10  0  0  1\,
\-
\+
\+
     The root element \4e   \1removed the singularity of the inciden-\A
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 11\/
\+\1
\+
ce matrices \4S\1. Similarly, it is possible to remove the singulari-\A
\-\/
\+
\+
ty of \ the incidence matrices of unoriented trees \4G\1. The code ma-\A
\-\/
\+
\+
trix must have negative elements.\,
\-
\+
\+
\414.7 Blocs schemes\,
\-\6\ \ \6t\6
\+\1
\+
     Graphs were introduced as the sums and differences of naive \,
\-
\+
\+
matrices. It is possible to study systematically matrices with an 
\-\/
\+
\+
arbitrary number of \ unit elements \ in a row. \ For practical rea-\A
\-\/
\+
\+
sons, this number must be constant, otherwise only special confi-\A
\-\/
\+
\+
gurations were accessibles for calculations. From matrices having 
\-\/
\+
\+
k unit elements in each row, only matrices \ having \ specific pro-\A
\-\/
\+
\+
perties corresponding to properties of complete graphs \ were stu-\A
\-\/
\+
\+
died. Such matrices are called block schemes \4B \1and give the quad-\A
\-\/
\+
\+
ratic forms\,
\-
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\4 \ \ \ \ \ \ \ \ \ \ \ \ BöB \1= (l -r)\4I \1+ r\4JJ        \1(14.5)\,
\-\2
\+\1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  
\+
\ \ \ \ \ where r is  the \ connectivity of the \ block. Sometimes there 
\-\/
\+\ \  
\+\2
\1is posed a stronger condition \ on block \ schemes, their \ matrices 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ T
\1should be \ square and both \ quadratic form equivalent \ \4B B \1= \4BB \1. 
\-\/
\+
\+
Without this condition the complete graph \ Kö is the block with k 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 3
\+\1
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T
\1= 2, \ r = \ 1. The \ other Kö \ are not \ blocs, since \ in their  \4GG\1ö 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n
\+\1
\+
appear zero elements.\,
\-\2
\+\1
\+
     The equation 14.5  shows that each unit vector \4e  \1must appe-\A
\-\2\ \ \ \ \ \ \   \ \ \ \ \ \ \ \ \ \ \    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j\/
\+\1
\+
ar in the scheme lötimes and each pair of elements rötimes. The \,
\-
\+
\+
numbers m, n, k, l ,r are limited by following conditions\,
\-
\+
\+
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ mk = nl            (14.6)\,
\-
\+
\+
\^\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l(k-1) = r(n-1)        (14.7)\^\,
\-
\+
\+
     14.6 counts \ the number of \ units in rows \ and columns, 14.7 
\-\/
\+
\+
the pairs in rows mk(k-1)/2 \ and in the quadratic form rn(n-1)/2. 
\-
\+
\+
Dividing both sides by l/2,  \ the result is simplified to the fi-\A
\-\/
\+
\+
nal form. The simplest \ example of \ a block scheme \ is the matrix 
\-\/
\+
\+
with m=n=4, k=l=3, r=2:\,
\-
\+
\+
1   1   1   0\,
\-
\+
\+
1   1   0   1\,
\-
\+
\+
1   0   1   1\,
\-
\+
\+
0   1   1   1\,
\-
\+
\+
     Block schemes \ with k=3 are known \ as Steiner's 3-tuples. It 
\-\/
\+
\+
is \ clear that \ construction of \ block schemes \ and finding their 
\-\/
\+
\+
numbers is not a simple task. If you are interested, the book:\,
\-
\+
\+
M. Hall Jr. Combinatorial \ Theory, Blaisdell Publ. Comp. Waltham, 
\-
\+
\+
1967 is recommended .\,
\-
\+
\+
\414.8 Hadamard matrices\,
\-\1
\+
\+
     Another \ special \ class \ of \ matrices \ are Hadamard matrices 
\-
\+
\+\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\ \ \ \ \ \ T
\4H \1with elements h   =+/-1 and quadratic \ forms \4H H \1= \4HH  \1= n\4I\1. It 
\-\2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ij
\+\1
\+\2
\1means that all rows and columns of the Hadamard matrices are ort-\A
\-\/
\+
\+\2
\1hogonal.  For example:\,
\-
\+
\+\8\ \ pp\ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
  pp \11   1\8pp         pp\11   1   1   1\8pp\,
\-\ \ pp\ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ pp\ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ pp\ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
  pp \11  -1\8pp         pp\11   1  -1  -1\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
                     pp\11  -1   1  -1\8pp\,
\-\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
\+\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ pp\ \ \ \ \ \ \ \ \ \ \ \ \ pp
                     pp\11  -1  -1   1\8pp\,
\-\1
\+
\+
     These matrices \ can be symmetrical as \ well as asymmetrical. 
\-\/
\+
\+
There exist some \ rules how it is possible \ to construct Hadamard 
\-
\+
\+
matrices \ of higher \ orders. Most \ easy it \ is for 2n dimensional 
\-\/
\+
\+
matrices, where blocks of lower matrices are used building stones\,
\-
\+
\+\8\ \ \ pp\ \ \ \ \ \ \ pp
   pp\4H   H\ \ \8pp\,
\-\ \ \ pp\ \2n   n\ \8pp
\+\ \ \ pp\ \ \ \ \ \ \ pp
\+\ \ \ pp\ \ \ \ \ \ \ pp
   pp\4H  \1-\4H\ \ \8pp\,
\-\2\ \ \ \ \ \ n   n
\=