The second immanant of some combinatorial matrices

Document Type: Research Paper

Authors

1 Stat-Math Unit, ISI Delhi

2 Dept of Mathematics, IIT Bombay

Abstract

Let $A = (a_{i,j})_{1 \leq i,j \leq n}$ be an $n \times n$ matrix‎ ‎where $n \geq 2$‎. ‎Let $\det 2(A)$‎, ‎its second immanant be the immanant‎ ‎corresponding to the partition $\lambda_2 = 2,1^{n-2}$‎. ‎Let $G$ be a connected graph with blocks $B_1‎, ‎B_2,\ldots‎, ‎B_p$ and with‎ ‎$q$-exponential distance matrix $ED_G$‎. ‎We give an explicit‎ ‎formula for $\det 2(ED_G)$ which shows that $\det 2(ED_G)$ is independent‎ ‎of the manner in which $G$'s blocks are connected‎. ‎Our result is similar in form to the result of Graham‎, ‎Hoffman and Hosoya‎ ‎and in spirit to that of Bapat‎, ‎Lal and Pati who show that $\det ED_T$‎ ‎where $T$ is a tree is independent of the structure of $T$ and only‎ ‎dependent on its number of vertices‎. ‎Our result extends more generally to a product‎ ‎distance matrix associated to a connected graph $G$‎. ‎Similar results are shown for the $q$-analogue of $T$'s laplacian‎ ‎and a suitably defined matrix for arbitrary connected graphs‎.

Keywords

Main Subjects

References

[1] R. B. Bapat, A. K. Lal and S. Pati, A q-analogue of the distance matrix of a tree, Linear Algebra Appl., 416 (2006) 799–814.

[2] R. B. Bapat and S. Sivasubramanian, Product Distance Matrix of a Graph and Squared Distance Matrix of a Tree, Appl. Anal. Discrete Math., 7 (2013) 285–301.

[3] R. B. Bapat and S. Sivasubramanian, Product distance matrix of a tree with matrix weights, Linear Algebra Appl., 468 (2015) 145-153.

[4] R. L. Graham, A. J. Hoffman and H. Hosoya, On the distance matrix of a directed graph, J. Graph Theory, 1 (1977) 85–88.

[5] R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J., 50 (1971) 2495–2519.

[6] R. Grone and R. Merris, An Algorithm for the Second Immanant, Maths. Comp., 43 no. 168 (1984) 589–591.

[7] D. E. Littlewood, The theory of group characters and matrix representations of groups, Reprint of the second (1950) edition, Providence, RI, 2006.

[8] R. Merris, The second immanantal polynomial and the centroid of a graph, SIAM J. Algebraic Discrete Methods, 7 (1986) 484–503.

[9] R. Merris and W. Watkins, Inequalities and identities for generalized matrix functions, Linear Algebra Appl., 64 (1985) 223–242.

[10] B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Second edition. Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001.

[11] I. Schur,Über endliche Gruppen und Hermitesche Formen, Math. Z., 1 (1918) 184–207.

[12] S. Sivasubramanian, A q-analogue of Graham, Hoffman and Hosoyas theorem, Electron. J. Combin., 17 (2010) pp. 9.

[13] R. P. Stanley, Enumerative Combinatorics, 2, Cambridge University Press, Cambridge, 1999.

[14] J. R. Stembridge, Some Conjectures For Immanants, Canad. J. Math., 44 (1992) 1079–1099.

[15] D. B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

Transactions on Combinatorics

Volume 4, Issue 2
June 2015
Pages 23-35

Files

Share

How to cite

Statistics