Hook immanantal equalities for linear combination matrices of (di)graphs and their applications
Xiangshuai Dong, Tingzeng Wu ∗ and Hong-Jian Lai · 2025
Read Hook immanantal equalities for linear combination matrices of (di)graphs and their applications by Xiangshuai Dong, Tingzeng Wu ∗ and Hong-Jian Lai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-17743.txt.
Introduction
Xiangshuai Dong, Tingzeng Wu, and Hong-Jian Lai present a 2025 mathematics paper on hook immanants of graph matrices. An immanant is a determinant-like summary of a matrix, weighted by characters of the symmetric group. The hook version uses a special family of those characters, and its polynomial form packages the values neatly.
The authors study matrices built by mixing a graph's degree matrix and adjacency matrix with two real weights. They characterize two equalities that the hook immanants of such mixtures must satisfy, for both plain graphs and directed ones. From those equalities they derive step-by-step formulas for the hook immanant polynomials and the immanants themselves. The results add exact tools to the algebra of graph matrices.
Catalog record
| CREATOR | Xiangshuai Dong, Tingzeng Wu ∗ and Hong-Jian Lai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-17743
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hook immanantal equalities for linear combination matrices of (di)graphs and their applications Thanks: *Corresponding author Xiangshuai Dong, Tingzeng Wu ∗ and Hong-Jian Lai Abstract . Let χ λ \chi_{\lambda} be an irreducible character of the symmetric group S n S_{n} . For an n × n n\times n matrix M = ( m i j ) M=(m_{ij}) , define the immanant of M M corresponding to χ λ \chi_{\lambda} by d λ ( M ) = ∑ σ ∈ S n χ λ ( σ ) ∏ i = 1 n m i σ ( i ) . \displaystyle d_{\lambda}(M)=\sum_{\sigma\in S_{n}}\chi_{\lambda}(\sigma)\prod_{i=1}^{n}m_{i\sigma(i)}. For λ = ( k , 1 n − k ) \lambda=(k,1^{n-k}) , the immanant d ( k , 1 n − k ) ( M ) d_{(k,1^{n-k})}(M) is called the hook immanant and denoted by d k ( M ) d_{k}(M) . The hook immanant polynomial of matrix M M is defined as d k ( x I n − M ) d_{k}(xI_{n}-M) , where I n I_{n} is the n × n n\times n identity matrix. Let G G and G → \overrightarrow{G} be a graph and a digraph, respectively. Suppose that D ( G ) D(G) and A ( G ) A(G) (resp. D ( G → ) D(\overrightarrow{G}) and A ( G → ) A(\overrightarrow{G}) ) are the degree matrix and adjacency matrix of G G (resp. G → \overrightarrow{G} ), respectively. In this paper, we characterize two hook immanantal equalities for the linear combination of matrices β D ( G ) + γ A ( G ) \beta D(G)+\gamma A(G) and β D ( G → ) + γ A ( G → ) \beta D(\overrightarrow{G})+\gamma A(\overrightarrow{G}) , where β \beta and γ \gamma are real numbers. As applications, we derive recursive formulas for the hook immanantal polynomials and hook immanants of graph matrices. 2020 Mathematics Subject Classification 05B20, 05E05, 05C31, 05C50, 15A15. 1. Introduction Let M=(m_{ij}) be an n\times n matrix. Let S_{n} be the permutation group on n symbols and \chi_{\lambda} be an irreducible character of the symmetric group S_{n} , indexed by a partition \lambda of n . The immanant function , d_{\lambda} associated with the character \chi_{\lambda} acting on M , is defined as \displaystyle d_{\lambda}(M)=\sum_{\sigma\in S_{n}}\chi_{\lambda}(\sigma)\prod_{i=1}^{n}m_{i\sigma(i)}. For \lambda=(k,1^{n-k}) , d_{(k,1^{n-k})}(M) is called the hook immanant of M , denoted by d_{k}(M) . In particular, d_{1}(M)=\text{det}M is the determinant of M , d_{2}(M) denotes the second immanant of M and d_{n}(M)=\text{per}M is the permanent of M . For the function d_{k}(M) related to k , we stipulate that if k<1 or k>n , then d_{k}(M)=0 . Calculating the hook immanant is extremely challenging. Bürgisser [ 5 ] proved that computing the hook immanant of a matrix is VNP-complete. The hook immanant holds significant importance in algebraic graph theory, with profound connections to graph invariants and structural properties [ 11 , 26 , 18 ] . Merris [ 20 , 21 ] established a relationship between hook immanants and the number of hamiltonian cycles. Chan and Lam [ 7 , 8 ] conducted systematic investigations into the Laplacian immanants of trees, determining the minimal values of Laplacian immanants for trees. The study of matrix immanants has been thoroughly elaborated in [ 1 , 12 , 14 , 15 , 19 , 28 ] and other references. Moreover, immanants of graph matrices have garnered considerable attention, as seen in [ 17 , 22 ] , among others. Let I_{n} be an n\times n identity matrix. The hook immanant polynomial \Phi_{k}(M,x) (simply \Phi_{k}(M) ) of an n\times n matrix M with afforded by the character \chi_{(k,1^{n-k})} is defined as d_{(k,1^{n-k})}(xI_{n}-M) , i.e., \displaystyle\Phi_{k}(M,x)=d_{(k,1^{n-k})}(xI_{n}-M). In particular, when k=1 , \Phi_{1}(M,x) is called the characteristic polynomial of M , denoted by \varphi(M,x) . When k=2 , \Phi_{2}(M,x) is called the second immanant polynomial . When k=n , \Phi_{n}(M,x) is called the permanental polynomial , denoted by \psi(M,x) . Merris [ 3 ] stated that almost all trees possess a complete set of immanantal polynomials. Cash [ 6 ] extended Sachs’ theorem to immanantal polynomials and applied this result to chemical structures containing hexagonal rings. Yu and Qu [ 33 ] utilized basic subgraphs to derive explicit expressions for the immanantal polynomials of matrix M . In algebraic graph theory, immanants corresponding to certain special partitions have been extensively investigated [ 30 , 31 , 9 , 2 , 17 ] . For further research on immanantal polynomials, refer to [ 4 , 23 , 24 ] . We are interested in conducting ongoing research into the properties of the hook immanant and hook immanantal polynomial of graph matrices. Below, we introduce some relevant notations. Let G=(V(G),E(G)) be a simple graph with vertex set V(G)=\{v_{1},v_{2},\ldots,v_{n}\} and edge set E(G) . Let d(v_{i}) be the degree of vertex v_{i} in G . The degree matrix of G is denoted by D(G)=\mathrm{diag}(d(v_{1}),d(v_{2}),\ldots,d(v_{n})) . The adjacency matrix of G is an n\times n matrix, denoted by A(G)=(a_{ij}) , whose entry a_{ij} is given by a_{ij}=\begin{cases}1,&\text{if }v_{i}\text{ is adjacent to }v_{j},\\ 0,&\text{otherwise}.\end{cases} Let \overrightarrow{G}=(V(\overrightarrow{G}),E(\overrightarrow{G})) be a digraph without loops or parallel arcs, where the vertex set is V(\overrightarrow{G})=\{v_{1},v_{2},\ldots,v_{n}\} and the arc set is E(\overrightarrow{G}) . The adjacency matrix of \overrightarrow{G} is defined as A(\overrightarrow{G})=(a_{ij})_{n\times n} , where a_{ij}=\begin{cases}1,&\text{if }(v_{i},v_{j})\in E(\overrightarrow{G}),\\ 0,&\text{otherwise}.\end{cases} The out-degree diagonal matrix is denoted by D(\overrightarrow{G})=\mathrm{diag}(d^{+}(v_{1}),d^{+}(v_{2}),\ldots,d^{+}(v_{n})) , where d^{+}(v_{i}) denotes the out-degree of the vertex v_{i} . Let H(G)=\beta D(G)+\gamma A(G) and H(\overrightarrow{G})=\beta D(\overrightarrow{G})+\gamma A(\overrightarrow{G}) , where \beta and \gamma are real numbers. If \beta=0 and \gamma=1 , then H(G)=A(G) (resp. H(\overrightarrow{G})=A(\overrightarrow{G}) ) is the adjacency matrix of graph G (resp. \overrightarrow{G} ). If \beta=1 and \gamma=-1 , then H(G)=D(G)-A(G)=L(G) (resp. H(\overrightarrow{G})=D(\overrightarrow{G})-A(\overrightarrow{G})=L(\overrightarrow{G}) ) is the Laplacian matrix of graph G (resp. \overrightarrow{G} ). If \beta=1 and \gamma=1 , then H(G)=D(G)+A(G)=Q(G) (resp. H(\overrightarrow{G})=D(\overrightarrow{G})+A(\overrightarrow{G})=Q(\overrightarrow{G}) ) is the signless Laplacian matrix of graph G (resp. \overrightarrow{G} ). Suppose 0\leq\alpha\leq 1 . If \beta=\alpha and \gamma=1-\alpha , then H(G)=\alpha D(G)+(1-\alpha)A(G)=A_{a}(G) (resp. H(\overrightarrow{G})=\alpha D(\overrightarrow{G})+(1-\alpha)A(\overrightarrow{G})=A_{a}(\overrightarrow{G}) ) is the A_{a} matrix of graph G (resp. \overrightarrow{G} ). Let S\subseteq V(G) be a vertex subset. Assume that H_{S}(G) is the principal submatrix of H(G) obtained by deleting the rows and columns corresponding to all vertices in S\subseteq V(G) . In particular, if S=\{v\} and v\in V(G) , then H_{\{v\}}(G) is simply written as H_{v}(G) . Similarly, if S=\{u,v\} where u,v\in V(G) , then is abbreviated as H_{uv}(G) . Suppose that G-S denotes the graph obtained by deleting all vertices in S and all edges incident with the vertices in S from G . In particular, if S=\{v\} and v\in V(G) , G-\{v\} is simply written as G-v . The graph obtained by deleting an edge from G is denoted by G-e . If v and \overrightarrow{e} are a vertex and an arc of \overrightarrow{G} respectively, {\overrightarrow{G}}-v is the graph obtained by deleting vertex v and the arcs incident to v from \overrightarrow{G} . {\overrightarrow{G}}-{\overrightarrow{e}} is obtained by deleting \overrightarrow{e} but retaining all vertices and other arcs. The set of vertices adjacent to v\in V(G) is called the neighborhood of v , denoted by