A Note about Eigenvalues of Some Matrices

Milan Kunz, August 8th, 2000, improved March 15th, 2003.

Introduction

I have shown that transforming of powers of elements of graph matrices transforms distances into adjacencies [1]. The distance matrices can be topological or geometrical ones. The geometrical distance matrices have only limited number of nonzero eigenvalues [2]. I conjectured that their number is determined by the dimensionality of the space, the graph is embedded in [3,4]. Here are studied some matrices M with changing elements.

The quadratic matrices M with any number n of rows and columns having the elements m1j = mi1 = 1, mii = 0, mij = x otherwise,

0

a

a

a

a

0

b

b

a

b

0

b

a

b

b

0

 

where a = 1, are interpreted as:

the adjacency matrix A of the stars S(n), if b = 0,

the adjacency matrix A of the complete graphs K(n), if b = 1,

the topological distance matrix D of the stars S(n), if b = 2,

the geometrical distance matrix D of the stars S(n), if b = < 2, or

the quadratic geometrical distance matrix D of the stars S(n), if b = > 2.

When a = (n-1) and b = 1, the matrix is the direct product of a Cluj matrix of a star graph with its transpose. The elements of Cluj matrices are the number of vertices on the side i (j) of the edge ij [5].

I already published a paper about the changes of the eigenvalues of some matrices, if the adjacencies are changing into distances [1].

Investigating the eigenvalues of the matrices M, when a = 1, I found that there are always (n-2) values equal to -b (where b can be any real number). Dividing any matrix M by a, we get these eigenvalues as -b/a.

For example, the adjacency matrices of the stars S(n), where b = 0, have the characteristic polynomials P(n) = xn - (n-1)x(n-2), and two nonzero eigenvalues Ö (n-1). The adjacency matrices A and simultaneously the topological distance matrices D of the complete graphs K(n), where b = 1, have one eigenvalue equal to (n-1) and other (n-1) eigenvalues equal to -1.

Supposing that this is always true, two other eigenvalues than b/a, say x and y, are bounded by the condition that the sum of the eigenvalues is equal to the trace, thus

x + y - (n-2)b/a = 0 (1)

since the traces of these matrices are zero. The eigenvalues x and y can be found using the fact, that the sum of the squared eigenvalues must be equal to the sum of the squared values mij which is

2(n-1) + (n-2)(n-1)(b/a)2 (2).

In the case, when n=3, the characteristic polynomials and eigenvalues are for a = 1:

b

Polynomial

Eigenvalues

0

x3 - 2x

Ö 2, 0, -Ö 2

1

x3 - 3x + 2

2, -1, -1

2

x3 - 6x + 4

1 +Ö 3, 1-Ö 3, -2

3

x3 - 11x + 6

3/2+Ö 17/4, 3/2-Ö 17/4, -3

generally

x3 - (b2+2)x + 2b

 

Using the equations (1) and (2), we get for the first eigenvalue x the quadratic equation

x2 -bx -2 = 0,

which solution is

x = b/2 + Ö ([b/2]2 + 2),

and

y = b/2 - Ö ([b/2]2 + 2).

This conforms with the given results.

In the case, when n = 4 and a = 1, the eigenvalues are:

b

Eigenvalues

-2

2, 2, 0,6458, -4,6458

0

1,7321, 0, 0, -1,7321

1

3, -1, -1, -1

2

4,6458, -0,6458, -2, -2

2,666

5,8452, -0,5132, -2,6660, -2,6660

3

6,4641, -0,4641, -3, -3

6

12,2450, -0,2450, -6, -6

The equation for the first eigenvalue is

x2 -2bx - 3 = 0,

which solution is

x = b + Ö (b2 + 3),

and

y = b - Ö (b2 + 3).

This again conforms with the given results.

For n = 5, the equation is

x2 -3bx - 4 = 0,

which solution is

x = Ö ([9/4]b2 + 3) +/- [3/2]b,

and for any n, the equations are

x2 - (n -2) bx - (n - 1) = 0.

For any dimension, the eigenvalues are a, (-c)n-2, -b.

For example, the adjacency matrices of the stars S(n), where c = 0, have the characteristic polynomials P(n) = xn - (n-1)xn-2, and two nonzero eigenvalues Ö (n-1).

The adjacency matrices A and simultaneously the topological distance matrices D of the complete graphs K(n), where c = 1, have one eigenvalue equal to (n-1) and other (n-1) eigenvalues equal to -1.

Since the sum of eigenvalues is zero, their relation is

a = (n-2)c + b (1).

The solution can be found from the fact, that the trace of M2 equals to the sum of the squared eigenvalues of M and simultaneouslyto the sum of the squared elements of the matrix M:

Tr(M2) = (n-1)[(n-2)c2 + 2] = a2 + b2  + (n-2)c2

Simplifying, we find

(n-2)2c2 + 2(n-1) = a2 + b2

substituting a as (1), we get the quadratical equation

b2 + (n-2)bc - n +1 = 0

Its solution is

b = - (n-2)c/2 ± {[(n-2)c/2]2 + n - 1}-2

The tested examples conformed with these equations. The proof could be given by the developing the corresponding polynomials.

Literature

1. M. Kunz: Transformations of distances into adjacencies. J. Serb. Chem. Soc. 62 (3) 277-287 )1997).

2. M. Kunz: On topological and geometrical distance matrices, J. Math. Chem., 13 (1993) 145-151.

3. M. Kunz: Distance matrices yielding angles between arcs of the graphs, J. Chem. Inform. Comput. Sci., 34, (1994) 957-959.

4. M. Kunz, About eigenvalues of quadratic distance matrices of planar objects, lowest.htm