It is well known that the Laplace-Kirchhoff matrices S^TS of oriented graphs have (n-1) nonzero eigenvalues. Both quadratic forms S^TS and SS^T have the same eigenvalues. Therefore, matrices SS^T of trees are nonsingular, and have true inverses, which I defined as walk matrices W^TW. Moreover, matrices S^TS have generalized inverses E, defined as the sum of partial inverses of differences

or the decomposition into the Ulam subgraphs (the set of n subgraphs, each with one eliminated vertex and its adjacent arcs). It follows that the spectra of the Laplace-Kirchhoff matrix of a graph G and its complementary graph G (G + G = K) are complementary, too.

The purpose of this note is to find relations for the analogue of the Laplace-Kirchhoff matrix of unoriented graphs G^TG, and the other quadratic form SS^T. Recall that the elements s_ij = -1, if the arc starts in the vertex j, s_ij =1, if the arc ends in the vertex j, s_ij = 0 otherwise, and g_ij = 1, if the edge starts or ends in the vertex j, s_ij = 0 otherwise. Moreover

where = V is the diagonal matrix of the vertex degrees and A is the adjacency matrix, a_ij = 1, if the bond starts or ends in the vertex j, and

where I_m is the unit diagonal matrix and A_L is the adjacency matrix of the corresponding line graph.

The incidence matrix of the complete unoriented graph G^T can be written in the block form similarly as the incidence matrix of the complete oriented graph S^T in the transposed form as

where I is the unit diagonal matrix, J^T is the unit vector- row.

Its quadratic forms have forms

G^TG =

GG^T =

Evaluating directly, we find that the eigenvalues are

(2n -2), (n -2)^n-1.

Since S^TS + G^TG = 2(n -1)I_a, the sum of eigenvalues of S and G are additive, too. S has (n - 1) eigenvalues equal n and one zero eigenvalue. Thus

The question is, if such a complementarity is true for all regular graphs. The eigenvalues must be

Since it is possible to choose the orientation of arcs at bipartite graphs in such a way, that arcs meet always head-head or tail-tail, all signs in the quadratic form SS^T can be positive, both SS^T and

Thus the matrices bipartite graphs have the same eigenvalues. This is obvious, if the spectrum is symmetrical.

In the quadratic form SS^T a bundle of (n-1) arcs appears to which only one nonzero eigenvalue belongs. They form a star S which eigenvalues are n, 1(n-1). They add to the previous eigenvalues as

There exist the additivity of the eigenvalues the Laplace-Kirchhoff matrices of a graph G and its complementary graph (K-G), where K is the complete graph.

The additivity of the eigenvalues of graphs which can be expressed as the sum of the star graph and the subgraph has the consequence that leads to the eigenvalues of such a graph are the sum of eigenvalues of both subgraphs.

For example:

The complete graph K(4) can be decomposed as: K(4) = S(4) + C(3).

The eigenvalues:

Graph G = K(4) - S(3) has the eigenvalues: 4, 3, 1, 0. This is the sum:

The eigenvalues: 4, 3, 1, 0 are formed in its turn by the sum of two linear chains L(3) with the eigenvalues: 3, 1, 0, 0:

The sum of the eigenvalues of the complete graph is n(n – 1). It has n(n – 1)/2 arcs, therefore, it can be decomposed into n(n – 1) complete graphs K(2) which eigenvalues are 2.

The decomposition of the complete graph into subgraphs is a necessary condition for the decomposition of the eigenvalues, but it is not a sufficient condition.

The arcs of complete graphs lies in n dimensional space on the plane orthogonal to the unit diagonal matrix, it is on (n-1) dimensional body. Therefore there are only limited number of nonzero eigenvalues. Adding a new vertex increases the dimensionality only for one dimension. This new dimension is correlated to one from the previous vertices. Other arcs within the vertex set must be expressed as linear combinations of the previous set of orthogonal vectors.