Immanants of Laplacians of Graphs

Onn Chan1 and M.Y Ong2

Department of Mathematics, National University of Singapore

Singapore 117543

Abstract

Let A be a nxn complex matrix. Then it is usual to define det(A) = sgn() , and per(A) = . When A = L(T) is a Laplacian matrix defined from a tree, we can give a formula for det(L(T)) and per(L(T)) in terms of some numbers associated with the matchings of the tree. Hence by studying the properties of these matching numbers, we can deduce some properties of det(L(T)) and per(L(T)). Among the results proven is that per(L(T)) is always even when T is any tree.

1. Introduction

Let A be a nxn matrix and f:Sn .Then, we define the generalized matrix function

d :Mn( ) , by d (A) = f() . When f = (being a partition of n), is an

irreducible character of Sn , d ( ) is called an immanant. Let A be a nxn matrix. When f = sgn, we get d (A) = det(A) and when f = 1, we get d (A) = per(A), where per(A) is the permanent of A. In general, calculating d (A) for any arbitrary matrix A, can be difficult because each Sn contributes a term a a … a in the calculation. However, when A = L(T)[where L(T) is a laplacian matrix defined from some tree T], a a … a = 0 wheneverSn has a cycle of lengthin its cycle decomposition, which greatly reduces the number of terms to be considered. Furthermore, certain numbers associated with matchings of a tree come up naturally in the computation of d (L(T)). We will derive an expression for d (L(T)) in terms of these numbers, and investigate some properties of these numbers.

2. Laplacian matrix of a graph

Let G = (V,E) be a graph of order n, having vertex set V = {v0,v1,…,vn }. The laplacian matrix of G denoted L(G) = [aij] is the nxn matrix with entries

-1, if ij and {vi,vj}E.

aij = 0, if ij and {vi,vj}E

deg(vi), if i = j

Note that(this is used to prove(3)), det(L(G)) = 0. To see this, consider each row sum of L(G) (the row sum is the sum of all entries in a single row). Then suppose L(G) were invertible. The there would exist a sequence of elementary matrices E1,E2,…,Ek, such that

1Senior lecturer

2Student

F = Ek…E2E1(L(G)) = I. However, note that if A were a matrix such that each row sum were 0, and E any elementary matrix, then EA is still a matrix with each row sum 0. Consequently, we see that but I, the identity matrix is not. This is a contradiction.

3. Computing d (L(T)) when T is a tree

Let T be a tree and L(T) = [aij]

Proposition : If Sn has a cycle of length 3 in its cycle decomposition, then,

a a …a = 0.

Proof: Let the cycle of length 3 be (l1 l2 … lk), k3. Suppose a a …a 0.

Then al1l2al2l3…alkl1 0. But since l1l2, l2 l3, … , lk l1, then li = -1 for every 1ik. This implies that we can find cycle of length greater than 3 in the tree T. But this is impossible since by definition, T does not have any cycles. From this, we see that the only permutations that can give rise to a non-zero term a a …a are those that have cycle structure (1j,2k) where j+2k = n and k is an integer from 0 to n/2 .This means we can drastically cut down the number of terms in the calculation of the permanent of L(T). We can also calculate d L(T) via numbers obtained from T itself. This involves the notion of matchings.

Definition: For a tree of order n, define for each integer k, k0, MT(k) = ,

Where v Ek means a vertex that is not incident with any edge in Ek.

Note that when k = 0, MT(0) is the product of the degrees of the vertices in V.

Definition : For each integer k from 0 to n/2 , let A(k) Sn, denote the conjugacy class where each A(k) has cycle structure (1j,2k) where j+2k = n. Let (k) denote the

value of a irreducible character on the conjugacy class A(k) and let A’ = A(0)…A( n/2 ). (A conjugacy class is an equivalence class of the equivalence relation xRy Sn such that x = y -1)

Proposition:

Let be an irreducible character of Sn.

Then,

d (L(T)) = (k) MT(k)

and when = (n),

d (L(T)) = per(L(T)) = MT(k) ---(1)

We will only show (1). The general proof is similar.

Proof:

Note that per (L(T)) = = +

= + 0 (follows from the earlier proposition in 3)

= ( ) ---(2)

We first fix k, for some k from 1 to n/2 . We shall prove that = MT(k), which upon substitution into (2) above, will give the result.

Define N(k) to be {A(k) | 0 }. Let H(k) be the set of all k-matchings of T.

Define f:N(k)H(k) to be the function such that for each , f() = {[vi,v ] | i}

Then f is bijective. And for eachN(k), = .

Then = =MT(k), since as runs through N(k), f() runs

through H(k). Clearly = and we are done.

Because (as will be shown later) MT(k) is even for all k when T is a tree of odd order, then from the above proposition, d (L(T)) is even for all irreducible characters of Sn. This is however not necessarily true for d L(T) when T is a tree of even order, for there may exist integers h such that MT(h) is odd.

4. Properties of MT(k)

Some properties are:--

a) MT(n/2) = 0 or 1 when T is a tree of order n, n even,

b) MT(0) MT(1) for all trees of order n > 1,

c) MT(k) = MT(k), ---(3)

d) MT(k) is even for all k, when the order of T is odd, and

e) MT(k) is even for all trees T.

We will only show that MT(k) is even for all k, when T is a tree of odd order.

But to do this we will need a result on trees. Let n . Let Y = (Vy,Ey) be a tree of order n. In general, given any vertex q in Ey, we can form two trees Xq and Zq where

Xq has vertex set Vy {u1,u2} and edge set Ey { {u1,u2} ,{u1,q}}

Zq has vertex set Vy {u1,u2} and edge set Ey { {u1,q} ,{u2,q}}

Lemma: Given any tree T of order n+2 (n, we can find a tree Y of order n, such that

T = Xq ,

T = Zq ,

for some vertex q of Y.

The proof consists of taking a maximal path in T, and then deleting two vertices appropriately to form the required Y.

Definition: Let T be a tree of order n and vertex set V. Let k be an integer.

HT,k is the set of all k-matchings in T.

LT,k = {EkHT,k | whenever u is an even vertex , u Ek}

When T is a tree of odd order n, MT(1) is even. This can be shown, but will not be done so here. We will need this later in the main inductive proof. Also, it is clear that MT(0) is even, since there is always a vertex of even order in a tree of odd order. Then, since MT(0) is the product of the degrees of all vertices, the product is even.

Theorem: When T is a tree of odd order, MT(k) is even for all k.

Proof: We just show that LT,k contains an even number of matchings, whence the result is quite clear. We do this by induction.

Induction hypothesis:-

Let m 3, with m odd. Then for all trees of odd order n, 3nm,

and for every k with 1 n/2 , LT,k has even number of matchings.

Then, note that when m = 3, LT,1 has two 1-matchings. Also, since LT,1 always contains an even number of 1-matchings, we are now trying to prove that LT,k contains an even number of matchings when k2.

Let T be a tree of order m+2, m3 and m odd. Assume the inductive hypothesis is true.

Then from the above lemma, T = Xq or Zq for some vertex q in a tree Y of order m.

We will only show the case when T = Xq. Since the case T = Zq is similar.

We now suppose the degree of q in T is odd. For k2, define two sets Q0 and Q1 as follows.

Q0 = { Ek LT,k | Ek = Ek-1 {u1,u2} for some Ek-1LY,k-1},and

Q1 = { Ek LT,k | Ek = Ek-1 {q,u1} or Ek = Ek-1 {u1,u2} },

where Ek-1 HY,k-1 is such that whenever u is even, u Ek-1.

Then, when k2, LT,k = Q0 Q1 and both Q0 and Q1 have an even number of matchings.

Suppose now that the degree of q in T is even. Then define for k2,

Q = { Ek LT,k | Ek = Ek-1 {q,u1} if Ek-1 leaves q uncovered

Ek = Ek-1 {u1,u2} if Ek-1 covers q }

Again Q = LT,k (k2)and Q contains an even number of vertices by construction.

References

1 Hsiu –Khuern Tang, Generalized Matrix Functions, Honours Thesis, National Univ. of

Singapore 1995

2 Onn Chan and T.K Lam, Hook immanantal inequalities for Laplacians of trees,

Linear Algebra Appl. 261:23-47(1997)