^{1}

^{*}

^{1}

The eigenvalues of the adjacency matrix of a graph are called the eigenvalues of the graph. Let the vector
*e _{j}* =(0,
… , 1, … , 0)

^{T}and the all -1 vector

*j*=(1, 1, …，1)

^{T}, the cosine of the (acute) angle formed by the vector

*e*and the eigensubspace is called an angle of the graph. The cosine of the (acute) angle formed by the vector

_{j}*j*and the eigensubspace is called a main angle of the graph. The angles and main angles are all important parameters on the graph, and they can be combined with the eigenvalues of the graph to determine the degree sequence of the graph, the number of triangles, quadrilaterals and pentagons on the graph, and the characteristic polynomials of the complement graph, but there is little study on the angles and main angles of the graph. In this paper, we determine the angles and main angles of the complete graph, the cube graph, the Petersen graph, the cycle and the complete bipartite graph.

This paper considers only finite undirected simple graphs. Let G be a graph with order n, its the adjacency matrix is defined as follows: A ( G ) = ( a i j ) n × n

a i j = ( 1 if i ~ j , 0 others .

where i~j denotes that the vertex i and the vertex j are adjacent. Obviously, A ( G ) is a real symmetric matrix in which all diagonal elements are 0 and all other elements are 0 or 1, its eigenvalues are all real numbers. The n eigenvalues of A ( G ) are said to be the eigenvalues of the graph G and to form the spectrum of this graph. Let μ 1 > μ 2 > ⋯ > μ m be the distinct eigenvalues of the graph G, and their multiplicities are n 1 , n 2 , ⋯ , n m , respectively, then n 1 + n 2 + ⋯ + n m = n . Throughout this paper, the spectrum of the graph G is often labeled as S p e c G = { μ 1 n 1 , μ 2 n 2 , ⋯ , μ m n m } . Let μ be an eigenvalue of the graph G, a subspace of the vector space C n in the complex field generated by all the vectors x that satisfy A ( G ) x = μ x is called the eigensubspace of the eigenvalue μ , and we denote it as ε ( μ ) . Its dimension is denoted by dim ε ( μ ) , which is equal to the multiplicity of the eigenvalue μ .

Since the adjacency matrix A = ( a i j ) is a real symmetric matrix, there exists a unitary matrix U such that U ¯ T A U = E , where E = d i a g ( μ 1 , μ 2 , ⋯ , μ n ) is a diagonal marix, and the columns of the matrix U are the eigenvetors corresponding to the eigenvalue, and they form a standard orthonormal basis of the vector space C n , U ¯ T denotes the conjugate transpose of the matrix U. If this basis is constructed by stringing together the orthonormal basis of the eigenspaces of A, then E = μ 1 E 1 + μ 2 E 2 + ⋯ + μ m E m , where μ 1 , μ 2 , ⋯ , μ m are the distinct eigenvalues of A and each E i has block diagonal form d i a g ( 0 , ⋯ , 0 , I , 0 , ⋯ , 0 ) , ( i = 1 , 2 , ⋯ , m ) . Then A has the spectral decomposition [

A = μ 1 P 1 + μ 2 P 2 + ⋯ + μ m P m , (1)

where P i = U E i U ¯ T ( i = 1 , 2 , ⋯ , m ) . For fixed i, if ε ( μ i ) has { x 1 , x 1 , ⋯ , x n } as a unit orthonormal basis, then

P i = x 1 x 1 ¯ T + x 2 x 2 ¯ T + ⋯ + x n x n ¯ T , (2)

and P i represents the orthonormal projection of C n on ε ( μ i ) . Moreover, it satisfies ∑ i = 1 m P i = I , P i 2 = P i = P i T , P i P j = 0 ( i ≠ j ) .

The module ‖ P i e j ‖ of the orthonormal projection of the vector

e j = ( 0, ⋯ ,1, ⋯ ,0 ) T into the eigensubspace ε ( μ i ) is exactly equal to the cosine of the (acute) angle between the vector e j and the eigensubspace ε ( μ i ) , in [

matrix B = ( α i j ) m × n formed by the angles is called the angle matrix of the graph G. The module ‖ P i j ‖ n of the orthonormal projection of the unit vector 1 n j

into the eigensubspace ε ( μ i ) is exactly equal to the cosine of the (acute) angle between the vector j and the eigensubspace ε ( μ i ) , in [

For positive integers m , n , K n , C n and K m , n denote the complete graph on n vertices, the n-cycle and the complete bipartite graph on m + n vertices, respectively. Q 8 denotes the cube graph on 8 vertices (as shown in

main angles are difficult to determine, there is a few study on them. Actually, they are all important parameters on the graph, and they can be combined with the eigenvalues of the graph to determine the degree sequence of the graph, the number of triangles, quadrilaterals and pentagons on the graph, and the characteristic polynomials of the complement graph [

Lemma 2.1 [

Let G be a graph on n vertices, and its vertices are labeled as 1,2, ⋯ , n . We assign a weight x i to each vertice on the graph, and we get a vector x = ( x 1 , x 2 , ⋯ , x n ) T .

Lemma 2.2 [

λ x i = ∑ j ~ i x j , ( i = 1,2, ⋯ , n )

holds, where ∑ is the sum of the weights x j of all vertices j adjacent to the vertice i.

Remark Lemma 2.2 shows that the nonzero vector x = ( x 1 , x 2 , ⋯ , x n ) T is an eigenvector of the graph G corresponding to eigenvalue λ if and only if the λ times of the weight x i of the i ( = 1,2, ⋯ , n ) th vertice is exactly equal to the sum of the weight of each vertice adjacent to it.

Lemma 2.3 [

∑ j = 1 n α i j 2 = dim ε ( μ i ) , ∑ i = 1 m α i j 2 = 1.

Lemma 2.4 [

∑ i = 1 m β i 2 = 1.

Theorem 3.1 The angle matrix of the complete graph K n is

B ( K n ) = ( n n n n ⋯ n n n − 1 n n − 1 n ⋯ n − 1 n ) ,

the main angle vector is b ( K n ) = ( 1,0 ) T .

Proof. By [

S p e c K n = { ( n − 1 ) 1 , ( − 1 ) n − 1 } ,

the eigenvector corresponding to the eigenvalue n − 1 is the all −1 vector j = ( 1,1, ⋯ ,1 ) T , and we unify it into 1 n j . So the matrix P 1 = ( 1 n j ) ( 1 n j ) T = 1 n j j T , by the definition of the angle, α 1 j = ‖ P 1 e j ‖ = ‖ 1 n j j T e j ‖ = ‖ 1 n j ‖ = 1 n ‖ j ‖ = n n . By Lemma 2.3, we can easily get the second row of the angle matrix B ( K n ) . By the definition of the main angle, and β i = ‖ P i j ‖ / n , β 1 = ‖ P 1 j ‖ / n = ‖ 1 n j j T j ‖ / n = ‖ j ‖ / n = n / n = 1 . By Lemma 2.4, we can easily get the main angle vector b ( K n ) . □

Theorem 3.2 The angle matrix of the cube graph Q 8 is

B ( Q 8 ) = ( 2 4 2 4 ⋯ 2 4 6 4 6 4 ⋯ 6 4 6 4 6 4 ⋯ 6 4 2 4 2 4 ⋯ 2 4 ) ,

the main angle vector is b ( Q 8 ) = ( 1,0,0,0 ) T .

Proof. By [

S p e c Q 8 = { 3 1 ,1 3 , ( − 1 ) 3 , ( − 3 ) 1 } ,

the eigenvector corresponding to the eigenvalue 3 is the all −1 vector j = ( 1,1,1,1,1,1,1,1 ) T , and we unify it into 1 8 j . So the matrix P 1 = ( 1 8 j ) ( 1 8 j ) T = 1 8 j j T , by the definition of the angle, α 1 j = ‖ P 1 e j ‖ = ‖ 1 8 j j T e j ‖ = ‖ 1 8 j ‖ = 1 8 ‖ j ‖ = 2 4 , ( j = 1 , 2 , ⋯ , 8 ) . By the definition of the main angle, β 1 = ‖ P 1 j ‖ / 8 = ‖ 1 8 j j T j ‖ / 8 = ‖ j ‖ / 8 = 8 / 8 = 1 . So all angles corresponding to the eigenvalue 3 are 2 4 , the main angle is 1.

By Lemma 2.1 and Lemma 2.2, we can know that the orthonormal eigenvectors corresponding to the eigenvalue 1 are (as shown in

ξ 1 = ( 1 , 1 , 1 , − 1 , 1 , − 1 , − 1 , − 1 ) T , ξ 2 = ( 1 , 1 , − 1 , 1 , − 1 , 1 , − 1 , − 1 ) T , ξ 3 = ( 1 , − 1 , 1 , 1 , − 1 , − 1 , 1 , − 1 ) T ,

and we unify them into 1 8 ξ 1 , 1 8 ξ 2 , 1 8 ξ 3 , then the orthonormal projection matrix

P 2 = ( 1 8 ξ 1 ) ( 1 8 ξ 1 ) T + ( 1 8 ξ 2 ) ( 1 8 ξ 2 ) T + ( 1 8 ξ 3 ) ( 1 8 ξ 3 ) T = 1 8 ( ξ 1 ξ 1 T + ξ 2 ξ 2 T + ξ 3 ξ 3 T ) ,

by the definition of the angle,

α 21 = ‖ P 2 e 1 ‖ = ‖ 1 8 ( ξ 1 ξ 1 T e 1 + ξ 2 ξ 2 T e 1 + ξ 3 ξ 3 T e 1 ) ‖ = 1 8 ‖ ( ξ 1 + ξ 2 + ξ 3 ) ‖ = 6 4 ,

in the same way,

α 22 = 1 8 ‖ ( ξ 1 + ξ 2 − ξ 3 ) ‖ = 6 4 , α 23 = 1 8 ‖ ( ξ 1 − ξ 2 + ξ 3 ) ‖ = 6 4 ,

α 24 = 1 8 ‖ ( − ξ 1 + ξ 2 + ξ 3 ) ‖ = 6 4 , α 25 = 1 8 ‖ ( ξ 1 − ξ 2 − ξ 3 ) ‖ = 6 4 ,

α 26 = 1 8 ‖ ( − ξ 1 + ξ 2 − ξ 3 ) ‖ = 6 4 , α 27 = 1 8 ‖ ( − ξ 1 − ξ 2 + ξ 3 ) ‖ = 6 4 ,

α 28 = 1 8 ‖ ( − ξ 1 − ξ 2 − ξ 3 ) ‖ = 6 4 .

Since ξ 1 , ξ 2 , ξ 3 are orthonormal to the all −1 vector, then

β 2 = ‖ P 2 j ‖ / n = ‖ ξ 1 ξ 1 T j + ξ 2 ξ 2 T j + ξ 3 ξ 3 T j ‖ / n = 0.

So all angles corresponding to the eigenvalue 1 are 6 4 , the main angle is 0.

By Lemma 2.1 and Lemma 2.2, we can know that the orthonormal eigenvectors corresponding to the eigenvalue −1 are (as shown in

η 1 = ( 1 , − 1 , − 1 , 1 , 1 , − 1 , − 1 , 1 ) T , η 2 = ( 1 , − 1 , 1 , − 1 , − 1 , 1 , − 1 , 1 ) T , η 3 = ( 1 , 1 , − 1 , − 1 , − 1 , − 1 , 1 , 1 ) T ,

and we unify them into 1 8 η 1 , 1 8 η 2 , 1 8 η 3 , then the orthonormal projection matrix

P 3 = ( 1 8 η 1 ) ( 1 8 η 1 ) T + ( 1 8 η 2 ) ( 1 8 η 2 ) T + ( 1 8 η 3 ) ( 1 8 η 3 ) T = 1 8 ( η 1 η 1 T + η 2 η 2 T + η 3 η 3 T ) ,

then

α 31 = α 38 = 1 8 ‖ ( η 1 + η 2 + η 3 ) ‖ = 6 4 , α 32 = α 37 = 1 8 ‖ ( − η 1 − η 2 + η 3 ) ‖ = 6 4 ,

α 33 = α 36 = 1 8 ‖ ( − η 1 + η 2 − η 3 ) ‖ = 6 4 , α 34 = α 35 = 1 8 ‖ ( η 1 − η 2 − η 3 ) ‖ = 6 4 .

Since η 1 , η 2 , η 3 are orthonormal to the all −1 vector, then

β 3 = ‖ P 3 j ‖ / n = ‖ η 1 η 1 T j + η 2 η 2 T j + η 3 η 3 T j ‖ / n = 0.

So all angles corresponding to the eigenvalue −1 are 6 4 , the main angle is 0.

By Lemma 2.1 and Lemma 2.2, we can know that the orthonormal eigenvector corresponding to the eigenvalue −3 is ζ = ( 1, − 1, − 1, − 1,1,1,1, − 1 ) T (as shown in

α 41 = α 45 = α 46 = α 47 = 1 8 ‖ ζ ‖ = 2 4 , α 42 = α 43 = α 44 = α 48 = 1 8 ‖ − ζ ‖ = 2 4 .

β 4 = ‖ P 4 j ‖ / 8 = ‖ 1 8 ζ ζ T j ‖ / 8 = 0.

So all angles corresponding to the eigenvalue −3 are 2 4 , the main angle is 0. □

Theorem 3.3 The angle matrix of the Petersen graph P is

B ( P ) = ( 10 10 10 10 ⋯ 10 10 2 2 2 2 ⋯ 2 2 10 5 10 5 ⋯ 10 5 ) ,

the main angle vector is b ( P ) = ( 1,0,0 ) T .

Proof. By [

S p e c P = { 3 1 ,1 5 , ( − 2 ) 4 } ,

the eigenvector corresponding to the eigenvalue 3 is the all −1 vector j = ( 1,1,1,1,1,1,1,1,1,1 ) T , and we unify it into 1 10 j . So the matrix P 1 = ( 1 10 j ) ( 1 10 j ) T = 1 10 j j T , then

α 1 j = ‖ P 1 e j ‖ = 1 10 ‖ j ‖ = 10 10 , ( j = 1 , 2 , ⋯ , 10 ) .

β 1 = ‖ P 1 j ‖ / 10 = ‖ 1 10 j j T j ‖ / 10 = ‖ j ‖ / 10 = 10 / 10 = 1.

So all angles corresponding to the eigenvalue 3 are 10 10 , the main angle is 1.

By Lemma 2.1 and Lemma 2.2, we can know that the eigenvectors corresponding to the eigenvalue 1 are (as shown in

δ 1 = ( 1 , 0 , − 1 , − 1 , 0 , 1 , 0 , 0 , 0 , 0 ) T , δ 2 = ( 0 , 1 , 0 , − 1 , − 1 , 0 , 1 , 0 , 0 , 0 ) T ,

δ 3 = ( − 1 , 0 , 1 , 0 , − 1 , 0 , 0 , 1 , 0 , 0 ) T , δ 4 = ( − 1 , − 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 ) T ,

δ 5 = ( 0 , − 1 , − 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 ) T ,

and we unify and orthogonality them into

γ 1 = ( 1 2 , 0 , − 1 2 , − 1 2 , 0 , 1 2 , 0 , 0 , 0 , 0 ) T ,

γ 2 = ( − 1 2 15 , 2 15 , 1 2 15 , − 3 2 15 , − 2 15 , − 1 2 15 , 2 15 , 0 , 0 , 0 ) T ,

γ 3 = ( − 1 15 , 1 15 , 1 15 , − 1 2 15 , − 3 2 15 , 3 2 15 , − 1 15 , 5 2 15 , 0 , 0 ) T ,

γ 4 = ( − 1 3 , − 1 3 , − 1 3 , 1 6 , − 1 6 , 1 6 , 1 3 , − 1 6 , 2 3 , 0 ) T ,

γ 5 = ( − 1 3 2 , − 1 3 2 , − 1 3 2 , − 1 3 2 , 1 3 2 , − 1 3 2 , 1 3 2 , 1 3 2 , − 1 3 2 , 1 2 ) T .

Then the orthonormal projection matrix P 2 = γ 1 γ 1 T + γ 2 γ 2 T + γ 3 γ 3 T + γ 4 γ 4 T + γ 5 γ 5 T ,

α 21 = ‖ P 2 e 1 ‖ = ‖ γ 1 γ 1 T e 1 + γ 2 γ 2 T e 1 + γ 3 γ 3 T e 1 + γ 4 γ 4 T e 1 + γ 5 γ 5 T e 1 ‖ = ‖ 1 2 γ 1 − 1 2 15 γ 2 − 1 15 γ 3 − 1 3 γ 4 − 1 3 2 γ 5 ‖ = 2 2 ,

in the same way, we have

α 2 j = 2 2 , ( j = 2 , 3 , ⋯ , 10 ) .

Since γ i ( i = 1 , 2 , 3 , 4 , 5 ) are orthonormal to the all −1 vector j, then

β 2 = ‖ P 2 j ‖ / 10 = ‖ γ 1 γ 1 T j + γ 2 γ 2 T j + γ 3 γ 3 T j + γ 4 γ 4 T j + γ 5 γ 5 T j ‖ / 10 = 0.

So all angles corresponding to the eigenvalue 1 are 2 2 , the main angle is 0.

By Lemma 2.1 and Lemma 2.2, we can easily know that all angles corresponding to the eigenvalue −2 are 10 5 , the main angle is 0. □

Theorem 3.4 The angle matrix of the n-cycle C n is

B ( C n ) = ( n n n n ⋯ n n n n n n ⋯ n n ⋮ ⋮ ⋱ ⋮ n n n n ⋯ n n ) ,

the main angle vector is b ( C n ) = ( 1,0, ⋯ ,0 ) T .

Proof. By [

S p e c C n = { 2 c o s ( 2 π j n ) ( j = 0,1,2, ⋯ , n − 1 ) } ,

when j = 0 , the eigenvector corresponding to the eigenvalue 2 is the all −1 vector j = ( 1,1, ⋯ ,1 ) T , and we unify it into 1 n j . So the orthonormal projection matrix P 1 = ( 1 n j ) ( 1 n j ) ¯ T = 1 n j j ¯ T , then

α 1 j = ‖ P 1 e j ‖ = 1 n ‖ j ‖ = n n , ( j = 1 , 2 , ⋯ , n ) ,

β 1 = ‖ P 1 j ‖ / n = ‖ 1 n j j ¯ T j ‖ / n = ‖ j ‖ / n = n / n = 1.

So all angles corresponding to the eigenvalue 2 are n n , the main angle is 1.

By Lemma 2.1 and Lemma 2.2, we can know that the eigenvectors corresponding to the eigenvalue 2 c o s ( 2 π j n ) ( j = 1,2, ⋯ , n − 1 ) are

θ 1 = ( 1, ω , ω 2 , ⋯ , ω n − 1 ) T , θ 2 = ( 1, ω 2 , ω 4 , ⋯ , ω 2 ( n − 1 ) ) T , ⋮ θ n − 1 = ( 1, ω n − 1 , ω 2 ( n − 1 ) , ⋯ , ω ( n − 1 ) ( n − 1 ) ) T ,

where ‖ θ j ‖ = 1 1 ¯ + ω ω ¯ + ⋯ + ω n − 1 ω n − 1 ¯ = n ( j = 1,2, ⋯ , n − 1 ) , then the orthonormal projection matrix P 2 = 1 n θ 1 θ 1 ¯ T , P 3 = 1 n θ 2 θ 2 ¯ T , ⋯ , P n = 1 n θ n − 1 θ n − 1 ¯ T , for example, when j = 1 , we have the orthonormal projection matrix P 2 corresponding to the eigenvalue 2 c o s ( 2 π n ) ,

α 21 = ‖ P 2 e 1 ‖ = ‖ 1 n θ 1 θ 1 ¯ T e 1 ‖ = 1 n ‖ θ 1 ‖ = n n , α 22 = ‖ P 2 e 2 ‖ = ‖ 1 n θ 1 θ 1 ¯ T e 2 ‖ = 1 n ‖ ω θ 1 ‖ = n n , ⋮ α 2 n = ‖ P 2 e n ‖ = ‖ 1 n θ 1 θ 1 ¯ T e n ‖ = 1 n ‖ ω n − 1 θ 1 ‖ = n n .

Since the eigenvectors corresponding to distinct eigenvalues are orthonormal, then

β 2 = ‖ P 2 j ‖ / n = ‖ 1 n θ 1 θ 1 ¯ T j ‖ / n = 0.

So all angles corresponding to the eigenvalue 2 c o s ( 2 π n ) are n n , the main angle is 0.

In the same way, all angles corresponding to the eigenvalue 2 cos ( 2 π j n ) ( j = 1 , 2 , ⋯ , n − 1 ) are n n , the main angle is 0. □

Theorem 3.5 The angle matrix of the complete bipartite graph K m , n is

B ( K m , n ) = ( 1 2 m ⋯ 1 2 m 1 2 n ⋯ 1 2 n m − 1 m ⋯ m − 1 m n − 1 n ⋯ n − 1 n 1 2 m ⋯ 1 2 m 1 2 n ⋯ 1 2 n ) ,

the main angle vector is b ( K m , n ) = ( m + n 2 ( m + n ) ,0, | m − n | 2 ( m + n ) ) T .

Proof. By [

S p e c K m , n = { ( m n ) 1 ,0 ( m + n − 2 ) , ( − m n ) 1 } .

The vertices of complete bipartite graph K m , n can be divided into two color

classes X and Y, | X | = m , | Y | = n . If we assign a weight 1 2 m to each vertex of X and a weight 1 2 n to each vertex of Y, by Lemma 2.2, we can know that the vector ρ 1 = ( 1 2 m , ⋯ , 1 2 m , 1 2 n , ⋯ , 1 2 n ) T is a unit eigenvector corresponding to the eigenvalue m n , so the orthonormal projection matrix corresponding to the eigenvalue m n is P 1 = ρ 1 ρ 1 T , then

α 1 i = ‖ P 1 e i ‖ = ‖ ρ 1 ρ 1 T e i ‖ = ‖ 1 2 m ρ 1 ‖ = 1 2 m , ( i = 1 , 2 , ⋯ , m ) ,

α 1 i = ‖ P 1 e i ‖ = ‖ ρ 1 ρ 1 T e i ‖ = ‖ 1 2 n ρ 1 ‖ = 1 2 n , ( i = m + 1 , m + 2 , ⋯ , m + n ) ,

β 1 = ‖ P 1 j ‖ / m + n = ‖ ρ 1 ρ 1 T j ‖ / m + n = m + n 2 ( m + n ) .

So all angles corresponding to the eigenvalue m n are m 1 2 m s and n 1 2 n s, the main angle is m + n 2 ( m + n ) .

If we assign a weight 1 2 m to each vertex of X and a weight − 1 2 n to each vertex of Y, by Lemma 2.2, we can know that the vector

ρ 2 = ( 1 2 m , ⋯ , 1 2 m , − 1 2 n , ⋯ , − 1 2 n ) T is a unit eigenvector corresponding

to the eigenvalue − m n , so the orthonormal projection matrix corresponding to the eigenvalue − m n is P 2 = ρ 2 ρ 2 T , then

α 2 i = ‖ P 2 e i ‖ = ‖ ρ 2 ρ 2 T e i ‖ = ‖ 1 2 m ρ 2 ‖ = 1 2 m , ( i = 1 , 2 , ⋯ , m ) ,

α 2 i = ‖ P 2 e i ‖ = ‖ ρ 2 ρ 2 T e i ‖ = ‖ − 1 2 n ρ 2 ‖ = 1 2 n , ( i = m + 1 , m + 2 , ⋯ , m + n ) ,

β 2 = ‖ P 2 j ‖ / m + n = ‖ ρ 2 ρ 2 T j ‖ / m + n = | m − n | 2 ( m + n ) .

So all angles corresponding to the eigenvalue − m n are m 1 2 m s and n 1 2 n s, the main angle is | m − n | 2 ( m + n ) .

By Lemma 2.3, all angles corresponding to the eigenvalue 0 are m m − 1 m s and n n − 1 n s. By Lemma 2.4, the main angle corresponding to the eigenvalue 0 is β 3 = 0 . □

In this paper, the angles and main angles of the complete graph, the cube graph, the Petersen graph, the cycle and the complete bipartite graph are determined.

This work is supported by National Natural Science Foundation of China (1561056, 11661066), Natural Science Foundation of Qinghai Provence (2016-ZJ-914).

The authors declare no conflicts of interest regarding the publication of this paper.

Ma, H.C. and Gao, S. (2020) The Angles and Main Angles of Some Special Graphs. Applied Mathematics, 11, 480-490. https://doi.org/10.4236/am.2020.116035