A $q$-analog of the adjacency matrix of the $n$-cube
Algebraic Combinatorics, Volume 6 (2023) no. 3, pp. 707-725.

Let $q$ be a prime power and define ${\left(n\right)}_{q}=1+q+{q}^{2}+\cdots +{q}^{n-1}$, for a nonnegative integer $n$. Let ${B}_{q}\left(n\right)$ 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}\left(n\right)×{B}_{q}\left(n\right)$ complex matrix ${M}_{q}\left(n\right)$ with entries given by

 ${M}_{q}\left(n\right)\left(X,Y\right)=\left\{\begin{array}{cc}1\hfill & \text{if}\phantom{\rule{4pt}{0ex}}Y\subseteq X,dim\left(Y\right)=dim\left(X\right)-1,\hfill \\ {q}^{k}\hfill & \text{if}\phantom{\rule{4pt}{0ex}}X\subseteq Y,dim\left(Y\right)=k+1,dim\left(X\right)=k,\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}\right\$

We think of ${M}_{q}\left(n\right)$ as a $q$-analog of the adjacency matrix of the $n$-cube. We show that the eigenvalues of ${M}_{q}\left(n\right)$ are

 ${\left(n-k\right)}_{q}-{\left(k\right)}_{q}\phantom{\rule{4pt}{0ex}}\text{with}\phantom{\rule{4pt}{0ex}}\text{multiplicity}\phantom{\rule{4pt}{0ex}}{\left(\genfrac{}{}{0pt}{}{n}{k}\right)}_{q},\phantom{\rule{0.277778em}{0ex}}\phantom{\rule{0.277778em}{0ex}}k=0,1,...,n,$

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

Revised:
Accepted:
Published online:
DOI: 10.5802/alco.282
Classification: 05E18, 05C81, 20C30
Keywords: $n$-cube, $q$-analog

Ghosh, Subhajit 1; Srinivasan, Murali K. 2

1 Bar-Ilan University Department of Mathematics Ramat-Gan 5290002 (Israel)
2 Indian Institute of Technology, Bombay Department of Mathematics Powai, Mumbai 400076 (India)
@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/

[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 $\mathrm{𝔰𝔩}\left(2,\phantom{\rule{0.166667em}{0ex}}ℂ\right)$ 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}\left({\mathrm{𝔰𝔩}}_{2}\right)$, 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: