Inverse of Adjacency Matrix of a Graph with Matrix Weights

2014-09-07CUIDenglan

湖南师范大学自然科学学报 2014年3期

CUI Deng-lan

(Department of Mathematics, College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)

CUI Deng-lan

(Department of Mathematics, College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)

The weighted graphs that the edge weights are square matrices with fixed orders are considered. The adjacency and skew-adjacency matrix of a weighted graph is defined in a natural way. The formula is obtained for the inverses of the adjacency and skew-adjacency matrices of a weighted graph when its underlying graph is a bipartite graph with a unique perfect matching, and some applications are given in inverse of block matrices.

weighted graph; adjacency matrix; skew-adjacency matrix; inverse matrix

1 Introduction

We only consider graphs which have no loops or multiple edges. LetG=(V，E) be a connected graph with vertex setV={1,2,…,n} and edge setE. A weighted graph is a graph in which each edge is assigned a weight, which is usually positive number. An unweighted graph, or simply a graph, is thus a weighted graph with each of the edges bearing weight 1.

A weighted graph is a graph, each edge of which has been assigned a square matrix, called the weight of the edge. All the weight matrices will be assumed to be of the same order and nonnull. In this note, by “weighted graph” we will mean a “weighted graph with each of its edges bearing a non-null matrix as weight”, unless otherwise stated. The spectra of these weighted graph were investigated by Das in [1～4] recently. We now introduce some more notation. LetGbe a weighted graph on n vertices. Denote bywi,jthe non-null weight matrix of orderpof the edgeij, and assume thatwi,j=wj,i. We writeij∈Eif verticesiandjare adjacent.

The adjacency matrix of a weighted graph is a block matrix, denoted and defined as A(G)=(ai,j),where

Notethatinthedefinitionabove,thezerodenotesthep×pzeromatrix.ThusA(G)isasquarematrixofordernp.NotealsothattheadjacencymatrixA=(ai,j)ofaweighteddigraphsatisesai,j=aj,ibutisnotnesessarysymmetricingeneral.A(weightedorunweighted)graphGissaidtobenonsingularifitsadjacencymatrixA(G)isnonsingular.

A combinatorial description of the inverse of the adjacency matrix of nonsingular tree has been given in[12]and in[13]. A combinatorial description of the inverse of the adjacency matrix of a bipartite graph without a cycle of length 4mis given in Cvetkovic[10]. A combinatorial description of the inverse of the adjacency matrix of a bipartite graph with a unique matching is given in[14]. In this note we supply a simple combinatorial description of the inverse of the adjacency matrix and skew-adjacency matrix of a weighted bipartite graph with a unique perfect matching, which contains the formula due to [14] as a special case.

2 The Main Results

Lemma 1[14]LetGbe a bipartite graph with a unique perfect matching M and the edgeii′ in M. If a vertexv≠i′ is adjacent toisuch that there exists an alternating pathP(v,j)=[v=x1,x2,…,xn=jbetween verticesvandj, thenP′=[i′,i,P(v,j)]=[i′,i,v,x2,…,x2k=j] is an alternating path fromi′ toj.

Note that the converse of Lemma 1 holds clearly. That is, if there is an alternating pathP(i′,j) fromi′ toj, it must have the form [i′,i,x1,x2,…,xm=j]. Thus there must exist a vertexv=x1≠i′ adjacent toisuch that an alternating path fromvtojexists.

Lemma 2[15]LetGbe a graph, thenGis bipartite and has a unique perfect matching if and only if the adjacency matrix ofGcan be expressed as

whereLis a lower-triangular, square (0,1)-matrix with every diagonal entry equal is 1.

It follows that the determinants of the adjacency and skew-adjacency matrix of a weighted bipartite graph with a unique perfect matching are ±∏i,j∈M(detwi,j)2. Thus, the adjacency and skew-adjacency matrix of a weighted bipartite graph with a unique perfect matching is nonsingular if and only if all weight matriceswi,j, whereij∈M, are nonsingular.

The following result gives a combinatorial description of the inverse of the adjacency matrix of a weighted bipartite graph with a unique perfect matching.

Theorem 1 LetGbe a weighted bipartite graph with a unique perfect matching M and let A(G)=(aij)beitsadjacencymatrix.Ifallweightmatriceswi,jwhereij∈M, are nonsingular, then A(G)isnonsingularanditsinverseistheblockmatrixB=(bi,j),where

(1)

Proof The (i,j)-th block matrix ofABis given by

(2)

Thus for eachi=1,2,…,n, as there exists exactly one vertex, sayi′, such that the edgei′i∈M, we have

hereIis the identity matrix of orderp,pis the order of the weight matrices.Now leti,jbe two distinct vertices inG. Suppose that for each vertexvadjacent toi, there is no alternating path fromvtoj, so that by (1)bv,j=0. Then from (2) we have that (AB)i,j=0.

Assumenowthatthereisavertexv≠i′adjacenttoisuchthatP(v,j)=[v=x1,x2,…,x2k=j]isanalternatingpathandletN={v1,v2,…,vr},withvl≠i′,betheverticesadjacenttoisuchthattherearealternatingpathsfromvltoj.ByLemma1wehavealreadyseenthatthealternatingpathfromi′tojarepreciselyoftheform[i′, i, P(vl,j)],whereP(vl,j)isanalternatingpathfromvltoj.Hence

andtheproofiscompleted.

Foratreewithaperfectmatching,thereisatmostonealternatingpathbetweenanypairofvertices.Thuswehave

Corollary 1 LetGbe a weighted tree with perfect matching M and Abeitsadjacencymatrix.Ifallweightmatriceswi,j,whereij∈M, are nonsingular, then AisnonsingularanditsinverseistheblockmatrixB=(bi,j),where

Foranunweightedgraph,wehave

Corollary 2[14]LetGbe a bipartite graph with a unique perfect matching M and let A be its adjacency matrix. Then A is nonsingular and its inverse is the matrix B=(bi,j), where

Next we consider the inverse of skew-adjacency matrix of a weighted graph.

(3)

Proof The (i,j)-th block matrix of ST is given by

(4)

Thus for eachi=1,2,…,n, as there exists exactly one vertex, sayi′, such that the edgei′i∈M, we have

hereIis the identity matrix of orderp,pis the order of weight matrices.

Now leti,jbe two distinct vertices inG. Suppose that for each vertexvadjacent toi, there is no alternating path fromvtoj, so that by (3)bv,j=0. Then from (2) we have that (ST)i,j=0.

Assumenowthatthereisavertexv≠i′adjacenttoisuchthatP(v,j)=[v=x1,x2,…,x2k=j]isanalternatingpathandletN={v1,v2,…,vr},withvl≠i′,betheverticesadjacenttoisuchthattherearealternatingpathsfromvltoj.LetN={v1,v2,…,vr},withvl≠i′,betheverticesadjacenttoisuchthattherearealternatingpathsfromvltoj.ByLemma1wehavealreadyseenthatthealternatingpathfromi′tojarepreciselyoftheform[i′,i,P(vl,j)],whereP(vl,j)isanalternatingpathfromvltoj.Hence

andtheproofiscompleted.

Corollary 3 LetGbe a weighted tree with perfect matching M and S=(si,j)beitsskew-adjacencymatrix.Ifallweightmatriceswi,jwhereij∈M, are nonsingular, then SisnonsingularanditsinverseistheblockmatrixT=(ti,j),where

Asanapplicationofourresults,wegiveanexampleasfollows.

LetA,B,C,D,E,Farep×pmatricesandA,C,Fbenonsingular,Thenwehavethefollowingformulaformatrixinverse.

whereX=A-1BC-1DF-1-A-1EF-1，Y=F-1DC-1BA-1-F-1EA-1，W=-C-1DF-1,Z=-F-1DC-1.

Infact,wetaketheweightedgraphandanorientationasFig.1.

Fig.1 A weighted graph G and its an orientation

NotethatP={[1,2]},P(1,3)=P(1,5)=∅,P(1,4)={[1,2,3,4]},P(1,6)={[1,2,3,4,5,6],[1,2,4,6]},P(2,3)=P(2,4)=P(2,5)=∅,P(3,4)={[3,4]},P(3,5)=∅,P(3,6)=[3,4,5,6],P(4,5)=P(4,6)=∅,P(5,6)={[5,6]}. Then by Theorems 2 and 5 we can get the above formula for matrices inverses.

[1] BAPAT R. Determinant of the distance matrix of a tree with matrix weights[J]. Linear Algebra Appl, 2006,416:2-7.

[2] DAS K. A sharp upper bound on the largest Laplacian eigenvalue of weighted graphs[J].Linear Algebra Appl, 2005,407: 55-69.

[3] DAS K, BAPAT R. A sharp upper bound on the largest Laplacian eigenvalue of weighted graphs[J]. Linear Algebra Appl, 2005,405:153-165.

[4] DAS K, BAPAT R. A sharp upper bound on the spectral radius of weighted graph[J].Discrete Math, 2008,308(15):3180-3186.

[5] HOU Y, LEI T. Characteristic polynomials of skew-adjacency matrices of oriented graphs[J]. Electron J Combinat, 2011,18:156-162.

[6] SHADER R, SO W. Skew spectra of oriented graphs[J]. Electron J Combinat, 2009,16:32-35.

[7] TIAN G. On the skew energy of orientations of hypercubes[J]. Linear Algebra Appl, 2011,435:2140-2149.

[8] YAN W, ZHANG F. Enumeration of perfect matchings of a type of Cartesian products of graphs[J].Discrete Appl Math, 2006,154(1):145-157.

[9] ZHANG F, YAN W. Enumeration of perfect matchings in type of graphs with reflective symmetry[J]. MATCH Commun Math Comput Chem, 2003,48(1):117-124.

[10] CVETKOVIC D, DOOB M, SACHS H. Spectra of graphs[M]. New York: Academic Press, 1980.

[11] LOVASE L, PLUMMER M. Matching theory[M]. Annual of Dicscrete Mathematics 29, New York: North-Holland, 1988.

[12] BAPAT R. Graphs and matrices[M]. Hindustan: Springer, 2010.

[13] BUCKLEY L, DOTY L, HARAARY F. On graphs with signed inverses [J].Networks, 1988,18(3):151-157.

[14] BARIK S, NEUMANN M, PATI S. On nonsingular trees and a reciprocal eigenvalue property[J]. Linear Mulitlinear Alge, 2006,54(6):453-465.

[15] SIMION R, CAO D. Solution to a problem of C.D Godsil regarding bipartite graphs with unique perfect matching[J]. Combinatorica, 1989,9(1):85-89.

(编辑沈小玲)

2013-02-27

国家自然科学基金资助项目(11171102)

O157

1000-2537(2014)03-0069-05

赋矩阵权图的邻接矩阵的逆矩阵