# A Geometric Property of the Laplacian matrix of a Connected Nonsingular Mixed Graph

Authors: Zheng-Da Zhou; Shi-Cai Gong
Journal: Journal of Chemistry
 (2020)

---

## Abstract

In this paper, we give a geometric interpretation of the Laplacian matrix of a connected nonsingular mixed graph which generalizes the results of M. Fiedler (M. Fiedler, Geometry of the Laplacian,Linear Algebra Appl., 2005, 403: 409–413). In addition, the relations of geometric properties between a connected (singular or nonsingular) mixed graph, and all its resigned graphs will be characterized.


---

## Body

## 1. Introduction

LetG=V,E be a mixed graph with vertex set V=VG=v1,v2,…,vn and edge set E=EG=e1,e2,…,em, which is obtained from an undirected simple graph by orienting some (possibly none or all) of its edges such that one of its endpoint forms a head and the another one is a tail. The incidence matrix of G is an n×m matrix M=MG=mij whose entries are defined by mij=1 if ej is an unoriented edge incident to vi or ej is an oriented edge with head vi, mij=−1 if ej is an oriented edge with tail vi, and mij=0 otherwise. The Laplacian matrix of G is defined as LG=lijn×n=MMT (see [1–4]), where the matrix MT denotes the transpose of M. Obviously LG is a Gram matrix and thus is positive semidefinite. G is called singular (or nonsingular) if LG is singular (or nonsingular).A mixed graph is calledquasi-bipartite if it does not contain a nonsingular cycle, or equivalently, it contains no cycles with an odd number of unoriented edges (see (1, Lemma 1)). The all-oriented graph obtained from the mixed graph G by arbitrarily orienting every unoriented edge of G (if one exists) will be denoted by G⟶, the signature matrix with 1 or −1 along its diagonal of a diagonal matrix will be denoted by D. A graph is called a resigned graph of G if it is obtained from G by resigning under the signature matrix D, and that the labelling of the vertices is the same as that of G, denoted by GD. Then each resigned graph of G gives a resigning of the edges of G (that is, some oriented edges of G may turn to be unoriented and vice versa), and LGD=DTLGD. The following results are well known.Lemma 1.
(see [3], Lemma 2.2, and [5], Lemma 5). Let G be a connected mixed graph. Then, G is singular if and only if G is quasi-bipartite.Theorem 1.
(see [1], Theorem 4). Let G be a connected mixed graph. Then, G is quasi-bipartite if and only if there exists a signature matrix D such that DTLGD=LG⟶.
In this paper, we firstly give a geometric interpretation of the Laplacian matrix of a connected nonsingular mixed graph which generalizes the results of Fiedler [6] from undirected graphs to mixed graphs. Finally, the relations of geometric properties between a connected (singular or nonsingular) mixed graph and its resigned graphs will be characterized.


## 2. Geometric Properties

### 2.1. Nonsingular Mixed Graphs

LetL=LG=lijn×n be the Laplacian matrix of a connected nonsingular mixed graph on nn≥3 vertices. Then, rankL=n. By the well-known equivalence of positive definite and Gram matrices, there exists uniquely n linear independent vectors denoted by u1,…,un, in a Euclidean space En of dimension n, such that the inner products of the vectors ui satisfy(1)ui,uj=lijfor all1≤i,j≤n.Observe that the vectorsui and uji≠j are orthogonal if and only if there is no edge in G between the vertices i and j. If i,j∈EG, then the angle between ui and uj is obtuse if i,j is oriented, the angle is acute otherwise.LetU=u1,…,un∈En, then we have the following geometric interpretation of LG.Theorem 2.
LetL=LG=lijn×n be the Laplacian matrix of a connected nonsingular mixed graph G on nn≥3 vertices. Then, there exists a unique quadric Q:(2)xTK−1x=1,such that(i)
Q contains all the end-points of the vectors ui, and(ii)
The tangent hyperplane at each of these end-points is parallel to the hyperplane containing the remainingn−1 vectors,
From the above equation,x means the column vector of orthonormal coordinates in En and K=UUT.Proof.
Note thatK−1=UUT−1=UT−1U−1, then Z=UTK−1U=In. Thus, all diagonal entries of Z are equal to 1, i.e.,(3)uiTK−1ui=1,i=1,2,…,n,and all nondiagonal entries of Z are 0, which proves that quadric equation (2) contains all the end-points of the vectors ui.
The equation of the tangent hyperplane at the end-points ofuk to the quadric equation (2) is(4)12xTK−1uk+ukTK−1x=1.
Note thatxTK−1ukT=ukTK−1x, then(5)xTK−1uk=1.
On the contrary, the hyperplane containing all vectorsui for i≠k satisfies the relation:(6)xTK−1uk=0,since uiTK−1uk=Zik=0 for i≠k. Thus, both the hyperplanes are parallel, and equation (2) is indeed the equation of Q.
Assume there exists another quadricQ′:(7)xTBx=1,which holds properties (i) and (ii) mentioned above. Then, by property (i), we have(8)uiTBui=1,fori=1,…,n.
Thus, the equation of the tangent hyperplane at the end-points ofuk to the quadric equation (2) is(9)xTBuk=1.
Consequently, by property (ii), the equation of the hyperplane containing all the remainingn−1 vectors is(10)xTBuk=0,since, for each i, the vector ui contains the origin as one end-point.
Associating equations (3) and (6), we have(11)UTBU=I.
Then,B=K−1. Hence, the uniqueness follows.
The quadricQ is an ellipsoid, usually called the Steiner circumscribed ellipsoid of the simplex with vertices in the end-points of the vector ui.
Now, suppose thatv is an eigenvector of L corresponding to the eigenvalue λ. We have UTUv=λv. Consequently, UUTUv=λUv. The vector z=Uv is thus an eigenvector of K as well as K−1 corresponding to the same λ and is thus the direction of an axis of the quadric Q. Indeed, the halfline x=μz, μ≥0, meets the quadric in the point in which the tangent is parallel to xTz=0, thus orthogonal to z. We have thus a correspondence Γ between the eigenvector of L and the axis of Q. If the eigenvector corresponds to the eigenvalue λ, then the length of the corresponding half axis is λ. Applying the method similar to that of Theorem 1 in [6], we have the following.Theorem 3.
The coordinates of the eigenvectorv of the Laplacian matrix L are proportioned to the Euclidean coordinates of the points on the one-dimensional line generated by the vector z (corresponding in Γ) obtained as orthogonal projections of the vectors ui on z.Let us transform the original orthogonal coordinate system inEn into an other orthogonal coordinate system in which the axes coincide with the axes of the quadric Q. This will be performed algebraically as follows.The matrixK can be written as OΛOT, where O is an orthogonal matrix and Λ is a diagonal matrix of the eigenvalues of K. Since K−1=OΛ−1OT, equation (2) of Q will be transformed into(12)xTOΛ−1OTx=1oryTΛ−1y=1,where y=OTx is again the column vector of orthogonal coordinates in the transformed system. Then, in the new system, the quadric Q has the equation:(13)∑i=1nyi2di=1.Of course, the numbersdi are positive. They are equal to the eigenvalues of L. Let dG=maxdii=1,…,n and αG=mindii=1,…,n. Then, dG (respectively, αG) is the semimajor (respectively, semiminor) axis of the quadric. On the contrary, dG is the spectral radius of LG, and αG is the smallest eigenvalue of LG. Then, the radius of the externally tangent circle of Q is dG, and the radius of the internally tangent circle of Q is αG.Then, the vectorui transforms into the vector wi=OTui for i=1 to n. The following result seems interesting, we say as usual that an affine transformation is such a linear transformation which transforms points at infinity into points at infinity.Theorem 4.
Let A be the affine transformation inEn which transforms the ellipsoid Q into a hypersphere:(14)
y
i
=
d
i
Y
i
.Then,A transforms the vector wi into vector Wi=di−1/2wi which form an eutactic star, being all of equal length and spanning equal mutual angles.Proof.
By equation (14), we obtain the matrix form(15)y=Λ−1/2Y,where Λ was defined earlier. Since wi=OTui and Wi=Λ−1/2wi, we have for the matrix W whose columns are the coordinates of the vectors Wi, W=Λ−1/2OTU. Therefore, the Gram matrix of the vectors Wi is(16)WTW=UTOΛ−1OTU=UTK−1U=UTUUT−1U=In,since this is the matrix Z mentioned above. Immediately, the last matrix is the Gram matrix of an eutactic star.


### 2.2. Mixed Graphs with the Same Underlying

In this section, we will characterize the relations of geometric properties between the graphG (singular or nonsingular) and all its resigned graphs GD.Denoted byK−1G, the matrix of quadric corresponding to the graph G, by uDi the column vector of the matrix UD since more than one graph is under discussion. Assume L=LG=lijn×n be the Laplacian matrix of a connected mixed graph G on n vertices. Let ℵG be the set of all resigned graphs of a mixed graph G. Obviously, ℵG has the following properties:(i)
G∈ℵG(ii)
All elements ofℵG have the same singularity as that of the graph G(iii)
All elements ofℵG can be considered as the resigned graphs of a (arbitrary) element of ℵGBy Lemma1 and Theorem 1, if G is nonsingular, we have(17)LGD=DTLGD=DTUTUD=UDTUD.Thus,(18)K−1GD=UDUDT−1=UUT−1=K−1G,where U=u1,…,un has been defined above.Consequently, we have the following.Theorem 5.
LetG be a connected nonsingular mixed graph on n vertices, and let ℵG be the set of all its resigned graphs. Then, there exists a unique quadric Q:(19)xTK−1Gx=1,such that, for all GD∈ℵG, the quadric Q contains all the endpoints of the vectors uDi of GD, and the tangent hyperplane at each of these endpoints is parallel to the hyperplane containing the remaining n−1 vectors, where K−1G=UUT∈En has been defined above.
Similarly, by the result of [6], we have the following.Theorem 6.
LetG be a connected singular mixed graph on n vertices, and let ℵG be the set of all its resigned graphs. Then, there exists a unique quadric Q:(20)xTK−1Gx=n−1n,such that, for all GD∈ℵG, the quadric Q contains all the endpoints of the vectors uDi of GD, and the tangent hyperplane at each of these endpoints is parallel to the hyperplane containing the endpoints of the remaining n−1 vectors, , where K−1G=UUT∈En−1, U=u1,u2,…,un which holds that ∑i=1nui=0 and UTU=LG′ the Laplacian matrix of the undirected graph G′ with the same underlying graph as that of G.Proof.
LetG be a connected singular mixed graph, then G⟶∈ℵG. By Lemma 1 and Theorem 1 and by the definition of the Laplacian matrix, the matrix LG⟶ is the same as that of the undirected graph G′ with the same underlying graph. To graph G′, by [6], there exists n vectors, u1,…,un, in a Euclidean space En−1 of dimension n−1, such that(21)∑i=1nui=0,LG′=UTU,where U=u1,…,un
And by [6], there exists a unique quadric Q:(22)xTK−1G′x−n−1n=0,such that the quadric Q contains all the endpoints of the vectors ui, and the tangent hyperplane at each of these endpoints is parallel to the hyperplane containing the endpoints of the remaining n−1 vectors, where K−1G′=UUT∈En−1.
LetGD be a arbitrary element of ℵG; now, we discuss the relation of the matrices between K−1GD and K−1G′. By Lemma 1 and Theorem 1, there exists a signature matrix D such that(23)LGD=DTLG′D=DTUTUD=UDTUD.
Thus,(24)K−1GD=UDUDT−1=UUT−1=K−1G′.
The result follows immediately.


## 2.1. Nonsingular Mixed Graphs

LetL=LG=lijn×n be the Laplacian matrix of a connected nonsingular mixed graph on nn≥3 vertices. Then, rankL=n. By the well-known equivalence of positive definite and Gram matrices, there exists uniquely n linear independent vectors denoted by u1,…,un, in a Euclidean space En of dimension n, such that the inner products of the vectors ui satisfy(1)ui,uj=lijfor all1≤i,j≤n.Observe that the vectorsui and uji≠j are orthogonal if and only if there is no edge in G between the vertices i and j. If i,j∈EG, then the angle between ui and uj is obtuse if i,j is oriented, the angle is acute otherwise.LetU=u1,…,un∈En, then we have the following geometric interpretation of LG.Theorem 2.
LetL=LG=lijn×n be the Laplacian matrix of a connected nonsingular mixed graph G on nn≥3 vertices. Then, there exists a unique quadric Q:(2)xTK−1x=1,such that(i)
Q contains all the end-points of the vectors ui, and(ii)
The tangent hyperplane at each of these end-points is parallel to the hyperplane containing the remainingn−1 vectors,
From the above equation,x means the column vector of orthonormal coordinates in En and K=UUT.Proof.
Note thatK−1=UUT−1=UT−1U−1, then Z=UTK−1U=In. Thus, all diagonal entries of Z are equal to 1, i.e.,(3)uiTK−1ui=1,i=1,2,…,n,and all nondiagonal entries of Z are 0, which proves that quadric equation (2) contains all the end-points of the vectors ui.
The equation of the tangent hyperplane at the end-points ofuk to the quadric equation (2) is(4)12xTK−1uk+ukTK−1x=1.
Note thatxTK−1ukT=ukTK−1x, then(5)xTK−1uk=1.
On the contrary, the hyperplane containing all vectorsui for i≠k satisfies the relation:(6)xTK−1uk=0,since uiTK−1uk=Zik=0 for i≠k. Thus, both the hyperplanes are parallel, and equation (2) is indeed the equation of Q.
Assume there exists another quadricQ′:(7)xTBx=1,which holds properties (i) and (ii) mentioned above. Then, by property (i), we have(8)uiTBui=1,fori=1,…,n.
Thus, the equation of the tangent hyperplane at the end-points ofuk to the quadric equation (2) is(9)xTBuk=1.
Consequently, by property (ii), the equation of the hyperplane containing all the remainingn−1 vectors is(10)xTBuk=0,since, for each i, the vector ui contains the origin as one end-point.
Associating equations (3) and (6), we have(11)UTBU=I.
Then,B=K−1. Hence, the uniqueness follows.
The quadricQ is an ellipsoid, usually called the Steiner circumscribed ellipsoid of the simplex with vertices in the end-points of the vector ui.
Now, suppose thatv is an eigenvector of L corresponding to the eigenvalue λ. We have UTUv=λv. Consequently, UUTUv=λUv. The vector z=Uv is thus an eigenvector of K as well as K−1 corresponding to the same λ and is thus the direction of an axis of the quadric Q. Indeed, the halfline x=μz, μ≥0, meets the quadric in the point in which the tangent is parallel to xTz=0, thus orthogonal to z. We have thus a correspondence Γ between the eigenvector of L and the axis of Q. If the eigenvector corresponds to the eigenvalue λ, then the length of the corresponding half axis is λ. Applying the method similar to that of Theorem 1 in [6], we have the following.Theorem 3.
The coordinates of the eigenvectorv of the Laplacian matrix L are proportioned to the Euclidean coordinates of the points on the one-dimensional line generated by the vector z (corresponding in Γ) obtained as orthogonal projections of the vectors ui on z.Let us transform the original orthogonal coordinate system inEn into an other orthogonal coordinate system in which the axes coincide with the axes of the quadric Q. This will be performed algebraically as follows.The matrixK can be written as OΛOT, where O is an orthogonal matrix and Λ is a diagonal matrix of the eigenvalues of K. Since K−1=OΛ−1OT, equation (2) of Q will be transformed into(12)xTOΛ−1OTx=1oryTΛ−1y=1,where y=OTx is again the column vector of orthogonal coordinates in the transformed system. Then, in the new system, the quadric Q has the equation:(13)∑i=1nyi2di=1.Of course, the numbersdi are positive. They are equal to the eigenvalues of L. Let dG=maxdii=1,…,n and αG=mindii=1,…,n. Then, dG (respectively, αG) is the semimajor (respectively, semiminor) axis of the quadric. On the contrary, dG is the spectral radius of LG, and αG is the smallest eigenvalue of LG. Then, the radius of the externally tangent circle of Q is dG, and the radius of the internally tangent circle of Q is αG.Then, the vectorui transforms into the vector wi=OTui for i=1 to n. The following result seems interesting, we say as usual that an affine transformation is such a linear transformation which transforms points at infinity into points at infinity.Theorem 4.
Let A be the affine transformation inEn which transforms the ellipsoid Q into a hypersphere:(14)
y
i
=
d
i
Y
i
.Then,A transforms the vector wi into vector Wi=di−1/2wi which form an eutactic star, being all of equal length and spanning equal mutual angles.Proof.
By equation (14), we obtain the matrix form(15)y=Λ−1/2Y,where Λ was defined earlier. Since wi=OTui and Wi=Λ−1/2wi, we have for the matrix W whose columns are the coordinates of the vectors Wi, W=Λ−1/2OTU. Therefore, the Gram matrix of the vectors Wi is(16)WTW=UTOΛ−1OTU=UTK−1U=UTUUT−1U=In,since this is the matrix Z mentioned above. Immediately, the last matrix is the Gram matrix of an eutactic star.


## 2.2. Mixed Graphs with the Same Underlying

In this section, we will characterize the relations of geometric properties between the graphG (singular or nonsingular) and all its resigned graphs GD.Denoted byK−1G, the matrix of quadric corresponding to the graph G, by uDi the column vector of the matrix UD since more than one graph is under discussion. Assume L=LG=lijn×n be the Laplacian matrix of a connected mixed graph G on n vertices. Let ℵG be the set of all resigned graphs of a mixed graph G. Obviously, ℵG has the following properties:(i)
G∈ℵG(ii)
All elements ofℵG have the same singularity as that of the graph G(iii)
All elements ofℵG can be considered as the resigned graphs of a (arbitrary) element of ℵGBy Lemma1 and Theorem 1, if G is nonsingular, we have(17)LGD=DTLGD=DTUTUD=UDTUD.Thus,(18)K−1GD=UDUDT−1=UUT−1=K−1G,where U=u1,…,un has been defined above.Consequently, we have the following.Theorem 5.
LetG be a connected nonsingular mixed graph on n vertices, and let ℵG be the set of all its resigned graphs. Then, there exists a unique quadric Q:(19)xTK−1Gx=1,such that, for all GD∈ℵG, the quadric Q contains all the endpoints of the vectors uDi of GD, and the tangent hyperplane at each of these endpoints is parallel to the hyperplane containing the remaining n−1 vectors, where K−1G=UUT∈En has been defined above.
Similarly, by the result of [6], we have the following.Theorem 6.
LetG be a connected singular mixed graph on n vertices, and let ℵG be the set of all its resigned graphs. Then, there exists a unique quadric Q:(20)xTK−1Gx=n−1n,such that, for all GD∈ℵG, the quadric Q contains all the endpoints of the vectors uDi of GD, and the tangent hyperplane at each of these endpoints is parallel to the hyperplane containing the endpoints of the remaining n−1 vectors, , where K−1G=UUT∈En−1, U=u1,u2,…,un which holds that ∑i=1nui=0 and UTU=LG′ the Laplacian matrix of the undirected graph G′ with the same underlying graph as that of G.Proof.
LetG be a connected singular mixed graph, then G⟶∈ℵG. By Lemma 1 and Theorem 1 and by the definition of the Laplacian matrix, the matrix LG⟶ is the same as that of the undirected graph G′ with the same underlying graph. To graph G′, by [6], there exists n vectors, u1,…,un, in a Euclidean space En−1 of dimension n−1, such that(21)∑i=1nui=0,LG′=UTU,where U=u1,…,un
And by [6], there exists a unique quadric Q:(22)xTK−1G′x−n−1n=0,such that the quadric Q contains all the endpoints of the vectors ui, and the tangent hyperplane at each of these endpoints is parallel to the hyperplane containing the endpoints of the remaining n−1 vectors, where K−1G′=UUT∈En−1.
LetGD be a arbitrary element of ℵG; now, we discuss the relation of the matrices between K−1GD and K−1G′. By Lemma 1 and Theorem 1, there exists a signature matrix D such that(23)LGD=DTLG′D=DTUTUD=UDTUD.
Thus,(24)K−1GD=UDUDT−1=UUT−1=K−1G′.
The result follows immediately.



---

*Source: 6210758-2020-02-28.xml*