A $q$-analog of the adjacency matrix of the $n$-cube

Ghosh, Subhajit; Srinivasan, Murali K.

doi:10.5802/alco.282

A

q

-analog of the adjacency matrix of the

n

-cube

Ghosh, Subhajit ¹; Srinivasan, Murali K.²

¹ Bar-Ilan University Department of Mathematics Ramat-Gan 5290002 (Israel)
² Indian Institute of Technology, Bombay Department of Mathematics Powai, Mumbai 400076 (India)

Algebraic Combinatorics, Volume 6 (2023) no. 3, pp. 707-725.

Abstract

Let $q$ be a prime power and define ${(n)}_{q} = 1 + q + q^{2} + \dots + q^{n - 1}$ , for a nonnegative integer $n$ . Let $B_{q} (n)$ denote the set of all subspaces of $𝔽_{q}^{n}$ , the $n$ -dimensional $𝔽 q$ -vector space of all column vectors with $n$ components.

Define a $B_{q} (n) \times B_{q} (n)$ complex matrix $M_{q} (n)$ with entries given by

M_{q} (n) (X, Y) = \{\begin{matrix} 1 & if Y \subseteq X, dim (Y) = dim (X) - 1, \\ q^{k} & if X \subseteq Y, dim (Y) = k + 1, dim (X) = k, \\ 0 & otherwise. \end{matrix}

We think of $M_{q} (n)$ as a $q$ -analog of the adjacency matrix of the $n$ -cube. We show that the eigenvalues of $M_{q} (n)$ are

{(n - k)}_{q} - {(k)}_{q} with multiplicity {(\binom{n}{k})}_{q}, k = 0, 1, ..., n,

and we write down an explicit canonical eigenbasis of $M_{q} (n)$ . We give a weighted count of the number of rooted spanning trees in the $q$ -analog of the $n$ -cube.

Received: 2022-04-29
Revised: 2022-11-15
Accepted: 2022-12-03
Published online: 2023-06-19

DOI: 10.5802/alco.282

Classification: 05E18, 05C81, 20C30
Keywords: $n$-cube, $q$-analog

Author's affiliations:

Ghosh, Subhajit ¹; Srinivasan, Murali K. ²

¹ Bar-Ilan University Department of Mathematics Ramat-Gan 5290002 (Israel)
² Indian Institute of Technology, Bombay Department of Mathematics Powai, Mumbai 400076 (India)

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2023__6_3_707_0,
     author = {Ghosh, Subhajit and Srinivasan, Murali K.},
     title = {A $q$-analog of the adjacency matrix of the $n$-cube},
     journal = {Algebraic Combinatorics},
     pages = {707--725},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {3},
     year = {2023},
     doi = {10.5802/alco.282},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.282/}
}

TY  - JOUR
AU  - Ghosh, Subhajit
AU  - Srinivasan, Murali K.
TI  - A $q$-analog of the adjacency matrix of the $n$-cube
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 707
EP  - 725
VL  - 6
IS  - 3
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.282/
DO  - 10.5802/alco.282
LA  - en
ID  - ALCO_2023__6_3_707_0
ER  -

%0 Journal Article
%A Ghosh, Subhajit
%A Srinivasan, Murali K.
%T A $q$-analog of the adjacency matrix of the $n$-cube
%J Algebraic Combinatorics
%D 2023
%P 707-725
%V 6
%N 3
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.282/
%R 10.5802/alco.282
%G en
%F ALCO_2023__6_3_707_0

Ghosh, Subhajit; Srinivasan, Murali K. A $q$-analog of the adjacency matrix of the $n$-cube. Algebraic Combinatorics, Volume 6 (2023) no. 3, pp. 707-725. doi : 10.5802/alco.282. https://alco.centre-mersenne.org/articles/10.5802/alco.282/

References
Cited by

[1] Askey, Richard Evaluation of Sylvester type determinants using orthogonal polynomials, Advances in analysis, World Sci. Publ., Hackensack, NJ, 2005, pp. 1-16 | MR | Zbl

[2] Ceccherini-Silberstein, Tullio; Scarabotti, Fabio; Tolli, Filippo Harmonic Analysis on Finite Groups–Representation Theory, Gelfand Pairs and Markov Chains, Cambridge Studies in Advanced Mathematics, 108, Cambridge University Press, Cambridge, 2008, xiv+440 pages | DOI | MR

[3] Edelman, Alan; Kostlan, Eric How many zeros of a random polynomial are real?, Bull. Amer. Math. Soc. (N.S.), Volume 32 (1995) no. 1, pp. 1-37 | DOI | MR | Zbl

[4] Gasper, George; Rahman, Mizan Basic hypergeometric series, Encyclopedia of Mathematics and its Applications, 35, Cambridge University Press, Cambridge, 1990, xx+287 pages (With a foreword by Richard Askey) | MR

[5] Ghosh, Subhajit; Srinivasan, Murali K. A random walk on subspaces, In preparation, 2023

[6] Goldman, Jay; Rota, Gian-Carlo The number of subspaces of a vector space, Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), Academic Press, New York (1969), pp. 75-83 | MR | Zbl

[7] Johnson, Warren P. Some tridiagonal determinants, Ramanujan J., Volume 61 (2023) no. 1, pp. 319-328 | DOI | MR | Zbl

[8] Kac, Mark Random walk and the theory of Brownian motion, Amer. Math. Monthly, Volume 54 (1947), pp. 369-391 | DOI | MR | Zbl

[9] Kac, Victor; Cheung, Pokman Quantum calculus, Universitext, Springer-Verlag, New York, 2002, x+112 pages | DOI | MR

[10] Kung, Joseph P. S. The subset-subspace analogy, Gian-Carlo Rota on combinatorics (Contemp. Mathematicians), Birkhäuser Boston, Boston, MA, 1995, pp. 277-283 | MR

[11] Proctor, Robert A. Representations of $𝔰𝔩 (2, ℂ)$ on posets and the Sperner property, SIAM J. Algebraic Discrete Methods, Volume 3 (1982) no. 2, pp. 275-280 | DOI | MR

[12] Srinivasan, Murali K. A positive combinatorial formula for the complexity of the $q$ -analog of the $n$ -cube, Electron. J. Combin., Volume 19 (2012) no. 2, Paper no. 34, 14 pages | MR | Zbl

[13] Srinivasan, Murali K. The Goldman-Rota identity and the Grassmann scheme, Electron. J. Combin., Volume 21 (2014) no. 1, Paper no. 1.37, 23 pages | MR | Zbl

[14] Stanley, Richard P. Algebraic Combinatorics–Walks, Trees, Tableaux, and More (Second Edition), Undergraduate Texts in Mathematics, Springer, Cham, 2018, xvi+263 pages | DOI | MR

[15] Taussky, Olga; Todd, John Another look at a matrix of Mark Kac, Proceedings of the First Conference of the International Linear Algebra Society (Provo, UT, 1989), Volume 150 (1991), pp. 341-360 | DOI | MR | Zbl

[16] Terwilliger, Paul The incidence algebra of a uniform poset, Coding theory and design theory, Part I (IMA Vol. Math. Appl.), Volume 20, Springer, New York, 1990, pp. 193-212 | DOI | MR | Zbl

[17] Terwilliger, Paul Two linear transformations each tridiagonal with respect to an eigenbasis of the other; an algebraic approach to the Askey scheme of orthogonal polynomials, 2004 | arXiv

[18] Terwilliger, Paul Lowering-raising triples and $U_{q} ({𝔰𝔩}_{2})$ , Linear Algebra Appl., Volume 486 (2015), pp. 1-172 | DOI | MR | Zbl

[19] Terwilliger, Paul Notes on the Leonard system classification, Graphs Combin., Volume 37 (2021) no. 5, pp. 1687-1748 | DOI | MR | Zbl

Cited by Sources: